When reading up on the UCT1 algorithm (I'm writing a Monte Carlo tree search), I'm having trouble with the formula. $$\frac{w_i}{n_i} + \sqrt{\frac{\ln t}{n_i}}$$ Wikipedia, this guy, and this guy all say that $t$, or whatever else they use for that variable, equals the "total number of simulations". What does this mean, exactly? The total number of simulations in the entire tree? The child nodes of that particular node? The "sibling" nodes? So, what is the $t$ is this equation? Thanks!
$\begingroup$
$\endgroup$
2
-
2$\begingroup$ Have you tried reading the original paper (by Kocsis and Szepesvári) that introduced the algorithm, to see what it says? $\endgroup$– D.W. ♦Commented Mar 20, 2016 at 17:19
-
$\begingroup$ @D.W. Is the answer on page 4 of that paper? If it is, I don't understand it :P They describe $t$ as time; does that mean all the nodes that are needed to get to the node in question? $\endgroup$– APCodingCommented Mar 20, 2016 at 18:35
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
0
The UCT1 algorithm is actually an algorithm for a multi-armed bandit. There is a machine with several arms. At each round you pull one of the arms and get some reward. Your goal is to maximize your total reward. In this algorithm, $t$ is the round number: $t = 1$ in the first round, $t = 2$ in the second round, and so on.
When using UCT1 to perform Monte Carlo tree search, you treat each explored node as a multi-armed bandit. Monte Carlo tree search consists of several rounds of simulations: in each round a complete game is played out. The value of $t$ for a particular node is the number of rounds at which you passed through the node.
$n_i$ is the number of simulations through the $i$th child, i.e. how many simulations encountered that state in their simulations. A simulation consists of an entire game played out. Once it exits the node it invariably goes through one of its children. So $t$ is the sum of the $n_i$.
You ask:
It's more like the latter.
Gilles 'SO- stop being evil'
43.9k8 gold badges118 silver badges184 bronze badges
answered Mar 20, 2016 at 20:49
$\begingroup$
$\endgroup$
1
$t$ = total number of visits for the node in question.
$n_i$ = total number of visits for its child.
$w_i$ = value of its child
You need to normalize each output over the total value and then select the maximum for best move.
-
$\begingroup$ This seems to contradict the comments below the accepted answer, so a citation to back up your claims would be a big help. (Or have I misunderstood something?) $\endgroup$ Commented Dec 22, 2017 at 18:11