Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
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?
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.
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.
