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

Kevin Waugh perfect indexing vs Djhemlig's LUT: river off?
http://poker-ai.org/phpbb/viewtopic.php?f=24&t=2993		 Page 1 of 1
Author:  SkyBot [ Tue Sep 13, 2016 2:46 am ]
Post subject:  Kevin Waugh perfect indexing vs Djhemlig's LUT: river off?
Hi,

I need a good and fast LUT. Currently my favourite is Djhemlig's LUT because single lookup speed is most important to me. I wanted to check how much space I would lose compared to Kevin Waugh perfect indexing.

What I don't get are the numbers for the river from the following 2 threads:

Djhemlig ( http://www.poker-ai.org/archive/pokerai ... &hilit=lut ):
"With these current rules I get right now 1361802 flop indexes, 15111642 turn indexes, 52402675 river indexes."

Kevin Waugh indexing ( http://poker-ai.org/phpbb/viewtopic.php?f=25&t=2660 ):
"Imperfect recall :
[169, 1286792, 13960050, 123156254]"

I assumed the Djhemlig numbers to be maybe 10-20% above Waugh numbers, but for the river Djhemlig (52M) is less than half of Waugh (123M), instead of more.
Can this be? Or are the numbers wrong?
Waugh are just isomorphisms I think, but can there be that many rivers where hole cards have no influence (so they could be the same case for Djhemlig) (plus all nut cases)? However, Djhemlig seems not to do these kind of optimizations anyway...
Author:  spears [ Tue Sep 13, 2016 7:36 am ]
Post subject:  Re: Kevin Waugh perfect indexing vs Djhemlig's LUT: river of
Maybe djhemlig uses an approximate technique
Quote:
Being exact costs alot of size so in the end I think a more interesting approach is |lookup - actual measure| < error.
Author:  SkyBot [ Tue Sep 13, 2016 3:24 pm ]
Post subject:  Re: Kevin Waugh perfect indexing vs Djhemlig's LUT: river of
I don't understand all of the Djhemlig code atm, but my suspicion is it is because it maps all hands with less than 3 of the same suit on the board to one suit pattern, e.g. 2*h + 2*c + 1*s and 2*h + 1*c + 1*s + 1*d.

So a "isomorphism" that contains more river specific poker knowledge. Will try to verify that.
Author:  SkyBot [ Tue Sep 13, 2016 8:32 pm ]
Post subject:  Re: Kevin Waugh perfect indexing vs Djhemlig's LUT: river of
Isomorph suit pattern on river (ordered hand: first 2 ordered holes, then 5 ordered board, we only care about suits):

Code:
7 same: 1
6+1: 7    (7 positions where the one suit can be)
5+2: (7 choose 5)=21    (choose which 5 of the 7 are the same)
5+1+1: (7 choose 5)=21    (choose which 5 of the 7 are the same)
4+3: (7 choose 4)=35    (choose which 4 of the 7 are the same)
4+1+1+1: (7 choose 4)=35
4+2+1: (7 choose 4)*(3 choose 2)=105
3+2+1+1: (7 choose 3)*(4 choose 2)=210
3+2+2: (7 choose 3)*(4 choose 2)/2=105   (div 2 because the suits with 2 are isomorph)
3+3+1: (7 choose 3)*(4 choose 3)/2=70   (div 2 because the suits with 3 are isomorph)
2+2+2+1: (7 choose 2)*(5 choose 2)*(3 choose 2)/6=105   (div 6 because the suits with 2 are isomorph)


Total: 1 + 7 + 21 + 21 + 35 + 35 + 105 + 210 + 105 + 70 + 105 = 715

How many does Djhemlig collapse (less than 3 of same suit on board)?
Code:
7 same: 0
6+1: 0
5+1+1 and 5+2: 0
4+3: 0
4+1+1+1: (5 choose 2)=10    (if we have suited holes and the suit is part of the 4, so choose the 2 same from the board, or alternative: (4/7)*(3/6)*35)
4+2+1: (5 choose 2)*(3 choose 2)=30   (if we have suited holes and the suit is part of the 4, so choose the matching suits on board, or alternative: (4/7)*(3/6)*105)
3+2+1+1: (2*(3/7)*(4/6) + (3/7)*(2/6)) * 210 = 150    (if holes contain 2 or 1 of the 3 => only 1: 2*(3/7)*(4/6), both: (3/7)*(2/6))
3+2+2: (2*(3/7)*(4/6) + (3/7)*(2/6)) * 105 = 75    (if holes contain 2 or 1 of the 3 => only 1: 2*(3/7)*(4/6), both: (3/7)*(2/6))
3+3+1: (3/7)(3/6) * 70 = 15    (if holes contain 1 of each 3 => (3/7)(3/6))
2+2+2+1: 105 (all)


Djhemlig Total: 1 + 7 + 42 + 35 + (35-10) + (105-30) + (210-150) + (105-75) + (70-15) + 0 = 330

So Djhemlig would be 715/330 = 2.1667 times larger without that trick.

So: 52402675 * 2.1667 = 113,540,876 (still smaller than 123M :( )

Probably a calculation error on my side or another optimization I did not find until now.
Author:  SkyBot [ Wed Sep 14, 2016 10:33 pm ]
Post subject:  Re: Kevin Waugh perfect indexing vs Djhemlig's LUT: river of
Note: my calculation above is too simple, not all suit patterns occur the same number of time.

I did a crude approximation, checking how many rank pattern are there per suit pattern (with not completely ordered cards for simplicity and no separation of holes and board, so very far away from truth).

How many rank pattern per suit pattern (hand not completely ordered!!!):
Code:
7 same: (13 choose 7) = 1716
6+1: (13 choose 6) * 13 = 22308
5+2: (13 choose 5) * (13 choose 2) = 100386
5+1+1: (13 choose 5) * 13^2 = 217503
4+3: (13 choose 4) * (13 choose 3) = 204490
4+1+1+1: (13 choose 4) * 13^3 = 1570855
4+2+1: (13 choose 4) (13 choose 2) * 13 = 725010
3+2+1+1: (13 choose 3) (13 choose 2) * 13^2 = 3770052
3+2+2: (13 choose 3) (13 choose 2)^2 = 1740024
3+3+1: (13 choose 3)^2 * 13 = 1063348
2+2+2+1: (13 choose 2)^3 * 13 = 6169176


Total sum(ordered_suit_pattern * not_ordered_rank_pattern):
(1*1716) + (7*22308) + (21*100386) + (21*217503) + (35*204490) + (35*1570855) + (105*725010) + (210*3770052) + (105*1740024) + (70*1063348) + (105*6169176) = 1841707946

Djhemlig Total: (1*1716) + (7*22308) + (21*100386) + (21*217503) + (35*204490) + ((35-10+1)*1570855) + ((105-30+1)*725010) + ((210-150+1)*3770052) + ((105-75+1)*1740024) + ((70-15+1)*1063348) + (1*6169176) = 459564261

So Djhemlig would be 1841707946/459564261 = 4.0075 times larger without that trick.

So: 52402675 * 4.0075 = 210,003,720 (so larger than 124M).

Note again: this is very ugly and far away from the truth, just wanted an estimate to know if that table size is possible without missing cases.

I let it be for now and just use Djhemlig LUT.
Page 1 of 1 All times are UTC
Powered by phpBB® Forum Software © phpBB Group
http://www.phpbb.com/