For each unsuited triple of hands (e.g. T7 K2 K3) work out the equity of each hand, disregarding flushes. (But take into account the fact that the pack only has four cards of each rank, so that with the example of T7 K2 K3, there are only two possible Kings left that the board can use).
For each of these triples, work out all the ways of "colouring" them with suits and work out the most difference flushes could make. (For the purposes of this description, "flush" includes straight flush.) Hopefully there will be many triples with one hand so far behind that the added equity of a flush couldn't enable it to catch up with the other hands.
Then for each of the resulting suited triples, do a full evaluation taking flushes into account.
For the original versions of the programs, the times taken for each of these passes were (1) a few minutes (2) a few seconds and (3) 30 hours. (Using a 600MHz pentium clone.)
In fact the answer of AcKc AdKd Td4c was found much more quickly than that, because it was guessed that the flush estimates in the second pass would be poor in most cases (in other words that a flush is usually going to help a hand by less than the "safe" amount estimated by the second pass). By artificially limiting the output the second pass produced to the most likely 10% of its full amount, it was expected that a good answer (as opposed to the best answer) could be found relatively quickly. Since the best answer happens to occur in the best 10% of the second pass output, it was found (and submitted) in about 3 hours. Subsequently the 30 hour run proved it to be the best (subject of course to mistakes!).
After all that, I tinkered with the programs a bit to make them faster. The second pass now produces less than half the output it did, and the third pass is about 5 times faster, so now the complete run (i.e., the run which proves the answer to be best) could be done in about 3 hours.
The three passes in more detail:
There are (14 choose 2)=91 unsuited hands (AA, AK, AQ, ..., 22).
Therefore there are (93 choose 3)=129766 unordered triples of unsuited
hands (AA AA AA, AA AA AK, AA AA AQ, ..., 22 22 22). Of course a few of
these are impossible (those involving 5 or 6 of a kind), but let's forget
about that.
There are (13+4 choose 5)=6188 unsuited boards (22222, 22223, ...,
AAAAA) (of which 13 are impossible, but let's forget about that too).
For each combination 6188x129766=803,000,000 approx, we can work out the
payoff, disregarding flushes, to each member of the triple. This gets
multiplied by the appropriate combinatorial factor to account for ways of
making the board suited. This is supposed to calculate the exact payoff
using a full suited pack of cards for the game of poker-with-no-flushes.
Example:
Board = 34469, Hands = A3 K2 96. How many ways to suit the board?
After A3, K2, 96 have been removed from the pack, there are 3 threes, 4
fours, 3 sixes and 3 nines left. So
Answer = (3 choose 1)x(4 choose 2)x(3 choose 1)x(3 choose 1) = 162
Note that for each board, you only need to do a "poker evaluation" (i.e., determine the rank of the best had makeable from 7 cards) for each of the 91 unsuited hands. This time is negligible.
So total time taken = 6188x(91x(time for poker evaluation)+129766x(time to calculate a few binomial coefficients and sort three numbers))
After the first pass, you have a file ("out0") with 129766
entries. Here are some lines towards the start of the file. (It has
been sorted by best-worst equity. The equities appear as numbers
in out0, but have been converted to percentages here for clarity.)
66 79 8Q 6.2733 32.8611 30.4328 36.7061 22 56 4T 6.2776 29.8549 36.1325 34.0126 67 3Q 6Q 6.2783 32.9180 30.4018 36.6801 45 8Q 2K 6.2790 29.6058 35.8848 34.5093 4A QA QA 6.2810 29.1460 35.4270 35.4270
and here are some lines further down:
36 TK 7A 15.4023 23.2124 38.6147 38.1729 34 79 7Q 15.4029 29.5190 27.5390 42.9419 34 68 59 15.4030 23.6147 37.3677 39.0177 5T 4Q 7K 15.4030 27.9308 28.7354 43.3338 56 9Q JK 15.4047 27.3757 29.8439 42.7804
The idea is now to add suits to each triple in all ways which could possibly cause the equities to change by enough.
Example 1:
67 3Q 6Q 6.2783 32.9180 30.4018 36.6801The equity of 3Q is so low that if it were unsuited it could never catch up to 1/3. Therefore 3Q has to be made suited. 67 is close enough that it can be made unsuited or suited. Taking into account suit symmetries, the complete list of possibilities is:
6h7c 3dQd 6cQc 6d7d 3dQd 6cQc 6h7d 3dQd 6cQc 6d7h 3dQd 6cQc 6h7h 3dQd 6cQc 6s7h 3dQd 6cQc 6c7c 3dQd 6dQc 6h7c 3dQd 6dQc 6h7d 3dQd 6dQc 6c7h 3dQd 6dQc 6h7h 3dQd 6dQc 6s7h 3dQd 6dQc 6c7c 3hQh 6dQc 6s7c 3hQh 6dQc 6c7d 3hQh 6dQc 6h7d 3hQh 6dQc 6s7d 3hQh 6dQc 6h7h 3hQh 6dQc 6s7h 3hQh 6dQc 6c7s 3hQh 6dQc 6h7s 3hQh 6dQc 6s7s 3hQh 6dQc
Example 2:
34 68 59 15.4030 23.6147 37.3677 39.0177In this case, 34 is so far behind that it can never catch up even if suited. Therefore no suited triples are produced from this entry.
The most equity a hand can catch up is probability it makes a flush.
| This is | <= 2.572% (if unsuited) |
| <= 8.039% (if suited) |
If you use these numbers (+a tiny amount to allow for the fact that we can't actually get a perfect 1/3,1/3,1/3 answer), then you find you have about 830000 suited triples to check. If you refine this slightly by counting the number of dead flush cards and taking into account the fact that, e.g., the 4c is dominated for flushes if the three hands are Td4c 9h6c 7s6s, then this number comes down to about 330000.
The preliminary run, which came up with the answer Td4c AcKc AdKd, differed effectively by choosing smaller numbers in place of 2.572% and 8.039%. It ended up with 86000 suited triples to check.
Now we loop over suited boards and triples from the above list. Actually this was done by first looping over unsuited boards, then looping over triples, then looping over ways to add suits to the board.