Giraffe: Using Deep Reinforcement Learning to Play Chess

1 Introduction

• Chess was once considered beyond computers because it demands creativity and sophisticated reasoning, and was grouped with poetry and painting as a task only humans could perform; computers have since achieved more success at chess.Source: §1.1 · p. 8
• Humans select game-tree branches more efficiently, while computers rely on brute-force search, motivating the project’s questions about computational efficiency and playing strength.The comparison cites Kasparov searching 3–5 positions per second and Deep Blue searching about 200 million [2].Source: §1.1 · p. 8
• Reliable rules for deciding which branches to explore or prune have been difficult to formulate because human selection relies on complex rules with many exceptions.People learn these rules by playing and observing thousands of games.Source: §1.1 · p. 8
• Giraffe uses self-play and machine learning rather than hard-coded rules to derive its chess-playing knowledge.Neural networks assist with static position evaluation and deciding which branches to search or discard.Source: §1.1 · p. 8

2 Background and Related Work

• The chess problem is to choose a legal move that maximizes the chance of winning while modeling how the opponent chooses moves.At high levels, engines commonly assume an equally skilled opponent who does not make mistakes; the paper describes this strategy as leading to Nash equilibrium.Source: §2 · p. 9
• An alternative formulation assigns a position a score that increases monotonically with the side-to-move’s chance of winning; the exact score-to-probability relationship need not be known.Scores are often centered at 0 with odd symmetry, and choosing the move with the lowest opponent score solves the move-selection formulation.Source: §2 · p. 9

2.1.1 Minimax

• A chess game tree is too large to search exhaustively, so engines use fixed-depth minimax and evaluate positions statically at the search boundary.The average branching factor is about 35 and average game length about 80 plies; the estimated tree size is about 10^123.Source: §2.1.1 · pp. 9–10
• A depth cutoff creates the horizon effect: a position can appear favorable at the boundary despite an immediate tactical reply beyond it.Quiescent search extends selected moves until reaching a relatively stable position, but including too many moves enlarges the search while too few can leave reduced horizon effects.Source: §2.1.1 · p. 11

2.1.2 α-β Pruning

• Move ordering matters because α-β can stop searching branches once their scores fall outside the current bounds; searching strong moves first can reduce node visits.Conventional heuristics reuse good moves from previous or sibling searches.Source: §2.1.2 · pp. 11–12
• In the best move-ordering case, α-β pruning reduces the effective branching factor to the square root of the original, allowing search about twice as far in the same time.In the worst case, α-β degenerates into minimax; the project investigates machine learning to assist move ordering.Source: §2.1.2 · p. 12

2.1.3 Evaluation

• Evaluation functions statically score positions and contain much of an engine’s domain-specific knowledge; improvements in top engines largely come from improving them.Stockfish’s function includes material, piece-square tables, pawn structure, piece-specific evaluation, mobility, king safety, threats, space, and draw likelihood; the many parameters are difficult to tune by hand.Source: §2.1.3 · pp. 12–13
• Stockfish’s evaluation combines local pawn features and piece-specific positional terms with mobility bonuses that depend on piece type and exclude squares controlled by lower-valued opposing pieces.Its material term accounts for synergies, such as a bonus for having both bishops.Source: §2.1.3 · p. 13

2.2.1 Mate Solvers

• Endgame-learning approaches using genetic programming and inductive learning target positions with few pieces, but do not scale to the more complicated midgames and openings described here.Endgames are usually defined as positions with fewer than about six pieces, where simpler optimal-play rules can often be derived.Source: §2.2.1 · p. 13

2.2.2 Learning Based on Hand-Selected Features

• Learning systems that tune parameters or score hand-picked features remain limited by the features designers choose.Examples include NeuroChess, Falcon, and Meep, which uses reinforcement learning to train weights for hand-designed features.Source: §2.2.2 · p. 14

2.2.3 Temporal-Difference Learning

• Game outcomes are a direct but computationally costly training signal, since small changes may require many games for statistical significance and each game yields less than 2 bits of information.Temporal-difference learning instead trains predictions of a system’s near-future evaluation, promoting temporal consistency.Source: §2.2.3 · p. 14
• Temporal-difference learning can assign different error signals to moves within one game, giving a blunder a high signal without similarly penalizing earlier good moves.This improves the signal-to-noise ratio compared with training from the game’s final result.Source: §2.2.3 · p. 14
• TD-Gammon reached master-level backgammon performance after 1.5 million self-play games, while using neural networks and no search.The system began from random initialization and selected moves by evaluating resulting positions.Source: §2.2.3 · p. 14
• TDLeaf(λ) combined temporal-difference learning with minimax search; KnightCap reached FIDE International Master strength after about 1,000 games [21].Its 5,872 hand-designed features made evaluation slow, and it was weaker than top engines in tournament conditions; the authors proposed selective search as a possible route to greater improvement [21].Source: §2.2.3 · p. 15

