Answers.Body: <p>In general, the solution concept of imperfect-information games is more complicated than games with perfect information. This is due to the neccesity of randomizing your own actions: e.g. in the rock-paper-scissors game, the Nash equlibirium (solution concept for games) is that both player randomize uniformly between all possible actions. This problem does not occur in games as e.g. backgamon - if all information is observed by all players, then there is no reason for randomization (even if the game include a factor of chance).</p>
  <p>A very large and popular class of algorithms for solving imperfect information games is based on so-called counterfactual regret minimization (CFR). You may want to check the foundation paper:
  <a href="https://poker.cs.ualberta.ca/publications/NIPS07-cfr.pdf" rel="nofollow noreferrer">Zinkevich, Martin, et al. &quot;Regret minimization in games with incomplete information.&quot; (2007)</a>.</p>
  <p>The 'vanilla' CFR operates on the whole game tree, which is intractable for larger games. Lots of methods were developed to abstract (make smaller) the game tree that CFR operates on, and / or use sampling techinques.</p>
  <p>For the application of MCTS on games with imperfect information, you may want to check this diseratition thesis: <a href="https://dspace.cvut.cz/bitstream/handle/10467/60842/Disertace_Lisy_2014.pdf?sequence=1&amp;isAllowed=y" rel="nofollow noreferrer">Monte Carlo Tree Search
  in Imperfect-Information Games</a> , it provides a nice overwiev of application of MCTS to this setting.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2023-10-11T09:21:03.280Z
Answers.LastActivityDate: 2023-10-11T09:21:03.280Z
Answers.UserDisplayName: Jakub Koubele
Answers.Body: <p>To handle games of imperfect information with Monte Carlo Tree Search, you will need to use a variant of the algorithm. The most common one I am familiar with is Information Set Monte Carlo Tree Search (IS-MCTS). In IS-MCTS, each node represents an information set of all states possible after a particular  sequence of actions.</p>
  <p>Implementing this is less difficult than it may initially sound. At each iteration of the algorithm, you create a new &quot;determinization&quot; of your game, which is a randomization of the game. During selection, you select moves available in the current determinization.</p>
  <p>If you are using UCB1 or similar for selection, a slight adjustment is needed. Since some moves are used only available some of the time, it does not make sense to use the parent node's game count in the exploration term. Instead we need a count of times the node we are scoring was available. Thus we will need to track this information during back propagation as well.</p>
  <p>See <a href="https://eprints.whiterose.ac.uk/75048/1/CowlingPowleyWhitehouse2012.pdf" rel="nofollow noreferrer">https://eprints.whiterose.ac.uk/75048/1/CowlingPowleyWhitehouse2012.pdf</a> for more details (or ask in comments below).</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2023-10-11T07:41:33.480Z
Answers.LastActivityDate: 2023-10-11T07:41:33.480Z
Answers.UserDisplayName: CleverLikeAnOx
Body: <p>I'm just learning the concepts and was interested in MCTS techniques.
  I can see in a simple game like tic-tac-toe how you would replace negamax say with MCTS.</p>
  <p>It looks more complicated in card games. If  you take a game like Whist or Bridge (ignoring bidding),</p>
  <p>A deck of 52 cards is distributed to 4 players (though you play in teams of two).
  Following a lead card, you try to win the trick by placing a higher card (with some rules around following if you can and 'trumps').</p>
  <p>I was trying to think of how you someone may implement this;</p>
  <p>I can see that if you simulate this a player will know their 13 cards and the remaining 39 cards are unknown.</p>
  <p>So, you could remove the 13 cards you know about from the deck and randomly assign those to the other players.</p>
  <p>Then would you use MCTS to play out that one random selection and repeat the whole process with another initial random assignment of cards at the start?</p>
  <p>The implementation would be monte-carlo simulations (the unknown 39 cards assigned amongst the 3 other players) where each simulation itself would play out via MCTS. I'm not sure if this is a sound technique? Or what techniques are used for similar games, existing solutions? I think maybe just taking the initial random allocation of cards and simulating playout using basic heuristics may be better?</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2023-08-17T01:11:13.813Z
