Body: <p>I'm trying to implement a MCTS-based AI for a trick-taking card game.</p>
  <h2><strong>The game : (<a href="https://en.wikipedia.org/wiki/Belote" rel="nofollow noreferrer">Belote</a>)</strong></h2>
  <ul>
  <li>The play consists of 8 tricks.</li>
  <li>A trick consists in each of the 4 players play successively 1 (legal) card from their hand (starting with 8 cards).</li>
  <li>A player can only play certain cards from his hand (depends on the current state of the trick). Thus, the other players can infer information of some other players hand based on the current and past tricks.</li>
  </ul>
  <h2><strong>My implementation so far:</strong></h2>
  <p><strong>The node:</strong></p>
  <p>The current state of the round (previous tricks, current trick, the play order...) + the position of the &quot;smart&quot; player.</p>
  <p><strong>Expansion function:</strong></p>
  <p>I can think of 2 possibilities :</p>
  <ul>
  <li>a card is played by a player</li>
  <li>a whole new trick is played</li>
  </ul>
  <p><strong>Other tools that I implemented:</strong></p>
  <ul>
  <li>A method that gives the legal cards of a hand (based on the current trick).</li>
  <li>A method that gives the smart player all the possible cards of another player (based on the current and previous tricks).</li>
  <li>A method that generates every possible next (legal) trick (based on the 2 previous methods).</li>
  </ul>
  <h2>Problem :</h2>
  <p>If I want to apply MCTS, I need to ensure that the succession of the simulated remaining tricks (or played cards) until the end of the round (ie the path in the tree) will not be a dead-end before reaching the final (32th) card.
  Indeed, a player could run out of legal cards during the simulation...</p>
  <p><em>How can I deal with that constraint in an MCTS context ?</em></p>
  <p><em>Is MCTS even a viable algorithm for what I want to achieve ?</em></p>
  <p>I could of course precompute the whole possible tree ahead of time, but his size would be huge, and the interest of the MCTS is kind of lost.</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2022-11-23T15:08:22.653Z
Comments.Text: How do the game rules deal with situations where there are no legal cards left for a player?
Comments.UserDisplayName: KarelPeeters
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2022-11-23T19:58:44.663Z
Comments.Text: There is always at least one legal card in every hand. The rules only specify a "priority order" of cards in a hand with respect to the current trick. "If you don't have these cards in your hand, then you should play these, if you still don't have these cards, then you have to play these... etc.". The legal cards in a hand depend on the current trick and the whole hand itself.
Comments.UserDisplayName: Betcha
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2022-11-23T20:09:16.820Z
Comments.Text: This is in real life. Now, in my MCTS implementation it's different because I make the opponents play cards that they *possibly* have, but the smart player doesn't know their actual hands of course.
Comments.UserDisplayName: Betcha
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2022-11-24T11:17:20.257Z
Comments.Text: Ah, I see. Could you randomly sample one possible set of cards at the start of the rollout and then keep taking cards from that set until the end of the rollout? More generally with hidden information everything becomes a lot more complicated game-theoretically, with things like bluffing and trading off good moves vs hiding information. Unfortunately I don't think there are any simple extensions to MCTS to deal with this (yet).
Comments.UserDisplayName: KarelPeeters
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2022-11-26T09:20:15.207Z
Comments.Text: If I understand correctly, you suggest to distribute the 3 other players the 24 remaining cards (32 - 8 known cards from the smart player's hand) and rollout from this node. And repeat N times with different initial distributions.
  I've tried that but unfortunately it did not work very well. I suppose that it because there is $\frac{(3*8)!}{{8!}^3}$ ~ 9 billions possible initial distributions. And even a 1 card change can have a great impact.
  If not with MCTS, do you see any possible way to achieve that ? Reinforcement learning ? Thanks.
Comments.UserDisplayName: Betcha
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2022-11-26T18:13:55.217Z
Comments.Text: Yeah I'm not too surprised it doesn't work that well, naive MCTS seems a bit hopeless it this case. For hidden information games two recent approaches (indeed using reinforcement learning) are [Player Of Games](https://arxiv.org/abs/2112.03178) and [ReBeL](https://arxiv.org/abs/2007.13544), so consider looking into those or some of the related work they cite.
Comments.UserDisplayName: KarelPeeters
Tags: <monte-carlo-tree-search><card-games>
Title: MCTS for trick-taking game?
UserDisplayName: Betcha
ThreadText: # MCTS for trick-taking game?
  
  (Asked by: username_0 on 2022-11-05)
  
  I'm trying to implement a MCTS-based AI for a trick-taking card game.
  
  ## **The game : ([Belote](https://en.wikipedia.org/wiki/Belote))**
  
  * The play consists of 8 tricks.
  * A trick consists in each of the 4 players play successively 1 (legal) card from their hand (starting with 8 cards).
  * A player can only play certain cards from his hand (depends on the current state of the trick). Thus, the other players can infer information of some other players hand based on the current and past tricks.
  
  ## **My implementation so far:**
  
  **The node:**
  
  The current state of the round (previous tricks, current trick, the play order...) + the position of the "smart" player.
  
  **Expansion function:**
  
  I can think of 2 possibilities :
  
  * a card is played by a player
  * a whole new trick is played
  
  **Other tools that I implemented:**
  
  * A method that gives the legal cards of a hand (based on the current trick).
  * A method that gives the smart player all the possible cards of another player (based on the current and previous tricks).
  * A method that generates every possible next (legal) trick (based on the 2 previous methods).
  
  ## Problem :
  
  If I want to apply MCTS, I need to ensure that the succession of the simulated remaining tricks (or played cards) until the end of the round (ie the path in the tree) will not be a dead-end before reaching the final (32th) card.
  Indeed, a player could run out of legal cards during the simulation...
  
  *How can I deal with that constraint in an MCTS context ?*
  
  *Is MCTS even a viable algorithm for what I want to achieve ?*
  
  I could of course precompute the whole possible tree ahead of time, but his size would be huge, and the interest of the MCTS is kind of lost.
  
  **Tags:** monte-carlo-tree-search, card-games
  
  > **Comments:**
  > **username_1**: How do the game rules deal with situations where there are no legal cards left for a player?  
  > **username_0**: There is always at least one legal card in every hand. The rules only specify a "priority order" of cards in a hand with respect to the current trick. "If you don't have these cards in your hand, then you should play these, if you still don't have these cards, then you have to play these... etc.". The legal cards in a hand depend on the current trick and the whole hand itself.  
  > **username_0**: This is in real life. Now, in my MCTS implementation it's different because I make the opponents play cards that they *possibly* have, but the smart player doesn't know their actual hands of course.  
  > **username_1**: Ah, I see. Could you randomly sample one possible set of cards at the start of the rollout and then keep taking cards from that set until the end of the rollout? More generally with hidden information everything becomes a lot more complicated game-theoretically, with things like bluffing and trading off good moves vs hiding information. Unfortunately I don't think there are any simple extensions to MCTS to deal with this (yet).  
  > **username_0**: If I understand correctly, you suggest to distribute the 3 other players the 24 remaining cards (32 - 8 known cards from the smart player's hand) and rollout from this node. And repeat N times with different initial distributions. I've tried that but unfortunately it did not work very well. I suppose that it because there is $\frac{(3*8)!}{{8!}^3}$ ~ 9 billions possible initial distributions. And even a 1 card change can have a great impact. If not with MCTS, do you see any possible way to achieve that ? Reinforcement learning ? Thanks.  
  > **username_1**: Yeah I'm not too surprised it doesn't work that well, naive MCTS seems a bit hopeless it this case. For hidden information games two recent approaches (indeed using reinforcement learning) are [Player Of Games](https://arxiv.org/abs/2112.03178) and [ReBeL](https://arxiv.org/abs/2007.13544), so consider looking into those or some of the related work they cite.  
  
  ---
  
  ## 0 answers
  
  