4
$\begingroup$

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!

$\endgroup$
  • 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. Mar 20 '16 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$ – APCoding Mar 20 '16 at 18:35
5
$\begingroup$

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:

I made some images. Is it like this or like this?

It's more like the latter.

$\endgroup$
0
$\begingroup$

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

$\endgroup$
  • $\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$ – David Richerby Dec 22 '17 at 18:11

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.