Shallow trees with heavy leaves (2020)

Summary

There are two very different state-of-the-art chess engines: Stockfish and Leela Chess Zero. Stockfish searches many more positions (100 000 000 per second) and evaluates them using computationally cheap heuristics. The tree search methodology is a refinement of alpha-beta pruning. Leela Chess Zero, a descendant of DeepMind’s AlphaZero, searches much fewer positions (40 000 per second), using a deep convolutional neural network (trained through millions of games of self-play) to evaluate positions. It has a different search methodology, namely Monte Carlo tree search. The neural network employed by Leela Chess Zero is itself fascinating, using an architecture similar to the SE-ResNet image classification model. This residual tower of squeeze-and-excitation layers feeds into separate ‘value’ and ‘policy’ heads, for evaluating the position and deciding what to do next, respectively. However, I want to talk more about the general strategy of searching much fewer positions and expending more effort on each position. In particular, this major difference between Stockfish and Leela Chess Zero is reflected in two of the many search programs used to find spaceships in Conway’s Game of Life and related cellular automata: The program ntzfind, originally written by a pseudonymous author ‘zdr’ and enhanced by Matthias Merzenich, Aidan Pierce, and Tom Rokicki, is a depth-first tree search which uses a huge in-memory lookup table to find all possible choices for the next row based on previous rows. The new program ikpx2, adapted from the program I wrote to find the first elementary knightship, is more analogous to Leela Chess Zero in that its search tree is much smaller, but the amount of work done at each node is much greater. In particular, ikpx2 uses a SAT solver to perform a deep lookahead to determine whether the current partial spaceship can be fully extended for several* more rows, and is therefore not close to a ‘dead end’. By comparison, ntzfind can only rule out a parti...