VP analysis is a really fun program, especially if you enjoy the
challenge of getting the code to run quickly. As a point of
reference, my VP program does a complete analysis of a
9/6 JoB game in 0.44 seconds on a 650 MHz AMD Duron
processor. Of course, this isn't a fair comparison, because
I've spent hundreds of hours working out efficient algorithms,
and you've just started. Given the speed difference, there
should be some fairly easy changes you could make to
reduce the run time to something like a few minutes.
8 seconds is a long time for analyzing a single hand, so
I suspect you could get a huge reduction in run time by
taking a different approach. I haven't seen your source
code (you said it was attached, but it didn't show up here),
but I'll throw out a couple ideas.
I have separate routines that compute the number of ways
to draw each of the final hands, given a particular set
of held cards and the set of cards that remain in the deck.
One routine computes the number of ways to draw a royal,
another computes the number of ways to draw a full house,
etc. Once you know these numbers, you can divide by
the total number of hands that can be drawn to get the
probabilities for each final hand. The trick here is to compute
the number of ways to draw each hand witout resorting to
dealing out every possibility and counting the results. For
example, if you are holding 3 spades and discarding two
non-spades, then the number of ways to draw a flush is
C(10,2) (the combination of 10 things taken two at a time)
= 10*9/2 = 45. If there are str-flush or royal draws possible
they are subtracted from this total. The total number of ways
to draw two cards is C(47,2) = 46*46/2 = 1081, so the
probability of drawing a flush is 45/1081. These numbers
can be computed much faster than you can deal out all
1081 hands and count the results.
Then I divide the payoffs into three classes. The "grouped"
payoffs are one pair, two pair, 3/kind, full house and 4/kind.
If your held cards already have a group, then it becomes
impossible to draw straights or flushes, so you can skip
the computations of straight, flush, str-flush and royal.
The second class of hands combines straights, str-flush
and royal -- any kind of hand that permits a straight to
be drawn. The third class is flushes where no straight
is possible. If the held cards do not permit any straights,
then you can skip the computation of straights, str-flush
and royals since none of these hands are possible.
The 134,459 starting hands can be reduced to a much
smaller set of starting hands by considering all of the
different symmetries in ranks and suits. My program
reduces this number to something like 8,000 cases,
but I believe it is possible to reduce the number of
cases even more.
Another way to reduce the run time is to look for
equivalent draws. If your initial hand is 2h 2c 3d
6s 8c and you want to compute every case, then
holding (8c 6s 3d 2h) is equivalent to holding
(8c 6s 3d 2c) -- it doesn't matter which two you
hold and which you discard, the numbers come
out the same. Many initial hands can be reduced
to less than 32 cases.
I don't pre-compute anything in my program, each
analysis starts from scratch and computes all the
numbers necessary for the analysis. However, the
first step I take is to compute tables that give the
part of the EV that comes from each of the three
classes of hands that I talked about earlier (grouped
hands, str8-ish hands, and flushes). Then, for
each set of held cards, I look up the value from
these three perspectives and add the three values
to get the overall EV for the hand. The reason
my program is so fast is that splitting up the problem
into these three cases makes each of the three tables
quite small, and the values in the tables are computed
only once at the beginning of the run.
···
On Sunday 14 November 2004 01:54 am, Neil Aggarwal wrote:
My current code takes about 8 seconds to calculate a
result for each of the starting hands on the modest
P4 I am running it on.
Multiplying this by the 134,459 starting hands to
analyze, it will take about two weeks for this
code to run through all of the hands. That is
not bad, but its not great. I can split the
processing across multiple machines to reduce the
time.