Cribbage Discard Pro: Methodology
Here's the basic algorithm:
- Select two cards to discard from the user's hand.
- Select a turn card from the remaining deck.
- Select two cards from the remaining deck to act as the opponent's discard.
- Score the hand and the crib for this combination.
- If it's the user's crib, record the sum of the hand and the crib. If it's not, record the difference.
- If this combination produces a maximum or minimum hand score, crib score, or sum/difference of the two, record this value. (If it's a maximum hand or hand-crib sum/difference, also record the turn card and opponent's discards.)
- Repeat for all possible opponent discards, for all possible turn cards, and for all possible user discards.
- If it's the user's crib, suggest they discard the combination with the highest average value for the sum of the hand and the crib. If it's not, suggest the one with the highest average value for the difference between the hand and the crib.
Because it's more or less likely that your opponent will discard certain combinations (e.g. a pair of fives if it's your crib), a weighting system is used when calculating the average crib score and the average hand-plus-crib/hand-minus-crib score. To calculate these weights, the algorithm analyzed large batches of random six-card hands to develop static weighting tables of discard probabilities, iterating this process until the values stabilized. (The initial tables were based on the discard tables kindly provided by Michael Schell of cribbageforum.com.)
The scores are then re-weighted to reflect the probability of the opponent discarding two suited cards. Due to the statistical improbability of a flush in the crib, the average crib score increases by only 0.04 points with suited discards, so this second weighting factor is almost insignificant.
Since these weights are applied to the opponent's discards, the algorithm inherently assumes that the opponent is an expert-level cribbage player.
The algorithm does not at all consider pegging capabilities when selecting the best discards. For advice on discarding with pegging in mind, see for example DeLynn Colvert's "magic eleven" tip.
Much like with the Battleship Calculator, the biggest challenge in this project lay in getting the processing down to a reasonable amount of time.
Every time it runs, the algorithm has to score 683,790 individual five-card hands – checking multiple combinations of the cards for runs, pairs, fifteens, flushes, and the nibs. But I was surprised to find that if you ignore suits, there are only 6,175 combinations of five cards! So before working on the user's hand, the program actually scores every possible hand and saves the results to a list*, which can be quickly referenced later on. (It still checks for flushes and His Nibs, but that's a fairly quick process.)
Aside from other minor coding stuff, there was one other trick I found while working on the algorithm. (It's a bit technical, so feel free to stop here if you're not into programming.) There are multiple instances where it needs to run through every combination of two cards from the deck, which takes a while. In those cases, to save time and avoid double-counting, the deck is numbered from 1 to 52; the first card's variable (C1) runs from 1 to 51, and then C2 runs from C1+1 to 52.
* Specifically, it saves the scores to an array with prime-based hash indices. Each card's numerical value is converted into its respective prime number (1 = 1, ... 4 = 5, 5 = 7, etc); multiplying all five primes together gives a unique key that can be used for fast storage and retrieval.