2
$\begingroup$

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?

$\endgroup$
3
  • $\begingroup$ It's very hard to apply MCTS in imperfect information games, usually something like CFR is used instead, look up Rebel and Libratus $\endgroup$
    – Alberto
    Aug 17, 2023 at 1:11
  • $\begingroup$ 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. $\endgroup$ Aug 17, 2023 at 7:31
  • $\begingroup$ Thanks for the comments; will look up CFR thanks. $\endgroup$ Aug 19, 2023 at 21:03

2 Answers 2

1
$\begingroup$

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).

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 , it provides a nice overwiev of application of MCTS to this setting.

$\endgroup$
1
  • $\begingroup$ Thanks for the link $\endgroup$ Oct 11, 2023 at 11:12
0
$\begingroup$

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).

$\endgroup$
1
  • $\begingroup$ Thanks again for the link. Very useful. $\endgroup$ Oct 11, 2023 at 11:13

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .