Poker-AI.org
https://poker-ai.org/phpbb/

Measuring the Size of Large No-Limit Poker Games (2013)
https://poker-ai.org/phpbb/viewtopic.php?f=25&t=2396		 Page 1 of 1
Author:  Joshua [ Fri Mar 15, 2013 12:13 pm ]
Post subject:  Measuring the Size of Large No-Limit Poker Games (2013)
PROPERTIES

type = "techreport"
title = "Measuring the Size of Large No-Limit Poker Games"
author = "JOHANSON, Michael"
year = "2013"
organization = "University of Alberta - Department of Computing Science"
url = "http://poker.cs.ualberta.ca/publications/2013-techreport-nl-size.pdf"
language = "en"
size = "16"


SUBJECT

abstract = "In the field of computational game theory, games are often compared in terms of their size. This can be measured in several ways, including the number of unique game states, the number of decision points, and the total number of legal actions over all decision points. These numbers are either known or estimated for a wide range of classic games such as chess and checkers. In the stochastic and imperfect information game of poker, these sizes are easily computed in "limit" games which restrict the players' available actions, but until now had only been estimated for the more complicated "no-limit" variants. In this paper, we describe a simple algorithm for quickly computing the size of two-player no-limit poker games, provide an implementation of this algorithm, and present for the first time precise counts of the number of game states, information sets, actions and terminal nodes in the no-limit poker games played in the Annual Computer Poker Competition."
Author:  alex [ Tue Apr 09, 2013 10:59 am ]
Post subject:  Re: Measuring the Size of Large No-Limit Poker Games (2013)
Hi, all.

I am trying to understand poker isomorphism. Right now I'm trying to reproduce the "canonical one player" combination counts that are presented in this paper. My results match the 1,286,792 number for flop. But for turn I get 48,540,726 instead of 55,190,538.

My approach consists of two steps: 1) canonical board sequences 2) strategically different hands for a given board.

1) canonical board sequences.
On PREFLOP the board is empty.
On FLOP two boards are equivalent if one can be obtained from the other by permutating the suits. I pick the board whose suits are lexicographically ordered as the "canonical" one.
On TURN the canonical boards are found as follows. Assume the suits are ordered as follows: cdhs. So we will say that clubs precedes diamonds, diamonds precedes spaces (by transitivity) etc. When obtaining a TURN board from a FLOP board we see if there are suits with the same sets of cards. An example of such board would be (2c, 4d, 4h). In such cases we add the 4th card only to the first of the equivalent suits. So, for example, (2c, 4d, 4h, 5d) would be a "canonical" TURN board, while (2c, 4d, 4h, 5h) woudln't.

I haven't yet got to thinking about canonical RIVER boards.

2) canonical hands for a given board.

Here I have implemented a function that given a board and a pair of hole cards converts these hole cards to a "canonical" pair. Equivalent hole card sets should be converted to the same pair of cards.

My logic here is as follows. If it is possible that there will be 3+ cards of a suit on the 5-card board then we say that this suit "can be a flush". For example for a FLOP board (5c, Qc, 2d) clubs and diamonds can be a flush while hearts and spades can't. So if in our hand we have a card of a suit that can be a flush, then we cannot freely change this card's suit. We can only do this if there is another suit that has exactly the same cards on the board. On the other hand if we have a card of a non-flush suit, then we are free to change the suit to any other non-flush suit (subject to not having duplicate cards afterwards). The code for "normalizing" hands is provided below.

