4
$\begingroup$

I have not been able to find a definitive answer about how opponent play works in Monte Carlo Tree Search. It makes sense that the agent is trying to optimize the moves that they make, but when we traverse the tree through the process of selection and expansion, etc., they are also "testing out" different moves by the opponent. I get the sense that the agent then makes its moves based on the opponent's making an optimal move - is this correct? What happens if the opponent does not behave optimally - is it possible that this makes the agents decision sub-optimal as well, or does it not matter because the agent throws out the stats tree after that turn and now makes new decisions based on the opponent's real move?

I am asking because I am trying to visualize the process for tic-tac-toe and it feels weird that the agent plays out the opponents moves too, as in the visualization I created below:

enter image description here

$\endgroup$

3 Answers 3

1
$\begingroup$

The main point is that the algorithm (similarly to minimax or alpha-beta) tries to find the move that has the best worst-case behavior. In other words, the value I assign to various moves is a lower bound on their actual value. If the opponent plays suboptimally, it means I will get into a better situation than I expected, but they cannot make a move that would make me worse. You would typically run a new search starting from the new position after the opponent moves so you adapt to it.

If your opponent is predictably stupid, you might be able to win quicker by doing risky moves that rely on your opponent's mistakes, but that is usually not reasonable - if the opponent is stupid, you will win anyway, but if they are not you may make your situation worse. It would also expose the agent to traps: a smart opponent could pretend to be stupid to make the agent attempt a risky move. Once the agent commits to the risky move, the opponent stops pretending and chooses the optimal (and devastating) response.

Note that this is not at all specific to MCTS, the same logic applies to all search-based algorithms for playing games.

$\endgroup$
1
$\begingroup$

The standard version such as used in AlphaGo and AlphaZero do propose moves for themselves and the opponent the same way (i.e. based on the policy predictions of the neural network, and then updated based on trying moves per the policy and seeing how they turn out). EDIT: I just realized you did not specify that we're talking about a setting with a neural network providing policy predictions, so maybe not entirely standard in a more generic "let's just play out lots of options without any skew towards better/more plausible moves".

This does not mean one could not try to do something clever to e.g. deal with situations where there are many equivalent options (e.g. in chess in a drawn endgame where a lot of options keep the draw, or to find new chess opening ideas in equal positions with many options where maybe some options are more likely to lead to human errors). You could imagine doing that using a neural network trained to imitate the moves of humans and to - to some extent - evaluate the options predicted by such a network in addition to those by stronger network trained using RL.

$\endgroup$
0
$\begingroup$

It's my understanding that MCTS plays out thousands of random games from each possible move for this turn. This is differs from your sense that it's "based on the opponent's making an optimal move". The gist of MCTS is: which of these moves puts me in a position to win the most blind/random games from that point on? The more games you could win blindly (randomly), the better your position. So MCTS is not "testing out" different moves by the opponent. It is instead measuring the effectiveness of each of its possible moves against each other, using random game results as the measuring stick.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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