The game of cribbage https://en.wikipedia.org/wiki/Cribbage is a two-player card game played over a series of deal with the goal to reach 121 points.
The game's elements are:
- the discard. There are three hands, one for each player of 4 cards selected from six. The discards go face down to a hand which belongs to the dealer (the crib). On average, because non-dealer is optimising one hand, his hand scores slightly more points, say 8 points vs 7.8 for dealer, while the crib scores around 4 points, because one player aims to toss trash (while not damaging his own hand), while the other aims to toss good cards (while likewise maximising his own hand)
- pegging. Here the dealer expects to peg on average around 4 points (he plays second, so has an advantage in responding to non-dealer's lead), and non-dealer around 2 points
- the cut. This is a fifth card which belongs to all three hands. If the cut is a Jack, dealer scores 2 points, for free.
- the order of play. This is:
- the cut. Averages 2/13 = 0.15 points for dealer (if a Jack is cut)
- pegs (played one card at a time, scoring for each). Dealer will peg at least 1 point, and non-dealer will peg 0 or more. Averages 4 and 2 points.
- non-dealer shows his hand. Averages 8 points
- dealer shows his hand. Averages 8 points.
- dealer shows his crib. Average 4 points.
As should be obvious the hands are generally the main source of points, so players will tend to optimise their hands to maximise points there. This problem is OUTSIDE OF THE SCOPE of this post, since there are exhaustive analyses that have solved this problem reasonably well. E.g., https://cliambrown.com/cribbage/
There are 6C4 = 15 discards possible for each hand, and often the correct play will be unambiguous. For example, if we had the hand A49QKK with mixed suits (no more than 3 of any 1 suit) and we are non-dealer, then the correct hold is obvious - A4KK (this hand has two ways to make 15 A4K and A4K for 2 points each, and a pair for 2 points, plus it improve swith cuts of A, 4, 5, T, J, Q K)
After we've held the card we must then 'play the pegging game'. The scope of this post/question is therefore limited to how to play a given 4-card hand that we have already selected using an exhaustive combinatorial analysis, hence I'm assuming that the bots inputs are a given 4 card hand, as well as the three dead cards (discard and cut), and the replies to each play from our opponent.
The scoring for pegging is:
- each pair scores 2 for the player playing the second card, 6 for 3 of a kind, 12 for 4 of a kind
- each time the count reaches 15, the player playing the card scores 2
- each time the count reaches 31, the player reaching scores 2 (it is not permitted to exceed 31, and if you have no card that will keep the count at/below 31, you must call 'go', and if both players call 'go', the last player scores 1 point). After this the cards are turned over, and play continues from zero
- each time a run of 3 or more cards is visible (between the cards played by both players), then you score 3, 4, 5, 6, 7, or even 8 points according to the length of the run.
Follows discussion about pegging strategy, which I have blockquoted for those who find this tl;dr
The optimum play for a given hand is not necessarily clear-cut. For example, with the hand A4KK, then we could lead:
- K - on the basis that if dealer replies with another K (for 2 points), then we reply with the third K (for 6 points), and then most likely dealer does not have an Ace, so we score 2 points for the 31 (K = 10, A = 1), AND dealer must lead the next round of pegging, which is a considerable disadvantage.
- not K - because there's a bias to holding 5s, so if dealer was dealt a 5, then he can reply with the 5 scoring 2 points for the 15, to which we have no scoring reply. In addition, non-dealer generally has a bias to leading from a pair, so if we lead the K, then in general a smart dealer says 'he is likely to have a pair of Ks'. So even if dealer has a K, he may decline to peg it, especially if he doesn't hold the A himself
- 4 - this is the most popular lead in cribbage because 15 cannot be scored on it. As indicated above there are 16 10 cards (TJQK), as opposed to 4 of every other denomination, so it's more likely to receive a ten back than any other denomination, and we hold an Ace, so we would score 2 points following a ten card reply
- A - this has the same advantage that dealer cannot reach 15, and again if we get a ten card back we can score 15-2.
- It might be that the A is better to lead because the 4 is such a popular lead that dealer is more likely to pair it (risking that we hold the third 4 for 6 points), in which case we have no good reply. If we lead the A, then the dealer is [probably!] less likely to reply with an A (which doesn't help us).
- We might prefer to lead the 4 if we think that the A is more likely to allow us to play the last card before 31, in which case dealer is forced to lead first next round, which is a disadvantage.
During pegging we have considerable information:
- which cards we hold and discarded. For example, clearly if we hold 3 4s, and the 4th was cut, then there is no chance that we get one played against us.
- which cards have been played and therefore which cards are likely to remain, based on the hand selection process. For example, if a 4 is led then x% of the time that will be from A4 TJQK, y% it will be from 4456, etc. As more cards are played, then this becomes more obvious. For example, if we've seen the 3 cards 5TK, then it's VERY likely that the 4th card is another TJQK card, and somewhat likely that it's a 5. It could be ANY card because maybe of the six cards the player was dealt he ended up with an unconnected card. But we can say that the chance of this is low.
In terms of exactly what cards are held, then if we analysed millions of games, we could calculate in general knowing one, two or three cards what the remaining cards could be.
Although there are in theory 270,725 4 card hands, in pegging terms (ignoring suits), there are only 1820 distinct hands (https://docs.google.com/spreadsheets/d/1fxkLBkWC2LA6J06zhku21jcG2ATHqE1RNHlPSDcc4fQ/edit#gid=834958733)
For any given hand, if we for example held the cards 358TTT and we were non-dealer, then we would choose to hold 5TTT and toss 38. We would then lead the T. In this spot, clearly of the 1820 possible hands, then combinations such as TT xy are no longer possible.
As another example if we were dealt A778JK, then we'd toss the JK. Here we'd likely lead the 7.
Before we play the 7 it's relatively simple to calculate the odds that dealer was dealt two 7s. Since he had six cards, that is 2/461/456C2, which is 1.45%. The chance that he chose to hold those two 7s is a different number, and we could theoretically calculate it by figuring out for each of the 45C6 (but simplifiable!) combinations, which hold he would make. However it won't be too far from this number of 1.45%.
HOWEVER, once we have played a 7 and dealer replies with a second 7, then this number is now very far away from accurate. Firstly because it's now a simple conditional probability where one condition is already satisfied, so the chance of any of 5 unknown cards being a specific card (e.g., the 7 of diamonds) is now almost 1/9. Of course dealer has 3 cards, not 5, so again the chances of this are not that number, but not too far off, because of those hands where dealer was dealt 77, and he holds one seven, then he is seldom going to toss the other one.
In terms of our possible plays, we have at the count of 14:
- play the Ace and score 2 points for the count of 15.
- play the 7 and bring the count to 21, which is 6 points. However, dealer is fairly likely to have a TJQK (bringing the count to 31, scoring 2 points, and making us lead the next deal). In addition, given that dealer has a similar analysis process to us, in hands where he holds say 78 then he probably replies to the 7 lead with the 8, as it doesn't allow us to score 6 points. So given that dealer has replied with 7, this increases the chance that he holds the fourth 7 as well. It's hard to say what this chance is, but for example there is an x% chance of 31-2, a y% chance of 28-12, and a z% chance of something else. Or we could consider the chance of any given card.
- probably not play the 8, because at 778 the count is 22, and dealer has many scoring replies: 6 is a run (3 points), 9 is a run AND 31 (5 points), and 8 is a pair (2 points)
In general it can be seen that there are:
- up to 1820 unique 4-card hands
- up to 455 3-card hands
- up to 91 2-card hands
- up to 13 1-card hands
Clearly we could weight each hand by the chance it has to be held, and this would work well BEFORE a card has been played.
However after 1 or more cards has been played this approach is going to be hopelessly naive. For example, let's say we led the 4. If dealer is holding a hand like 5JJK then he's definitely not going to reply with the 5, because we can play a 3 for 3 points (run), or a 6 for 5 points (run and count of 15).
Further, against non beginner-level players, it will be obvious that we often hold hands like A4 JK or 23 KK, etc. So if we lead the 3, and dealer replies with a ten card (TJQK), then it's likely he's NOT holding cards such as 789, which a non-beginner player would likely prefer to reply with here. It's possible of course that dealer has the same cards. For example, if we hold 23JK, dealer might be holding 23QQ. In this case, the Q reply might be preferred by dealer, because if the play goes 3-Q-2, then dealer can pair our 2, and perhaps dealer doesn't like to pair our 3 lead, for fear we have a third 3, while he lacks the fourth.
In addition, while for pegging terms suits don't matter at all, suit information is during important, so long as the player has a flush. For example if we were dealt 2468h Jd Js, we'd hold the 2468 of hearts, because that's a flush worth 4 points. So if during we play, we've seen 468h from our opponent, then the probability distribution of possible hands is going to contain a good weight for every heart card. Whereas if we've seen 4h 6d 8h, then we know after two cards that he does NOT have a flush, so this weights likely hands towards hand such as 4568, 4678 and so on, and it's unlikely that the remaining card is, say, a K.
In general the goal of a pegging bot could be seen as:
- score most points or
- concede fewest points or
- maximise net points
Nuance: In early game it's likely max net points is the best approach. But if we are at a score like 117-117 (121 is the winning mark) as dealer, then it's (let's say) 80% likely that non-dealer has 4 points in his hand, which means he wins if we do not peg 4 points. In this case non-dealer would try to hold cards that score 4 points (as a hand), and if there are multiple options, try to hold cards that reduce dealer's chance of pegging. Meanwhile dealer's realistic route to victory would be to hold the 4 cards that give him the best chance of pegging 4 points (remembering that dealer will on average score more pegs, while non-dealer scores his hand first). If the score was 113-113, then dealer would play differently as he has NO chance of pegging 8 points, but there's perhaps a 40% chance that non-dealer fails to score 8 points from pegging and his hand. So in this case dealer would try to stop non-dealer pegging anything. So it seems that an AI would need to take into account the current score to decide how to peg.
I have read a couple of papers on cribbage AI, but they have been superficial and tended to concentrate on the discard game, which can be optimised at least for discarding purposes (without considering the relative pegging value), by simply iterating through the possible hands.
- http://r6.ca/cs486/ (does not cover pegging)
- https://helda.helsinki.fi/bitstream/handle/10138/273545/SeanLang_MS_thesis.pdf (addresses pegging very superficially by maximising the score of the next card, not considering that that might result in very poor total scores)
Now the question is to what extent this is a problem of machine learning, and to what extent this is an exhaustive analysis? If we ignore the discard problem, and we say that we will input four-card hands to our bot using the output of a process similar to the one here https://cliambrown.com/cribbage/methodology.php then for example:
- we could calculate the exact probability that our opponent holds any given four card hand, by iterating through the 45C6 hands (subject to appropriate simplifications) that our opponent could have, and then producing a weight for each of the (up to) 1820 possible hands, and for the 715 different hands of 4 unique denominations, the further chance for each to be a flush
- I am not quite clear how computationally expensive this is, but it seems to me that should be calculate the weights in a reasonable amount of time
So we have 4 cards, and we have weighted possibilities for each of 1820 hands.
Clearly it's not appropriate for us to simply randomly iterate through the hands. I.e. there are four choices for our first card, likewise four for our opponent, then 3 for the next. Roughly there will be 4!*4! choices in this way (roughly because the issue of the count resetting at 31 means that the card order after the third card is not always the samme). But our opponent's reply is not random. If we lead the 5, then he will certainly reply with a TJQK if he has one. He won't possibly reply with a 5.
So it seems to me that some kind of learning process is appropriate. But I am not really familiar with AI to say how this should work. Do we need a pool of human training data? Or do we allow the bot to play against itself?
And what role do probability tables have in this process? Is it going to be productive on a hand level to iterate through possible hands that our opponent might have, or is a Monte Carlo process just as good?
I should note that humans might make sub-optimal play. So for example, if we play PERFECTLY, then if we hold the hand 6699, and the 4 is led, then we SHOULD reply with the 9, rather than risk a 5 on our 6, conceding 5 points. So the play of a 6 on a 4 SHOULD indicate that we hold a hand such as 5566, in which case then we are informed accordingly. But clearly the chance that we hold 6699 and just made a blunder is not zero. So the bot cannot ever be completely certain about our holds.
Likewise it might be we choose to make 'sub-optimal' plays in order to avoid becoming predictable ourselves. For example, the question 'will our opponent pair our lead' is an important one - if we have a pair, we generally want him to. But sometimes we will hold a hand such as A4 JK, in which case we don't want him to pair our lead. Some players will play more aggressively than others, and against an aggressive player, he might pair our lead every time, and a more defensive player might almost never pair our lead.
