Number of hold 'em simulations required (Was: eternity...)
Steve Brecher
"Barbara Yoon" <by...@erols.com> wrote:
> Where do Steve Brecher and I diverge on our computer
> running time estimates for Dick Taylor's proposed enumeration?
> Brecher estimates one "fast" computer doing it in 115 years;
> I estimate 6 billion computers taking more than 10 million years
> based on the following:
>
> A> Combinations of 10 starting hands and 5 upcards:
>
> 52!
> -------------------------- = 1.66 x 10^28
> 2^10 x 10! x 5! x 27!
>
> B> Taylor's program running on 200mHz Pentium
> computer at 25 million combinations/hour.
(Whine: Yet another thread on this angels-on-pinhead subject. Ain'tcha
got a follow-up feature in that newsreader over there? And informative
subject fields are a courtesy to newsgroup readers.)
My original post on this subject (another thread) was explicitly an
*underestimate* intended to show merely that the enumeration project is
not feasible. I will now accommodate Barbara's fervency for an exact
number of evaluations required.
The question is: how many (simulated) games of hold 'em are required to
determine the average pot equity of pocket aces against nine opponents
when all hands see the river. A subsidiary question is how long it would
take to simulate that number of games on a fast personal computer.
Since one hand is specified -- the pocket aces -- there are 50 cards
remaining in the deck.
Symbology:
* -- multiplication
^ -- exponentiation
! -- factorial
XcY -- the number of possible combinations of Y things drawn/dealt from X
things, which is equal to X!/((X-Y)! * Y!)
The number of different deals to 9 players from a 50-card deck is
50c18 * 18!/(2 * 9!)
i.e, the number of combinations of 18 cards dealt from 50, times the
number of ways they can be dealt to nine players. The cards can be
ordered 18! ways; but neither the order of the cards within each hole-card
pair nor the order in which the hole-card pairs are dealt among the
opponents is significant.
The number of different 5-card boards from a (50-18)=32 card deck is
32c5
The number of required games is the product of the two foregoing, which is
equal to
50! * 18! * 32!
-----------------------------
32! * 18! * 2 * 9! * 27! * 5!
or
50!
-----------------
2 * 9! * 27! * 5!
or
3.2071 * (10^28).
Now we get to "how fast can a computer do a game simulation" and thus
leave the realm of exactitude, since we have no measurements for "the
fastest available personal computer," whatever that is, using the fastest
possible code, whatever that is, working on this exact problem.
My 160MHz PowerPC, running a program of my own, computes the results of
all possible 1,712,304 boards for a heads-up game with specified hole
cards in 2.9 sec, which is 2.1 billion games per hour. Our problem has
five times as many hands (players) to be evaluated for each game; but
since there is an overhead constant for each game, let's say it would take
only four times as long to compute each game. And let's say that
bleeding-edge personal computers are about twice as fast as mine. Hence
it might take around 4/2 or twice as long per game on such a computer,
which would be a rate of around 1 billion hands/hour.
3.2071 * (10^28) games at 1 billion per hour takes 3.2071 * (10^19) hours,
or 1.3363 * (10^18) days, or 3.6586 * (10^15) years. Yes, a long time.
--
st...@brecher.reno.nv.us (Steve Brecher)
Tim Dierks
In article <steve-24089...@brecher.reno.nv.us>,
st...@brecher.reno.nv.us (Steve Brecher) wrote:
>The number of different deals to 9 players from a 50-card deck is
> 50c18 * 18!/(2 * 9!)
>i.e, the number of combinations of 18 cards dealt from 50, times the
>number of ways they can be dealt to nine players. The cards can be
>ordered 18! ways; but neither the order of the cards within each hole-card
>pair nor the order in which the hole-card pairs are dealt among the
>opponents is significant.
I believe this should be 50c18 * 18!/(2^9 * 9!) because there are 2^9
different ways to internally order 9 groups of 2 cards. This means your
final number is 2^8 too large; i.e., it doesn't change it significantly.
What about approaching this problem in another way? Enumerate all the
possible ways in which AA can win (or lose) a hand:
opponent makes flush
straight
trips (pair on board)
set (pair in hand, one on board)
etc.
And for each possible situation, calculate how many boards make that
situation possible, and for each board, how many opponent's hands make that
result possible. You should be able to do a precise calculation from that.
Note that the categories above aren't precise enough; they should be:
opponent wins with flush (3 on board)
opponent makes flush (3 on board), but loses to AA with quads
opponent makes flush (3 on board), but loses to AA with A's full of n's
opponent makes flush (3 on board), but loses to AA with n's full of A's
opponent wins with flush (4 on board)
opponent makes flush (4 on board), but loses to AA with quads
opponent makes flush (4 on board), but loses to AA with full house
opponent makes flush (4 on board), but loses to AA with better flush
opponent makes flush (3 on board), but loses to AA with A's full of n's
etc.
Even these aren't precise enough to calculate. For example, the 3 on board
flushes need to be subdivided into cases where the flush suit matches one
of the aces and where it doesn't in order to be calcuable.
Determining all of these categories is hard
Calculating the exact number of boards for each category is hard
Calculating the number of matching opponent hands for each board is hard
Extending the calculation on the above to deal with more than 2 players is hard
But none of it sounds infeasible.
- Tim
--
Tim Dierks - Software Haruspex - t...@dierks.org
Does the Internet have Buddha nature?
jac...@xmission.com
t...@dierks.org (Tim Dierks) writes:
> In article <steve-24089...@brecher.reno.nv.us>,
> st...@brecher.reno.nv.us (Steve Brecher) wrote:
> >The number of different deals to 9 players from a 50-card deck is
> > 50c18 * 18!/(2 * 9!)
> >i.e, the number of combinations of 18 cards dealt from 50, times the
> >number of ways they can be dealt to nine players. The cards can be
> >ordered 18! ways; but neither the order of the cards within each hole-card
> >pair nor the order in which the hole-card pairs are dealt among the
> >opponents is significant.
>
> I believe this should be 50c18 * 18!/(2^9 * 9!) because there are 2^9
> different ways to internally order 9 groups of 2 cards. This means your
> final number is 2^8 too large; i.e., it doesn't change it significantly.
Consideration of other symmetry conditions can reduce the number even
more. For example, 7-3 offsuit (ahem) can occur 12 different ways,
but they are essentially equivalent. The suit patterns need to account
for suits of the aces and the cards in/on the board, but the concept
still applies.
Excellent. This is similar to the approach I use in my VP program,
which reduces a complete analysis from several hours to mere seconds.
It would require a pretty sophisticated algorithm, but I believe it
would make the problem feasible.
--
Steve Jacobs (jac...@xmission.com) \ IDSP
"Expectation isn't everything..." \
Calks
[Summary:
- Win rate for Pocket Aces vs 9 opponents: 30.8% or 31.1%?
- Formula to calculate: lots of fancy words like combinatorics, factorial
and exponentiation
- Time to calculate: 115 to 16 bazillion gazillion years
- Angles dancing on pinheads]
Reall value to a poker player: zero, nada, zilch, bubkus!
Practical advice for a poker player: Aces?!! Jam it!!!!
I'm only trying to tweak, but not annoy, the computer wonks, but if
this thread goes on much longer I'm going to miss the wonderful words
or Mr. Reiman.
Best, Jeff Calkins
PS Please don't flame me, I'm primarily a stud player
Jeff Calkins
JSwinson
I agree. Who is Mr.Reiman?