6
$\begingroup$

When the time allotted to Monte Carlo tree search runs out, what action should be chosen from the root?

The game action finally executed by the program in the actual game, is the one corresponding to the child which was explored the most.

The basic algorithm involves iteratively building a search tree until some predefined computational budget – typically a time, memory or iteration constraint – is reached, at which point the search is halted and the best-performing root action returned.

[...] The result of the overall search a(BESTCHILD(v0)) is the action a that leads to the best child of the root node v0, where the exact definition of “best” is defined by the implementation.

[...] As soon as the search is interrupted or the computation budget is reached, the search terminates and an action a of the root nodet0is selected by some mechanism. Schadd [188] describes four criteria for selecting the winning action, based on the work of Chaslot et al [60]:

  1. Max child: Select the root child with the highest reward.

  2. Robust child: Select the most visited root child.

  3. Max-Robust child: Select the root child with both the highest visit count and the highest reward. If none exist, then continue searching until an acceptable visit count is achieved [70].

  4. Secure child: Select the child which maximises a lower confidence bound.

[...] Once some computational budget has been reached, the algorithm terminates and returns the best move found,corresponding to the child of the root with the highest visit count.

The return value of the overall search in this case is a(BESTCHILD(v0,0)) which will give the action a that leads to the child with the highest reward, since the exploration parameter c is set to 0 for this final call on the root node v0. The algorithm could instead return the action that leads to the most visited child; these two options will usually – but not always! – describe the same action. This potential discrepancy is addressed in the Go program ERICA by continuing the search if the most visited root action is not also the one with the highest reward. This improved ERICA’s winning rate against GNU GO from 47% to 55% [107].

But their algorithm 2 uses the same criterion as the internal-node selection policy:

$$\operatorname{argmax}_{v'} \frac{Q(v')}{N(v')} + c \sqrt{\frac{2 \ln N(v)}{N(v')}}$$

which is neither the max child nor the robust child! This situation is quite confusing, and I'm wondering which approach is nowadays considered most successful/appropriate.

$\endgroup$
  • $\begingroup$ Best action (best Q) from root. The selection formula with UCT is used for tree expansion, Q from root used for actual gameplay $\endgroup$ – mirror2image Dec 3 '19 at 6:35
  • $\begingroup$ @mirror2image Do you mean the other approaches do worse? Do you have a reference for that? $\endgroup$ – user76284 Dec 3 '19 at 6:51
2
$\begingroup$

By far the most commonly used strategy is to select the child with the highest number of visits. This is as described in the 2008 paper you linked. It's also what's referred to as the "robust child" in the 2012 paper you linked.

In algorithm 2 of the 2012 paper, they actually use the highest average reward, which corresponds to "Max child". It looks like they're using the UCB1 policy, but they actually use a value of $0$ for the exploration parameter $c$, which makes the entire square root term drop out. This is also explained in the text at the end of your quote. But usually, a robust child / max visit count performs better.

Progressive Strategies for Monte-Carlo Tree Search is a different paper from 2008, in which these strategies are experimented with a bit. Usually, they perform similarly, but a robust child tends to be the best if there is any difference at all.

$\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.