Source-linked AI summary
Mastering Chess and Shogi by Self-Play with a General Reinforcement Learning Algorithm
David Silver, Thomas Hubert, Julian Schrittwieser, Ioannis Antonoglou, Matthew Lai, Arthur Guez, Marc Lanctot, Laurent Sifre, Dharshan Kumaran, Thore Graepel, Timothy Lillicrap, Karen Simonyan, Demis Hassabis
TL;DR
Traditional computer-chess programs rely on handcrafted features and domain-specialized techniques, motivating a more general approach. AlphaZero instead combines deep neural-network evaluation with domain-independent Monte Carlo tree search and pure self-play reinforcement learning, and the supplied passages document its evaluation against Stockfish in a 100-game match.
Problem
Computer-chess programs rely on handcrafted evaluation features and domain-specialized search, leaving motivation for a more general approach.
Method
AlphaZero uses deep neural-network evaluation with Monte Carlo tree search in a pure self-play reinforcement-learning approach, using no domain knowledge beyond the listed design choices.
Results
AlphaZero was evaluated against Stockfish in a 100-game match using one minute per move.
Takeaways & Limitations
The evaluation examines AlphaZero’s performance against a strong established chess program under a fixed time control.
Takeaways & Limitations
The study focuses on pure self-play reinforcement learning and leaves possible extensions using domain-specific techniques for future research.
Abstract
from arXiv · showhide
The game of chess is the most widely-studied domain in the history of artificial intelligence. The strongest programs are based on a combination of sophisticated search techniques, domain-specific adaptations, and handcrafted evaluation functions that have been refined by human experts over several decades. In contrast, the AlphaGo Zero program recently achieved superhuman performance in the game of Go, by tabula rasa reinforcement learning from games of self-play. In this paper, we generalise this approach into a single AlphaZero algorithm that can achieve, tabula rasa, superhuman performance in many challenging domains. Starting from random play, and given no domain knowledge except the game rules, AlphaZero achieved within 24 hours a superhuman level of play in the games of chess and shogi (Japanese chess) as well as Go, and convincingly defeated a world-champion program in each case.
Methods · Anatomy of a Computer Chess Program
A typical computer chess program combines handcrafted linear evaluation with heavily engineered minimax search, move ordering, pruning, transposition reuse, and table-based knowledge. AlphaZero uses none of these techniques, instead pursuing pure self-play reinforcement learning and leaving possible extensions for future work.
- Anatomy of a Computer Chess Program: Other strong chess programs, including Deep Blue, use similar architectures, although important implementation details vary considerably.Stockfish is presented as a typical example of this architecture and won the 2016 TCEC computer chess championship.
- Anatomy of a Computer Chess Program: Stockfish evaluates positions with sparse handcrafted features, manually and automatically tuned weights, and a linear value function v(s, w) = φ(s)⊤w.Features include material, mobility, pawn structure, king safety, outposts, and other evaluation patterns.
- Anatomy of a Computer Chess Program: Minimax search evaluates leaves with quiescence search and uses alpha-beta pruning, aspiration windows, principal variation search, and null move pruning.Null move pruning assumes a pass move is worse than any variation in positions unlikely to be zugzwang.
- Anatomy of a Computer Chess Program: Search depth is extended for promising variations and reduced for unpromising ones using history, static-exchange evaluation, moving-piece, singular-move, check-move, and late-move heuristics.The extensions combine domain-independent rules with domain-dependent rules such as extending check moves.
- Anatomy of a Computer Chess Program: Move ordering uses iterative deepening together with killer, history, counter-move, capture, static-exchange, and MVV/LVA heuristics to improve alpha-beta efficiency.Iterative deepening uses a shallower search to order moves for a deeper search.
- Anatomy of a Computer Chess Program: Transposition tables reuse values and move orders, while opening books and endgame tablebases provide specialized move selection and optimal play in positions with six and sometimes seven pieces or less.The tablebases are precalculated by exhaustive retrograde analysis.
- Anatomy of a Computer Chess Program: None of these conventional techniques are used by AlphaZero, which focuses on a pure self-play reinforcement learning approach and leaves possible performance-improving extensions for future research.The paper suggests some conventional techniques could further improve AlphaZero but does not incorporate them here.
Prior Work on Computer Chess and Shogi
Prior chess and shogi systems learned evaluation functions using handcrafted features, temporal-difference variants, self-play, expert games, or expert move selection. These learned evaluators were generally combined with alpha-beta search, while several systems reached strong human or computer benchmarks.
- Chess reinforcement learning: NeuroChess used 175 handcrafted input features and temporal-difference learning, winning 13% of games against GnuChess with fixed depth 2 search.It predicted both final game outcome and expected features after two moves.
- Shogi evaluation learning: Beal and Smith learned chess and shogi piece values from random values solely by self-play, while Kaneko and Hoki trained a shogi evaluator with a million features from expert moves.Kaneko and Hoki also used expert game logs and minimax optimization in Bonanza, which won the 2013 World Computer Shogi Championship.
- Chess reinforcement learning: KnightCap used attack-table knowledge and TD(leaf), achieving human master level after training against a strong computer opponent.TD(leaf) updated the leaf value of the principal variation in alpha-beta search; piece-value weights were hand-initialised.
- Chess reinforcement learning: Meep used handcrafted linear features and TreeStrap, defeating human international masters in 13 out of 15 games after self-play from randomly initialised weights.TreeStrap updated all nodes of an alpha-beta search.
- Chess reinforcement learning: Giraffe used mobility, attack, and defend maps in a neural network trained by self-play with TD(leaf), reaching play comparable to international masters.Its maps described the lowest valued attacker and defender of each square.
- Alternative training and search: DeepChess learned pair-wise position evaluations from filtered human expert games and reached strong grandmaster level; these programs combined learned evaluators with extended alpha-beta search.The database excluded capture moves and drawn games, and all listed programs used alpha-beta search with various extensions.
MCTS and Alpha-Beta Search
AlphaZero differs from the alpha-beta search used by leading chess programs by averaging position evaluations within a subtree rather than computing its minimax evaluation. Its neural-network approximation errors may cancel under MCTS averaging, whereas alpha-beta propagates the largest errors through explicit minimax.
- For at least four decades, the strongest computer chess programs have used alpha-beta search.
- AlphaZero averages position evaluations within a subtree instead of computing that subtree’s minimax evaluation.
- AlphaZero uses nonlinear deep-neural-network approximation, providing a more powerful representation than the linear approximation typical of chess programs but potentially introducing spurious errors.
- MCTS averages approximation errors across large subtrees, so errors tend to cancel, while alpha-beta’s explicit minimax propagates the biggest errors.
Domain Knowledge
AlphaZero used only game rules and board-structured representations as domain knowledge. The rules supported search, termination, scoring, and encoding of game-specific inputs and moves.
- Representations: Inputs and outputs were represented as planes, matching the neural-network architecture to the board’s grid structure.The structured planes described both position features and move features.
- Rule Use: Perfect game-rule knowledge guided MCTS simulations, identified terminal positions, and scored simulations reaching game termination.Rules were applied to simulate positions after move sequences and evaluate terminal outcomes.
- Rule Use: Game rules encoded input features such as castling, repetition, and no-progress, plus output features for movement, promotions, and shogi piece drops.These encodings incorporated game-specific legal-state and move information.
- Search: The typical number of legal moves was used to scale exploration noise during search.This connected branching-factor information to the exploration mechanism.
- Domain Knowledge: AlphaZero used no domain knowledge beyond the listed board representation, game rules, rule-based encodings, exploration-noise scaling, and termination procedures.This defines the complete scope of domain knowledge used by the algorithm.
Representation
AlphaZero represents board states as player-oriented stacks of historical feature planes and represents actions with game-specific policy-plane encodings. The training algorithm worked robustly across many reasonable representation choices.
- Representation choices: The training algorithm worked robustly for many reasonable representation choices.The section notes that alternative representations could have been used.
- Board-state representation: AlphaZero’s input is an N × N × (MT + L) image stack concatenating T historical board states, oriented from the current player’s perspective.Each historical state uses M planes of size N × N, with earlier-than-initial time-steps zeroed.
- Action representation: 4,672 possible chess moves are encoded by an 8 × 8 × 73 policy-plane stack representing move origins and move types.The encoding covers queen-like moves, knight moves, and pawn underpromotions.
- Action representation: 11,259 possible shogi moves are encoded by a 9 × 9 × 139 policy-plane stack covering moves, promotions, and captured-piece drops.The planes include queen and knight moves, promoting variants, and seven captured-piece drop types.
- Action representation: Go uses a flat distribution over 19 × 19 + 1 moves for stone placements and passing.Using flat move distributions for chess and shogi produced almost identical final results but slightly slower training.
Configuration
AlphaZero’s configuration used 800-simulation MCTS during training, a shared learning-rate schedule across games, and root-visit-count-based move selection. During evaluation, it selected moves greedily and ran each MCTS on a single machine with 4 TPUs.
- Training: 800 MCTS simulations were used during training, with moves selected in proportion to the root visit count.Dirichlet noise was added to root-node prior probabilities.
- Training: The learning rate was 0.2 for each game and was dropped three times to 0.02, 0.002, and 0.0002.The number of games, positions, and thinking time varied by game, largely because of different board sizes and game lengths.
- Evaluation: During evaluation, AlphaZero selected moves greedily with respect to the root visit count.Each MCTS was executed on a single machine with 4 TPUs.
Evaluation
Evaluation used Stockfish 8 for chess and Elmo with YaneuraOu for shogi as baseline programs, assessing AlphaZero through Elo ratings and head-to-head matches under fixed time controls and settings.
- Stockfish version 8 was the chess baseline, run with 64 CPU threads and a 1GB hash size.
- Elmo version WCSC27 combined with YaneuraOu 2017 Early KPPT 4.73 64AVX2 was the shogi baseline, using 64 CPU threads and a 1GB hash size.The usi option EnteringKingRule was set to NoEnteringKing.
- AlphaZero’s relative strength was evaluated with Elo ratings estimated by Bayesian logistic regression using BayesElo and c_elo = 1/400.Ratings came from 1 second per move tournaments between AlphaZero training iterations.
- Head-to-head matches allowed 1 minute per move, enabled resignation, and disabled pondering for all players.Resignation thresholds were -900 centipawns for 10 consecutive moves for Stockfish and Elmo, and 5% winrate for AlphaZero.
Example games
This section presents 10 example games from AlphaZero’s 100-game match against Stockfish, played using one minute per move.
- 10 example games were played by AlphaZero against Stockfish during a 100-game match using 1 minute per move.