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

Range Equity Distribution Calculation
http://poker-ai.org/phpbb/viewtopic.php?f=24&t=2489		 Page 1 of 2
Author:  EternalGuest [ Sun May 12, 2013 6:07 pm ]
Post subject:  Range Equity Distribution Calculation
I asked a question in another forum. Now it disappeared. Maybe because I asked in the wrong forum, so I try to ask here. What happened so far is attached in the screenshot.

____________________________________________________________________________________________________________________________________
My post then:

Yes, I have an implementation of that already. I can do like 120MM hand-lookups/s which leads to (ideally 60MM hand-evaluations/s).

My problem now is, that, given a larger range like (22+, A2s+, K2s+, Q2s+, A2o+, K2o+, Q2o+) there are so many hands, that calculating the postflop equities takes ... some time. Approximating the partial equities with (i.e. a Monte Carlo simulation) works fine in most of the cases (even if I only have ~10k samples per specific hand after like 4s), but maybe anybody is aware of some "synergy effects" which allow you to obtain 4 samples by doing 3 simulations by smartly choosing specific flop and turn-cards or something like that.

Cheers

Attachments:
File comment: History
thread.jpg
thread.jpg [ 51.03 KiB | Viewed 22956 times ]
Author:  EternalGuest [ Sun May 12, 2013 11:02 pm ]
Post subject:  Re: Range Equity Distribution Calculation
Implementing Monte Carlo in ASM with a few preparations (Pre-Lookup all possibly required values from the LUT in an array and ensuring a collision-free choice of cards for each iteration) does the trick for now.

Still looking for smart improvements. This part is crucial for me

Sorry for bothering and thanks for your help
Author:  loudion [ Mon May 13, 2013 8:54 pm ]
Post subject:  Re: Range Equity Distribution Calculation
EternalGuest wrote:
Implementing Monte Carlo in ASM with a few preparations (Pre-Lookup all possibly required values from the LUT in an array and ensuring a collision-free choice of cards for each iteration) does the trick for now.

Still looking for smart improvements. This part is crucial for me

Sorry for bothering and thanks for your help

I agree that Monte Carlo and LUTs are the way to go when facing huge calculations and little time to perform them. But I don't think it's really necessary to write anything in ASM. The compilers of today will do a lot of optimizations and you probably won't get any better performance out of it unless you write your ASM code flawless. If you got extra time over then it's much better spent refining your AI or grabbing a beer.
Author:  spears [ Tue May 14, 2013 6:54 am ]
Post subject:  Re: Range Equity Distribution Calculation
Here's what happened...
1 You posted in Online Botting
2 I answered
3 I moved the thread to Miscellaneous
4 You started a new thread in AI Research
5 I deleted the thread in Miscellaneous
Author:  spears [ Tue May 14, 2013 7:26 am ]
Post subject:  Re: Range Equity Distribution Calculation
I'm not sure I completely understand your post.

You say you can do 120MM hand lookups / sec using a LUT. Does MM mean a million? And by hand lookup do you mean for example Ac3d v random hand for a particular board? It shouldn't be hard to achieve 120 million hand lookups using a LUT of all hands against a random hand for all boards. In any case the expensive part is computing the index of the board, and after that finding a particular hand equity for that board is quite cheap.

And then you use MC simulation to evaluate the range expression (22+, A2s+, K2s+, Q2s+, A2o+, K2o+, Q2o+) ?

Could you construct a LUT containing the equity of each of the range elements (22+, A2s+, K2s+...) v a random hand for all boards, and then just average them at runtime? IIRC correctly there are only about 1800 flops and 16000 turns taking account of isomorphisms
Author:  somehomelessguy [ Tue May 14, 2013 10:33 am ]
Post subject:  Re: Range Equity Distribution Calculation
how fast do you need it?

are you only interested in a range vs random hand, or also range vs range?

anyway, you should only need range_size*range_size LUT lookups, so i don't see why you would need MC simulation unless you need the value superfast.
Author:  EternalGuest [ Wed May 15, 2013 9:40 pm ]
Post subject:  Re: Range Equity Distribution Calculation
Hey both of you,

thanks for answering

