Poker-AI.org

Re: A Fast and Optimal Hand Isomorphism Algorithm (2013)

2017-04-14T17:09:38+00:00

Can this code also be used for Omaha, if you only change the cards per street value, or do you think there could be some problems with that?

edit: ok I have read it again, it will be possible

Statistics: Posted by HontoNiBaka — Fri Apr 14, 2017 5:09 pm

Re: A Fast and Optimal Hand Isomorphism Algorithm (2013)

2015-10-17T09:23:12+00:00

HontoNiBaka wrote:

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.

http://www.poker-ai.org/archive/www.pok ... a&start=60

Statistics: Posted by spears — Sat Oct 17, 2015 9:23 am

Re: A Fast and Optimal Hand Isomorphism Algorithm (2013)

2015-10-16T02:14:06+00:00

Pitt wrote:

Don't know about C compilation options, kind of a noob for that.

For instance not using the -g flag, as this compile in the debug mode. Also enabling the optimisations, for instance with the -O2 flag.

I don't use gcc often, but O2 should be enough to be faster than java. Turning optimisations on really makes a big difference.

Statistics: Posted by HontoNiBaka — Fri Oct 16, 2015 2:14 am

Re: A Fast and Optimal Hand Isomorphism Algorithm (2013)

2015-10-11T10:18:07+00:00

Don't know about C compilation options, kind of a noob for that.
For CFRM you say that Waugh's indexer is faster than Djhemlig's one because of incremental indexing ?
I completely forgot about that in my Java implementation of Waugh's indexer, i'll look into it !

Statistics: Posted by Pitt — Sun Oct 11, 2015 10:18 am

Re: A Fast and Optimal Hand Isomorphism Algorithm (2013)

2015-09-09T14:02:07+00:00

Have you turned all optimisations on in your C compiler?

I also observed a speed improvement over djhelmig code, it mostly came from the fact, that you can index the streets incrementally, so when you index the river, you basically get the flop and turn for free. That makes a substantial difference in the CFRM algorithm, but maybe not in test cases.

Statistics: Posted by HontoNiBaka — Wed Sep 09, 2015 2:02 pm

Re: A Fast and Optimal Hand Isomorphism Algorithm (2013)

2015-07-26T12:35:21+00:00

After several month doing nothing about poker, I decided to code Waugh's indexer in Java.
I didn't look at the original code and just did what was written in the paper (omitting errors, understanding misleading notations and wrong examples ), then tried to optimize it.

Tested and working ! (to do a quite fast test, I implemented a full index/unindex test for 2-2 cards groups)

But I'm quite surprised with performance (of indexing because I didn't optimize unindexing).

I tried it for all flop permutations (311 875 200 indexing).

I modified the C test_full to skip the unindexing part and it took 572s => 545 236 indexings/s on a 2,2 Ghz i7

With my code, it took about 51s on a 2,3Ghz i7, so 6M indexings/s.

I'm not surprised of my code's perf but more by the C test of original code.

To compare, I tried indexing with Djhemlig's flop indexer and it gave me 12M indexings/s so my code is apparently twice slower.

So I'm wondering :
- why is the C code so slow ?
- how did Kevin Waugh observe such speed improvements over Hyperborean's implementation ? ("we also observed a 3.5x speed up of our indexing scheme over Hyperborean") I don't know the Hyperborean's implementation, is it that bad (or just old) ? And did he use its code with this bad execution speed to compare ?..

Statistics: Posted by Pitt — Sun Jul 26, 2015 12:35 pm

Re: A Fast and Optimal Hand Isomorphism Algorithm (2013)

2014-10-27T23:07:36+00:00

It does only work for windows x64 sorry. For the unsatisfied link error, you have to put the dll in the classpath.

Sacré d'Jeu said he did port the native code to Java (no JNI), and I asked him if he could publish the code but he didn't answer yet.
I'm a bit lazy and busy so I won't do it myself now, but still interested if anyone does

Statistics: Posted by Pitt — Mon Oct 27, 2014 11:07 pm

Re: A Fast and Optimal Hand Isomorphism Algorithm (2013)

2014-10-24T16:15:29+00:00

Ok, I understand

When trying to load the library I get an unsatisfied link error, it say dependant libraries are missing

Also does it run under both, Wnidows and Linux? Because I would need it on both systems.

Statistics: Posted by HontoNiBaka — Fri Oct 24, 2014 4:15 pm

Re: A Fast and Optimal Hand Isomorphism Algorithm (2013)

2014-10-17T09:13:18+00:00

Nop, IR on the turn is indexing two groups of cards with cardinal 2 and 4. We still need to separate hole cards from board

