Enumerating Every Cribbage Deal

Claude and AI tools now make it possible to analyse problems that come up while playing cards at lunch. In Cribbage, given six dealt cards and you must discard two, what is the optimum play? Years ago, we thought about this problem, but running through all of the possibilities would take significant processing time. Now, I can do it in under an hour.

The below text is AI generated, along with the code. Just thought I’d get that out of the way. All of this came with my discussion with Claude Opus 5.0, and I had it work out the details. Claude is saying this better than I could anyway.

Here is a question that is easy to ask and annoying to answer: you have been dealt six cards, you must throw two away, which two?

There are 20,358,520 six-card deals and fifteen ways to discard from each. I wanted to work out the answer for all of them, not sample it. The interesting parts were not the ones I expected.

The problem shrinks before it speeds up

My first honest estimate for a full sweep was 18.3 hours on one core. The fix was not faster code.

Permuting the four suits maps the deck onto itself. Hearts and spades are interchangeable labels, so relabelling them cannot change a score. If you only keep one representative from each equivalence class, 20,358,520 deals collapse to 962,988 — a 21.1x reduction, and by far the biggest win in the project. It shrinks the problem rather than speeding up the code, and no amount of micro-optimisation would have bought the same thing.

The second win was similar in spirit. Fifteens, pairs and runs depend only on ranks, and a 52-card deck can only produce 6,175 distinct five-card rank multisets. So precompute all of them. Only flush and nobs care about suits at all.

That leaves the question of how to look up a rank multiset quickly. The trick I liked: give each rank its own nibble in an integer. Adding five cards’ values together counts the ranks without ever carrying between nibbles, so the table key needs no sort, no tuple, and no sequence hash — just an addition and an array index. Inlining the suit rules at the same time gave 3.3x on CPython.

End to end, scoring a hand went from 4.6 µs to 0.15 µs, and the sweep that framed the whole project went from impossible to a 24-minute coffee break.

PyPy was a useful disappointment

I expected 5-15x from PyPy. On the original code I got 2.7x.

The reason is worth internalising. PyPy’s wins come from removing object overhead, and my slow function was dominated by allocating a sorted tuple and hashing it. That is an algorithm problem wearing an interpreter-overhead costume. Once I rewrote it into integer arithmetic, the JIT finally had something to work with — 52 ns per scoring against CPython’s 177 ns.

PyPy is also slower than CPython on my short paths: 0.19 ms versus 0.14 ms for a single deal’s hand EV, because the JIT never warms up. It only wins on the long loops. I now use CPython for everything except the sweeps.

Parallel scaling landed at 17.4x on 32 cores, not 32x, because the enumeration phase is serial and the parent process pickles and collects about a million results. Any estimate that just divides by core count will be optimistic by roughly that factor — one of mine was, which is how a “4.2 hour” projection turned out to be 7.1.

What the sweep actually says

Weighted across the whole space, playing the best discard:

The dealer keeps their crib; the pone’s is subtracted, which is where the gap comes from. But look at the hand column: the pone’s hand is worth more than the dealer’s. A dealer will trade hand value to feed their own crib. A pone never will, because the crib works against them. It is a small effect and it falls straight out of whose crib it is.

The same six cards, and the two roles keep different cards 60% of the time. Which side of the table you are sitting on flips the right answer more often than not.

For the curious: the best possible deal is four 5s plus an ace and a two. Keep the 5s, hand EV 22.78.

Modelling the opponent

The default assumption in most analysis is that the two cards your opponent throws into the crib are a uniform random pair. They are nothing of the sort. I sampled 20,000 hands per policy and scored them:

The starvation is stark. A real opponent puts a 5 in your crib 1.1% of the time against 16.8% for a random pair — a 15x suppression. People guard 5s, and they guard them hard.

The dealer row corrected an assumption I did not know I had. Dealers do not stuff their own crib with 5s. They throw one 12.4% of the time, which is less often than chance, because a 5 is also the best card to keep. What they actually feed the crib is pairs and touching cards.

So the uniform model is wrong. The useful question is whether being wrong matters, and the answer is a nice split: it matters a great deal for calibration and almost not at all for decisions. Your crib is worth about 0.6 points less than the uniform model claims and theirs about 0.4 more — both errors running against you, call it half a point per deal of systematic optimism. Yet the same discard gets chosen 92-96% of the time, because the bias is roughly uniform across all fifteen options and shifts the whole slate instead of reordering it.

