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

A Fast and Optimal Hand Isomorphism Algorithm (2013)
http://poker-ai.org/phpbb/viewtopic.php?f=25&t=2660		 Page 1 of 2
Author:  ConvexPolytope [ Mon Dec 09, 2013 1:43 am ]
Post subject:  A Fast and Optimal Hand Isomorphism Algorithm (2013)
A Fast and Optimal Hand Isomorphism Algorithm
by: Kevin Waugh

Abstract

In a section of their 2007 paper, Gilpen et. al. outline a technique for indexing poker hands that accounts for suit isomorphisms. Their implementation is specific to Texas Hold'em as it requires a large case analysis, and is not optimal as many cases are omitted. In this paper, we build on their ideas and provide a fast and optimal technique that generalizes beyond Texas Hold'em as well as provide an inverse mapping from an index to a canonical hand.

Link: https://www.aaai.org/ocs/index.php/WS/A ... /7042/6491
Author:  Nose [ Mon Dec 09, 2013 11:17 am ]
Post subject:  Re: A Fast and Optimal Hand Isomorphism Algorithm (2013)
Once again this post gives a great insight to isomorphic hand-board-constellations

http://poker-ai.org/archive/www.pokerai ... view=print
Author:  proud2bBot [ Mon Dec 09, 2013 5:38 pm ]
Post subject:  Re: A Fast and Optimal Hand Isomorphism Algorithm (2013)
Does anyone know the actual meaning of the numbers in the table? For instance, they list the perfect turn indexing with ~55M entries, while a typical turn LUT only has ~15M entries. Hence, I wonder which information they additionally store. Is their approach considering different transitions from flops to the same turn, i.e. AsKhQd2s != 2sAsKhQd?
Author:  ConvexPolytope [ Fri Dec 13, 2013 5:41 am ]
Post subject:  Re: A Fast and Optimal Hand Isomorphism Algorithm (2013)
I only skimmed the paper so I hope I got this right

Quote:
Is their approach considering different transitions from flops to the same turn, i.e. AsKhQd2s != 2sAsKhQd?


For example

AsKhQd|2s = KhAsQd|2s = AhQcKd|2h

The 3 card configurations above result in the same index. Your 2 examples result in a different index (if we assume the cards represent 3 flop cards and 1 turn card). It depends on how you group the cards. If we look at hole cards and flops instead of flops and turns we have the following grouping:

