Hi,

Has anyone implemented or has an idea for a full optimization for ranges against ranges evaluation in holdem using isomporhisms for multiplayer (>2 players) games?

There is an optimization in pre-flop evaluations that Andy Prock is doing in PokerStove, and mikechops is not doing in Holdem Ranger, and I think this may be it (there is a comment on Holdem Ranger's home page that recognizes "some pretty sick pre-flop equity optimizations" on PokerStove).

I've searched and only found something about this in the paper "Potential-aware automated abstraction of sequential games, and holistic equilibrium analysis of Texas Hold’em poker"; Andrew Gilpin, Tuomas Sandholm & Troels Bjerre; AAAI'07.

But it only considers two players games, any idea???

TIA & Regards ...

I remember reading somewhere about some of the tricks Andrew Prock used to speed up PokerStove, but can't remember exactly where. Perhaps it's in his blog somewhere: http://www.headsupclub.com/aprock/

Juk

I've found this, it seems it is all there is on that site:
http://www.headsupclub.com/aprock/2005/02/source-code/

But, the link is not working, I'm gonna review later again the site and try again the download link.

BTW, I was refering to suit isomorphisms.

TIA & Regards ...

Adrian, did you read the monster thread "7 card hand evaluators" now in the archives?

I do not know what isomorphisms are (and wikipedia looks too complex for me right now - saved tab for later ) - but there wer some silly fast evaluators in there.

Wow, wikipedia did make that sound complex! If you look at the picture at the bottom of this page (http://en.wikipedia.org/wiki/Graph_isomorphism) it should make more sense - basically isomorphism means "structurally equivalent".

In terms of poker then "suit isomorphism" simply means that by evaluating JcJs vs AcKc all-in you also get the evaluation of JhJs vs AhHh (and JhJc vs AhHh, JsJc AsHs, etc, etc) for free (which saves on lots of unnecessary computation). You can apply the same ideas post-flop too.

Juk

The point here is which is the more efficient way to check if two instances of multiple player hands are "suit isomorphic" to each other.
One way is to test the 4!=24 combinations, but I think there should be a more efficient way.
For what I've seen, the way to test for an isomorphism is to reduce the multiple hands to a "normal form".

Let's say you order the hands in an arbitrary order.

If you have only one player with AKo, so that's easy, you name the suit of the Ace "suit 1", the suit of the King "suit 2", and you proceede from there with the rest of the hands of that evaluation.

But there are cases that are more complex, if you have two pairs of Aces, let's say AcAs and AdAh, for me the information that you gain is (c>d && c>h && s>d && s>h) || (c<d && c<h && s<d && ssh). Because you can be evaluating more hands, so now if you have player 3 with AsKs (only AKs) theee is more information to add that is "s=1", so we get the partial order s < c < (d,h). Now you get player 4 with KcQc (only player with KQs), there is not new information you get. And now you get player 5 with JhTh (only player with JTs), and we have completed the mapping, s < c < h < d. Now we can add the hands of players 6 to 10, and the combo of this hands will be in normal form by replacing s with suit1, c with suit2, h with suit 3 and d with suit 4.

And if we are evaluating AcAh, AsAd ; AdKd; KsQs ; JcTc we go thru the same process, and decide that this hand is isomorphic to the previous one, so instead of evaluating in the same hand range these two hands we do only evaluate one of them (and adjust the results accordingly, obviously).

I'll check Andrew's code, and see if I get something new from there.

TIA & Regards ...

Yes, I've read the monster thread a couple of times. But, the monster thread only deals with 7 cards hand evaluators (a function that from 7 cards returns an integer).

When you have to do a multiple players evaluation of ranges against ranges (or even hands against hands), the evaluation can be speed by using these suits isomorphisms as I've tried to explain in my post.

At the end is the relevant part of the paper, but only deals with two players optimizations.

TIA & Regards ...



Potential-aware automated abstraction of sequential games, and holistic equilibrium analysis of Texas Hold’em poker
http://www.cs.cmu.edu/~sandholm/gs3.aaai07.pdf

Exploiting suit isomorphisms
We now introduce ways in which we exploit suit isomorphisms. We first discuss a custom indexing scheme which dramatically reduces the space requirements of representing the abstraction. In the subsection after that, we present a way to exploit suit isomorphisms to speed up a key computation.
Indexing for efficient abstraction representation
One challenge that is especially difficult when using a four-round model is that the number of distinct hands a player can face is huge. Our algorithm requires an integer index for each distinct hand in order to perform the lookup to see which abstracted bucket the given hand belongs to. The number of distinct hands, C(52;2) * C(50;3) * C(47;1) * C(46;1) ≈ 5.6 * 1010, is an order of magnitude too big to give each hand a unique index. For example, encoding the bucket for each hand using two bytes requires more than 104 gigabytes of storage. This would severely limit the practicality of the approach, since this storage is also required by our player at run-time.
We therefore introduce a more compact representation of the abstraction that capitalizes on a canonical representation of each hand based on suit symmetries. (This technique is valid since the rules of poker state that all suits are equally strong.) These canonical representations are computed using permutations (total orderings of the suits) and partial permutations (partial orderings of the suits), as we will describe later in this section.
The best size reduction one could hope for with this approach is a factor of 4! = 24, since we can map any permutation of the four suits to the same canonical hand. That this is not fully achievable is due to the fact that some hands are unaffected by some of the permutations of the suits, e.g. 4c4h is equivalent to 4h4c, in which case there are less than 24 distinct hands mapping to the same canonical one. We call this phenomenon self symmetry.
Our approach uses the following concept. The colexicographical index (Bollob´as 1986) of a set of integers x = {xi … xk}  {0..n-1}, with xi < xj whenever i < j, is colex(x) = ki=1 C(xi;i). This index has the important property that for a given n, each of the C(n;k) sets of size k has a distinct colexicographical index. Furthermore, these indices are compactly encoded as the integers from 0 to C(n;k)-1.
We need to compute indices for hands from each of the four rounds. We compute these indices incrementally, using the index from round i to compute the index in round i + 1. This approach gradually computes the permutations that map the given hand to its canonical representation. This incremental computation is useful both for providing a convenient way of computing the indices and for speeding up the index computation.
The index for the first round is computed, of course, using only the hole cards. If they are of the same suit, e.g. Ac7c, that suit is named “suit 1”, and we get the partial permutation c < {s,h,•}. If they are of different suits and different values, e.g. Ac7s, we name the suit of the card with the highest value “suit 1” and the other “suit 2”, resulting in the partial permutation c < s < {h,d}. Lastly, if they have the same value, e.g. 7s7h, the hand is self symmetric, and we have the partial permutation {s,h} < {c,d}. (At this point it is unspecified which of s and his “suit 1” and which is “suit 2”.)
The later rounds also give rise to partial permutations, which are then used to refine the permutation of suits that were undecided in previous rounds. For instance if the hole cards are 7s7h and the flop is 3dJdAh, we refine the partial permutation {s,h} < {c,d} with d < h < {s,c} to get < {h < s} < {d < c}, i.e. h < s < d < c.
Then, to compute the index from the (perhaps partial) permutation, our algorithm uses a case analysis which has far too many cases (60) to describe here. As an example, if the hole cards are 7s7h and the flop is 3dJdAh, then the analysis is in the category of one new suit in two cards and one old suit in a single card, breaking the self symmetry from the previous round. In this case the card with the old suit (h) only has 12 possible canonical values (even though there are 24 spades and hearts left in the deck), since no matter whether that new card would have been a s or a h, its suit will now have become “suit 1”. In the same way, the two other cards only have C(13;2) possible canonical values, since their suit will now have become “suit 3” no matter whether it is d or c. Thus this case has C(13;2) • 12 = 936 canonical hands representing four times that many actual hands, all of which share 7s7h as the hole cards.
Each of the cases simply breaks the hand up into sets to be encoded with colexicographical indexing. In the case above, the sets are {1,9} and {11} (index 11 is the highest of the 12 cards in the group). Here, 1 corresponds to the three, 9 corresponds to the Jack, and 11 corresponds to an Ace. The index within this case is then computed as colex({1, 9}) • 12 + colex({11}). This is then combined with the index within the case of the first round. There are 13 possible pairs, and our sevens have index 5. We thus get (colex({1, 9}) • 12 + colex({11})) • 13 + 5. Finally, to get the index, this is added to a global offset associated with this particular case.
With this indexing scheme, the memory consumption of the index for all four rounds reduces by a factor of 23.1 (which is close to the optimistic upper bound of 24).
Using symmetries to speed up 9-card rollout
For each pair of buckets in the fourth round, we need to compute the expected number of wins, losses, and draws for hands randomly drawn from those buckets. The straightforward approach of generating C(52;2) * C(50;2) * C(48;3) * C(45;1)* C(44;1) ≈ 5.56 • 1013 possible ways the cards can be dealt would require more than a month of CPU time. Furthermore, this computation would have to be started from scratch when we consider a new, different abstraction. But since we know that the indexing scheme will do the “suit renaming” anyway, we are able to just generate cards for all possible indices, with a weight indicating how many symmetric situations the current cards are representing. Furthermore, we use the fact that the two sets of hole cards are symmetric to only generate those where Player 1’s cards are “less” than Player 2’s cards, using an arbitrary ordering of the hole cards. Doing all this gives us more than a factor 44 speed up of the 9-card rollout, bringing it down to less than a day.

I just did some tests with PokerStove for an 8 player case. The performance is pretty similar in all cases, and the difference in performance (only 20%) for doing 400000 times the number of evaluations indicates that Andrew Prock is reducing the evaluations to a normal form before doing the evaluations (see the results at the end).

Is anyone aware of an algorithm or an idea to compute efficently the normal forms for testing for isomorphisms in an efficient way (without computing all the suits permutations)? Some cases are pretty straight forward, but for example when I start with AcKh vs AhKd vs AdKs vs AsKc I have problems to incorporate the information that I gain (player 5 can come QsJs with only one QJs and then I have to incorporate the new info to the previous one).

Any help will be appreciated.

TIA & Regards ...



1) AcKc vs AsKs vs AdKd vs AhKh vs QcJc vs QsJs vs QdJd vs QhJh

Text results appended to pokerstove.txt
376,992 games 0.001 secs 376,992,000 games/sec

2) AsKs vs AsKs vs AsKs vs AsKs vs QJs vs QJs vs QJs vs QJs