• Automatic hierarchical feature extraction requires a powerful, highly nonlinear function approximator to model chess evaluation beyond hand-designed features.Source: §2.3 · p. 15
• A hierarchical image classifier builds from gradients, corners, and edges to shapes, then uses shape locations to classify objects.Source: §2.3 · p. 15
• Deep learning algorithms for hierarchical knowledge extraction were popularized by Hinton et al. in 2007.Source: §2.3 · p. 15
• ImageNet top-5 error was 15.3% versus the previous best of 26.2%, while handwriting-recognition error was 0.3%.Source: §2.3 · pp. 15–16
• Deep networks surpassed previous game-specific AI on six of seven arcade games and exceeded human expert performance on three.Source: §2.3 · p. 16
• Deep networks evaluate chess positions, decide which branches to search, and order moves.Source: §2.3 · p. 16

• The project combines established algorithms such as TDLeaf(λ) [21] with newly developed algorithms to build a machine-learning-based chess engine.Source: §2.4 · p. 16
• The project adapts the TDLeaf(λ) evaluation-learning experiment [21] with newer neural-network advances and greater computational power to pursue automatic high-level feature extraction.Source: §2.4 · p. 16
• A novel probability-based framework uses neural networks to guide time spent on each subtree, challenging distance-from-root as the primary search criterion.Source: §2.4 · p. 16

• With material, piece-square tables, mobility, and some king safety, the basic linear evaluator plays slightly below FIDE Candidate Master strength.Source: §3 · p. 16
• Aggressive heuristic pruning was omitted from the otherwise fairly standard search routine so learned systems could make the heuristic decisions.Source: §3 · p. 16
• The custom neural-network implementation supports restricted connectivity, which the authors say existing frameworks would require extensive modification to accommodate.Source: §3 · p. 17
• Experiments found AdaDelta produced the fastest convergence and highest-quality minimums among the tested optimization algorithms.AdaGrad and AdaDelta maintain individual learning rates per parameter, useful for chess patterns that are rarely present.Source: §3 · p. 17
• The engine modifications replace parts of the system with learned systems.Source: §3 · p. 17

4.1 Feature Representation

• The 363-feature representation uses low-level, smooth board encodings; piece lists are the most important features and alone support reasonable play.Source: §4.1 · pp. 17, 19

4.2 Network Architecture

• The evaluator separates piece-, square-, and position-centric features in early layers, then connects them fully in later layers; hidden nodes use ReLU and the output uses tanh.Source: §4.2 · p. 21

4.3 Training Set Generation

• Training starts from 5 million computer-game positions, adds a random legal move to each, and uses self-play to generate about 175 million unlabeled positions.Source: §4.3 · p. 22

4.4 Network Initialization

• A basic material-only evaluator bootstraps the network in seconds, bringing it closer to a good minimum than random initialization would.Source: §4.4 · p. 22

4.5 TD-Leaf

• TD-Leaf(λ) learns temporal consistency from minimax leaf gradients; 12-move self-play yields discounted errors, optimized with L1 loss and AdaDelta.Source: §4.5 · pp. 23–24

4.6 Results and Evaluation

• After training, STS scores rose from approximately 6000/15000 to approximately 9500/15000, peaking above 9700/15000; Giraffe's positional understanding was at least comparable to top engines.Source: §4.6 · pp. 24–25, Figure 4 · p. 25

5 Probabilistic Search

• Probabilistic search provides a foundation for the later learned systems for move ordering and time allocation, and is described as a generalization of certain depth-search extensions.The authors report that it provides a small playing-strength benefit by itself; they identify it as Giraffe’s first implementation of probability-limited search.Source: §5 · p. 26, §5.4 · p. 29

5.1 The Search Problem Redefined

• The search objective is to find as much of the theoretical principal variation as practical, because searching the complete tree is generally impractical.The paper assumes one theoretical principal variation per position, noting that determining how many exist would require searching the entire space.Source: §5.1 · p. 26

5.2 Conventional Depth-Limited Search

• Unlike depth-limited search, which remains the foundation of chess-engine search despite extensions and reductions, probability-limited search uses a different boundary for selecting tree nodes.Conventional minimax evaluates positions at the search boundary and recursively considers possible moves.Source: §5.2 · pp. 26–27, §5.3 · p. 27

5.3 Probability-Limited Search

• Probability-limited search stops expanding nodes below a probability threshold for belonging to the theoretical principal variation, rather than stopping at a fixed depth.Child probabilities are distributed from the parent estimate; the initial assumption gives siblings equal probability when move information is unavailable.Source: §5.3 · p. 27

5.4 Depth-Limited Search vs Probability-Limited Search

