Answers.Body: <p>Deep reinforcement learning might be suitable for your requirement. If possible I would recommend you to add DRL hashtag to your thread, so that it can reach to larger number of  DRL researchers and practitioners, to help you out.</p>
  <p>Thanks ,
  Durga</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-07-29T19:36:28.453Z
Answers.LastActivityDate: 2020-07-29T19:36:28.453Z
Answers.UserDisplayName: Durga K
Body: <p>The game of cribbage <a href="https://en.wikipedia.org/wiki/Cribbage" rel="nofollow noreferrer">https://en.wikipedia.org/wiki/Cribbage</a> is a two-player card game played over a series of deal with the goal to reach 121 points.</p>
  <p>The game's elements are:</p>
  <ul>
  <li>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)</li>
  <li><strong>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</strong></li>
  <li>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.</li>
  <li>the order of play. This is:
  <ul>
  <li>the cut. Averages 2/13 = 0.15 points for dealer (if a Jack is cut)</li>
  <li>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.</li>
  <li>non-dealer shows his hand. Averages 8 points</li>
  <li>dealer shows his hand. Averages 8 points.</li>
  <li>dealer shows his crib. Average 4 points.</li>
  </ul>
  </li>
  </ul>
  <p>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.,  <a href="https://cliambrown.com/cribbage/" rel="nofollow noreferrer">https://cliambrown.com/cribbage/</a></p>
  <p>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)</p>
  <p>After we've held the card we must then 'play the pegging game'. <strong>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.</strong></p>
  <p>The scoring for pegging is:</p>
  <ul>
  <li>each pair scores 2 for the player playing the second card, 6 for 3 of a kind, 12 for 4 of a kind</li>
  <li>each time the count reaches 15, the player playing the card scores 2</li>
  <li>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</li>
  <li>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.</li>
  </ul>
  <p>Follows discussion about pegging strategy, which I have blockquoted for those who find this tl;dr</p>
  <blockquote>
  <p>The optimum play for a given hand is not necessarily clear-cut. For
  example, with the hand A4KK, then we could lead:</p>
  <ul>
  <li>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.</li>
  <li>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</li>
  <li>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</li>
  <li>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.</li>
  <li>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).</li>
  <li>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.</li>
  </ul>
  <p>During pegging we have considerable information:</p>
  <ul>
  <li>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.</li>
  <li>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.</li>
  </ul>
  <p>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.</p>
  <p>Although there are in theory 270,725 4 card hands, in pegging terms
  (ignoring suits), there are only 1820  distinct hands
  (<a href="https://docs.google.com/spreadsheets/d/1fxkLBkWC2LA6J06zhku21jcG2ATHqE1RNHlPSDcc4fQ/edit#gid=834958733" rel="nofollow noreferrer">https://docs.google.com/spreadsheets/d/1fxkLBkWC2LA6J06zhku21jcG2ATHqE1RNHlPSDcc4fQ/edit#gid=834958733</a>)</p>
  <p>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.</p>
  <p>As another example if we were dealt A778JK, then we'd toss the JK.
  Here we'd likely lead the 7.</p>
  <p>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/46<em>1/45</em>6C2, 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%.</p>
  <p>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.</p>
  <p>In terms of our possible plays, we have at the count of 14:</p>
  <ul>
  <li>play the Ace and score 2 points for the count of 15.</li>
  <li>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.</li>
  <li>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)</li>
  </ul>
  <p>In general it can be seen that there are:</p>
  <ul>
  <li>up to 1820 unique 4-card hands</li>
  <li>up to 455 3-card hands</li>
  <li>up to 91 2-card hands</li>
  <li>up to 13 1-card hands</li>
  </ul>
  <p>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.</p>
  <p>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).</p>
  <p>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.</p>
  <p>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.</p>
  </blockquote>
  <p>In general the goal of a pegging bot could be seen as:</p>
  <ul>
  <li>score most points or</li>
  <li>concede fewest points or</li>
  <li>maximise net points</li>
  </ul>
  <blockquote>
  <p>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.</p>
  </blockquote>
  <p>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.</p>
  <ul>
  <li><a href="http://r6.ca/cs486/" rel="nofollow noreferrer">http://r6.ca/cs486/</a> (does not cover pegging)</li>
  <li><a href="https://helda.helsinki.fi/bitstream/handle/10138/273545/SeanLang_MS_thesis.pdf" rel="nofollow noreferrer">https://helda.helsinki.fi/bitstream/handle/10138/273545/SeanLang_MS_thesis.pdf</a> (addresses pegging very superficially by maximising the score of the next card, not considering that that might result in very poor total scores)</li>
  </ul>
  <p>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 <a href="https://cliambrown.com/cribbage/methodology.php" rel="nofollow noreferrer">https://cliambrown.com/cribbage/methodology.php</a> then for example:</p>
  <ul>
  <li>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</li>
  <li>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</li>
  </ul>
  <p>So we have 4 cards, and we have weighted possibilities for each of 1820 hands.</p>
  <p>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.</p>
  <p>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?</p>
  <p>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?</p>
  <p>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.</p>
  <p>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.</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-07-28T20:41:23.837Z
