This blog introduces MCTS (Monte Carlo Tree Search) basic concepts, and then discuss AlphaGo Zero which combines both MCTS and reinforcement learning.
More ideas (especially about LLM & LLM agent, in another blog “From AlphaGo Zero to LLM Agent Planning” ) inspired by this still work in process…… I’ll finish this part in July.
Before MCTS, we always utilize [minmax algorithm], with heuristic [value function] to restrict the search depth, and [alpha-beta pruning] to avoid the unnecessary search of some branches. But raising up a useful heuristic value function is difficult, requiring a lot of prior human knowledge or the training of a deep network.
In fact, we do not need search all branches, of which only a few leads to potential optimal solutions and many are useless. This motivates an important algorithm called [selective search]. And we do not like heuristically-proposed value functions. Instead, in mathematics, frequency can measure probability. Here, if we do multiple simulations or [roll-outs], than combine the results, we can get the value function of some node.
Above is the main idea of MCTS. Following will be the detailed implementation.
For one state, if its all states have been searched, which one should we select to search again?
Here we use [UCT] to calculate for each child-state.
$$ \textbf{UCT} = \frac{child.value }{ child.visits} + C * \sqrt{\frac{log(state.visits)}{ child.visits}} $$
Exploitation: The first item measures the average value of each child state. A child state that holds higher avg. value indicates to be more potentially valuable to search.
Exploration: The second item measures how frequent this child-state has been explored. A child state which is explored less frequently, should be searched in the future to avoid missing some good less-explored child-state.
This equation, corresponds to our direct feelings, and is guaranteed by [UCB1 formula (Auer et al 2002)] theory.
In my implementation, we trivially choose random strategy to do simulations for calculation efficiency. But in my implementation and experiment, the value after several roll-outs, always negative. Though it may not influence the final result of policy, which depends on comparison, it still shows the short coming of trivially random strategy.