MCTS & neural policies

Monty§

Monty is a chess engine using the Predictor + Upper Confidence bounds applied to Trees (PUCT) search algorithm. It uses neural networks to evaluate positions and to predict the likelihood of each move being the bestThis is a simplification. In fact, the network is trained to perform distribution-matching against an amplified version of itself. See Iterated Distillation and Amplification for a video treatment of the concept., which together guide the tree search. It is written in Rust, and wasDevelopment is on hiatus at time of writing. developed publicly on the montychess testing instance. Monty is particularly interesting because it runs on the CPU – most MCTS chess engines use very large & very deep neural networks, which require a GPU to run at reasonable speeds. As such, the design constraints involved in Monty are quite different to those of other MCTS engines.

Policy networks§

As the policy network's task is to predict the behaviour of a tree search, the limiting behaviour of the network is incentivised to implicitly search ahead in the game tree. There is some research indicating that sufficiently powerful chess networks do in fact learn to “imagine” future moves, using simulated futures to guide their decisions over a single forward pass. Monty’s networks are much smaller than those studied in such research, and are not likely to be well-described as performing lookahead.

That small policy networks cannot implement search (or other forms of active optimisation) is a problematic limitation when compared to equivalent mechanisms in state-of-the-art chess engines.

What do typical alpha-beta chess engines do?§

Most chess engines use a combination of several different heuristic techniques to order the moves that they consider. These heuristics include local features of the moves in position to be searched, like the value of captured pieces, the outcome of exchanges on the target square, threats from less-valued pieces, and piece-square lookup tables. They also use dynamic heuristics, with statistics accumulated from the search tree that are updates with each new position searched. The main heuristic of this sort is the history heuristic (and variants thereof are very successful).

In abstract, the history heuristic involves the continual updating of a table of counters, or “scores”, representing the relative quality of moves. Each time a move proves comparatively high-quality against expectation, its history score is increased, and vice-versa for unexpectedly poor moves. By this mechanism, chess engines can “learn as they think” which moves are better or worse, and therefore more deserving of future search effort.

How do policy networks compare to the history heuristic?§

An issue that policy networks suffer is that the information they bring to bear on any given position is purely local. They only consider the features of the position itself when deciding how to score moves, and only have their internal parameters available to them when making that decision. This pales in comparison to what alpha-beta engines have access to – a record of the success and failure of every move considered so far over potentially billions of positions. As such, the idea of somehow collecting statistics from the MCTS tree and using them to guide the search is a very attractive one. How might this be done?

Existing approaches to tree statistic collection and use§

There have been several attempts at mechanisms similar to history in MCTS programs, notably RAVE and a history-like heuristic in the Vine chess engine.

Rapid Action Value Estimation§

The RAVE heuristic was developed for UCT programs prior to the invention of neural policies, and involves a history-like procedure.

The UCT algorithm must sample every action from a state $s \in T$ before it has a basis on which to compare values. Furthermore, to produce a low-variance estimate of the value, each action in state $s$ must be sampled multiple times. When the action space is large, this can cause slow learning. To solve this problem, we introduce a new algorithm $UCT_{RAVE}$ , which forms a rapid action value estimate for action $a$ in state $s$, and combines this online knowledge into UCT.

Normally, Monte-Carlo methods estimate the value by averaging the return of all episodes in which $a$ is selected immediately. Instead, we average the returns of all episodes in which $a$ is selected at any subsequent time.

Sylvain Gelly, David Silver, Combining Online and Offline Knowledge in UCT, 2007-07-19

Here, returns are attributed to actions, and tree branches (action prefixes) maintain statistics aggregating the downstream returns of actions. This is a little difficult to wrap one’s head around, and it’s not totally clear to me whether the RAVE values are intended to include the actions selected by the simulation policy, or only the actions selected by the tree policy. Applying this to games that do not involve “board filling” seems difficult.

A genuine history heuristic§

Another CPU-MCTS engine, Vine successfully integrated a history aggregation function similar to those in AB-NNUE engines in this PRTest result viewable at https://furybench.com/test/3244/., gaining a not-insignificant amount of strength.

Elo   | 10.42 +- 5.75 (95%)
SPRT  | 10.0+0.10s Threads=1 Hash=16MB
LLR   | 3.03 (-2.25, 2.89) [0.00, 5.00]
Games | N: 4738 W: 1149 L: 1007 D: 2582
Penta | [43, 530, 1110, 614, 72]

The approach is very similar to RAVE, but does not use subtree-prefixing – scores are aggregated in a global 2 × 64 × 64 table during the backpropagation step, and history values are directly folded in to the neural policy logits, which achieves a similar effect to RAVE’s explicit downweighting of heuristic action values as nodes get more visits.

Future directions§

I think it would be very interesting to train future PUCT networks with access to tree statistics collected from training games. Such heuristics should endeavour to be consistent at any search budget – statistics from an 800-playout search should be “indistinguishable” from those produced by an 8 000 000-playout search.