2
$\begingroup$

I am trying to understand the similarities and differences between: (i) the UCT algorithm in Kocsis and Szepesvári (2006); (ii) the UCT algorithm in Section 3.3 of Browne et al (2012); (iii) the MCTS algorithm in Silver et al. (2016); (iv) the MCTS algorithm in Silver et al. (2017).

I would be really grateful for some help identifying the similarities and differences in these papers, I am doing some research and really struggling right now.

(i) http://ggp.stanford.edu/readings/uct.pdf

(ii) http://mcts.ai/pubs/mcts-survey-master.pdf (Section 3.3)

(iii) https://storage.googleapis.com/deepmind-media/alphago/AlphaGoNaturePaper.pdf

(iv) https://deepmind.com/documents/119/agz_unformatted_nature.pdf

$\endgroup$
1
$\begingroup$

The algorithm in the 2012 survey article (your second link) is the most common / standard implementation. Whenever someone mentions using MCTS or UCT, without explicitly stating any other info, it's safe to assume that that pseudocode is what they're using.

The paper by Kocsis and Szepesvári from 2006 (your first link) is (one of) the original publication(s) on UCT. It is very similar to the "standard" implementation as described in the survey paper. If I recall correctly, the only important difference is that the algorithm as described in 2006 keeps track of at which point in time during an episode a reward is observed, and accounts for that timing in the backpropagation phase (i.e. if a reward is observed at time $t$ in an episode, credit for that reward is not assigned to states/action after time $t$). It also used a discounting factor $\gamma$ to discount the importance of reward depending on temporal distance, which is uncommon otherwise in MCTS literature.

Both of those differences are due to the original, 2006 paper having more of a "Markov decision process" or "Reinforcement Learning" flavour, whereas otherwise MCTS has especially become popular in AI for (board) games where we often by default assume that there is only a single nonzero reward (win or lose) at the end of every episode anyway, which makes those differences less meaningful.


Both of the AlphaGo papers (AlphaGo and AlphaGo Zero) use a "foundation" of MCTS that is mostly similar to the one from the 2012 survey article. The core components are all the same. Both of those systems add on a lot of (very important, and some quite complex) bells and whistles though.

Going off the top of my head (should be mostly accurate, but best details are in the original source of course!) AlphaGo (your third link) added Neural Networks trained in various ways to output policies (mapping from states to probability distributions over actions) and value functions (mapping from states to "value estimates", or estimates of win percentage). Trained policy networks were used in a variant of the "selection" phase (no longer UCB1 strategy as in UCT) to bias selection. A different (simpler function, not a deep net) policy was used to run play-outs (no long uniform at random action selection as in UCT). A combination of observed reward at end of play-out + value function estimate at start of play-out was used for backpropagation (no longer only backpropagating reward observed in play-out as in UCT).

AlphaGo Zero is, if we're purely looking at the MCTS part, quite similar to AlphaGo. The Neural Networks were a bit different (a single one, with multiple outputs for policy + value), and play-outs were no longer used at all (just immediate backpropagation of value function estimates after MCTS' selection + expansion phases). Apart from that, the primary differences going from AlphaGo to AlphaGo Zero were in the learning process used to train the Neural Networks really, not so much in the MCTS side of things.

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