@spears:
(1) yes, by MM I mean million. it's a finance abbreviation I guess
(2) yes, by a hand lookup I mean := obtaining a hand-strength-value given some
(a) holecards
(b) flop
(c) turn and
(d) river
==> to evaluate whether hero's hand won or not there are two lookups (in HU) or n lookups (in a n-ring game) required
(sorry if I mess up the terminology)

@spears, somehomelessguy:
I am interested in obtaining the equities of all holecards in a specific range at once. by that I mean: given any range R I am looking for an algorithm that gives me the equities of all holecards H \in R at once and especially NOT for the overall equity of R against a random range

@spears: these calculations come into play postflop which leads us (naively) to a [#firstHolecards=53][#secondHoleCards=53][#turnCards=53][#riverCards=53]-array of possible lookup values. assuming 4 bytes per entry (including redundant and invalid combinations) this takes ~31,561,924bytes in memory
... oh by the way one question: Are you aware of papers building somewhat like an homomorphism of holecards given a specific board. (for instance if you have a monotone-flop of spades all suited holecards of clubs, hearts and diamonds would be in the same equivalence-class ... regarding equity)

@somehomelessguy: if I am not mistaken: assuming you are at the flop you have to do range_size*range_size*[#turncards]*[#rivercards] which (worst case) is a little less then (49*48)/2 * (47*46)/2 * (45*44)/2 = 1,258,543,440 * 2 lookups to obtain the equity of each holecard in your range

my problem now is that exhaustive enumeration takes somewhat like 15-30 seconds so I am looking for methods to approximations the equities.

@loudion: there are several practical reasons why I need the equities rather quickly. Anyway I took your advice to grab a (few) beer. cheers ;)

[EDIT] a few numbers
Author:  nemesis17 [ Mon May 20, 2013 5:48 am ]
Post subject:  Re: Range Equity Distribution Calculation
Here http://www.site.uottawa.ca/~lucia/courses/5165-09/ you can find information on isomorphism-free exhaustive generation.
Author:  Nose [ Thu May 30, 2013 3:35 pm ]
Post subject:  Re: Range Equity Distribution Calculation
spears wrote:
[...] IIRC correctly there are only about 1800 flops and 16000 turns taking account of isomorphisms


Just for cross-checking. I am currently working on that: 1755 isomorphic flops and 16432 isomorphic (flop-turn) combinations?
Author:  spears [ Thu May 30, 2013 4:20 pm ]
Post subject:  Re: Range Equity Distribution Calculation
Yes. 134459 river, 42769 non nut river boards
Author:  Nose [ Thu May 30, 2013 4:30 pm ]
Post subject:  Re: Range Equity Distribution Calculation
spears wrote:
Yes. 134459 river, 42769 non nut river boards

thx
Author:  Nose [ Thu May 30, 2013 4:35 pm ]
Post subject:  Re: Range Equity Distribution Calculation
I ask just to be sure:

A nut river board is any board that guarantees a split pot such as

- any royal flush
- any xxxxA or AAAAK board
- any ace high straight such there is no flush possible
Author:  winnie [ Thu May 30, 2013 4:53 pm ]
Post subject:  Re: Range Equity Distribution Calculation
correct
Author:  Nose [ Fri May 31, 2013 10:48 am ]
Post subject:  Re: Range Equity Distribution Calculation
Jippi, I found them all. But now I am wondering how to translate each board to an index that can be used when running CFRM.

One way to do it would be to store all iso-boards with its corresponding index in a hashtable. But the same problem arises in another case, where it cannot be solved that easy:

Assuming you are precomputing all EHS and EHS²-values and store them in a file like approached by dipitlow:
http://poker-ai.org/archive/www.pokerai ... 455#p13455

Now, given a certain board a formula is required to translate its board-bit-structure into a number representing the offset in the file where the numbers are stored.

This time a hashtable-approach seems quite inefficient to me since there are so many possible boards for which values need to be stored in memory.
Author:  spears [ Fri May 31, 2013 12:06 pm ]
Post subject:  Re: Range Equity Distribution Calculation
- Don't translate from boards to board isomorphs. Just sample from the board isomorphs.
- Forget about files. Keep it in memory.
Author:  Nose [ Fri May 31, 2013 1:11 pm ]
Post subject:  Re: Range Equity Distribution Calculation
spears wrote:
- Don't translate from boards to board isomorphs. Just sample from the board isomorphs.


Nice hint. Thanks

spears wrote:
- Forget about files. Keep it in memory.


Also thanks a lot for that. That saved me from wasting a lot of time. For EHS² I did some math for further readers:

Code:
Assuming 16,432 turns and 2,652 possible holecards (neglecting redundancies) we need to obtain 43,577,664 (rather cheap) EHS² values, requiring 348,621,312bytes in memory (assuming 8 byte doubles)
Assuming 1,755 flops and 2,652 possible holecards (neglecting redundancies) we need to obtain 4,654,260 (rather expensive) EHS² values, requiring 37,234,080 bytes in memory (assuming 8 byte doubles)

Leading to a total of 385,855,392 bytes  ~368 Mb in memory



I am now asking myself how long it would take to precompute all EHS² values. Are there already tables available in the archive? The search method does not work really well for me
Author:  spears [ Fri May 31, 2013 2:28 pm ]
Post subject:  Re: Range Equity Distribution Calculation
- It takes a few hours.
- You need to remember the number of instances per isomorph to sample accurately
- I don't think anyone has uploaded the tables
Author:  Nose [ Mon Jun 03, 2013 10:53 am ]
Post subject:  Re: Range Equity Distribution Calculation
spears wrote:
- It takes a few hours.
- You need to remember the number of instances per isomorph to sample accurately
- I don't think anyone has uploaded the tables


Thanks again for your useful hints. When looking at the file sizes I understand why nobody uploaded them before :)

