11
$\begingroup$

I would like to ask whether MCTS is usually chosen when the branching factor for the states that we have available is large and not suitable for Minimax. Also, other than MCTS simluates actions, where Minimax actually 'brute-forces' all possible actions, what are some other benefits for using Monte Carlo for adversarial (2-player) games?

Improve this question
$\endgroup$
1

1 Answer 1

Reset to default
6
$\begingroup$

Some basic advantages of MCTS over Minimax (and its many extensions, like Alpha-Beta pruning and all the other extensions over that) are:

  • MCTS does not need a heuristic evaluation function for states. It can make meaningful evaluations just from random playouts that reach terminal game states where you can use the loss/draw/win outcome. So if you're faced with a domain where you have absolutely no heuristic domain knowledge that you can plug in, MCTS is likely a better choice. Minimax must have a heuristic evaluation function for states (exception: if you game is so simple that you can afford to compute the complete game tree and reach all terminal game states immediately from the the initial game state, you don't need heuristics). If you do have strong evaluation functions, you can still incorporate them and use them to improve MCTS too; they're just not strictly necessary for MCTS.

  • MCTS has simpler anytime behaviour; you can just keep running iterations until you run out of computing time, and then return the best move. Typically we expect the performance level of MCTS to grow with computatinon time / iteration count relatively smoothly (not always 100% true, but intuitively you can usually expect something like this). You can sort of achieve anytime behaviour in minimax with iterative deepening, but that's usually a bit less "smooth", a bit more "bumpy"; this is because every time you increase the search depth, you need significantly more processing time than you did for the previous depth limit. If you run out of time and have to abort your current search at your current depth limit, that last search will be completely useless; you'll have to discard it and stick to the results from the previous search with the previous depth limit.

A difference, which is not necessarily an advantage or disadvantage either way in the general case (but can be in specific cases):

  • The computation time of MCTS is generally dominated by running (semi-)random playouts. This means that functions for computing legal move lists, and applying moves to game states, typically dictate how fast or slow your MCTS runs; making these functions faster will generally make your MCTS faster. On the other hand, the computation time of Minimax is generally dominated by copying game states (or "undoing" moves, which is an operation that in most games will require additional memory usage for game states to be possible) and heuristic evaluation functions (though the latter are likely to also become important in terms of computation cost in MCTS if you choose to include them there). In some games it will be easier to provide efficient implementations for one of these, and in other games it may be different.

A basic advantage of Minimax over MCTS:

  • In settings where MCTS can only run very few iterations relative to the branching factor (or in the extreme case, fewer iterations than there are actions available in the root node), MCTS will perform extremely poorly / close to random play. We've noticed this being the case for quite a decent number of games in our general game system Ludii (where the "general game system" often implies that games are implemented less efficiently than they could be in a dedicated single-game-specific program) with low time controls (like 1 second per move). This same general game setting often makes it difficult to find super strong heuristics, but it's generally still possible to come up with some relatively simple ones (like just a simple material heuristic in chess). An alpha-beta search with just a couple of search plies and a basic, simple heuristic will often outperform a close-to-random MCTS if the MCTS can't manage to run significantly more iterations than it has legal moves in the root node.
Improve this answer
$\endgroup$
2
  • 2
    $\begingroup$ Interestingly lots of these points about mcts are reversed with NN versions of MCTS. For them, the main reason you are using mcts is because you can afford a slower search, and mcts does a much better job of pruning. $\endgroup$
    – Oscar Smith
    Commented Jul 12, 2020 at 3:29
  • $\begingroup$ @OscarSmith Yep. Arguably MCTS is also a bit easier to combine with NNs, they can work better with "smooth" biases from a policy network. I suppose you could technically use a policy network in AlphaBeta for move ordering, or maybe even for deciding different search depth limits for different moves, but these are discrete and fairly "big" jumps in the behaviour of AlphaBeta. If your policy network thinks two moves are almost equally good, you can have them give MCTS almost equal biases. In AlphaBeta you'd sort one before the other regardless of how big or small the difference between them is. $\endgroup$
    – Dennis Soemers ♦
    Commented Jul 12, 2020 at 8:35

You must log in to answer this question.

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