How does MCTS handle games with large numbers of poor moves?

Question

I am trying to understand how pure Monte Carlo tree search (https://en.wikipedia.org/wiki/Monte_Carlo_tree_search) handles games where random playout will likely result in a loss easily avoided by other types of agents.

For example, imagine a hypothetical game with a single player. At game start, the player can choose between move A or move B.

Move A results in a fair coin flip that determines win/loss.

Move B results in a second set of 10 possible moves for player A, one of which is a win (move C, let's call it), and the other 9 a loss.

Random playout will have move A winning 50% of the time, and Move B winning 10% of the time, even though the ability to always pick the winning move B->C is within the player's power.

Can MCTS handle games of this nature well? How does it do so?

Obviously this toy example can trivially be solved by other search methods, but the real game I'm interested in has a prohibitive branching factor for things like depth- or breadth-first search, and a proper evaluation function is difficult.

Answer 1

Issues like these are essentially solved in the MCTS itself. The principle of the algorithm is that it tries to make the best pick, rather than guaranteeing it (if done in this randomized fashion rather than a 'pure MCTS' fashion). The trees are built up out of large amounts of collected data, aggretating success rates in the nodes. Nodes that end up being succesful more often will have a larger likelihood of being picked. This process of positive reinforcement means that nodes that always lead to a victory will, over the course of many playthroughs, approach a 100% pick rate.

In your example, node A will have a rougly 50/50 success/failure ratio throughout any number of playthroughs (due to the coinflip). Node B will have a 10/90 ratio of success/failure at first but will approach a 100/0 ratio as the number of playthroughs nears infinity (node C will end up always being picked due to the 100% success rate, and this propagates to node B).

The result is that node B will gradually end up being picked more often than node A, reinforcing the effect and causing it to be picked even more often.

The image on the wikipedia page illustrates it very well; the nodes with a high chance of success gradually make up a larger fraction of the total 'node weight' on a level, thus increasing the odds that it is picked with every playthrough.