I don't know how to say this without coming across as a
bit abrupt, so I'll just blurt it out. You don't know what you
are talking about. You've never actually written a program
to evaluate poker hands, have you? Perhaps you missed
the part where he asked "... from those that have done this..".
There are plenty of shortcuts, and the right shortcuts can
cut the CPU time tremendously. By "tremendously" I mean
several orders of magnitude, as in "thousands of times
faster". Perhaps millions of times faster, depending on
the extent to which the original method was "brute force."
Most of the shortcuts boil down to finding ways to exploit
symmetry. One kind of symmetry is the order of the drawn
cards. We don't really care what order the cards are
removed from the deck, so when drawing three cards the
order "Ks 9d 2c" is no different than "2c 9d Ks". The worst
possible form of "brute force" would look at all possible
orderings, and for the initial draw this would increase the
CPU time by a factor of 120. For the case of drawing
three cards from the remaining 47, ignoring the order
saves a factor of six. This reduces the total number of
cases from (47*46*45=97,290) to 16,215.
Let's step back and look at the brute force approach.
The brute force method amounts to "list each possible
draw, determine the final hands from the draw, and
tally the results." Let's also change the problem
slightly. Suppose that instead of evaluating a single
hand, you wanted to write a program to find the best
possible playing strategy. Then the brute force
approach breaks down like this:
1) List each of the 2,598,960 starting hands.
2) For each starting hand, there are 32 ways to
play the hand. This breaks down as one way
to stand pat, 5 ways to draw one card, 10 ways
to draw two cards, 10 ways to draw three cards,
5 ways to draw four cards, and one way to draw
five cards. So, for each starting hand, we'll make
32 lists of "results of the draw.
3) The number of possibilities for each draw depends
on the number of cards drawn from the 47 that were
unused in the initial draw, as follows:
draw one: 47 ways
draw two: (47*46/2)= 1081 ways
draw three: (47*46*45/(3*2)) = 16,215 ways
draw four: (47*46*45*44/(4*3*2)) = 178,365 ways
draw five: (47*46*45*44*43/(5*4*3*2)) = 1,533,939 ways
Combining the information from 2) and 3) shows that for
any one starting hand, brute force would require us to
evaluate a total of 2,589,231 final hands. So, to find an
optimal strategy, the brute force method would require
the program to evaluate 2,598,960 * 2,589,231 hands,
or 6,729,307,799,760 hands. Even with today's blazing
fast computeres, looking at 6.7 trillion hands takes too
long. I wrote a small C program to estimate CPU time
for simply doing a table lookup on this many items, and
based on that program, it would take approximately 4 days
to perform this many table lookups, when running on a
computer that is 3X as fast as my old 650MHz machine.
I know of several different programs that compute overall
EV for VP games, and none of them take anywhere near
this long. My own program does it in about 1 second,
which is about 3 million times faster than using brute force.
I believe most other programs are slower than this, but still
improve tremendously over the brute force approach.
Brute force is analogous to listing all possible outcomes
and counting them one by one. The trick to avoiding
brute force is to find ways to counts whole groups of
outcomes together, or more generally, to find ways to
"compute" the outcome in a way that is more direct than
counting. I'll try to outline a general approach to doing
this, without filling in the fine details.
Suppose we are dealt Qs Js 8d 4c 2h. We decide to
keep the Qs Js and want to compute the EV for drawing
three cards. Drawing three cards means there are
16,215 possible final hands. Computing the EV involves
finding the number of ways to draw a royal, a str-flush,
4-kind, etc. This breaks the problem down into several
smaller problems -- finding ways_to_draw(X) where X
is one of the final hands in the pay table.
You don't have to list all 16,215 possible draws and
look at each one, saying "this one is a flush, this one
is two pair, this one is garbage". As an example, let's
look at computing the number of ways to draw a high
pair when holding QJ and discarding three small cards.
To end up with a high pair, you can draw a card that
matches your Q or J, or you can draw a pair of aces
or a pair of kings. To correctly count the "high pair"
hands, we also need to be careful to avoid drawing
a higher hand. Here is a breakdown of the number
of ways to draw a high pair:
1) To draw a "new" pair (aces or kings) there are
two ways to select the rank of the new pair. Once
the rank is selected, there are 6 ways to assign
two different suits to the paired cards. To avoid
another pair (or 3-kind) we then remove the Q's,
J's, and the "unused" cards that match our pair.
This leaves 37 cards for drawing the final card.
So, there are 12*37=444 ways to draw a "new"
pair.
2) To end up with a pair of Q's or J's, there are six
ways to draw a match, then we must draw two
other cards of different ranks. Again, we remove
the Q's and J's from the deck before drawing the
"unmatched" cards, but this time there will be 41
cards left. For this case, drawing two unmatched
cards is complicated because we have to keep
track of the discards. The 41 cards available are
3 each of ranks (8,4,2) for the discards, and 4 each
for the remaining 8 "untouched" ranks. There are
three distinct ways to draw two unmatched cards.
A) Both cards are "4 way" draws. There are
comb(8,2)=28 distinct ways to assign the
ranks, and 4 ways to assign suit to each
of the distinct ranks, for a total of 448 ways.
B) Both cards are "3 way" draws. There are
comb(3,2)=3 ways to assign the ranks,
and 3 ways to assign suit to each of
the distinct ranks, for a total of 81 ways.
C) One card is a "4 way" draw and one card
is a "3 way" draw. There are 3*8=24 ways
to assign the ranks, and 3*4=12 ways to
assign suits, for a total of 288 ways.
Overall, this case has 817 ways to pair by catching
a Q or J.
In total, there are 1261 ways to end up with a high pair
for this draw. Other "grouped" hands like 3-kind,
full house are computed in similar ways.
For suited draws, there are 11 remaining spades
to draw from, so there are comb(11,3)=165 ways
to draw a final hand that is suited. Of these, one
is the royal, two are straight-flushes, and the other
162 are ordinary flushes.
There are 4*4*4=64 ways to draw an ace-high
straight, but we have to exclude the royal, leaving
63 ways to draw an ace-high straight. Similarly,
there are 63 ways to draw a king-high straight.
However, there are only (4*4*3 - 1)=47 ways to
draw a queen-high straight. In all, there are
173 ways to draw a straight.
I wouldn't really call this a shortcut. It is simply
doing a direct computation rather than mechanically
dealing out each possible outcome.
···
On Friday 09 May 2003 12:58 pm, mkl54321 wrote:
--- In vpFREE@yahoogroups.com, "Dick Kalagher" <dick@k...> wrote:
> I am playing around with Java programming and thought I would
write a little
> program to calculate EV given a starting hand. I know how to do
the
> calculation, but I and wondering if there are any shortcuts other
than brute
> force (i.e., going through every possible combination of 0-5 cards
drawn)?
> For example, with a pat hand you could skip most calculations.
Just
> wondering from those that have done this what they found to be the
most
> satisfactory algorithm.
Unfortunately, there's no real shortcut.
