Shallow trees with heavy leaves (2020)
5 days ago
- #cellular-automata
- #SAT-solving
- #chess-engines
- Stockfish and Leela Chess Zero are two state-of-the-art chess engines with different approaches.
- Stockfish evaluates many positions per second using heuristics and alpha-beta pruning.
- Leela Chess Zero evaluates fewer positions using a deep neural network and Monte Carlo tree search.
- The neural network in Leela Chess Zero uses SE-ResNet architecture with separate 'value' and 'policy' heads.
- Similar strategies are used in cellular automata search programs like ntzfind and ikpx2.
- ntzfind uses a depth-first tree search with a large lookup table.
- ikpx2 uses a SAT solver for deep lookahead, similar to Leela Chess Zero's approach.
- ikpx2 employs reinforcement learning to choose between SAT solvers like kissat and CaDiCaL.
- The 'shallow tree with heavy leaves' approach allows for easy parallelism and memory efficiency.
- Extended partials are simulated in the cellular automaton, sometimes leading to new discoveries.
- ikpx2 has found novel spaceships and puffers, though no new velocities in standard Life rules.
- The program can search a wide family of related cellular automata by encoding rule mechanics into SAT problems.
- ikpx2 is open-source and x86_64-specific, with dependencies like apgsearch for simulation.