1
$\begingroup$

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.

$\endgroup$
2
+50
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ My understanding is that when picking between nodes A and B, the random playouts from node B were pure random and essentially stateless, so wouldn't record any information about states deeper than B (because doing so would be essentially depth-first search). Am I missing something? $\endgroup$ – Eli Stevens Jan 18 '17 at 20:26
  • $\begingroup$ If at any point in the traversal of the MCTS a failing node is chosen then it will be unlikely to pick the same path again; the same principle applies. It appears to me that you're asking "what happens if we consistently pick entirely random nodes". At that point you've broken from the principles of the algorithm and can no longer be considered Monte Carlo Search. Of course you can make various adjustments to the amount of randomness, but the backpropagation is essential in what makes it a MCS. Disregarding that would mean randomly picking a child node at every parent, which is not MCS. $\endgroup$ – DeBunkeD Jan 18 '17 at 21:37
  • $\begingroup$ Ah, my misunderstanding of the algorithm, I think, was that I thought MCTS discarded the child nodes of the random playout once it was done with the playout, and only kept the win/loss info at the root of the current choice to be made. Thanks! $\endgroup$ – Eli Stevens Jan 19 '17 at 0:07

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.