Statistics: Posted by Pitt — Fri Oct 17, 2014 9:13 am

Re: A Fast and Optimal Hand Isomorphism Algorithm (2013)

2014-10-07T05:43:55+00:00

Statistics: Posted by HontoNiBaka — Tue Oct 07, 2014 5:43 am

Re: A Fast and Optimal Hand Isomorphism Algorithm (2013)

2014-02-24T18:46:03+00:00

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").

Statistics: Posted by Pitt — Mon Feb 24, 2014 6:46 pm

Re: A Fast and Optimal Hand Isomorphism Algorithm (2013)

2014-02-14T12:50:58+00:00

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

Statistics: Posted by Pitt — Fri Feb 14, 2014 12:50 pm

Re: A Fast and Optimal Hand Isomorphism Algorithm (2013)

2014-02-02T16:48:38+00:00

+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

Statistics: Posted by Pitt — Sun Feb 02, 2014 4:48 pm

Re: A Fast and Optimal Hand Isomorphism Algorithm (2013)

2014-02-02T02:03:48+00:00

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.)

Statistics: Posted by nonpareil — Sun Feb 02, 2014 2:03 am

Re: A Fast and Optimal Hand Isomorphism Algorithm (2013)

2014-02-01T23:39:46+00:00

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.)

Statistics: Posted by nonpareil — Sat Feb 01, 2014 11:39 pm

Re: A Fast and Optimal Hand Isomorphism Algorithm (2013)

2014-01-31T11:19:51+00:00

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

Statistics: Posted by Pitt — Fri Jan 31, 2014 11:19 am

Re: A Fast and Optimal Hand Isomorphism Algorithm (2013)

2014-01-04T06:36:35+00:00

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.

Statistics: Posted by nonpareil — Sat Jan 04, 2014 6:36 am

Re: A Fast and Optimal Hand Isomorphism Algorithm (2013)

2013-12-19T02:40:11+00:00

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.

Statistics: Posted by ConvexPolytope — Thu Dec 19, 2013 2:40 am

Re: A Fast and Optimal Hand Isomorphism Algorithm (2013)

2013-12-19T02:25:02+00:00

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.

Statistics: Posted by algonoob — Thu Dec 19, 2013 2:25 am

Re: A Fast and Optimal Hand Isomorphism Algorithm (2013)

2013-12-19T02:09:45+00:00

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< ^
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<
but it interprets it like so:
set=(~i&(1<
Add brackets like in the first example, that should fix it.

Statistics: Posted by ConvexPolytope — Thu Dec 19, 2013 2:09 am

Re: A Fast and Optimal Hand Isomorphism Algorithm (2013)

2013-12-19T00:06:45+00:00

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< ^
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

Statistics: Posted by algonoob — Thu Dec 19, 2013 12:06 am

Re: A Fast and Optimal Hand Isomorphism Algorithm (2013)

2013-12-14T17:34:04+00:00

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.

Statistics: Posted by proud2bBot — Sat Dec 14, 2013 5:34 pm

Re: A Fast and Optimal Hand Isomorphism Algorithm (2013)

2013-12-14T11:29:12+00:00

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.

Statistics: Posted by spears — Sat Dec 14, 2013 11:29 am

Re: A Fast and Optimal Hand Isomorphism Algorithm (2013)

2013-12-14T09:46:04+00:00

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.

Statistics: Posted by ConvexPolytope — Sat Dec 14, 2013 9:46 am

Re: A Fast and Optimal Hand Isomorphism Algorithm (2013)

2013-12-13T17:53:36+00:00

Great about Kevin Waugh is he has some code published:

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

Statistics: Posted by amago — Fri Dec 13, 2013 5:53 pm

Re: A Fast and Optimal Hand Isomorphism Algorithm (2013)

2013-12-13T05:41:35+00:00

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.

Statistics: Posted by ConvexPolytope — Fri Dec 13, 2013 5:41 am

Re: A Fast and Optimal Hand Isomorphism Algorithm (2013)

2013-12-09T17:38:03+00:00

Statistics: Posted by proud2bBot — Mon Dec 09, 2013 5:38 pm

Re: A Fast and Optimal Hand Isomorphism Algorithm (2013)

2013-12-09T11:17:30+00:00

Once again this post gives a great insight to isomorphic hand-board-constellations

http://poker-ai.org/archive/www.pokerai ... view=print

Statistics: Posted by Nose — Mon Dec 09, 2013 11:17 am

A Fast and Optimal Hand Isomorphism Algorithm (2013)

2013-12-09T01:43:17+00:00

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

Statistics: Posted by ConvexPolytope — Mon Dec 09, 2013 1:43 am