Use the simple model to choose. Apply the correction only when you need a calibrated absolute number, like counting out an endgame.

Then the obvious recursion: that model describes an opponent who is sharp about their own cards, but which model do they use? So I regenerated the tables from players who best-respond to the previous generation. Averaged across all fifteen discards, crib EV moved by 0.003 points against the ~0.5 the first iteration gained — convergence rather than oscillation.

My notes recorded that as “modelling the opponent is worth half a point; modelling their model of you is worth nothing.” The second half was wrong, and I did not catch it until I rewrote the whole thing in another language. The real number is closer to 0.025 — still small, but ten times what I had written down. That story is below.

Being wrong in an interesting way

A partial sweep reported dealer 12.480 and pone 3.277 at the halfway mark. Both wrong, and wrong in a way I want to remember.

I was using imap_unordered, and I reasoned that since results arrive as they complete, half the results would be a fair half of the space. Results do arrive unordered — but tasks are dispatched in order. The first half completed was the first half of the canonical enumeration, which is ordered by card index and therefore skewed toward low-rank deals. Unordered output, ordered input. I had a biased sample and no reason to suspect it, because nothing about it looked like a sample at all.

The other real bug was in how I divided probability mass across throw classes. I was dividing by how many instances of a class were still available given my own cards, which keeps a fully blocked class at full weight — holding the cards a class needs ought to cost it mass, not preserve it. It never showed up as a crash or a bad-looking number. It showed up as a 0.11-point disagreement with an independent Monte Carlo simulation.

Which is the actual lesson. Every genuine bug in this project was caught by differential testing — running the new implementation against the slower one it replaced, or against a reference written a completely different way. Not by unit tests over hand-picked cases, though I have those too, including the 29-hand. By two independent implementations disagreeing about a number.

Then a friend asked to see it in C

Which turned out to be the most useful question anyone asked about this project.

The port is a straight translation — same algorithms, same comments explaining why they look like that, no dependencies beyond libc and pthreads. What it cost in effort it paid back in numbers. All of these are on the same 32-core machine:

Remember that the whole thing started as an 18.3-hour estimate on one core. The hand sweep now runs in the time it takes to read this sentence.

Two things are worth saying about that 2.6 ns. First, a note of mine had guessed 3–5 ns for a C core before one existed, which turned out to be about right — a rare thing for a performance estimate, which are usually wrong in the optimistic direction.

Second, and more to the point: against PyPy’s 52 ns, rewriting in C bought about 20x on the scoring. Noticing that hearts and spades are interchangeable labels bought 21x on the size of the problem itself, in roughly four lines of code. An entire reimplementation in another language was worth about what one observation about symmetry was worth.

But the port earned its keep somewhere else entirely.

Every result had to match the Python exactly — random hands, random deals, the full discard ranking, crib EV under all three opponent models. It does. The C sweep also independently rediscovers 962,988 canonical deals summing to 20,358,520, which is the check that its canonicalisation agrees with the original.

And then the policy sweep came out 0.026 away from the pone figure in my own analysis.

Not a rounding difference. I chased it, and the answer was that my comparison tool averaged the iteration-1-to-2 repricing across all fifteen discards. But you only ever play one of them, and the one you play moves about ten times further, because which discard you choose is correlated with exactly the throw classes the new iteration moved. As pone you pick the throw that starves the dealer’s crib — which lands you precisely in the part of the table that shifted.

Both numbers were correct. They answer different questions, and the one I had written down was the one that makes the effect look ignorable. A 400-deal sample and a 962,988-deal enumeration now agree on the corrected figure to within a thousandth.

Which is the same lesson as before, arriving by a different road. I did not find that by re-reading my analysis. I found it because a second implementation disagreed with the first about a number.

Left on the table

Everything above is hand and crib EV. The pegging — the actual play of the hand — is untouched, and that is where the rest of the game lives.

The Python has no dependencies and the C has none worth the name; both are paused in a working, fully tested state. The code, the analysis and the test suites are at github.com/orner/cribbage-analysis. If you want to argue with any of these numbers, I would enjoy that.