Comments.Text: Welcome to SE:AI!  Although interesting, this post is very long.  Could you possibly synopsize at the beginning and post the actual question in the opening of the body text?  (Part of the problem I see here is what constitutes "large" in terms of a data set in context?  I get what you're asking, but it's a relative term.)  I think this question would be well served by describing the *structure of the problem (i.e. the rules of cribbage)* more succinctly.  If you could reduce that to Mathjax formulas, that would be optimal.
Comments.UserDisplayName: DukeZhou
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-07-28T20:49:26.540Z
Comments.Text: Also maybe specify the features of the game in more formal language, if possible.  (The game involves randomness, imperfect information, etc.  The card pool is size x, the number of possible hand combinations y.)  I suspect it's very similar to poker from an AI perspective, and likely the same complexity class.  Since poker has been rigorously studied, and statistical AI recently validated as able to play poker strongly, I might research that game.  For instance [Measuring the Size of Large
  No-Limit Poker Games](https://poker.cs.ualberta.ca/publications/2013-techreport-nl-size.pdf)
Comments.UserDisplayName: DukeZhou
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-07-28T20:57:16.817Z
Comments.Text: [Superhuman AI for multiplayer poker (Nature)](https://science.sciencemag.org/content/365/6456/885)
Comments.UserDisplayName: DukeZhou
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-07-29T08:47:26.620Z
Comments.Text: hi, thanks for the comments. 
  
  I guess my problem is that I know very little about AI.
  
  OTOH very few people know much about cribbage. Even if they play it casually, they typically focus on the hand discard problem and don't optimise the play of cards.
  
  Rules are one thing, but the approaches I have seen to cribbage play seem to treat it at as a problem that will solve itself, artificially. Whereas I am not sure if AI works like that.
Comments.UserDisplayName: thelawnet
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-07-29T09:15:18.810Z
Comments.Text: I have edited the post to indent the strategy about pegging so that it can be ignored, and try to focus the question on the extent to which this is a problem of probability analysis from our inputs, and to what extent perhaps the bot can learn without doing such an analyses (presumably via a very large pool of training data).
Comments.UserDisplayName: thelawnet
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-07-29T22:57:06.200Z
Comments.Text: Thanks for the edit.  My sense is that the same methods used for poker would work, since they are problems with similar structures.  The caveat is that training such a network to play strongly would almost certainly be quite expensive in terms of compute time and memory for an individual developer.  (Just a guess.)
Comments.UserDisplayName: DukeZhou
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-07-31T11:28:12.730Z
Comments.Text: maybe so. essentially there are 4!*4! possible pegging decisions (some illegal for certain card sets = 576), 52C6 cards and 46C6 cards for each player, and 6C4 = 15 discard decisions. This comes to 9.5 * 10^25 decisions. There are also 121^2 score states = 14,641, and there will be different correct decisions for each state, although they will be similar for scores like 0-0 and 10-10, but very different for say 120-120 vs. 110-110 vs. 60-60.
Comments.UserDisplayName: thelawnet
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-08-04T21:36:34.327Z
Comments.Text: Might be worthwhile to dip your toe into computational complexity theory and algorithmic combinatorial game theory.  Essentially, we can mathematically group problems with similar structures into classes, such that, even though they are distinct games, both poker and cribbage are very likely in the same complexity class, and the same algorithmic methods will work for both.
Comments.UserDisplayName: DukeZhou
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-08-07T15:38:07.427Z
Comments.Text: thanks. I have got a bit further down the road to scoping the problem since posting this.
Comments.UserDisplayName: thelawnet
Tags: <ai-design><game-ai><deep-rl>
Title: Do I need a large pool of training data to train a bot to play the 'pegging' game in the cribbage card game
UserDisplayName: thelawnet
ThreadText: # Do I need a large pool of training data to train a bot to play the 'pegging' game in the cribbage card game
  
  (Asked by: username_0 on 2020-07-28)
  
  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/46*1/45*6C2, 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.
  
  **Tags:** ai-design, game-ai, deep-rl
  > **Comments:**
  > **username_1**: Welcome to SE:AI!  Although interesting, this post is very long.  Could you possibly synopsize at the beginning and post the actual question in the opening of the body text?  (Part of the problem I see here is what constitutes "large" in terms of a data set in context?  I get what you're asking, but it's a relative term.)  I think this question would be well served by describing the *structure of the problem (i.e. the rules of cribbage)* more succinctly.  If you could reduce that to Mathjax formulas, that would be optimal.  
  > **username_1**: Also maybe specify the features of the game in more formal language, if possible.  (The game involves randomness, imperfect information, etc.  The card pool is size x, the number of possible hand combinations y.)  I suspect it's very similar to poker from an AI perspective, and likely the same complexity class.  Since poker has been rigorously studied, and statistical AI recently validated as able to play poker strongly, I might research that game.  For instance [Measuring the Size of Large No-Limit Poker Games](https://poker.cs.ualberta.ca/publications/2013-techreport-nl-size.pdf)  
  > **username_1**: [Superhuman AI for multiplayer poker (Nature)](https://science.sciencemag.org/content/365/6456/885)  
  > **username_0**: hi, thanks for the comments.   I guess my problem is that I know very little about AI.  OTOH very few people know much about cribbage. Even if they play it casually, they typically focus on the hand discard problem and don't optimise the play of cards.  Rules are one thing, but the approaches I have seen to cribbage play seem to treat it at as a problem that will solve itself, artificially. Whereas I am not sure if AI works like that.  
  > **username_0**: I have edited the post to indent the strategy about pegging so that it can be ignored, and try to focus the question on the extent to which this is a problem of probability analysis from our inputs, and to what extent perhaps the bot can learn without doing such an analyses (presumably via a very large pool of training data).  
  > **username_1**: Thanks for the edit.  My sense is that the same methods used for poker would work, since they are problems with similar structures.  The caveat is that training such a network to play strongly would almost certainly be quite expensive in terms of compute time and memory for an individual developer.  (Just a guess.)  
  > **username_0**: maybe so. essentially there are 4!*4! possible pegging decisions (some illegal for certain card sets = 576), 52C6 cards and 46C6 cards for each player, and 6C4 = 15 discard decisions. This comes to 9.5 * 10^25 decisions. There are also 121^2 score states = 14,641, and there will be different correct decisions for each state, although they will be similar for scores like 0-0 and 10-10, but very different for say 120-120 vs. 110-110 vs. 60-60.  
  > **username_1**: Might be worthwhile to dip your toe into computational complexity theory and algorithmic combinatorial game theory.  Essentially, we can mathematically group problems with similar structures into classes, such that, even though they are distinct games, both poker and cribbage are very likely in the same complexity class, and the same algorithmic methods will work for both.  
  > **username_0**: thanks. I have got a bit further down the road to scoping the problem since posting this.  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_2 on 2020-07-29. Score: 0
  
  Deep reinforcement learning might be suitable for your requirement. If possible I would recommend you to add DRL hashtag to your thread, so that it can reach to larger number of DRL researchers and practitioners, to help you out.
  
  Thanks ,
  Durga
  
  
  ---
  
  