Text results appended to pokerstove.txt
217,147,392 games 0.717 secs 302,855,497 games/sec

These are 4! * 4! = 24 * 24 = 576 cases that are all isomorphic to case (1).

3) AKs,QJs vs AKs,QJs vs AKs,QJs vs AKs,QJs vs AKs,QJs vs AKs,QJs vs AKs,QJs vs AKs,QJs

Text results appended to pokerstove.txt
15,200,317,440 games 51.620 secs 294,465,661 games/sec

These are 8! = 40320 cases that are all isomorphic to case (1)

F me, F me, F me.

Andrew is not taking advantage of the suits isomorphisms (the hands per second have to go way up, not a bit down), I've interpreted the results wrong.

So, the search for the best algorithm to detect isomorphisms will not come from PokerStove, alltough I've finally succeded to download the old java code from Andrew (http://www.pokerstove.com/download/jpoker.tar.gz).

Regards ...

Just to clarify, PokerStove does keep track of certain kinds of suit isomorphisms internally. It does not do general suit isomporhisms, as can be verified by comparing AcKc vs. 2s2h to AKs vs. 22. If it used full suit isomorphisms the two cases should be very close in time, but they aren't.

Internally, evaluations are decomposed into partial evaluations, and under certain circumstances a partial evaluation can be applied across many different scenarios. Many of these scenarios are certain kinds of suit isomorphisms.