I attached my results for preflop EHS and EHS2-values.

[GREEN] refers to the top 25%
[GRAY] refers to the top 50%
[WHITE] refers to the top 75%
[RED] refers to the top 100%

But honestly I am a bit disappointed. When looking at the "winners" and "losers" table I created

Formula: CHANGE = EHS - SQRT(EHS2)

you can see that all weak cards benefit from that rule and all strong cards get punished. As you can see even 82o gets a huge bonus. This surprises me. I thought the idea behind using EHS<n> is to give hands with strong potential (such as connectors, suiteds) a bonus regarding to the ring size n.

On the other hand holecards like J3o and 82o should be punished since they are weak hands overall and have no potential. But as you can see the most punished hand is AA while - just to mention it again - 82o gets a bonus in strength.

Is that really what we want? Does anybody know why we want that?

[EDIT] Attached the tables since a few people are interested in the numbers

Attachments:
File comment: SQRT(EHS2) - EHS
eq_vs_eq2.zip [14 KiB]
Downloaded 475 times
File comment: EHS - SQRT(EHS2)
ehs-sqrt(ehs2).png
ehs-sqrt(ehs2).png [ 11.8 KiB | Viewed 22643 times ]
File comment: EHS and EHS2 values
eq.jpg
eq.jpg [ 157.77 KiB | Viewed 22643 times ]
Author:  spears [ Mon Jun 03, 2013 11:31 am ]
Post subject:  Re: Range Equity Distribution Calculation
IIRC first mention of ehs2 and its rationale is http://poker.cs.ualberta.ca/publication ... on.msc.pdf
Author:  Nose [ Mon Jun 03, 2013 2:12 pm ]
Post subject:  Re: Range Equity Distribution Calculation
http://poker.cs.ualberta.ca/publications/johanson.msc.pdf wrote:
Expected Hand Strength Squared
Earlier, we explained how potential was not well measured by the E[HS] metric. In our new bucketing
approach, we roll out the cards for each hand and measure the expected value of the square of
the hand strength. This approach (abbreviated as E[HS2]) also assigns values in the range [0, 1] to
hands, but assigns a higher value to hands that have potential to improve in strength.
[...]


This - if I understand it correctly - means: The higher the potential to improve in strength, the higher the assigned value. But then - why is a higher value assigned to 82o? Since all values are < 1 : shouldn't EHS^(1/2) be a better metric to express potential to improve in strength? This starts confusing me :?
Page 1 of 2 All times are UTC
Powered by phpBB® Forum Software © phpBB Group
http://www.phpbb.com/