Code:
void NormalizeHand( const Cards_set& board, short c1, short c2, short& c1Out, short& c2Out )
{
    unsigned mask[4] = {0};
    unsigned cardCount[4] = {0};
    for( unsigned i = 0; i < board.cards.size(); ++i )
    {
        mask[board.cards[i].get_suit()] |= (1 << board.cards[i].get_power());
        ++cardCount[board.cards[i].get_suit()];
    }

    bool canBeFlush[4];
    for( int i = 0; i < 4; ++i )
        canBeFlush[i] = ( 3 <= cardCount[i] + 5 - board.cards.size() );
   
    Card card1;
    card1.set_number( std::min(c1, c2) );
    Card card2;
    card2.set_number( std::max(c1, c2) );
   
    int newSuit1 = card1.get_suit();
    int newSuit2 = card2.get_suit();
   
    if( canBeFlush[card1.get_suit()] )
    {
        for( int i = 0; i < card1.get_suit(); ++i )
            if( mask[i] == mask[card1.get_suit()] )
            {
                newSuit1 = i;
                break;
            }
    }
    else
    {
        for( int i = 0; i < 4; ++i )
        {
            if( !canBeFlush[i] && ( (mask[i] & (1 << card1.get_power()) ) == 0 ) )
            {
                newSuit1 = i;
                mask[i] |= (1 << card1.get_power());
                break;
            }
        }
    }
   
    if( canBeFlush[card2.get_suit()] )
    {
        if( card2.get_suit() == card1.get_suit() )
            newSuit2 = newSuit1;
        else
        {
            for( int i = 0; i < 4; ++i )
                if( (mask[i] == mask[card2.get_suit()]) && (i != newSuit1) )
                {
                    newSuit2 = i;
                    break;
                }           
        }
    }
    else
    {
        for( int i = 0; i < 4; ++i )
        {
            if( !canBeFlush[i] && ( (mask[i] & (1 << card2.get_power()) ) == 0 ) )
            {
                newSuit2 = i;
                break;
            }
        }
    }
   
    card1.set_suit( newSuit1 );
    card2.set_suit( newSuit2 );
    c1Out = card1.get_number();
    c2Out = card2.get_number();
}


The overall structure of the algorithm at the TURN stage is as follows. I iterate over all "canonical" TURN boards. From each board I obtain the PREFLOP board (the first 3 cards). Then I go over all possible hand card combinations h1 and obtain the normalized preflop hand h1_preflop, the normalized flop hand h1_flop and the normalized turn hand h1_turn. Then I check if there exists h2 - another pair of hand cards that normalizes to the same h1_preflop, h1_flop, h1_turn and such that h2 precedes h1 in the lexicographic order. If there is no such h2 then h1 in combination with the given turn board is one of the canonical combinations.

Can anyone please point me to an error in my reasoning or suggest an idea for narrowing the search down?

Many thanks.
Author:  proud2bBot [ Tue Apr 09, 2013 1:02 pm ]
Post subject:  Re: Measuring the Size of Large No-Limit Poker Games (2013)
you might check out some LUT implementations - they do the same (for flop, turn and river)
Author:  alex [ Wed Apr 10, 2013 9:28 am ]
Post subject:  Re: Measuring the Size of Large No-Limit Poker Games (2013)
[I have editted my post because there was an error in the code]

Hi, proud2bBot.

Thanks for replying. I found some information in this thread: https://poker-ai.org/archive/www.pokerai.org/pf3/viewtopic3c0f.html?f=3&t=2881&hilit=. Kevin says there that 55190538 is the number of turn combinations "taking into account only suit isomorphisms". MegaZhiraf later replies to this that this number is actually is wrong.

I am not 100% sure what "taking into account only suit isomorphisms" means. But I am starting to feel that 55190538 is actually GREATER than the "number of canonical card combinations from one player's point of view" - the term used in the tech report.

