How does one handle different player turns in MCTS?

Question

Suppose we have a two player game like Tic Tac Toe where the two players take turns to play their moves. It is my understanding that in the game tree that MCTS builds, consecutive levels in the tree correspond to different player's turns.

So, for instance, in the root node it is Player1's turn to play, in the children of the root node it is Player2's turn to play, in the children of those children it is Player1's turn again, etc.

Is that correct?

If so, is it really prudent to treat nodes where it's the enemy's turn to play the same as those where we choose the next action (i.e. by averaging rollout results in backpropagation). Since, it's not us choosing the next action but the enemy, shouldn't we "pick" the minimum "return" (like in minimax) in those cases instead of the average like we do for nodes where we get to pick the next action?

By picking I mean to only count the win ratio of that child node (i.e. the minimum win ratio).

I suspect I am missing something (e.g. that might mess up exploration vs exploitation with UCT) but I can't put my finger on it.

What do you guys think about this?

Edit: Maybe a solution to this is only considering good moves for the opponent? But then again.. how do we define good? Heuristics?

Answer 1

The original (vanilla) MCTS use random rollouts. In some games this is enough to produce a strong agent. However, in most of the games, using a heuristic that finds the opponent's likely moves makes stronger agents. There is another line of practice that uses Opponent Modeling to predict the opponent moves. That is important in games where you have several opponent "types" or when an opponent can go for different goals.

From my experience, a good heuristic can greatly improve the agent. I have implemented UCT agents for Spades (the card game). I made a vanilla UCT and one that uses a different (simpler) agent as heuristic. The second UCT is stronger.

Picture from wiki:MCTS

The four phases of MCTS:

Selection: Start from root R and select successive child nodes until a leaf node L is reached. The root is the current game state and a leaf is any node that has a potential child from which no simulation (playout) has yet been initiated. The section below says more about a way of biasing choice of child nodes that lets the game tree expand towards the most promising moves, which is the essence of Monte Carlo tree search.

Expansion: Unless L ends the game decisively (e.g. win/loss/draw) for either player, create one (or more) child nodes and choose node C from one of them. Child nodes are any valid moves from the game position defined by L.

Simulation: Complete one random playout from node C. This step is sometimes also called playout or rollout. A playout may be as simple as choosing uniform random moves until the game is decided (for example in chess, the game is won, lost, or drawn).

Backpropagation: Use the result of the playout to update information in the nodes on the path from C to R.

Answer 2

I think I came up with an intuitively good solution. During the selection phase, if in the current state it's the opponent's turn to play then the winrate in the UCT formula becomes 1.0 - winrate instead. This should make us invest more in good opponent moves rather than bad ones.

I am implementing MCTS for Quoridor at the moment I ll update if it works better or not when I am done.

Edit: Yup, this seems to be the way. Now the tree is symmetrical and we can also generate moves for the opponent as well.