Comments.Text: It's very hard to apply MCTS in imperfect information games, usually something like CFR is used instead, look up Rebel and Libratus
Comments.UserDisplayName: Alberto
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2023-08-17T07:31:57.133Z
Comments.Text: In Bridge you actually know half the cards: your own hand, and dummy, which is on the table after the first card has been played.
Comments.UserDisplayName: Oliver Mason
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2023-08-19T21:03:06.480Z
Comments.Text: Thanks for the comments; will look up CFR thanks.
Comments.UserDisplayName: Michael Lewis
Tags: <monte-carlo-tree-search><card-games>
Title: Monte Carlo Tree Search for trick taking games, such as Whist, Bridge
UserDisplayName: Michael Lewis
ThreadText: # Monte Carlo Tree Search for trick taking games, such as Whist, Bridge
  
  (Asked by: username_0 on 2023-08-16)
  
  I'm just learning the concepts and was interested in MCTS techniques.
  I can see in a simple game like tic-tac-toe how you would replace negamax say with MCTS.
  
  It looks more complicated in card games. If you take a game like Whist or Bridge (ignoring bidding),
  
  A deck of 52 cards is distributed to 4 players (though you play in teams of two).
  Following a lead card, you try to win the trick by placing a higher card (with some rules around following if you can and 'trumps').
  
  I was trying to think of how you someone may implement this;
  
  I can see that if you simulate this a player will know their 13 cards and the remaining 39 cards are unknown.
  
  So, you could remove the 13 cards you know about from the deck and randomly assign those to the other players.
  
  Then would you use MCTS to play out that one random selection and repeat the whole process with another initial random assignment of cards at the start?
  
  The implementation would be monte-carlo simulations (the unknown 39 cards assigned amongst the 3 other players) where each simulation itself would play out via MCTS. I'm not sure if this is a sound technique? Or what techniques are used for similar games, existing solutions? I think maybe just taking the initial random allocation of cards and simulating playout using basic heuristics may be better?
  
  **Tags:** monte-carlo-tree-search, card-games
  > **Comments:**
  > **username_1**: It's very hard to apply MCTS in imperfect information games, usually something like CFR is used instead, look up Rebel and Libratus  
  > **username_2**: In Bridge you actually know half the cards: your own hand, and dummy, which is on the table after the first card has been played.  
  > **username_0**: Thanks for the comments; will look up CFR thanks.  
  
  ---
  
  ## 2 answers
  
  ### Answer by username_3 on 2023-10-11. Score: 2
  
  In general, the solution concept of imperfect-information games is more complicated than games with perfect information. This is due to the neccesity of randomizing your own actions: e.g. in the rock-paper-scissors game, the Nash equlibirium (solution concept for games) is that both player randomize uniformly between all possible actions. This problem does not occur in games as e.g. backgamon - if all information is observed by all players, then there is no reason for randomization (even if the game include a factor of chance).
  
  A very large and popular class of algorithms for solving imperfect information games is based on so-called counterfactual regret minimization (CFR). You may want to check the foundation paper:
  [Zinkevich, Martin, et al. "Regret minimization in games with incomplete information." (2007)](https://poker.cs.ualberta.ca/publications/NIPS07-cfr.pdf).
  
  The 'vanilla' CFR operates on the whole game tree, which is intractable for larger games. Lots of methods were developed to abstract (make smaller) the game tree that CFR operates on, and / or use sampling techinques.
  
  For the application of MCTS on games with imperfect information, you may want to check this diseratition thesis: [Monte Carlo Tree Search
  in Imperfect-Information Games](https://dspace.cvut.cz/bitstream/handle/10467/60842/Disertace_Lisy_2014.pdf?sequence=1&isAllowed=y) , it provides a nice overwiev of application of MCTS to this setting.
  
  
  ---
  
  ### Answer by username_4 on 2023-10-11. Score: 1
  
  To handle games of imperfect information with Monte Carlo Tree Search, you will need to use a variant of the algorithm. The most common one I am familiar with is Information Set Monte Carlo Tree Search (IS-MCTS). In IS-MCTS, each node represents an information set of all states possible after a particular sequence of actions.
  
  Implementing this is less difficult than it may initially sound. At each iteration of the algorithm, you create a new "determinization" of your game, which is a randomization of the game. During selection, you select moves available in the current determinization.
  
  If you are using UCB1 or similar for selection, a slight adjustment is needed. Since some moves are used only available some of the time, it does not make sense to use the parent node's game count in the exploration term. Instead we need a count of times the node we are scoring was available. Thus we will need to track this information during back propagation as well.
  
  See <https://eprints.whiterose.ac.uk/75048/1/CowlingPowleyWhitehouse2012.pdf> for more details (or ask in comments below).
  
  
  ---
  
  