I have put together a piece of C++ code that counts turn combinations. It reprocuces the number from the article - 55190538. But imagine the turn board is AcKcQc2d (on turn the new public card was 2d). This code will treat the following two hands as different: AdAh, AhAs. But I believe they are strategically the same, after flop the diamond suit had no chance of becoming a flush. So (if I haven't made an error in my reasoning) they should have defined properly what they mean by "canonical combinations".

Code:
int CountUniqueTurnHands( int (&flopMask)[4], int (&turnMask)[4] )
{
    int result = 0;
    for( int c1 = 0; c1 + 1 < 52; ++c1 )
    {
        if( turnMask[c1 % 4] & (1 << (c1 / 4)) ) // card is already on the board
            continue;
        for( int c2 = c1 + 1; c2 < 52; ++c2 )
        {
            if( turnMask[c2 % 4] & (1 << (c2 / 4)) )
                continue;
           
            bool isDuplicate = false;
           
            for( int c1x = 0; c1x <= c1; ++c1x )
            {
                if( turnMask[c1x % 4] & (1 << (c1x / 4)) )
                    continue;
                for( int c2x = c1x + 1; c2x < 52; ++c2x )
                {
                    if( c1 == c1x && c2x >= c2 ) // we only check lexicographically preceding hands
                        continue;
                    if( turnMask[c2x % 4] & (1 << (c2x / 4)) )
                        continue;
                   
                    // hands must have the same suited-ness
                    if( ((c1%4)==(c2%4)) && ((c1x%4)!=(c2x%4)) )
                        continue;
                    if( ((c1%4)!=(c2%4)) && ((c1x%4)==(c2x%4)) )
                        continue;
                   
                    // checking if (c1, c2) is equivalent to (c1x, c2x) or to (c2x, c1x)
                    if( (c1/4 == c1x/4) && (flopMask[c1%4]==flopMask[c1x%4]) && (turnMask[c1%4]==turnMask[c1x%4]) && (c2/4 == c2x/4) && (flopMask[c2%4]==flopMask[c2x%4]) && (turnMask[c2%4]==turnMask[c2x%4]))
                        isDuplicate = true;
                    if( (c1/4 == c2x/4) && (flopMask[c1%4]==flopMask[c2x%4]) && (turnMask[c1%4]==turnMask[c2x%4]) && (c2/4 == c1x/4) && (flopMask[c2%4]==flopMask[c1x%4]) && (turnMask[c2%4]==turnMask[c1x%4]))
                        isDuplicate = true;
                }
            }
           
            if( !isDuplicate )
                ++result;
        }
    }
   
    return result;
}

void CountTurnCombinationsTurnPart( int& result, int (&flopMask)[4] )
{
    int turnMask[4] = { flopMask[0], flopMask[1], flopMask[2], flopMask[3] };
   
    for( int i = 0; i < 4; ++i )
    {
        bool skipSuit = false;
        for ( int j = 0; j < i; ++j ) // checking if there is another suit with exactly the same cards
            skipSuit = skipSuit || ( flopMask[i] == flopMask[j] );
       
        if( skipSuit )
            continue;
       
        for( int j = 0; j < 13; ++j )
        {
            if( (flopMask[i] & (1 << j)) != 0 ) // if there already is a card with rank j
                continue;
           
            turnMask[i] |= ( 1 << j ); // adding the 4th card to the mask
           
            result += CountUniqueTurnHands( flopMask, turnMask );
           
            turnMask[i] ^= ( 1 << j ); // removing the 4th card
        }
    }
}

void CountTurnCombinationsFlopPart( int& result )
{
    int mask[4] = {0};
    for( int c1 = 0; c1 + 2 < 52; ++c1 )
    {
        mask[c1%4] |= ( 1 << (c1/4) );
       
        for( int c2 = c1 + 1; c2 + 1 < 52; ++c2 )
        {
            mask[c2%4] |= ( 1 << (c2/4) );
       
            for( int c3 = c2 + 1; c3 < 52; ++c3 )
            {
                mask[c3%4] |= ( 1 << (c3/4) );       
       
                if( mask[0] >= mask[1] && mask[1] >= mask[2] && mask[2] >= mask[3] )
                    CountTurnCombinationsTurnPart( result, mask );
               
                mask[c3%4] ^= ( 1 << (c3/4) );
            }
           
            mask[c2%4] ^= ( 1 << (c2/4) );
        }
       
        mask[c1%4] ^= ( 1 << (c1/4) );
    }
}

int main()
{
    int n = 0;
    CountTurnCombinationsFlopPart(n);
    std::cout << n << "\n";
    return 0;
}
Author:  MBJ [ Wed Apr 10, 2013 9:39 pm ]
Post subject:  Re: Measuring the Size of Large No-Limit Poker Games (2013)
"Canonical" and "Isomorphic" have a simple definition in the poker papers. Two sets of cards are isomorphic if you can do a suit rotation on one (all spades become hearts, all hearts become diamonds, etc) to make them exactly identical. For a set of isomorphic hands, you can pick one arbitrarily and call it the canonical form. Usually you use some pattern for that, like "the lowest card in the first group is always a spade, the next card of a different suit is a heart, ..." and so on, but it doesn't matter much.

In the example you gave, AdAh and AhAs on a AcKcQc2d board aren't isomorphic by the standard definition of isomorphism I gave above. You can't only do a suit rotation to turn one into the other.

By reasoning about when flushes are and aren't possible, you're trying to get a little bit more of a reduction than is had with the usual definition. That probably can work; you might be able to get a slightly lower number, but it'd be a different type of isomorphism than is usually implied. I don't see a problem so far with the reasoning in your example.

But it might be tricky to tell exactly when you can shrink the number a little more by reasoning about flushes being impossible. For example, lets say we're on the river, there were two spades on the flop and the other three board cards are a club, a heart and a diamond, and we have the ace of spades in our hand. No flushes are possible for anyone in any suit. However, even though we can't make a flush, this state is not strategically identical to hands where our ace was a different suit, because our holding that ace tells us something about the opponent's hand: namely, that they couldn't have been trying for an ace-high flush on the flop. If our ace was a different suit, then they might have been trying for that ace-high flush. Meaning that on the river, my opponent might have a different distribution of hands in these two states. So they aren't strategically equivalent by the usual definition or by your extended one. So yep - you might be able to get a slightly smaller number through this type of reasoning, but (at least so far) I'm not sure it'll be completely simple to tell when hands are strategically equivalent when they aren't isomorphic in the cards.

[Edit: After my example, I should have said that changing the ace to a different suit wouldn't be isomorphic by the usual definition, and they wouldn't be strategically identical because I might rationally choose to act differently in the two states. If your extended notion of isomorphism would say that they're equivalent, then that seems like an error.]
Author:  proud2bBot [ Thu Apr 11, 2013 2:44 am ]
Post subject:  Re: Measuring the Size of Large No-Limit Poker Games (2013)
MBJ made a good point in his example. For stuff like EHS2/EHS LUTs where you are implicitly assuming a 100% range, you can use the isomorphism to shrink the LUTs and most LUT implementation use this technique. However, if you want to have more advanced stuff like board texture development in your LUT, you are losing this information, as Boards like As5s6hTc and As6hTc5 are mapped to the same LUT entry, even though a villain might have a very different range on these two boards. I wonder if there are LUT implementations that only apply suit isomorphism out there?
Author:  alex [ Thu Apr 11, 2013 4:53 am ]
Post subject:  Re: Measuring the Size of Large No-Limit Poker Games (2013)
Thanks for your replies.

It's a pity that the definition of "canonical" (or a link to one) is not given in this paper. So I believe, strictly speaking, this paper doesn't give the exact MINIMAL amounts of memory needed to store stuff.
Author:  alex [ Thu Apr 11, 2013 5:20 am ]
Post subject:  Re: Measuring the Size of Large No-Limit Poker Games (2013)
MBJ, my extended isomorphism check would also say they are not equivalent. Two hands are said to be equivalent if they "normalize" to the same hand for all prefixes of the board. For the preflop prefix the ace of spades cannot change suit.

I am not 100% sure this will not give false positives. Neither do I know at this point how to prove that this will be the MINIMAL combination count.
Author:  alex [ Thu Apr 11, 2013 7:01 am ]
Post subject:  Re: Measuring the Size of Large No-Limit Poker Games (2013)
I keep thinkng about it and now it seems that AdAh is NOT equivalent to AhAs when the turn board is AcKcQc2d. 8 - )

Let's say we are holding AdAh and the turn board is AcKcQc2d. What cards are left to the other player? 9 clubs, 11 diamonds, 12 hears and 13 spades. The number of possible suited pairs he might be holding is:
45 + 66 + 78 + 91 = 280.
On the other hand if we are holding AhAs the remaining cards are 9 clubs and 12 diamonds, hearts and spades each. The number of suited pairs the other player could possibly have is:
45 + 3 * 78 = 279.

This suggests that there can be no 1-to-1 correspondace between possible opponent's hands in the AdAh and AhAs cases.

Apologies for the statement in my previous post.
Author:  Coffee4tw [ Wed Apr 17, 2013 1:01 am ]
Post subject:  Re: Measuring the Size of Large No-Limit Poker Games (2013)
@alex: The fact why they are not similar is that in AdAh the Ad matches the same suit as the 2d whereas AhAs doesn't match any suits on the board. This is called suit isomorphism and, as MBJ said, canonical is just the general representation of all isomorphic hands. It's the version they all map to, the version that you would use as your entry in an LUT.

@p2bb: I have code that does isomorphism but keeps the order of turn and river intact. That's what you are looking for right? I didn't create an LUT with it but it's actually fairly simple.

Along those lines I actually experimented with just generalizing turn and river suits to 'x' if they can't fill a flush but that became a little too difficult to handle with the Meerkat Card data structure so I scratched the idea. In general it should be possible though. Not sure how much memory you would actually save though and if it's really worth it.
Author:  alex [ Wed Apr 17, 2013 12:41 pm ]
Post subject:  Re: Measuring the Size of Large No-Limit Poker Games (2013)
I realize there is a 2d, I thought it didn't matter but it did.
I am curious whether "being suit isomorphic" is the same as "being strategically equivalent". I realize my example was wrong, but I don't see why there can't be two hand/board combinations that are strategically equivalent and not suit-isomorphic.

My attempt at defining being strategically equivalent is:
There exists a mapping between chance events, such that
- All events that have occured in hand/board combination (1) are mapped to events that have occured in hand/board combination(2)
- If we follow the tree down to the leaves (substituting chance events in tree(1) to what they map to in tree (2)) the payoff should be the same in tree (1) and in tree (2). This must be true for every node that belongs to the round.
Author:  Coffee4tw [ Wed Apr 17, 2013 10:18 pm ]
Post subject:  Re: Measuring the Size of Large No-Limit Poker Games (2013)
Not just the pay-off but also the action probabilities aka the strategy needs to be exactly the same.

I don't think this is possible. There might be very similar cases that might not make a great deal of difference strategically but there are subtle things that do matter. To make your idea work you would need to condense cases where a certain suit hits your holecards with suits that didn't hit your holecards, which is a mistake strategically because they are different in the amount of information they give you as it impacts the possible holdings of your opponent.

For LUTs this might not matter, depending on what kind of LUT you are building but in a strategy sense it matters.
Author:  alex [ Thu Apr 18, 2013 5:47 am ]
Post subject:  Re: Measuring the Size of Large No-Limit Poker Games (2013)
My thinking was that if the payoffs are the same then the strategies will have to be the same.

I have the same gut feeling that suit rotation is what it boils down to. It would still be nice to have some kind of formal proof of that.
Author:  Coffee4tw [ Thu Apr 18, 2013 11:04 pm ]
Post subject:  Re: Measuring the Size of Large No-Limit Poker Games (2013)
alex wrote:
My thinking was that if the payoffs are the same then the strategies will have to be the same.

That's definitely wrong. It's pretty simple to come up with a toy game where two different strategies have the same payoff.
Page 1 of 1 All times are UTC
Powered by phpBB® Forum Software © phpBB Group
http://www.phpbb.com/