7 Card Hand Evaluators

[jukofyork]

[ QUOTE ]
Phil why are you hostile? Did I ever say the world needed a poker stove that was 10,000 times faster? In fact, you gloss over the fact I said the exact opposite, because you want to pick a fight.

[/ QUOTE ]
Phil153 + Poker AI = Flames

Juk [img]/images/graemlins/smile.gif[/img]

[Andrew Prock]

If you really did get 60 million general evals per second on a normal machine (3 MHz or so), I'm truly impressed. But you have to keep in mind that when it come to doing poker calculations there is more to it than just plain evaluation speed. The guy with the Poker Bolide software demonstrated that recently by making a fast monte carlo evaluator, but not much else.

It's unclear what you're striving for here, or what you've achieved. There is no world record for evals/second, but even at 60 million per second, interesting poker calculations can be done much faster. PokerStove can do about 2 billion evaluations per second in the optimized Enumeration code. In the unoptimized code, it does about 10 million evals per second when enumerating. That may seem slow, but many of the calculations finish with the exact solution nearly instantly. The same can't be said for monte carlo evaluation. While PokerStove does have various lookup tables, those consist mostly of things like bit counting tables. Admittedly, the monte carlo code is not it's strong point, but there's a reason for that.

Under monte carlo, once the code is fast enough, it doesn't really matter too much if you make it twice as fast. You'll get close to the exact value quickly, but you'll never get the exact value. Said another way, doubling the number of evals won't double the convergence of the result. There are also issues of what sort of RNG you use, and equally important how you use it. Getting the RNG problem wrong can mean that your monte carlo simulations converge to the wrong result.

If you can calculate the exact value, you're usually much better off, assuming you can actually calculate it quickly enough. The nice thing is that many of the interesting questions the people ask about poker are computable using exact enumeration, and can be done in a reasonable amount of time. In a lot of ways that was the whole point of PokerStove. If you know what you are trying to calculate, you can do it significantly faster by taking the whole calculation into consideration instead of just relying on fast 7 card hand evaluators. Unfortunatly, not all things can be calculated exactly in a short period of time, and for those you often have to resort to monte carlo, precomputation, or other methods.

If you look at the work of eastbay and bachfan, you can see that they've done a great job in actually answering questions that people want to ask. As for your software, until you make it public in some fashion, it'll mean the world to you, but not much to the world. That's certainly not a bad thing. I have a lot of software which isn't public either. And it does mean quite a bit to me.

On the other hand, all this thread has piqued my curiosity. I'v never really tried to make a fast general purpose evaluator. I wonder how fast I could make it?

- Andrew

[_D&L_]

Well right now I use two lookup tables; and some on-the-fly processing. With 2 gigs of memory, you could just have one big lookup table, and reduce processing time to just retreiving a value from an array. Is that 1000x faster, maybe not, but it would be exponentially faster. Can modern CPU's retreive more than one integer value per CPU cycle? How about from a multi-dimensional Array? Well at any rate, that is the limiting factor, if memory wasn't an issue.

[_D&L_]

Hey Andrew,

First, for anybody else reading Andrew is the author of poker stove. Second, Andrew you may remember me. I wrote you about a year or so ago, inquiring about access to poker stove source code, offering to make some "improvements," sign a confidentiality agreement, etc. You declined, as I probably would have too in your situation, but you can't really fault me for trying.

At any rate, i wrote this code to be used with bots and junk that I was working on. I didn't have your code as a starting point, so maybe i needed to re-invent the wheel - to some extent. Certainly poker stove is great at what it's designed to do, and my intent was never to write a program to displace yours.

One thing i noticed is that with poker stove is that if you set all the players to distributions, the program slows considerably. Its not a big deal for Poker_stove, because rarely are there 9 other players on the flop with you, but Pstove does slow from about 100,000 million games a sec to about 1 game every 4 seconds (9 players on broadway, final player on random all). The slow down isn't as severe with 3 or 4 players on the flop, but it still slows by a magnitude of about 200.

Again, not a big deal for pokerstove, because few Pokerstove users need a question like this answered. But when you set a bot to search for the right strategy, u don't want it hit bottlenecks like that. So thats why my program tries to process everything at a more uniform speed. Besides, even if poker stove does do a better job than my program in answering these questions, i still didn't have access to the source to use in other programs. So at any rate, thats why I wrote my own...

Dirty & Litigious

-Dirty & Litigious

[bachfan]

[ QUOTE ]

From what I just read it sounds like one of you is generating your timings with essentially 5 of the 7 cards statically pre-assigned, and the other is generating the timings with no static cards and possibly some are using a 52 element bitstring rather than 7 unordered integers (bachfan?).


[/ QUOTE ]

Here's what I did (and it looks like I was right with my FIRST quote of approx 15mil/sec, not 30. Oh well. [img]/images/graemlins/smile.gif[/img]

I just spewed out 15 million random 7-card poker hands and computed the ranking for each. I looked up the cpu utilization for the ranking function and extrapolated the rate from that (i thought 30 mil for a minute but i forget to include a part which in all fairness really is part of the evaluation function - long story...)