• When branches have different branching factors, depth-limited search can spend much of its effort on high-branching branches, while probability-limited search can search deeper on a lower-branching branch.In the illustrated queen-exchange case, probability-limited search reaches deeper on the queenless branch; the figure examples depict nodes searched by the two approaches.Source: §5.4 · pp. 28–29, Figure 5 · p. 28, Figure 6 · p. 29
• A naive probability-limited search was 26±12 rating points stronger than a naive depth-limited search, corresponding to a 53%-47% score split.No comparison of advanced implementations was conducted because of time constraints.Source: §5.4 · p. 29

6 Neural Network-Based Probability Estimation

• The network estimates P(childi|parent) from a parent position and candidate move, then normalizes move estimates into a distribution and multiplies by the parent's probability.The resulting child probabilities guide the probability-based search.Source: §6 · pp. 29–30

6.1 Feature Representation

• Move features combine the evaluation network's parent-position representation with piece type, origin and destination squares, promotion type, and move rank.Move rank matters because a move's chance of being best depends on the other legal moves in that position.Source: §6.1 · p. 30

6.2 Network Architecture

• The probability network uses logistic output activation for values between 0 and 1, with rectified-linear hidden nodes and separately connected modality layers.The logistic output simplifies gradient calculations with cross-entropy loss.Source: §6.2 · p. 31

6.3 Training Positions Generation

• Training positions were sampled from internal nodes reached in time-limited searches, producing a corpus of 5 million positions.The internal-node distribution differs from the root-position distribution used to train the evaluation network.Source: §6.3 · p. 31

6.4 Network Training

• The existing evaluator and uniform-probability search label each position's best move, after which all legal moves receive binary targets for stochastic gradient descent.Training uses AdaDelta updates and cross-entropy loss.Source: §6.4 · p. 31

6.5 Results and Evaluation

• 46% of the time the actual best move was predicted first, and 70% of the time it was among the top three predicted moves.Table 4 reports move prediction results for all move types.Source: §6.5 · p. 31, Table 4 · p. 32
• For quiet positions excluding winning captures, the correct best move was predicted 28% of the time and ranked in the top three 55% of the time.Table 5 reports results for these filtered positions.Source: §6.5 · p. 32, Table 5 · p. 32
• 48 ± 12 Elo points after 3,000 games measured the strength difference with the neural probability estimator when its search-speed penalty was excluded.When used only on nodes with more than about 100 nodes to search below them, the improvement was approximately 20 ± 12 Elo points.Source: §6.5 · p. 32

7 Conclusion

• The report concludes that the learned system performs comparably to the best expert-designed counterparts, and that probability-bounded minimax is at least comparable and possibly superior to depth-bounded search.It also reports that probability-bounded search works especially well with the learned probability approach.Source: §7 · pp. 32–33
• Giraffe reaches FIDE International Master level on a mainstream PC, while remaining below super-Grandmaster engines and searching at less than one order of magnitude slower than the best modern engines.The report says its strength comes from accurate evaluation of difficult positions rather than searching farther ahead.Source: §7 · p. 33

7.1.1 Neural Network-Based Time Management

• Neural-network time management is proposed as an alternative to the simple time-allocation heuristics used by Giraffe and other engines.The proposal concerns choosing time per move based on considerations such as position complexity and confidence in the move.Source: §7.1.1 · pp. 33–34

7.1.2 More Fine-Grained Caching, and Model Compression

• Search speed remains a major weakness; proposed improvements include caching intermediate network activations and compressing large networks into smaller ones.The existing cache has a low hit rate because identical positions are rarely evaluated twice.Source: §7.1.2 · p. 34

7.1.3 Evaluation Error Estimation

• A proposed two-output network would estimate score bounds, using asymmetric error functions to train lower- and upper-bound predictions.If the possible score range lies entirely outside the alpha-beta window, a full evaluation is unnecessary.Source: §7.1.3 · p. 34

7.1.4 Similarity Pruning

• The report proposes learning signatures for positions and clustering them to estimate similarity, but says it is unclear how to train such networks.The motivation is to identify effectively equivalent moves and reduce the average branching factor.Source: §7.1.4 · p. 34

Appendix A The Elo Rating System

• Elo ratings are comparable only within the same player pool, and a 200-point difference corresponds to an expected score split of about 75% to 25%.The stronger player is expected to receive 75% of the points.Source: Appendix A · p. 36
• Unless otherwise specified, ratings in the paper use the FIDE scale.Source: Appendix A · p. 36
• On the FIDE scale, the appendix places a rules-knowing beginner near 1000 and a serious low-level tournament player near 1800; it lists International Master at 2400.It notes that human and computer rating pools lack enough games to establish an accurate relationship.Source: Appendix A · p. 36