1
$\begingroup$

I've developed a Monte Carlo tree search algorithm in checkers.

Here is my question. What should be the value of $C$, the exploration parameter in the following formula described in Monte Carlo Tree Search (MCTS)?

$$ S_i=x_i+C\sqrt{\frac{\ln (t)}{n_i}}$$

General consensus is that a value of $\sqrt 2$ should be used, but when I use a value of 10 it works, which save me a lot of time.

So, how can I find the best value for $C$, that best suits my problem?

$\endgroup$
  • 1
    $\begingroup$ Please make your question self-contained. People shouldn't have to follow a link to find out what you're even asking, and if that link dies (and it will, eventually), your question will make no sense at all. $\endgroup$ – David Richerby Apr 5 at 23:24
  • 2
    $\begingroup$ Try several different values, and see which one works best. $\endgroup$ – Yuval Filmus Apr 6 at 7:44
1
$\begingroup$

You can go with whatever the literature recommends is a reasonable value without knowing any specifics of your problem. Otherwise, it is perfectly possible (and even to be expected) that a good value of $C$ will depend not only on your problem, but on the details of your instances.

In general with all (meta)heuristics, a good choice of parameters comes down to experimentation.

$\endgroup$
1
$\begingroup$

The value of $C = \sqrt 2$ was shown to ensure the asymptotic optimality when rewards are in the $[0,1]$ range (Kocsis, Szepesvári, 2006).

In many games, that reward range is straightforward: maximum and minimum possible scores can be translated to 0 and 1 (0 could mean a loss and 1 a win).

The accuracy of this squashing seems to have a minimal impact (e.g. Using Domain Knowledge to Improve Monte-Carlo Tree Search Performance in Parameterized Poker Squares - Robert Arrington, Clay Langley, and Steven Bogaerts - 2016).

Unfortunately squashing isn't always possible.

With rewards outside the $[0, 1]$ range and/or for fine-tuning the Cross Entropy Method works quite well.

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