I've got some more comments coming. [img]/images/graemlins/smile.gif[/img]

- bachfan

[bachfan]

[ QUOTE ]

Under monte carlo, once the code is fast enough, it doesn't really matter too much if you make it twice as fast. You'll get close to the exact value quickly, but you'll never get the exact value. Said another way, doubling the number of evals won't double the convergence of the result. There are also issues of what sort of RNG you use, and equally important how you use it. Getting the RNG problem wrong can mean that your monte carlo simulations converge to the wrong result.

[/ QUOTE ]

I'd just like to echo that an elaborate a bit. While computing exact results is very satisfying (and has a certain "gee whiz" appeal), in my case generating a fast exhaustive algorithm was a lot easier than generating a fast monte-carlo algorithm. Fortunately, it doesn't matter a lot in practice, at least not for me, because in almost all cases it is pretty easy to converge on a useful result.

There's another point I'd like to raise here - perhaps some other programmer types have some thoughts.

In developing propokertools, one of the biggest challenges has been generating random hands for monte carlo simulations such that the results correctly approach the same results from an exhaustive simulation. Now, I am fairly confident my algorithms work, and I have automated tests to "prove" it, but there are some situations (most of them academic and not useful in practice) where the random hand generation gets really bogged down. I don't want to get into too many technical details as that isn't my point (get to it, bachfan!). My point is, there may be a tradeoff to be made in certain situations between "correctness" and speed. In fact, you can think of monte-carlo as just such a tradeoff. There may well be some psycho-fast algorithm out there that is almost-but-not-quite-entirely-correct that, for purposes of mass generation (ie, for creating a bot using neural networks or whatever), might be the right way to go.

Just a thought, (babbling now)
bachfan

[Andrew Prock]

Pstove does slow from about 100,000 million games a sec to about 1 game every 4 seconds (9 players on broadway, final player on random all).

Interesting behaviour. I looked at the code, and it seems that my method for selecting monte carlo hands is fairly inefficient. For those who are interested, in the monte carlo code I draw cards from an infinite deck for all the hands and then discard scenarios where two hands hold duplicate cards. Of course, when all the hands are drawn from a narrow distribution, this happens far too often.

Like I said, it's not how fast you evaluate...

[img]/images/graemlins/smile.gif[/img]

Thanks for the info. I'll try and get a fix for that by the end of the year.

- Andrew

[bachfan]

[ QUOTE ]
I'v never really tried to make a fast general purpose evaluator. I wonder how fast I could make it?


[/ QUOTE ]

I must admit, the same thing occurred to me in the shower this morning. I even started coding up a new approach, but then I realized it was almost isomorphic to my existing one. Ooops.

I did have a fun idea for a new way of evaluating omaha hands, which i coded up, but it turned out to be just about as fast as my existing code in most cases.
Ooops again. I may come back to that at some point.

- bachfan

[bachfan]

[ QUOTE ]

Interesting behaviour. I looked at the code, and it seems that my method for selecting monte carlo hands is fairly inefficient. For those who are interested, in the monte carlo code I draw cards from an infinite deck for all the hands and then discard scenarios where two hands hold duplicate cards. Of course, when all the hands are drawn from a narrow distribution, this happens far too often.


[/ QUOTE ]

This is exactly the problem I was referring to a few posts back (sounds like we are taking the same approach here). I found some tricks for making things a bit faster in various cases, but I have yet to find a fast algorithm that generates the hands with the correct probability in these kinds of cases. I described the problem to my brother (a math professor at a major university), and the best he could come up with was "it sounds hard." [img]/images/graemlins/smile.gif[/img]

Cheers,
bachfan

[_D&L_]

Pretend we have two players that play only two hands:

AK or AA.

First player: AK - 16 combos, AA 6 combos, total 22
First Players chance of playing AK is 16/22
First Players chance of playing AA is 6/22

Now assign the second player:

If player 1 was assigned AK (p = 16/22), then
Player 2: (Baysian updating)
Plays AK with 9/12 probability
Plays AA with 3/12 probability
If player 1 was assigned AA (p = 6/22), then
Player 2: (Baysian updating)
Plays AK with 8/9 probability
Plays AA with 1/9 probability

Now what is Player 2's chance of playing AA
(16/22)*(3/12) + (6/22)*(1/9) = 7/33

Now the problem: Player 1 and Player 2 had the same distributions. But 7/33 != 6/22. The problem is that assigning PLAYER 1 his distribution frist, gives player 2 an unequal chance of getting AA. The player most likely to be dealt pocket pairs, is the one where all the aces are in deck when he gets a card on his distribution. Notice that Player 2's chance of being distributed AA is less than Player 1, regardless of whether Player 1 was dealt AK or AA. (6/22 >> 3/12 or 1/9)

A correct algorithm, would at the very least, have to give both players (with equal distributions) an equal chance of getting AA. Thus, dealing everyone random hands, and discarding until everyone gets a hand on their distribution is an unbiased, but albeit extremely slow method of getting the right answer.