Right now I'm working on a general game evaluator, which will use full suit isomorphisms (as well as a dozen other things) to hopefully evaluate any game at a greatly improved rate.

- Andrew

Adrian20XX,

After reading the AAAI paper I understand how you arrived at s < c < h < d for the first starting hand combination: {AcAs, AdAh, AsKs, KcQc, JhTh}. Furthermore, for the next starting hand combination (which we know is suit isomorphic): {AcAh, AsAd, AdKd, KsQs, JcTc}, I arrived at the following suit ordering: c < h < d < s (is this correct?).

The problem I have, though, is that I don't know how to show that both starting hand combinations are equivalent using the suit orderings. I'm assuming all that needs to be done is to transform them into normal form using the suit orderings, but I can't figure out how to do this.

If you don't mind, could you show me how to transform each of the starting hand combinations into normal form using the suit orderings so I can verify that both combinations are equivalent?

How are you progressing with your general game evaluator project? Do you have any plans to incorporate the full suit isomorphisms optimisation into PokerStove? Any plans to post any more source code applicable to poker?

- Quatari

Slowly in general, but more quickly in recent months. I am actually playing around with the idea of opening up some of the basic functionality after I'm done with the rewrite. I would guess that even if I do open it up, the poker-eval open source project would still have more functionality.

- Andrew