h1 h2 | f1 f2 f3 (and that's the grouping they use in their examples in the paper)

A complete Hold'em hand:

h1 h2 | f1 f2 f3 | t1 | r1

An Omaha hand:

h1 h2 h3 h4 | f1 f2 f3 | t1 | r1

Some weird Hold'em games deal another card after the river, called the 'ocean'. So then the grouping would be:
h1 h2 | f1 f2 f3 | t1 | r1 | o1

You get the point. This method generalizes earlier approaches that could only be used for Hold'em.
--------

Unrelated to the above question: They state that their indexing procedure leaves no holes. I don't know if this is true for other methods as well, but it is a nice property. For example, assume that N is the number of strategically different holecard/flop combinations. In order to enumerate all possible combinations, it is sufficient to loop from 1 to N, since every number represents exactly 1 combination.
Author:  amago [ Fri Dec 13, 2013 5:53 pm ]
Post subject:  Re: A Fast and Optimal Hand Isomorphism Algorithm (2013)
Great about Kevin Waugh is he has some code published:

https://github.com/kdub0/hand-isomorphism
Author:  ConvexPolytope [ Sat Dec 14, 2013 9:46 am ]
Post subject:  Re: A Fast and Optimal Hand Isomorphism Algorithm (2013)
proud2bBot wrote:
Does anyone know the actual meaning of the numbers in the table? For instance, they list the perfect turn indexing with ~55M entries, while a typical turn LUT only has ~15M entries. Hence, I wonder which information they additionally store. Is their approach considering different transitions from flops to the same turn, i.e. AsKhQd2s != 2sAsKhQd?


I thought about this some more. In your example, if the 2 boards resulted in the same index, wouldn't this be a lossy abstraction? We 'forget' in which order the cards fell, so in a way we have imperfect recall (regarding the cards, not the betting in earlier rounds). Is this the standard way of building a typical turn LUT with 15M entries? In this case, for a given set of 4 cards, any one of them could be the turn card, so we need 4 times more entries if we want to remember which one the turn card was. We see this factor of 4 in your 15M number vs. the 55M number in the paper.

I always assumed the order has to be preserved. After all, different turn cards often have different strategic implications.

Quote:
Great about Kevin Waugh is he has some code published:

https://github.com/kdub0/hand-isomorphism


For Rhode Island Hold'em this implementation results in LUT sizes 13, 325, 9997 for preflop, flop and turn respectively.
Author:  spears [ Sat Dec 14, 2013 11:29 am ]
Post subject:  Re: A Fast and Optimal Hand Isomorphism Algorithm (2013)
Quote:
Is this the standard way of building a typical turn LUT with 15M entries?
Probably, yes. AFIK most people deal with the imperfect/perfect recall issue in other ways. Imperfect recall is known to be am effective way of reducing the problem size.
Author:  proud2bBot [ Sat Dec 14, 2013 5:34 pm ]
Post subject:  Re: A Fast and Optimal Hand Isomorphism Algorithm (2013)
It always depends on which kind of data you store in the LUT. For instance, storing EHS2 values on the turn, a reduced LUT is sufficient. However, I wanted to store bucket information, in which case the order of the public board is actually relevant for me and then you want to have a LUT like the one in the paper. The cool thing about their approach is that you can easily create both indexing schemes.
Author:  algonoob [ Thu Dec 19, 2013 12:06 am ]
Post subject:  Re: A Fast and Optimal Hand Isomorphism Algorithm (2013)
amago wrote:
Great about Kevin Waugh is he has some code published:

https://github.com/kdub0/hand-isomorphism


I tried to run check.exe and got an assertion error. Anyone else get this?
(note there was a compile warning)

$ make check
cc -std=c99 -Wall -g -O2 -c -o src/check-main.o src/check-main.c
cc -std=c99 -Wall -g -O2 -c -o src/deck.o src/deck.c
cc -std=c99 -Wall -g -O2 -c -o src/hand_index.o src/hand_index.c
src/hand_index.c: In function ‘hand_index_ctor’:
src/hand_index.c:25:5: warning: suggest parentheses around ‘-’ in operand of ‘&’ [-Wparentheses]
for(uint_fast32_t j=0, set=~i&(1<<RANKS)-1; j<RANKS; ++j, set&=set-1) {
^
cc -o src/check src/check-main.o src/deck.o src/hand_index.o
./src/check
testing hand-isomorphism...
sizes: 169 1286792 55190538 2428287420
configurations: 2 15 46 158
permutations: 19 1315 8227 63523
preflop table:
A K Q J T 9 8 7 6 5 4 3 2
A 3053826047 7149443039322 7149443039321 7149443039320 7149443039319 7149443039318 7149443039317 7149443039316 7149443039315 7149443039314 7149443039313 7149443039312 7149443039311
K 3053826046 3053826034 7149443039310 7149443039309 7149443039308 7149443039307 7149443039306 7149443039305 7149443039304 7149443039303 7149443039302 7149443039301 7149443039300
Q 3053826045 3053826033 3053826022 7149443039299 7149443039298 7149443039297 7149443039296 7149443039295 7149443039294 7149443039293 7149443039292 7149443039291 7149443039290
...
...
full preflop...
assertion "index < size" failed: file "src/check-main.c", line 30, function: test_full
Author:  ConvexPolytope [ Thu Dec 19, 2013 2:09 am ]
Post subject:  Re: A Fast and Optimal Hand Isomorphism Algorithm (2013)
algonoob wrote:
amago wrote:
Great about Kevin Waugh is he has some code published:

https://github.com/kdub0/hand-isomorphism


I tried to run check.exe and got an assertion error. Anyone else get this?


I did not get this error.

Quote:
(note there was a compile warning)

[...]
src/hand_index.c:25:5: warning: suggest parentheses around ‘-’ in operand of ‘&’ [-Wparentheses]
for(uint_fast32_t j=0, set=~i&(1<<RANKS)-1; j<RANKS; ++j, set&=set-1) {
^
cc -o src/check src/check-main.o src/deck.o src/hand_index.o


The line where the warning is thrown is interpreted wrong by your compiler. It's supposed to interpret it like so
set=~i&((1<<RANKS)-1);

but it interprets it like so:
set=(~i&(1<<RANKS))-1;

Add brackets like in the first example, that should fix it.
Author:  algonoob [ Thu Dec 19, 2013 2:25 am ]
Post subject:  Re: A Fast and Optimal Hand Isomorphism Algorithm (2013)
Thank you for the reply,
After modifying that line as you described, different numbers show but it's still an assert error.
I also tried different combinations of parentheses with no success.
What compiler are you using?

Here's the new table generated
A K Q J T 9 8 7 6 5 4 3 2
A 8280 6408570 6168251 5934016 5705787 5483486 5267035 5056356 4851371 4652002 4458171 4269800 4086811
K 8280 7084 3909126 3736667 3569356 3407115 3249866 3097531 2950032 2807291 2669230 2535771 2406836
Q 8280 7084 5980 2282347 2162226 2046395 1934776 1827291 1723862 1624411 1528860 1437131 1349146
J 8280 7084 5980 4968 1264827 1184096 1106875 1033086 962651 895492 831531 770690 712891
T 8280 7084 5980 4968 4048 658056 606107 556966 510555 466796 425611 386922 350651
9 8280 7084 5980 4968 4048 3220 316720 285051 255566 228187 202836 179435 157906
8 8280 7084 5980 4968 4048 3220 2484 138171 120152 103771 88950 75611 63676
7 8280 7084 5980 4968 4048 3220 2484 1840 53067 43706 35515 28416 22331
6 8280 7084 5980 4968 4048 3220 2484 1840 1288 17182 12891 9380 6571
5 8280 7084 5980 4968 4048 3220 2484 1840 1288 828 4386 2747 1576
4 8280 7084 5980 4968 4048 3220 2484 1840 1288 828 460 795 326
3 8280 7084 5980 4968 4048 3220 2484 1840 1288 828 460 184 91
2 8280 7084 5980 4968 4048 3220 2484 1840 1288 828 460 184 0
full preflop...
assertion "index < size" failed: file "src/check-main.c", line 30, function: test_full
Makefile:27: recipe for target `check' failed
make: *** [check] Aborted (core dumped)

edit: nevermind, the table generated doesn't change, I misread your post. The above table is generated using the incorrect order of operations. So it seems the compiler was treating it correctly the first time, which still gives the assertion error.
Author:  ConvexPolytope [ Thu Dec 19, 2013 2:40 am ]
Post subject:  Re: A Fast and Optimal Hand Isomorphism Algorithm (2013)
ok, so the failed assertion doesn't have anything to do with the compiler warning. don't know what else could be the reason. i use gcc and it compiles just fine.
Author:  nonpareil [ Sat Jan 04, 2014 6:36 am ]
Post subject:  Re: A Fast and Optimal Hand Isomorphism Algorithm (2013)
This is very nifty code... I wish I had a way to run k-means with 2 billion entries but I think my computer would explode.

You can still cut down on the number of indexes if you're thinking about Hold'em/Omaha because suits can become irrelevant eventually. e.g. on a three heart flop, if your hole cards don't contain a heart, it doesn't matter if your hole cards are suited or not. Like 7s6s on 2h3h4h is the same as 7d6c on 2h3h4h. Taking that into account, you can collapse a huge number of rivers together because oftentimes all suits become irrelevant because no flushes are possible. I wonder if there is a way to keep this setup as general/elegant as it is but add in a way to collapse suits when they can no longer make flushes.
Author:  Pitt [ Fri Jan 31, 2014 11:19 am ]
Post subject:  Re: A Fast and Optimal Hand Isomorphism Algorithm (2013)
I was porting this to a JNI dll (first time!).
I get the method executed, but get the same assertion error...
It may have something to do with compilation chain options or flags I think, but I'm very bad at that (lazy Java guy).

I'll let you know if I find out what this mess is, please do the same ;)
Author:  nonpareil [ Sat Feb 01, 2014 11:39 pm ]
Post subject:  Re: A Fast and Optimal Hand Isomorphism Algorithm (2013)
The grid of numbers that's displayed is supposed to be a table of all the holdem preflop indexes (from 0-168). The assertion error occurs because the table is wrong. First line should be:

90 168 167 166 165 164 163 162 161 160 159 158 157

I do think it's some compiler option causing the strange output. When compiling in "Release" mode in Visual Studio 2012, I got an incorrect grid of huge numbers like above, but when compiling in "Debug" mode I got the proper output. (I thought I made sure none of the initialization was done inside assert macros as well.)
Author:  nonpareil [ Sun Feb 02, 2014 2:03 am ]
Post subject:  Re: A Fast and Optimal Hand Isomorphism Algorithm (2013)
Eventually, I just refactored the code my own way and specialized it for the most common indexes I use. Be warned when testing that both examples at the end of the paper have mistakes in them...

In the step from Equation (13) to Equation (14), he incorrectly has C(12,2) = 72 when actually it's 66, so the index within that suit configuration Equation (19) should actually be 55212.

The next example he tries to illustrate changing a hand to canonical form, but unfortunately changes one hand into a completely different hand when they are NOT isomorphic. You can tell that 6dTc|Jc7dKh is not the same as Ts6h|7sJhKd because in the first version the 6 in the hand and 7 on the board are the same suit, but not in the second version. (Same goes for the T in hand and J on board being suited in the first version, then not so in the second.)
Author:  Pitt [ Sun Feb 02, 2014 4:48 pm ]
Post subject:  Re: A Fast and Optimal Hand Isomorphism Algorithm (2013)
+1 for the assertion failure origin :
I had
CFLAGS ?=-m64 -Wl, -std=c99 -Wall -g -O2

Now it's ok with
CFLAGS ?=-O0 -g3 -Wall -c -fmessage-length=0 -std=c99

Don't know what every flag means, but it works this way :)
Author:  Pitt [ Fri Feb 14, 2014 12:50 pm ]
Post subject:  Re: A Fast and Optimal Hand Isomorphism Algorithm (2013)
Hi there,

I wrapped the C code into a x64 JNI dll, making some of the methods available to build Hold'em hands perfect recall and imperfect recall indexers, and a boards imperfect recall indexer.
You have to put the dll in the path of your x64 JVM, (using -Djava.library.path=path/to/the/library/directory for example).

The packages names are arbitrary, but you can't change com.pokertricks.HandIndexing's package because of JNI mecanism.

Look at com.pokertricks.HoldemIRHandIndexer, HoldemPRHandIndexer, and HoldemIRBoardIndexer to see how this intends to be used.

Didn't produce any benchmark.
Let me know if you need another native linking to have better indexers (other native methods for incremental indexing for example).
But keep the JNI cost in mind : a hand or board should be indexed for each round in one call.

Here are the sizes for hand indexers :

Imperfect recall :
[169, 1286792, 13960050, 123156254]

Perfect recall :
[169, 1286792, 55190538, 2428287420]

And for board IR indexer :

[1755, 16432, 134459]

Hope it can be helpful ! Tell me about any bug/potential improvement please.

Cheers

Attachments:
HandIndexing.rar [110.15 KiB]
Downloaded 2577 times
Author:  Pitt [ Mon Feb 24, 2014 6:46 pm ]
Post subject:  Re: A Fast and Optimal Hand Isomorphism Algorithm (2013)
I see some of you downloaded the jni wrapper.

I just wanted to say I'm interested in any feedback (even : "It's useless, pointless and stupid, hope I didn't read your post at all you poor miserable Java demon").
Author:  HontoNiBaka [ Tue Oct 07, 2014 5:43 am ]
Post subject:  Re: A Fast and Optimal Hand Isomorphism Algorithm (2013)
How did you come up with those numbers? I have different numbers for imperfect hand indexing. Basically imperfect hand indexing on the turn let's say, would just be indexing of 6 cards, 1 round. My number is much smaller.
Page 1 of 2 All times are UTC
Powered by phpBB® Forum Software © phpBB Group
http://www.phpbb.com/