UCT Algorithm

“Upper Confidence Bound applied to Trees”: improve selection / expansion process by guiding the search more effectively.

When selecting nodes, we consider:

• total number of simulations ran at a given node
• total number of winning simulations
• number of simulations ran by parent node

The UCT Algorithm uses:

$$\frac{w_i}{s_i}+c\cdot \sqrt{\frac{\ln s_p}{s_i}}$$

• where $w_i$ is the number of simulations won from this node
• where $s_i$ is the total number of simulations ran from this node
• where $s_p$ is the total number of simulations ran from parent node
• where $c$ is the exploration parameter

The $\frac{w_i}{s_i}$ is the exploitation term, i.e. the average win rate. The $\sqrt{\frac{\ln s_p}{s_i}}$ is the exploration term, the less frequently a node has been selected for expansion / simulation, the larger the value. The $c$, exploration parameter, is used to control the exploration / exploitation trade-off. Typically $c=\sqrt{2}$.

After running backpropagation, we run the UCT Algorithm on all of the states.