1
$\begingroup$

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?

$\endgroup$
0
1
$\begingroup$

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 Step of Monte Carlo tree search.

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.

$\endgroup$
8
  • 1
    $\begingroup$ Interesting input. I am not talking about the rollout phase though. I am talking about the tree itself. For example, I believe AlphaGo prunes candidate moves in the tree by only considering moves deemed "worthy" from a neural network. That is, it doesn't fully expand each node based on all possible moves. Hence it won't consider bad moves for the opponent, therefore avoiding our agent from dreaming that it will ever get to such states (where he would probably win). $\endgroup$
    – Michael
    Aug 5 at 16:00
  • $\begingroup$ Added a picture from wiki that describe the four phases of a MCTS step. What phase are you asking about? I think you are talking about the Simulation phase, where the algorithm plays for all the players until it reaches a the game's end and can evaluate the score. $\endgroup$
    – Cohensius
    Aug 6 at 16:03
  • $\begingroup$ No, I am talking about the selection phase and the moves we consider there on each expansion. Those moves could be all of the legal moves but maybe it should be only good moves to prevent the problem I discuss in my post. $\endgroup$
    – Michael
    Aug 7 at 16:24
  • $\begingroup$ In the selection phase, MCTS choses the node to expand, those nodes are the agent's moves. I think the problem you talking about is in the Simulation phase, where the algorithm guesses the opponents' moves. $\endgroup$
    – Cohensius
    Aug 7 at 20:51
  • $\begingroup$ Wiki:MCTS explains the four phases well. In the Selection phase we only choose a node, then expend it by 1 move (our move), then in the simulation phase we playout to the game's end (only here we consider opponents moves). $\endgroup$
    – Cohensius
    Aug 7 at 20:55
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.