PaperlayerView exact revision on arXiv

Source-linked AI summary

Learning to Play: Reinforcement Learning and Games

Aske Plaat

arXiv:2610.17391v1cs.AI

TL;DR

Poker’s hidden information and large action space challenged search-based AI. The book explains methods such as Monte Carlo Tree Search and concludes that Atari and Go results indicate stable training and generalization are possible.

  • Problem

    Poker’s hidden information and large action set challenged search-based AI and held back the development of strong Poker programs.

    Source: §2.3.6 · p. 52

  • Method

    The book introduces Monte Carlo Tree Search (MCTS), which combines adaptive exploration, sampling-based evaluation, and averaging for node-selection statistics.

    Source: Adaptive Sampling · p. 125

  • Results

    Atari and Go results, alongside further studies, indicate that stable training and generalizing reinforcement learning are possible.

    Source: Conclusion · p. 183

  • Takeaways & Limitations

    DQN demonstrated end-to-end control learning from raw pixels across challenging Atari games with minimal prior knowledge.

    Source: Summary · p. 204

Abstract

from arXiv · show

Amazing breakthroughs in reinforcement learning have taken place. Computers teach themselves to play Chess and Go and beat world champions. There is talk about expanding application areas towards general artificial intelligence (AI). The breakthroughs in Backgammon, Checkers, Chess, Atari, Go, Poker, and StarCraft have shown that we can build machines that exhibit intelligent game playing of the highest level. These successes have been widely publicized in the media, and inspire AI entrepreneurs and scientists alike. Reinforcement learning in games has become a mainstream AI research topic. It is a broad topic, and the successes build on a range of diverse techniques, from exact planning algorithms, to adaptive sampling, deep function approximation, and ingenious self-play methods. Perhaps because of the breadth of these technologies, or because of the recency of the breakthroughs, there are few books that explain these methods in depth. This book covers all methods in one comprehensive volume, explaining the latest research, bringing you as close as possible to working implementations, with many references to the original research papers. The programming examples in this book are in Python, the language in which most current reinforcement learning research is conducted. We help you to get started with machine learning frameworks such as Gym, TensorFlow, and Keras, and provide exercises to help understand how AI is learning to play.

7 Self-Play

Section 7 is organized around self-play architecture, AlphaGo, self-play enhancements, and practice, with appendices listing deep reinforcement learning environments and technical details on AlphaGo systems.

7.1 Self-Play Architecture

  • The section covers self-play architecture.This is subsection 7.1.Source: §7 · p. 6

7.2 AlphaGo

  • AlphaGo is covered in subsection 7.2.Source: §7 · p. 6

7.3 Self-Play Enhancements

  • Subsection 7.3 is devoted to self-play enhancements.Source: §7 · p. 6

7.4 Practice

B AlphaGo Technical Details

C Matches of Fan Hui, Lee Sedol, and Ke Jie

Game-playing AI progressed from search-based methods to Monte Carlo Tree Search and deep reinforcement learning, culminating in AlphaGo’s defeat of Go world champions. The account also notes reinforcement-learning breakthroughs in StarCraft and Poker.

Artificial Intelligence

  • Early game-playing programs used a search-and-evaluation architecture to find good moves, an approach dating to computer Chess and used by Deep Blue.Source: Artificial Intelligence · p. 8
  • Monte Carlo Tree Search introduced randomness and sampling that deliberately skipped moves, yet worked in Go much better than minimax, though it initially could not beat world champions.Source: Artificial Intelligence · p. 8
  • Deep reinforcement learning enabled a simple neural network to learn Atari games from video pixels, and was later combined with Monte Carlo Tree Search in AlphaGo.Source: Artificial Intelligence · pp. 8–9
  • Combining deep reinforcement learning with Monte Carlo Tree Search in AlphaGo raised play enough to defeat Go world champions; self-play reinforcement learning also advanced StarCraft and Poker.The account says the world-champion wins came a year after the combination.Source: Artificial Intelligence · p. 9

Introduction

The section traces reinforcement learning and game-playing AI from games as benchmarks and foundational concepts to planning, heuristic and Monte Carlo search, deep function approximation, and deep reinforcement learning. It surveys landmark programs, methods, challenges, and practical tools for understanding how agents learn and play.

1.1 Tuesday March 15, 2016

  • AlphaGo beat Lee Sedol 4–1 in 2016, surprising researchers who had expected grandmaster-level computer Go to be at least a decade away.The book notes that AlphaGo later defeated Ke Jie and that its play inspired human Go players.Source: §1.1 · p. 13

Problem Statement

  • The book asks how machine-learning methods enable Chess and Go programs to surpass the strongest humans, and explains heuristic planning, adaptive sampling, deep reinforcement learning, and self-play using reinforcement learning as a common framework.It describes the algorithms and architectures and provides example code.Source: Problem Statement · p. 14

1.2 Intended Audience

  • Designed for graduate-level study, the book makes research methods accessible through foundational introductions, intuitive explanations, implementation examples, exercises, and code pointers.It aims to help readers build a self-learning program even without Google-scale computing resources.Source: §1.2 · p. 15

Graduate Course

  • The material is organized as a semester course with source-code assignments, chapter summaries, review questions, and programming exercises.Starred sections are advanced and may be skipped without losing the main thread, though they cover enhancements important for high-performing implementations.Source: Graduate Course · p. 15, *Starred Sections · p. 18

Experiment and Theory

  • Reinforcement-learning progress combines theory with experimentation, but prominent advances have relied on experimental and engineering work while a comprehensive theory of deep reinforcement learning remains future work.The book therefore emphasizes experiments and intuitions more than formulas, lemmas, or proofs in later chapters.Source: Experiment and Theory · p. 17

1.3 Outline

  • The book moves from domain-specific heuristic methods toward adaptive methods that learn features and self-play methods that choose their own learning examples.It presents this progression as a move from narrow toward somewhat more general intelligence.Source: §1.3 · p. 17

The Chapters

  • The chapter sequence covers heuristic minimax planning, Monte Carlo Tree Search, deep reinforcement learning, and AlphaGo methods combining planning and training.MCTS is described as achieving major performance improvements, especially in 9 × 9 Go; deep Q-learning required enhancements for stable training.Source: The Chapters · pp. 18–19

Thinking, Fast and Slow

  • The introduction distinguishes human intelligence from AI’s study of intelligent behavior and presents AlphaGo as evidence of learning and reasoning beyond human level in combinatorial board games, without establishing similarity to human thought.It also previews historical game-playing programs and approaches to intelligence.Source: Intelligence and Games · p. 21, Thinking, Fast and Slow · p. 23

2.1.2 Artificial Intelligence

  • AI developed from early ideas about mechanical thought through the founding of modern AI research at Dartmouth in 1956, followed by cycles of optimism, AI winters, and renewed progress.The introduction also relates symbolic planning to Kahneman’s system 2 and connectionist learning to system 1 as a crude analogy between artificial and human thought.Source: §2.1.2 · pp. 24–25, Thinking, Fast and Slow · p. 24

Behavior: Turing Test

  • AI focuses pragmatically on intelligent behavior rather than defining intelligence, while the Turing test can reward human imitation instead of intelligence.The test asks whether an evaluator can distinguish a machine from a human in text conversation; Eliza showed that superficial tricks could fool people, and the test may discourage unusually capable behavior.Source: §2.1.3 · p. 26, Behavior: Turing Test · pp. 27–28

Drosophila melanogaster

Specialized and General Intelligence

  • Artificial intelligence is usually specialized rather than general, so success at a particular game does not establish general intelligence.The introduction defines AGI as a machine’s ability to perform any intellectual task a human can, and notes that people may anthropomorphize systems such as Deep Blue, Watson, and AlphaGo after narrow-domain achievements.Source: Specialized and General Intelligence · pp. 28–29, Anthropomorphization · p. 30

2.1.4 Machine Learning

  • Machine learning includes supervised, reinforcement, and unsupervised learning; reinforcement learning learns through interaction, with actions producing new states and rewards.Reinforcement-learning problems are often modeled as Markov decision processes, and most games can be modeled as reinforcement-learning problems.Source: §2.1.4 · pp. 30–31

Reinforcement Learning in Games

  • The book studies reinforcement learning in games, where symbolic methods suit some problems, connectionist methods suit others, and self-play can combine both.Planning is associated with symbolic AI and learning with connectionism; the discussion links Chess breakthroughs to symbolic AI, Atari to connectionism, and AlphaGo and other self-play programs to an integrated approach.Source: Reinforcement Learning in Games · p. 31

Number of Players

  • Games vary by player count and strategic structure: puzzles are single-player, many AI-studied games are competitive two-player contests, and multiplayer games can involve collaboration and hidden information.Zero-sum competition models strategy and conflict, while collaborative games involve win/win outcomes; examples include Chess, Poker, Bridge, and Diplomacy.Source: §2.2.1 · p. 31, Number of Players · p. 32, Zero-Sum vs. Non-Zero-Sum · p. 33

2.2.1 Characteristics of Games

State Space Complexity

  • State space complexity counts legal positions reachable from a game’s initial position; larger state spaces generally make games harder for humans and computers.Exact values are nontrivial to determine, so most games use approximations.Source: State Space Complexity · p. 34

Chess

  • Chess programs use search and heuristic evaluation, while Go resisted Chess- and Checkers-style approaches until Monte Carlo Tree Search and deep reinforcement learning enabled breakthroughs.Chess heuristics include material balance, mobility, and center control; Go’s long-term strategic effects often lie beyond a search horizon.Source: Chess · p. 35, Othello · pp. 38–39

Checkers

  • Checkers has an estimated state space of 10^18 and was solved by traversing relevant lines of play, proving perfect play by both sides yields a draw.The computation took months on a state-of-the-art research team’s computers.Source: Checkers · p. 36

Poker

  • Poker combines hidden information, betting, and bluffing, while StarCraft combines partial observability, multiplayer play, long-term strategy, and short-term tactics.Poker’s hidden hands make it closer to some real-world decision situations than Chess or Checkers.Source: Poker · pp. 39–40, StarCraft · p. 41

Alan Turing 1950

  • Early Chess programs used position evaluation and move selection; Turing’s Turbochamp became the first program to play a full Chess game, executed by hand, using search and evaluation.Shannon’s 1949 paper described restricting the possibilities considered, and Strachey’s 1951 Checkers program played a complete game at reasonable speed.Source: Claude Shannon 1949 · p. 41, Alan Turing 1950 · p. 43, Christopher Strachey 1951 · p. 43

Arthur Samuel 1959

  • Arthur Samuel’s Checkers program adapted evaluation coefficients based on search outcomes and later used supervised learning and self-play, reaching amateur level around the 1970s.It used alpha-beta pruning, heuristic evaluation, and memorized search results.Source: Arthur Samuel 1959 · p. 43

2.3.1 TD-Gammon 1992

  • In 1992, TD-Gammon reached world-class human championship level through temporal-difference learning and self-play combined with hand-crafted heuristics.The self-play version using raw board encoding alone reached intermediate level; adding a simple heuristic search brought it to world-class play.Source: §2.3.1 · p. 44

2.3.2 Chinook 1994

  • Chinook became the Man–Machine Checkers World Champion, defended its title with 31 draws in a 32-game match, and later helped prove perfect play yields a draw.Its strength combined enhanced alpha-beta search and handcrafted evaluation with endgame databases covering positions with eight or fewer pieces.Source: §2.3.2 · p. 45

2.3.3 Deep Blue 1997

  • Deep Blue became the first computer to defeat a reigning Chess world champion in a standard-time-control match, evaluating 200 million positions per second.Its parallel hardware and search-evaluation design supported the high evaluation rate.Source: §2.3.3 · p. 47

2.3.4 Logistello 1997

  • Logistello, written by Michael Buro, beat Othello world champion Takeshi Murakami 6–0 in 1997 using over a million pattern-evaluation parameters tuned by logistic linear regression.The best Othello programs are now much stronger than human players.Source: §2.3.4 · p. 48

2.3.5 AlphaGo 2016

  • AlphaGo beat every human champion it played in three matches during 2015–2017; Fan Hui described it as a strong, stable player that seemed like a wall.The Fan Hui games were part of AlphaGo’s development effort in October 2015.Source: §2.3.5 · p. 48, Fan Hui · p. 49

Lee Sedol

  • AlphaGo defeated Lee Sedol 4–1, and its unusual game-two move 37 changed the course of the game and contributed to another win.Lee won game four; his loss was the first match defeat by a computer for a Go champion of his caliber.Source: Lee Sedol · pp. 49–51

Ke Jie

  • AlphaGo Master, using the same basic architecture with supervised and reinforcement learning, won its 2017 match against Ke Jie 3–0 after a 60-game online preparation tournament.The preparation version achieved an Elo rating of 4858 against online pros and was described as three stones stronger than the Lee Sedol version.Source: Ke Jie · p. 51

2.3.6 Poker 2018

  • DeepStack and Libratus defeated some of the strongest humans in one-on-one Poker, while Pluribus beat top players in six-player Poker.Poker’s hidden cards and large action set had challenged search-based AI approaches.Source: §2.3.6 · p. 52

2.3.7 StarCraft 2018

  • In 2018, DeepMind’s AlphaStar won two-person test matches against some of the world’s strongest StarCraft players.Academic competitions and a Python interface helped establish StarCraft as an AI research test bed [727].Source: §2.3.7 · p. 52

Reinforcement Learning

  • Reinforcement learning studies agents learning through environmental interaction, with Markov decision processes providing a precise formalism for games and their solution methods.The core topics include state, action, policy, reward, value, credit assignment, and exploration versus exploitation.Source: Reinforcement Learning · p. 55, Core Problem · p. 55, Core Concepts · p. 55

3.1 Markov Decision Processes

  • An MDP models states, actions, transition probabilities, rewards, and discounting; its Markov property makes the current state sufficient for reasoning about the future.In games, states are board configurations, actions are moves, and rewards typically encode win, loss, or draw; deterministic games transition to one successor state.Source: §3.1 · pp. 56–57, Terminology · p. 57

Terminology

  • Game state spaces form graphs or trees: terminal rewards can be backed up using max/min values, while transpositions let multiple move sequences reach the same position.The Markov formulation applies to Chess and Go versions without repetition-prevention rules, which require memory.Source: Terminology · pp. 57–58

3.2 Policy Function, State-Value Function, Action-Value Function

  • A policy maps states to actions, while state-value and action-value functions estimate expected outcomes; optimal policies select actions leading to wins in two-person games.The state value depends on the policy and discounted future rewards; Qπ(s, a) evaluates taking action a before following policy π, and underlies Q-learning and DQN.Source: §3.2.1 · p. 59, §3.2.2 · p. 59, §3.2.3 · pp. 59–60

3.2.4 Implementing Functions

  • Functions can be implemented as code, lookup tables, or parameterized approximators; neural networks compress large state spaces and generalize from examples to unseen states.Exact tables suit manageable spaces, whereas function approximation is needed when states are too numerous to store or the training set must generalize.Source: §3.2.4 · p. 60, Approximate Solutions · p. 64

3.3.1 Bellman Recursion

  • The Bellman equation recursively relates a state's value to its reward and successor values; with known transitions, dynamic programming uses this structure for model-based planning.In common two-player zero-sum perfect-information games, γ = 1 and rewards are often +1 for wins, −1 for losses, and 0 for draws, reducing the equation to a backup function.Source: §3.3.1 · pp. 61–62, Dynamic Programming · p. 62

Value Iteration

  • Value iteration repeatedly updates values until convergence but may inefficiently enumerate large state spaces; policy iteration updates the policy directly and can converge faster when only the best move matters.Both methods require a known transition and reward model; policy iteration is also useful with continuous or stochastic action spaces.Source: Value Iteration · p. 63, Policy Iteration · pp. 63–64

3.3.2 Exploration and Exploitation

  • Exploration balances trying the currently best-known action against testing alternatives; ε-greedy policies explore randomly a fraction of the time, since always exploiting may miss optimal solutions.The section identifies smart exploration–exploitation use as foundational to Go breakthroughs and previews MCTS's UCT selection rule as using bandit theory to manage the trade-off.Source: §3.3.2 · p. 65

Temporal Difference

  • When the transition model is unknown, Bellman-based planning is insufficient; model-free problems require methods that learn from sampling.The section previews temporal-difference learning, value and policy iteration, and on- and off-policy methods as reinforcement-learning building blocks.Source: §3.3 · p. 61, Temporal Difference · p. 65
  • Temporal-difference learning updates a state-value estimate from sampled transitions without knowing the transition function, and SARSA or Q-learning supplies the control method.TD bootstraps from the next-state estimate; SARSA is on-policy control and Q-learning is off-policy control.Source: Temporal Difference · pp. 65–66

3.3.3 Actor-Critic

  • Actor-critic combines a policy actor with a value-function critic, using value estimates to provide more reliable learning signals and alternating policy evaluation with improvement.The section describes better convergence than value methods and reduced variance; it later introduces A3C and PPO, noting that A3C improves on DQN.Source: §3.3.3 · p. 67

3.3.4 Model-Free and Model-Based Methods

  • Model-free methods learn value and policy functions directly from observations, whereas model-based methods use a transition model for planning; AlphaGo is cited as a combined approach.Models may come from rules or be learned; when none is available, sampling can be used to learn one.Source: §3.3.4 · p. 68

3.3.5 On-Policy Learning and Off-Policy Learning

  • Off-policy backups use the best action rather than the exploratory action, while on-policy backups follow the selected action; both converge with sufficiently frequent state-action sampling.During exploitation, the two backup approaches coincide.Source: §3.3.5 · p. 69

Differentiating On-Policy and Off-Policy Learning

  • On-policy learning directly optimizes its target and can be stable but sample-inefficient; off-policy learning can use fixed stored trajectories, though Q-learning’s max operator can increase instability and overestimation.With neural-network function approximators, on-policy methods are usually more stable; off-policy learning that diverges too far from its selection policy may become inefficient.Source: On-Policy · p. 70, Differentiating On-Policy and… · p. 71

3.3.6 Sample Efficiency

  • Model-free methods may discard samples and need many to converge, while model-based methods can be more sample-efficient if their transition predictions are good, though accurate models are difficult to construct.Importance sampling is one proposed model-free improvement, emphasizing important regions without neglecting the rest of the search space.Source: §3.3.6 · pp. 71–72

Supervised Learning; Interaction; Credit Assignment; Dependency

  • Unlike supervised learning from labeled examples, reinforcement learning generates experience through environment interaction, where sparse rewards create credit-assignment challenges and dependent samples can cause learning anomalies.In many games, only terminal states receive rewards, which must be propagated backward to earlier states.Source: Interaction · p. 73, Credit Assignment · p. 73, Dependency · p. 73

MDP Tuple and Reinforcement Learning; 3.5 Practice; Questions; 3.5.1 Algorithms

  • The chapter maps reinforcement-learning methods onto the MDP tuple as methods progress from simple search to adaptive self-learning, then provides exercises and introduces Taxi comparisons using SARSA and Q-learning.The exercises review chapter concepts, including value and policy functions, exploration and exploitation, temporal difference, and on-policy versus off-policy learning.Source: MDP Tuple and Reinforcement Learning · pp. 73–74, Table 3.1 · p. 74, Questions · pp. 74–75

3.5.1 Algorithms

  • The Taxi world has 500 discrete states, six deterministic actions, a −1 step reward, +20 for delivery, and −10 for illegal pickups or dropoffs.SARSA is introduced as the on-policy algorithm for learning in this environment.Source: §3.5.1 · p. 76

Q-Learning

  • On average, Q-learning tends to find better policies than SARSA in the Taxi world.The passage describes this as a tendency, not a quantified comparison.Source: Q-Learning · p. 78

Exercises

  • Exercises ask readers to trace Taxi simulations and compare SARSA with Q-learning using controlled starts, statistical testing, parameter changes, and Mountain Car.They also invite running and rendering the Taxi simulator step by step.Source: Exercises · pp. 78–80

Summary

  • The chapter summary defines agent-environment interaction through states, actions, and rewards, and reviews value functions, policies, Bellman equations, TD learning, SARSA, and Q-learning.It distinguishes on-policy from off-policy learning and exact tabular methods from approximate methods such as neural networks.Source: Summary · p. 80

Historical and Bibliographical Notes

  • The notes point to Sutton and Barto and Bertsekas and Tsitsiklis for comprehensive treatments, and identify Watkins as the source of Q-learning.They also mention Kaelbling’s review and a robotics review.Source: Historical and Bibliographical Notes · p. 81

Heuristic Planning

  • Heuristic planning models look-ahead by combining a search function with a heuristic evaluation function, with minimax as an initial implementation.The approach has been successful in tactical games such as Chess, Checkers, and Othello, while domain-specific heuristics limit general applicability.Source: Heuristic Planning · p. 83

Core Problems; Core Concepts

  • Core problems are searching large state spaces efficiently and directing effort toward promising areas; the chapter covers evaluation, alpha-beta pruning, move ordering, transposition tables, and end-game databases.The sequence moves from the search-eval architecture and state-space size to search and evaluation enhancements.Source: Core Problems · p. 84, Core Concepts · p. 84

4.1 The Search-Eval Architecture; Exact Search and Approximate Eval

  • The search-eval architecture uses exact search to traverse part of a game tree and approximate evaluation at its horizon, since exhaustive search is infeasible and static evaluation misses game dynamics.The evaluation function assesses leaf states heuristically, while search accounts for consequences of moves such as captures and other tactical play.Source: §4.1 · pp. 84–85, Exact Search and Approximate Eval · pp. 85–86

4.1.1 State Space

  • Tic Tac Toe has 19,683 possible board configurations, an overestimate of reachable states; removing unreachable and illegal positions leaves 5,478 states, and removing symmetric positions (rotations and reflections) leaves 765 positions.Source: §4.1.1 · pp. 86–87

4.1.2 Search

  • Minimax alternates maximizing and minimizing successor values; the accompanying Python example uses a max root, three min nodes, and nine heuristic leaves.The root value in the example is 2.Source: §4.1.2 · pp. 87–88, Code · p. 87

Search Tree

  • Minimax traverses the full game tree, whose leaf count and approximate running time grow exponentially with depth, as w^d for regular trees of width w and depth d.For Chess, the text says a tree of size 10^47 would take too long to search, motivating reduced search depth.Source: Search Tree · p. 90, §4.1.3 · p. 91

4.1.3 Eval

  • Depth-limited minimax uses heuristic values at artificial leaves instead of searching to game-ending positions, on the assumption that deeper searches better approximate optimal values and policies.The example code decrements a depth parameter and evaluates material when the depth reaches zero.Source: §4.1.3 · p. 91

Domain Knowledge

  • A heuristic efficiently encodes domain knowledge, often as a weighted combination of features such as material, mobility, king safety, and center control.Heuristics apply statically to one position; search handles tactical aspects, so evaluations are often optimized for speed rather than accuracy.Source: Domain Knowledge · pp. 91–92

Heuristic Approximations

  • Heuristics are crude, game-specific approximations that can amplify estimation errors through minimax, and their labor-intensive manual tuning can create weaknesses elsewhere.Deep minimax on noisy estimates can produce search pathology, though the text says it is infrequent in practice; championship-level Chess and Checkers heuristics took years to refine.Source: Heuristic Approximations · p. 92

Heuristics in Practice

  • Chess and Checkers programs mostly use manually designed and tuned evaluation functions, while learned evaluation functions can be more general and easier to debug.The text also notes machine-learning successes in Othello, Backgammon, and Go, and that AlphaGo learns both features and coefficients.Source: Heuristics in Practice · p. 93

Critical Tree

  • The minimax state space contains exponential redundancy, and the critical path consists of nodes whose values equal the root; only a small subtree determines that value.Partial expansion at max nodes gives a lower bound, while partial expansion at min nodes gives an upper bound; establishing the opposite bounds requires expanding all children.Source: §4.2 · p. 93, Critical Path · p. 94, Critical Tree · p. 95
  • 1,000 leaves suffice to determine a minimax tree’s value when it has 1,000,000 leaves; the critical tree is the square root of the full tree’s size.The critical tree is the union of the min and max solution trees, and every algorithm must traverse it to determine the value with certainty.Source: Critical Tree · p. 96

4.3 Search Enhancements

  • Minimax’s fixed-width, fixed-depth search is too inefficient for high performance, and its heuristic evaluation function is domain dependent.The enhancements trend toward variable-depth search and generalization of evaluation; alpha-beta is central to decades of efficient game-playing search.Source: §4.3 · p. 97

Alpha-Beta Window

  • Alpha-beta tracks lower and upper bounds in an ⟨α, β⟩ window, stopping a node’s search when the bounds collapse and its value is known.At max nodes, results update α; at min nodes, they update β, and a sufficiently strong opposing reply can make remaining children irrelevant.Source: Alpha-Beta Window · p. 98, Alpha-Beta Cutoff · p. 100

Alpha-Beta Example

  • With w=10 and d=6, alpha-beta can cut off 999,000 of 1,000,000 leaves in the best case, searching a 1,000-leaf critical tree.Typical high-performance game-playing programs approach this best case; at more than 90% of nodes, the first child is also the best child.Source: Alpha-Beta Example · p. 99

Move Ordering

  • Alpha-beta’s efficiency depends on successor ordering: well-ordered trees enable many cutoffs, while its worst-case time complexity remains w^d.A perfectly ordered tree puts the best child first at each node; iterative deepening and transposition tables are among the ordering heuristics discussed.Source: Move Ordering · p. 101

4.3.2 Iterative Deepening

  • Iterative deepening makes fixed-depth search anytime by running progressively deeper searches, so a useful answer is available when time runs out.Earlier iterations add little time because search grows exponentially; their results can also improve alpha-beta move ordering when retained in a transposition table, though they expand extra nodes.Source: §4.3.2 · p. 102

4.3.3 Transposition Tables

  • Transposition tables cache positions and search results to avoid repeatedly searching identical states in a game graph.Stored best moves from shallower searches can improve ordering in deeper alpha-beta searches and frequently trigger cutoffs, even when the cached value is not deep enough to reuse.Source: §4.3.3 · pp. 103–104
  • Iterative deepening with transposition tables supports well-ordered trees and efficient alpha-beta search approaching its best case; cached results also make re-searches incur no new node expansions.The best-case behavior is an empirical finding, since pathological counter-examples can be constructed but are uncommon in practice.Source: §4.3.3 · p. 104, Transposition Table and Null Window… · p. 109

Narrow Windows, Bounds, and Solution Trees

  • A low narrow window can return a lower bound and a min solution tree, while a high window can return an upper bound and a max solution tree; equal bounds establish the minimax value.In the illustrated example, both bounds equal 3, and their solution trees form a proof tree.Source: Narrow Windows, Bounds, and Solution… · p. 106, Figure 4.10 · p. 106

Post-condition and Bounds

  • A null window with α = β−1 yields an efficient Boolean test of whether the minimax value lies above or below the window, so finding the value requires repeated calls.The two described approaches are Scout, which uses null-window search recursively, and MTD(f), which uses it iteratively from the root.Source: Post-condition and Bounds · p. 107

Scout

  • Scout searches its assumed best first child with a wide window, then uses null-window searches to test whether other children are inferior and searches promising ones with a wide window.The first child is called the principal variation.Source: Scout · p. 107

Transposition Table and Null Window Search

  • MTD(f) expands fewer nodes than Scout on average, though either can perform best on constructed trees, and MTD(f) relies heavily on a well-functioning lookup table.The lookup table must handle inconsistencies in the tree carefully.Source: Transposition Table and Null Window… · p. 109

4.3.5 *Heuristic Forward Pruning

  • Heuristic forward pruning searches only moves judged important, but static heuristics can miss valuable tactical moves; later variants include null-move pruning and Prob-cut.Early Go programs used generators for “sensible” moves, while Chess and Checkers programs moved toward full-width move lists as computing power increased.Source: §4.3.5 · p. 110

4.3.6 *Capture Moves; 4.3.7 *Killer Moves and History Heuristic

  • Capture ordering prioritizes material-taking moves but is domain-dependent; killer moves reuse cutoff-causing moves, while the history heuristic ranks moves using counters for prior cutoffs.Capture ordering can fail when a non-capture is best and is unimportant in Go; history counters may be weighted by search depth.Source: §4.3.6 · p. 111, §4.3.7 · p. 111

4.3.8 *Backup Rules Other than Minimax

  • For chance or imperfect-information games, alternatives include Expectimax, *-minimax, and sampling; averaging underlies successful MCTS, while proof-number search solves Boolean outcomes.Expectimax and *-minimax had limited popularity after experiments, although a 2013 combination of Expectimax and statistical sampling reported good results.Source: §4.3.8 · p. 112

4.3.9 Trends in Search

  • Search trends favor variable-depth pruning and move ordering to focus effort on promising branches, alongside general methods such as iterative deepening and transposition tables.Source: §4.3.9 · p. 113

4.4.1 *Search Extensions

  • Search extensions deepen selected positions to reveal tactical dynamics beyond the static evaluator’s horizon, but excessive capture extensions can expand the search too much.Partial-depth extensions address this risk, and tuning extension types and amounts is important, especially in tactical Chess.Source: §4.4.1 · pp. 113–114

4.4.2 *Quiescence Search

  • Quiescence search reduces horizon effects by searching noisy positions until a quiet position can be evaluated more reliably.Its effectiveness requires experimentation with the program’s static evaluation heuristics.Source: §4.4.2 · p. 114

4.4.3 *Null-Move Heuristic

  • The null-move heuristic tests whether passing yields an inexpensive alpha-beta cutoff, working well in Chess but requiring caution in games where Zugzwang is more common.Othello is such a case; ProbCut has nevertheless succeeded there.Source: §4.4.3 · pp. 114–115

4.4.4 *Odd/Even Effect

  • The minimax odd/even effect causes scores to swing across search depths, complicating empirical comparisons; search extensions and depth adjustments in multiples of two can reduce it.The effect follows from minimax’s min-max structure, not search instability.Source: §4.4.4 · p. 115

4.4.5 *Piece-Square Tables; 4.4.6 Coefficient Learning

  • Piece-square tables efficiently score piece locations and can be learned, while supervised learning can tune evaluation coefficients from known grandmaster positions or moves.Machine-learned coefficients may differ considerably from hand-tuned values, and some work learns evaluation functions directly from board positions without handcrafted features.Source: §4.4.5 · pp. 115–116, §4.4.6 · p. 116

4.4.7 End-Game Database; 4.4.8 Opponent Modeling

  • Endgame databases store exact minimax values for sparse endings, while opponent modeling can choose moves that exploit perceived weaknesses rather than assume identical play.Retrograde analysis computes databases backward from the end; pattern databases extend the idea to all search stages.Source: §4.4.7 · p. 117, §4.4.8 · p. 117

4.4.9 Trends in Eval

  • Evaluation enhancements increasingly use automated feature creation and learning, though some search-extension and quiescence methods remain domain-specific.Examples include retrograde analysis for endgame databases and machine learning for coefficients or piece-square tables.Source: §4.4.9 · pp. 117–118

Adaptive Sampling

  • MCTS addresses adaptive node selection and missing efficient heuristics through adaptive exploration, sampled evaluation, and averaging rather than minimax, working well in Go but less well than heuristic alpha-beta in Chess, Checkers, and Othello.The contrast reflects that tactical search works well in games such as Chess, Checkers, and Othello, whereas Go's long-term strategic effects resist short tactical search.Source: Adaptive Sampling · p. 125

5.1 Monte Carlo Evaluation

  • Recursive tree search with smart exploration/exploitation transformed Monte Carlo playouts into effective Go programs, which rapidly reached weak-master strength and stronger play on 9 × 9 boards.Earlier playout-only approaches played better than random but underperformed hand-crafted programs; MoGo and Crazy Stone were among the first successful MCTS programs.Source: §5.1 · pp. 127–128

Reinforcement Learning

  • MCTS represents reinforcement learning's sampling paradigm and incorporates the exploration/exploitation trade-off into its core, unlike minimax, which needed domain-specific enhancements for variable-depth search.Its selection uses node statistics to guide exploration and exploitation.Source: Core Concepts · p. 126, Reinforcement Learning · p. 128

Iteration vs. Recursion

  • MCTS builds its tree iteratively, typically over 1,000–10,000 iterations, updating win and visit counts after each playout so selection can balance win rate against under-explored nodes.Each iteration selects a path, expands a node, runs a playout, and propagates its result back to the root.Source: Iteration vs. Recursion · p. 129

Select

  • Selection follows a rule such as UCT from the root to a leaf, while expansion usually adds one child but can add every successor.Selection choices form the policy for the look-ahead simulation.Source: Select · pp. 130–131, Expand · p. 131

Playout

  • During playout, self-play continues to the game's end and yields a win, draw, or loss reward; Go programs often improve random play with small-pattern databases and fast heuristics.The simulated playout nodes are not added to the MCTS tree, though their result is used during backpropagation.Source: Playout · p. 131

5.2.4 UCT Selection Rule

  • UCT selects the child with the highest sum of win-rate exploitation and uncertainty-driven exploration, while MCTS backs up rewards and returns the root action with the most visits.In the recursive bandit framing, each state is a bandit and each action is an arm; MCTS also distinguishes its selection, playout, and final action policies.Source: Backpropagation · p. 131, §5.2.2 · p. 132, §5.2.4 · p. 133

5.2.5 The Impact of MCTS

  • MCTS made selective search practical by sampling paths rather than full trees, changing the search paradigm from exponential O(w^d) to polynomial O(d) and reducing reliance on domain-specific heuristics.The text describes the shift as a paradigm change in game programming and says MCTS can find promising search regions using its own statistics.Source: §5.2.5 · pp. 135–136, Applications of MCTS · p. 137

Applications of MCTS

  • MCTS raised Go programs from around 10 kyu to 2–3 dan, while 19 × 19 performance plateaued near 4–5 dan despite substantial research.The supplied figure shows performance over time on the large board; the text also notes very strong play on 9 × 9 boards.Source: Figure 5.6 · p. 136, Applications of MCTS · p. 136

5.3.1 Exploration/Exploitation

  • ≈4,000 operations was the lowest polynomial size found at N = 3,000 iterations, with good results for 0.7 ≤ Cp ≤ 1.2; small searches favored exploitation, larger ones exploration.Intermediate Cp ≈ 1 balanced the two and usually found orderings near the best known; too little exploration could trap search in local minima, while too much often missed the global minimum.Source: §5.3.1 · pp. 138–139, Figure 5.8 · p. 139

5.3.2 Selection: RAVE

  • RAVE uses AMAF-like off-policy updates early in search to spread statistics to related nodes, then reduces those updates as the tree grows to limit their loss of precision.AMAF updates counts for sibling actions occurring in playouts, giving UCT information across more nodes sooner.Source: §5.3.2 · p. 140

5.3.3 Playout: Pattern Database

  • Go programs commonly use small pattern databases learned from grandmaster games to guide playouts, and MoGo achieved grandmaster performance on 9 × 9 Go using them.The patterns often cover 3 × 3 positions around the previous move.Source: §5.3.3 · p. 140

5.3.4 Adaptive Exploitation/Exploration

  • For formula optimization, an adaptive Cp schedule starts explorative and decreases toward zero, shifting search toward deeper trees near the end.The described scheme is beneficial for optimizing large formulas with MCTS.Source: §5.3.4 · p. 141

5.3.5 Ensembles and Parallelism

  • MCTS iterations are semi-independent and communicate through win and visit counts, making the search amenable to parallel speedup; most large Go programs run iterations in parallel.Independent iterations miss some statistics accumulated by the others.Source: §5.3.5 · p. 141
  • Root parallelism searches independent trees with less communication but less efficient statistics; tree parallelism shares a tree, while leaf parallelism runs independent playouts.Mirsoleimani et al. [452] unify tree and root parallelism and enable hybrid pipeline-parallel MCTS.Source: §5.3.5 · p. 141
  • Independent MCTS searches explore more of the tree, so root parallelism with a reduced Cp can moderate each search’s exploration while retaining exploration across searches.Ensemble searches are discussed in relation to exploration by Fern and Lewis and Mirsoleimani et al..Source: §5.3.5 · pp. 141–142

5.3.6 Rollout Algorithms

  • Rollout algorithms evaluate a base policy and improve it by one-step look-ahead; Huang’s alpha-beta rollout and MCTS differ in selection rules and backed-up values.Alpha-beta selects left-first and backs up upper and lower bounds, whereas MCTS selects by UCT and backs up node and win counts; Huang’s formulation highlights their shared algorithmic structure.Source: §5.3.6 · p. 142

Exercises

  • MCTS needs no domain-specific heuristic evaluation, enabling master-level play on 9 × 9 Go, while UCT makes its selective search balance exploration and exploitation.The chapter presents MCTS as addressing rigid search and the lack of efficient heuristic evaluation; it also identifies UCT as its popular bandit-theory-based selection rule.Source: Exercises · p. 145

Function Approximation

  • The function-approximation chapter aims to find end-to-end value or policy functions for high-dimensional problems, choosing actions from states without hand-crafted intermediate features.Deep learning approximates objective functions—including regression, classification, value, and policy functions—by automatically discovering features.Source: Function Approximation · p. 147, Core Problem · p. 148

6.1 Deep Supervised Learning

Learning as Generalization from Training Set to Test Set

  • A training/test split evaluates generalization on unseen examples: a typical split uses 90% for training and 10% for testing, with mismatched accuracy indicating possible underfitting or overfitting.Supervised learning is tied to generalization, the formulation of common properties across data instances.Source: Learning as Generalization from… · p. 149

Generalization as Feature Discovery

  • Deep nets automate feature discovery through hierarchies of increasingly abstract representations, avoiding labor-intensive handcrafted features that may not generalize across domains.Deep feature recognizers often work across domains but typically require retraining for each one; automated optimization is also more reproducible than expert hand-tuning.Source: Generalization as Feature Discovery · pp. 149–150

End-to-End Learning

  • End-to-end learning trains features from raw pixels but is computationally demanding, unlike manually designed Chess heuristics whose feature weights can be learned separately.The Chess evaluation function combines hand-crafted features linearly, while deep-network features are trained automatically from examples.Source: End-to-End Learning · p. 150

6.1.2 Shallow Neural Network

Stochastic Gradient Descent and Backpropagation

  • Training uses forward passes to produce outputs and backward passes to compare them with labels, calculate error, and adjust weights by gradients; SGD samples gradients to speed training and add noise.Training stops when the error or validation loss reaches a sufficient threshold.Source: Stochastic Gradient Descent and… · p. 153

6.1.3 Deep Learning

  • Deep networks learn increasingly abstract features across layers, enabling complex recognition that shallow networks may not perform well on without hand-coded preprocessing.The universal approximation theorem does not explain how to learn the required parameters, and learning may take impractically long or require many hidden neurons.Source: §6.1.3 · p. 154

Increasing Width: Slow Learning and Overfitting

6.1.5 Convolutional Neural Nets

Shared Weights

  • Shared convolutional weights detect features regardless of position, reducing trained parameters and overfitting while increasing the effective data available per weight.Replicated filters give neurons in a layer the same feature response across their local fields, providing translation invariance.Source: Shared Weights · p. 158

Max Pooling

  • Max pooling downsamples feature maps to reduce network dimensions and allows small translations or scaling; a typical CNN stacks convolution, max-pooling, and ReLU layers before a fully connected layer.A common pooling operation reduces a 2 × 2 block to a scalar.Source: Max Pooling · pp. 159–160

Gradients

  • Sigmoid and tanh networks can suffer vanishing gradients across layers, while deep-network gradients may also explode, impeding gradient-based learning.Backpropagation multiplies derivatives through successive layers, and sigmoid derivatives can shrink toward zero in deeper layers.Source: Gradients · pp. 160–161

ReLU / Batch Normalization

  • ReLU is a fast, simple activation that reduces vanishing gradients, while batch normalization rescales batches to reduce gradient instability and overfitting.Batch normalization adds computation and is described as speeding training and reducing overfitting; ReLU's derivative discontinuity motivated soft-ReLU.Source: ReLU · p. 161, Batch Normalization · p. 162

6.1.7 Overfitting / Data Augmentation / Capacity Reduction

  • Overfitting occurs when a network fits training-set noise, often when it has more parameters than examples; data augmentation adds transformed examples, while capacity reduction narrows or shortens the network.Augmentation can use rotations, reflections, noise, or rescaling, but increases training cost.Source: §6.1.7 · p. 162, Data Augmentation · p. 163, Capacity Reduction · p. 163

L1 and L2 Regularization / Early Stopping / Dropout

  • Regularization penalizes high weights, early stopping ends training before it fits noise, and dropout stochastically removes neurons to reduce effective network capacity.A holdout validation set can be evaluated after each epoch to help decide when to stop; L1 and L2 are popular regularizers.Source: L1 and L2 Regularization · p. 163, Early Stopping · p. 163, Dropout · p. 164

6.1.8 Datasets and Networks / LeNet-5

  • UCI, MNIST, CIFAR-10, and ImageNet provide datasets for machine learning; LeNet-5 is a seven-layer CNN trained on handwritten MNIST digits and used commercially for check recognition.MNIST and CIFAR-10 each contain 60,000 examples; ImageNet contains over 14 million annotated image URLs across more than 20,000 categories.Source: §6.1.8 · p. 164, LeNet-5 · p. 165

Crafting Neural Architectures / ZFnet

  • Some effort once spent hand crafting heuristic features is now spent hand crafting network architectures to learn features automatically; ZFnet visualized inner layers, while VGG used 3 × 3 filters in 16–19-layer networks.VGG implemented the idea that many layers (16) build a hierarchical representation of visual data.Source: Crafting Neural Architectures · p. 166, ZFnet · pp. 169–170

TensorFlow / Conclusion / 6.2 *Advanced Network Architectures

  • Deep-learning progress combined algorithmic advances, large labeled datasets, and GPU computation, and high-quality software implementations were identified as a possible fourth contributor.TensorFlow represents programs as data-flow graphs, while Keras provides an easier interface; advanced architectures and ImageNet benchmarks further shaped supervised-learning research.Source: TensorFlow · pp. 166–167, Conclusion · p. 167, §6.2 · p. 168

AlexNet

  • AlexNet won the 2012 ImageNet competition with a 15% error rate, compared with 26% for the runner-up.Its eight-layer network used ReLU, data augmentation, and L2 regularization to address vanishing gradients and overfitting.Source: AlexNet · pp. 165, 168

GoogLeNet

  • GoogLeNet’s 22-layer inception architecture performed better than AlexNet with 12 times fewer parameters, using parallel convolutions to create sparse networks.Batch normalization and dropout were also used to address vanishing gradients and regularization, respectively.Source: GoogLeNet · p. 170

Residual Networks

  • ResNet won the 2015 ImageNet challenge with a 3.57% error rate, below the 5–10% most humans achieve, and skip links address accuracy degradation and vanishing gradients.Skip links let the network learn identity mappings more easily; the text says image-recognition tasks now frequently exceed human performance.Source: Residual Networks · p. 171

Generative Adversarial Networks

  • GANs pair a generator that tries to mislead a discriminator with the aim of improving discrimination; generative networks can also produce photo-realistic images and deep fakes.Slight image perturbations can fool recognizers, a brittleness called the one-pixel problem; GANs have also increased theoretical understanding of supervised training.Source: Generative Adversarial Networks · pp. 172–173

6.2.3 Sequential Processing

  • RNNs model sequences by carrying state through recurrent connections, which can be unrolled across time; sequence inputs and outputs support tasks such as sentiment analysis, translation, and captioning.RNNs are used for sequential data such as speech, text, and time series; their configurations include sequence input, output, or both.Source: §6.2.3 · pp. 174–176

Long Short-Term Memory

  • LSTMs are designed for sequential problems and long-term remembering, using skip connections that make them less susceptible to vanishing gradients than ordinary RNN training.The text also notes early success experimenting with LSTMs in hybrid architectures that combine planning and learning.Source: Long Short-Term Memory · p. 177

6.3.1 End-to-End Reinforcement Learning

  • Deep reinforcement learning aims to learn end-to-end from high-dimensional raw inputs beyond the reach of hand-crafted heuristics, but faces generalization and convergence challenges.Unlike supervised learning from fixed labeled examples, reinforcement learning learns policy or value functions through environment interaction, with sparse rewards that can require long-range credit assignment.Source: §6.3 · p. 178, §6.3.1 · pp. 178–179

Generalization to Test Set

  • Sparse, correlated state-action samples can limit coverage and generalization to new problem instances, while randomizing samples reduces correlations and the risk of getting stuck.Correlated consecutive samples contain little new information, reducing effective data and learning efficiency.Source: Generalization to Test Set · pp. 180–181

Fluctuating Data Distribution

  • Reinforcement learning’s training distribution can fluctuate because environment interaction changes which examples are generated, while infrequent or bootstrapped signals may be polluted by old or approximate values.Source: Fluctuating Data Distribution · p. 181

Convergent Training: Deadly Triad

  • Function approximation, bootstrapping, and off-policy learning form the deadly triad, which can make Q-values diverge; even two elements may cause instability, and on-policy feedback loops can also destabilize training [461].Changing behavior can skew training toward a narrow part of the state space; replay buffers smooth this short-term effect, but should not be so large that they prevent forgetting ineffective behavior.Source: Fluctuating Data Distribution · p. 181, Convergent Training: Deadly Triad · p. 182

6.3.2 Atari 2600 Games

  • DQN learned joystick actions directly from raw visual pixels without hand-crafted features, but a network trained on one game did not play another well [461].The same architecture and training procedure were used across games, with minimal prior knowledge; the network processed pixels and game score.Source: §6.3.2 · p. 184
  • 2013 DQN achieved human-level play in six games; its 2015 follow-up matched humans in 49 test games, while the ALE account reports better-than-human play in 29 of 49.The 2013 ALE results were above expert-human performance on Breakout, Enduro, and Pong but far below human performance on Seaquest, Q*Bert, and Space Invaders.Source: §6.3.2 · p. 184, Arcade Learning Environment · pp. 185–186

Arcade Learning Environment

  • Long-delayed rewards remained difficult: Montezuma’s Revenge challenged DQN, while a 2020 meta-controller succeeded in 57 games [28].The original experiments used seven Atari games and trained for 50 million frames; the 2015 network exceeded human-level play in 29 of 49 games, with longer credit delays more difficult.Source: §6.3.2 · p. 184, Arcade Learning Environment · pp. 185–186

Network Architecture

  • DQN reduced Atari input to 84 × 84 grayscale images and used three hidden layers, with convolutional filters followed by a 256-unit fully connected layer.It used the last four frames, skipped frames, output one Q-value per action, and applied RMSprop with a decaying ε-greedy exploration rate.Source: Network Architecture · p. 186

Experience Replay

  • Experience replay samples randomly from past states to break temporal correlations and feedback loops, smoothing training; it is nevertheless a form of off-policy learning.A typical replay buffer stores 10^6 examples; further analysis found larger networks could be more unstable, while longer multi-step returns yielded fewer unrealistically high reward values.Source: Experience Replay · pp. 187–188

Infrequent Weight Updates

  • DQN’s separate target network uses older weights to generate update targets, delaying feedback between Q-value updates and their targets and making oscillations less likely.The online Q network is copied to the target network every x updates, which then supplies targets for the following x updates.Source: Infrequent Weight Updates · p. 188

6.4 *Deep Reinforcement Learning Enhancements

  • The deadly triad remains a source of instability, but later enhancements—including prioritized replay, Double DQN, A3C, PPO, and distributional DQN—targeted stability, convergence, or generalization [596, 711, 459, 610, 52].The enhancements largely address coverage, correlation, and convergence; separate networks, multi-step returns, and prioritized replay can mitigate divergence or overestimation bias [710].Source: §6.3.4 · p. 188, §6.4 · pp. 189–190

6.4.1 Overestimation

  • DDQN reduces DQN’s action-value overestimation and achieved about twice DQN’s average score with the same hyperparameters, or four times the score with tuned hyperparameters, on 49 Atari games.The method extends double Q-learning from the tabular setting to deep networks.Source: §6.4.1 · p. 191

6.4.2 Prioritized Experience Replay

  • Prioritized replay samples important transitions more often to improve learning efficiency, using TD error for priority or, in Rainbow’s distributional variants, Kullback-Leibler loss [290].Dueling DDQN [747] separately estimates state value and action advantage, improving policy evaluation when a state has many similarly valued actions.Source: §6.4.2 · p. 192, §6.4.3 · p. 192

6.4.4 Distributional DQN

  • Distributional Q-learning [52] learns a probability distribution over discounted returns rather than only their mean, while NoisyNet [224] learns parameterized weight noise to drive exploration.Distributional DQN performs well on Atari; NoisyNet replaces exploration heuristics and yields substantially higher Atari scores.Source: §6.4.4 · p. 192, §6.4.5 · p. 193

6.4.6 R2D2

  • R2D2 combines prioritized distributed replay, 5-step double Q-learning, a dueling network, and an LSTM to exploit long-term dependencies; Agent57 exceeds human baseline scores on all 57 Atari games.Agent57 uses a meta-controller to adapt long- and short-term behavior while training policies ranging from exploitative to explorative.Source: §6.4.6 · p. 193

6.4.7 Actor-Critic Approaches

  • Actor-critic methods interleave value and policy learning; A3C uses parallel asynchronous gradient descent, whose learners decorrelate experience and stabilize training.Policy-gradient methods can be sensitive to step size and have poor sample efficiency when action-value estimates are weak.Source: §6.4.7 · pp. 193–194

Proximal Policy Optimization

  • PPO [610] uses simpler first-order updates to keep new policies close to old ones, seeking TRPO-like performance without its expensive second-order calculations [284].PPO trains an on-policy stochastic policy, unlike off-policy DQN.Source: Proximal Policy Optimization · pp. 194–195

Reinforcement Learning

6.4.8 Enhancements in the Context of Game Playing Programs

  • Giraffe used DQN and self-play for end-to-end Chess learning and reached master-level play; small networks, handcrafted features, and the compute demands of end-to-end learning constrained earlier work.Self-learning can be unstable and hard to diagnose without known training examples; clear benchmarks, including Gym [98] and ALE [53], helped researchers identify effective ideas.Source: §6.4.8 · p. 195, Reinforcement Learning · p. 198, §6.4.9 · p. 198

Cartpole

  • The Cartpole example trains an agent to balance a stick on a cart, and understanding its DQN implementation requires looking beyond the simple high-level code.The code is available through the OpenAI Cartpole baseline; DQN is implemented in deepq.learn in a few hundred lines.Source: Cartpole · p. 201

More Exercises

  • Exercises ask readers to vary Mountain Car and Cartpole settings, train and assess a Space Invaders player, and test how replay-buffer changes affect DQN convergence and player quality.They also ask readers to try other Atari games, including Montezuma’s Revenge, and consider how to improve DQN there [28].Source: More Exercises · pp. 201–202

Stable Baselines

  • OpenAI Baselines, Stable Baselines, and RL Baselines Zoo provide downloadable algorithms, documentation, Rainbow code, and pretrained agents.Open software and datasets also support replication and improvement of chapter methods; Keras applications include VGG and ResNet implementations.Source: Stable Baselines · pp. 202–203

*Advanced Exercises

  • Project-sized advanced exercises cover reproducing AlexNet, VGG, and ResNet results, generating images with GANs, ImageNet captioning with an RNN, and ablating Rainbow components [356] [290].The section cautions that these exercises may require substantial research and work, potentially thesis-sized.Source: *Advanced Exercises · p. 203

Summary

  • Replay buffers and infrequent weight updates decouple correlated states to help deep reinforcement learning converge.Unlike supervised learning on independent examples, RL training can diverge because states are correlated.Source: Summary · p. 204
  • DQN learned end-to-end Atari control from raw pixels across a wide variety of challenging games using one architecture and minimal prior knowledge.The cited account says it used the same algorithm, network architecture, and hyperparameters across games, receiving pixels and game score as inputs.Source: Summary · p. 204

Learning in Games

  • Neural game-playing progressed from heuristic-feature learning in Backgammon and Go to strong TD-Gammon play and deep-learning results in Go and Chess.Neurogammon used supervised learning on 400 self-played examples; TD-Gammon later trained the same features with reinforcement learning, while Chess results were on par with Falcon and Crafty.Source: Learning in Games · p. 205

Deep Learning

  • Deep learning advances such as backpropagation, max pooling, GPUs, ReLU, and batch renormalization addressed training speed and vanishing gradients, while early game nets learned heuristic coefficients rather than state features [756, 328, 599].NeuroGo and Neurogammon used small nets because computing power and training advances were insufficient to learn features directly from game states.Source: Deep Learning · pp. 205–206

Chapter 7 Self-Play

Chapter 7 examines AlphaGo-style self-play, which combines MCTS and deep reinforcement learning and demonstrated world-champion-level play in a highly complex game. It focuses on creating stable, high-performance self-play and the problems and concepts involved.

Chapter 7 Self-Play

  • AlphaGo-style self-play combines MCTS with deep reinforcement learning and achieved world-champion-level play in a highly complex game.The 2016 results demonstrated this capability, years after TD-Gammon.Source: Chapter 7 Self-Play · p. 207
  • The chapter’s central challenge is achieving stable, high-performance self-play in a very challenging state space.It also examines why stable self-play is difficult and how it compares with pretraining on human grandmaster games.Source: Chapter 7 Self-Play · p. 207

Core Problems

  • The core problems are creating training examples that support learning beyond human grandmaster play and using function approximation to improve adaptive sampling.Source: Core Problems · p. 208

Core Concepts

  • The chapter identifies coverage, correlation, and convergence as stable-self-play concerns, alongside curriculum learning.Source: Core Concepts · p. 208

A Note on Names … Triple Recursion

The section distinguishes AlphaGo, AlphaGo Zero, and AlphaZero, then explains how AlphaGo Zero’s self-play combines search and learning in a curriculum that progressively improves its network.

A Note on Names

  • AlphaGo, AlphaGo Zero, and AlphaZero are three related programs, each marking an AI milestone published in a top journal.The chapter focuses on their methods and advances in reinforcement learning, especially self-play.Source: A Note on Names · p. 208

7.1 Self-Play Architecture

  • Minimax and MCTS use the same algorithm for both players during look-ahead, while self-play learning replaces the environment opponent with the agent itself.This extends self-play from selecting a move to creating a self-learning program.Source: §7.1 · p. 209, §7.1.1 · p. 209

7.1.1 Self-Play Learning

  • AlphaGo Zero combines agent self-learning with MCTS look-ahead, using search to improve its own training examples and iteratively train a stronger network.Each iteration generates higher-quality actions, trains the network on the improved examples, and advances the level of play.Source: §7.1.1 · p. 209

Self-Learning

  • Each game yields state-action pairs and an outcome; MCTS uses the policy and value network to select moves, and the resulting triples train the network for the next tournament.The loop repeats tournaments, games, and network training, using the updated network as the next search evaluation function.Source: Self-Learning · pp. 210–211

Levels of Abstraction

  • AlphaGo Zero’s curriculum comprises tournaments of 25,000 games, while each MCTS search comprises 1600 simulations that add nodes to its tree.Game outcomes are added to moves to form training examples, and each tournament ends with a buffer of positions for further network training.Source: Levels of Abstraction · p. 212

Triple Recursion

  • AlphaGo Zero uses a single residual network with 19 hidden layers and policy and value heads, supporting training that is triply recursive across tournaments, games, and MCTS look-ahead.At the third level, MCTS uses the same opponent model for both players in its look-ahead.Source: Triple Recursion · pp. 212–213

7.1.2 Self-Play and Search-Eval

  • AlphaGo Zero’s search-eval architecture uses MCTS as its search function and a deep network as its evaluation function, in both training and usage phases.The section connects this setup to policy and value functions, search-eval methods, and techniques developed in earlier chapters.Source: §7.1.2 · p. 213

Evaluation · Search

In self-play, the evaluation network supplies policy and value estimates, while MCTS generates training examples and selects actions during play. Both are used in training and in the usage phase, with network guidance shaping the search.

Evaluation

  • The evaluation network learns during training, then serves as the policy/value function queried during play.Its two outputs guide action selection and value backup in MCTS.Source: Evaluation · p. 213

Search

  • MCTS serves both to generate higher-quality training examples and to look ahead for the best action during actual play.The look-ahead algorithm is the same in both phases; its role in the self-play scheme changes.Source: Search · p. 214
  • Unlike the chapter 5 MCTS, Alpha-★ MCTS runs inside the training loop to improve examples generated in each self-play iteration.Source: Search · p. 214
  • In ★-Zero MCTS, the value approximator supplies backups instead of random playouts, leaving statistics-based exploration and exploitation.The passage notes that the “Monte Carlo” label is therefore a misnomer for this network-guided tree search.Source: Search · p. 214
  • Self-play MCTS uses the policy head alongside win rate and newness for node selection, and replaces leaf playouts with the value head.UCT still concentrates effort on high-win-rate branches while balancing exploration of underexplored parts of the tree.Source: Search · p. 214
  • P-UCT adds the policy probability π(s, a) to UCT’s exploration term, using a variant cited as [466].Source: Search · p. 215

Dual-Headed Network

AlphaGo Zero combines a dual-headed network with exploration-heavy self-play, using large-scale training and an easy-to-hard curriculum to improve play and accelerate learning.

Dual-Headed Network

  • AlphaGo Zero’s dual-headed residual network has 19 hidden layers, equally weighted policy and value losses, and trains with 2,048-example batches sampled from 500,000 recent self-play games.The batches are distributed across 64 GPU workers, and the learning rate decreases from 0.01 to 0.0001 during self-play.Source: Dual-Headed Network · p. 215
  • After 4.9 million games over three days, AlphaGo Zero outperformed the previous version, AlphaGo.Each self-play iteration contained 25,000 games, with 1,600 MCTS simulations per move.Source: Dual-Headed Network · p. 215

7.1.3 Stable Self-Play through Exploration

  • Stable self-play uses many games, MCTS look-ahead and root Dirichlet noise for coverage, replay buffers to reduce state correlation, and on-policy MCTS with small training steps to support convergence.Despite published hyperparameters, achieving stable, high-quality self-play requires slow training and tuning, making reproduction difficult.Source: §7.1.3 · p. 216

7.1.4 Curriculum Learning

  • Self-play curriculum learning [477] orders examples from easy to hard as trainer and trainee improve together, shortening training from weeks or months to days while increasing playing strength.AlphaGo Zero is based purely on self-play, whereas AlphaGo combines supervised and reinforcement learning.Source: §7.1.4 · pp. 216–217

Training Speed · Correlation Revisited · Active Learning and Related Learning

Curriculum learning is expected to speed early training and improve generalization in difficult settings, while self-play combines exploration with difficulty ordering. The discussion also connects curriculum learning to active learning, adversarial policies, and GANs.

Training Speed

  • Curriculum learning is expected to speed learning, especially early in training, and improve generalization on difficult tasks, with small networks, or under strong regularization [753].These theoretical findings are supported by empirical evidence [438] [58].Source: Training Speed · p. 217
  • Curriculum learning is rarely used in practice because supervised and reinforcement learning examples often lack an available easy-to-hard ordering.Finding a teacher able to rank examples by difficulty is challenging.Source: Training Speed · p. 217

Correlation Revisited

  • Breaking correlations between examples can improve state-space coverage and prevent cycles or local minima, while curriculum learning relies on correlating difficulty [753].The passage frames this as a tension between diversity for exploration and ordering examples from easy to hard.Source: Training Speed · p. 217, Correlation Revisited · p. 218
  • In self-play, state features should be uncorrelated while error values correlate; learning implicitly sorts by error, and MCTS and replay buffers support exploration within iterations.Source: Correlation Revisited · p. 218

Active Learning and Related Learning

  • Active learning iteratively queries labels that are available at a cost, connecting supervised and reinforcement learning as the learner chooses what to reveal.The passage notes its relevance to recommender systems, where acquiring information may carry a cost.Source: Active Learning and Related Learning · p. 218
  • Deep-learning one-pixel vulnerabilities can cause unwanted deep-reinforcement-learning behavior [313], and Gleave et al. [246] identify adversarial policies in zero-sum simulated robotics.Source: Active Learning and Related Learning · p. 218
  • Recent work suggests GAN performance may benefit from easy-to-hard examples generated through the generator-discriminator tandem [620] [177].Curriculum learning attracted more attention following AlphaGo Zero and interest in GANs; an overview is cited in.Source: Active Learning and Related Learning · p. 218

Human Learning is Curriculum Learning … Impact on AI

Human and machine learning can benefit from curricula that progress from easier to harder tasks. AlphaGo’s strength and the response to its matches renewed interest in self-play, AI, and Go.

Human Learning is Curriculum Learning

  • Human teachers order examples from easy to hard and divide tasks into subtasks called shaping; staged curricula improved generalization and convergence speed.Elman argued for starting language learning with a small network and gradually increasing example difficulty and network size; curriculum learning has drawn renewed AI interest with self-play [477].Source: Human Learning is Curriculum Learning · p. 219

7.2 AlphaGo

  • AlphaGo combined supervised and reinforcement learning with MCTS and three neural networks, refining existing approaches rather than relying on a single new technology.The search-eval design used fast and slow policy nets and a value net; the earlier hybrid system preceded AlphaGo Zero’s tabula rasa self-play design.Source: §7.2 · p. 219, §7.2.1 · p. 220, Figure 7.6 · p. 220

7.2.1 *AlphaGo Architecture

  • AlphaGo trained its slow policy from grandmaster games and self-play, its value net from self-play positions, and its fast rollout policy from human games.The slow policy used 160,000 grandmaster games comprising 28 million positions; the value net used 30 million self-play positions, and a parameter 𝜆 mixed its estimates with rollout outcomes.Source: §7.2.1 · pp. 220–221

7.2.2 AlphaGo Results

  • AlphaGo reached 5p dan, and its versions that faced Lee Sedol and Ke Jie reached 9p dan; all three networks contributed significantly and independently.A distributed cluster increased performance by around 200 Elo points; multiple GPUs and multithreading were also advantageous.Source: §7.2.2 · pp. 221–222, Figure 7.7 · p. 222, Figure 7.8 · p. 222

Playing Strength in Go

  • Go programs progressed from heuristic planning at medium-amateur strength to MCTS at strong-amateur strength and neural-net MCTS in AlphaGo at superhuman strength.The cited comparison also includes Tencent’s Fine Art.Source: Playing Strength in Go · p. 223, Figure 7.10 · p. 223

Popular Media

  • AlphaGo’s matches attracted extensive media attention, while building an open-source-inspired system was algorithmically doable but training its function approximators required substantial compute.Newspaper coverage, a movie, and enthusiast blogs followed the matches.Source: Popular Media · p. 224

Impact on Go

  • Go players welcomed AlphaGo’s innovations and new style, studied resulting Go theory, and showed increased interest in the game.Books on the new theory included Zhou.Source: Impact on Go · p. 224

Impact on Science; Impact on AI

  • The matches increased societal and scientific interest in AI, encouraged cross-disciplinary collaborations, and brought new talent and attendance to machine learning and reinforcement-learning communities.Interest in Go as an intelligence benchmark also increased attention to reproducibility [329] [476] and suites including ALE [53], Gym [98], ELF, StarCraft [727], and Mario; self-play remains computationally demanding, with reported speedups [765].Source: Impact on Science · pp. 224–225, Impact on AI · p. 225

Weak, Strong, and Ultrastrong AI

Michie distinguished weak AI by improved prediction with more data, strong AI by hypotheses and explanations, and ultrastrong AI by teaching hypotheses to humans. The passage says modern machine learning, including AlphaGo, remains weak AI, while explainable AI seeks strong AI.

Weak, Strong, and Ultrastrong AI

  • Weak AI improves prediction as data increases; strong AI also provides hypotheses and explanations; ultrastrong AI teaches its hypothesis to a human.Michie’s criteria assess the comprehensibility of learned knowledge, beyond predictive performance.Source: Weak, Strong, and Ultrastrong AI · p. 225
  • Modern machine learning, including AlphaGo, has achieved only weak AI, while explainable AI aims to achieve strong AI.The passage argues that AI must achieve more than weak AI to be truly useful in society.Source: Weak, Strong, and Ultrastrong AI · p. 225

Playing Strength

AlphaGo Zero surpassed the original AlphaGo after 36 hours of training, and its performance depended substantially on MCTS search.

Playing Strength

Tabula Rasa

AlphaGo Zero’s self-play learned Go from scratch, including standard and nonstandard knowledge; the discussion then turns to AlphaZero’s form of general learning across three games, with game-specific networks and no strict transfer between them.

Tabula Rasa

  • AlphaGo Zero discovered fundamental Go knowledge and nonstandard strategies beyond traditional Go knowledge during self-play.Source: Tabula Rasa · p. 226
  • Across hours of self-play, AlphaGo Zero learned joseki from a standard beginner opening to harder configurations; after 10 more hours, it favored a better 3-3 sequence over a weak corner move.Further training revealed more and better variations.Source: Tabula Rasa · p. 226, Figure 7.12 · p. 227

7.3.1 General Play: AlphaZero

  • Self-play taught the same MCTS-with-20-ResNet-blocks architecture to play Go, Chess, and Shogi, a form of general tabula rasa learning limited to three games [624].Source: §7.3.1 · p. 227
  • AlphaZero beat the strongest conventional players in Go, Chess, and Shogi: AlphaGo Zero, Stockfish, and Elmo, respectively.Source: §7.3.1 · p. 228
  • The networks used game-specific hand-crafted input and output layers and trained weights, so a Shogi-trained network could not play Go well.Chess and Shogi’s more complicated move patterns required more elaborate input planes than Go’s.Source: §7.3.1 · p. 228

Playing Strength · Go, Chess, and Shogi

AlphaZero is stronger than the compared programs across Chess, Shogi, and Go despite learning through self-play, and it demonstrates that one architecture can play all three games strongly. Its strength gap is smallest in Chess and larger in Shogi, while the games’ differing dynamics make this generality notable.

Playing Strength

  • AlphaZero is stronger than the compared programs across Chess, Shogi, and Go through self-play, with the smallest strength gap in Chess and a larger gap in Shogi.The comparison includes Stockfish, Elmo, AlphaGo Zero, and AlphaGo Lee.Source: Playing Strength · pp. 228–229, Figure 7.13 · p. 229
  • AlphaZero slightly outperforms AlphaGo Zero; it updates its network continually, while AlphaGo Zero accepts a new network only after it wins 55% of games against the old one.AlphaZero also does not exploit Go symmetries, and the paper gives no other reasons for the difference.Source: Playing Strength · p. 229

Go, Chess, and Shogi

  • AlphaZero uses one architecture across Go, Chess, and Shogi, whose strategic and tactical dynamics differ substantially.Go is static, Chess is dynamic, and Shogi adds captured pieces back into play under a change of loyalty.Source: Go, Chess, and Shogi · pp. 229–230
  • Conventional game-playing programs were crafted for individual games with game-specific knowledge and heuristics, an approach that had worked well in Chess and Shogi.The section identifies AlphaZero as the first demonstration that a general approach can also be strong.Source: Go, Chess, and Shogi · p. 230
  • For Go, the difficulty of finding successful hand-crafted heuristics led to learning from game databases in AlphaGo and later through self-play in AlphaGo Zero.Source: Go, Chess, and Shogi · p. 230
  • AlphaZero shows that different move patterns do not require a different kind of program to learn to play well.Source: Go, Chess, and Shogi · p. 230

One General Architecture … Explainable AI

This section examines AlphaZero’s self-play architecture and approaches to improving learning, scaling, and explainability in reinforcement learning, while identifying open directions for extending self-play. It then transitions from advanced topics to practice and chapter-review questions.

One General Architecture

  • AlphaZero learned Go, chess, and shogi with the same self-play algorithms, network, search, most hyperparameters, and hardware, changing only the input and output layers.The learning-rate decay scheme differed slightly for Go.Source: One General Architecture · p. 230, §7.3.2 · p. 230

Sample Efficiency

  • Self-play is sample-inefficient because model-free evaluation and repeated planning require many samples; pretraining and curriculum learning can lower initial error and make learning easier.Curriculum learning pretrains the network over successive iterations, each building on the previous one.Source: Sample Efficiency · p. 231, Pretraining · p. 231

Transfer Learning

  • Transfer learning initializes all or part of a network with weights from related tasks, while multitask learning trains related tasks jointly and meta-learning can adapt beyond weights.Lifelong learning seeks selective knowledge transfer across tasks; general game-playing programs typically trade generality for playing strength.Source: §7.3.2 · p. 230, Transfer Learning · p. 232, Multi-task learning · p. 232

7.3.3 Hyperparameter Optimization

  • Hyperparameter interactions make manual tuning difficult; AlphaGo Zero used Bayesian optimization, AlphaZero reused its hyperparameters, and alternatives include architecture search and evolution-strategy network optimization.Evolution strategies can be parallelized; distributional optimization considers both expected error and its variance.Source: §7.3.3 · pp. 233–234, Network Architecture · p. 234, Network Optimization · p. 235

7.3.4 Parallelism

  • Self-play can be sped up by parallelizing network training, MCTS, and independent tournament games within an iteration.GPUs and TPUs support parallel training; parallel games can fill the example buffer faster.Source: §7.3.4 · p. 235

7.3.5 Further Research

  • Open questions include speeding up self-play, extending it beyond two-agent board games, and understanding transfer, overfitting, the deadly triad, and which architectures or methods work best.The questions also cover imperfect-information games and the role of evolutionary or population-based methods.Source: §7.3.5 · pp. 235–236

Single-Agent Games

  • Research extends self-play beyond two-agent zero-sum games to single-agent optimization, cooperative or population games, sparse-reward exploration, and large action spaces.Single-agent problems may benefit from intermediate goals and self-play’s curriculum effect; Go-Explore combines remembered states, look-ahead, and exploration from promising states, with reported results on Montezuma’s Revenge and Pitfall [192]. Large action spaces can be segmented or discretized.Source: Single-Agent Games · p. 236, Multi-agent and Population-Based Methods · p. 237, Sparse Rewards · p. 237

Hierarchical Reinforcement Learning

Explainable AI

  • Explainable AI seeks symbolic reasoning with connectionist accuracy, using soft decision trees [229] [292] and adaptive neural trees [669] to distill neural-net knowledge.This work builds partly on model compression [136]; knowledge representation and reinforcement learning also intersect in decision support that explains recommendations, a field related to Bayesian and belief networks [678] [96].Source: Explainable AI · p. 239

7.4 Practice

  • The chapter turns from advanced topics to implementations, followed by closed review questions answerable in one sentence.Source: §7.4 · p. 240

Questions … Reinforcement Learning Generalization

The chapter presents self-play as a system combining planning, evaluation, and iterative learning, then connects game-playing methods to broader questions about intelligence and generalization. It traces a progression from explicit search to adaptive sampling and learned representations.

Questions / Core Concepts

  • The study questions range from AlphaGo and AlphaZero’s architectures and training to hierarchical reinforcement learning, sparse rewards, continuous actions, and explainable AI.The listed core concepts also include specialized versus general intelligence, sample efficiency, transfer learning, population-based methods, and multi-agent imperfect-information games.Source: Questions · pp. 240–241, Core Concepts · p. 245

7.4.1 Exercises

  • The exercises use AlphaZero General for self-play experiments, inviting learners to vary training and search settings, test transfer across board sizes, and implement new games.They also propose comparing an A0G-trained Othello player with a traditional program and exploring tabula rasa Chess against Sunfish.Source: §7.4.1 · p. 241
  • Self-play combines MCTS planning, neural-network evaluation, and a learning loop that repeatedly trains on search-generated examples, enabling tabula rasa play across Go, Chess, and Shogi.The chapter identifies this combination as its main conceptual innovation; MCTS supplies high-quality examples, and each new network guides the next self-play iteration. The self-play setting removes random rollouts and relies heavily on policy and value approximation.Source: §7.4.1 · p. 242
  • Self-play learns faster than a database approach and creates a natural curriculum by ordering examples from easy to hard.The chapter also links self-play’s success to research interest in curriculum and transfer learning.Source: §7.4.1 · p. 242

Historical and Bibliographical Notes

  • The historical notes identify AlphaGo as a landmark and trace relevant work from earlier Go and MCTS research to learning successes in other games.Examples include pre-MCTS shape and move prediction, Gelly and Silver’s work, Logistello, CNN Go results [144], DeepChess [160], Blondie24, Atari MCTS-DQN, and Poker combinations of planning and learning.Source: Historical and Bibliographical Notes · pp. 243–244

Chapter 8 Conclusion / Core Problems

  • The concluding chapter seeks ways to extend narrow, single-game intelligence toward general intelligence by analyzing prior methods, new domains, and human–AI relations.Its core questions concern the relation between artificial and human intelligence, which games support progress toward general intelligence, and essential methods for decision-making in games.Source: Chapter 8 Conclusion · p. 245, Core Problems · p. 245, §8.1 · p. 246

Planning / Heuristics / Adaptive / Sampling

  • The paradigm stack moves from reinforcement learning foundations through state-space planning, heuristic search, adaptive selection, and sampling with MCTS.Planning enumerates states; heuristics guide search toward promising nodes; UCT balances exploration and exploitation; sampling combines averaging, sampled evaluation, and UCT for large-branching domains without efficient heuristic features.Source: §8.1.1 · p. 246, Planning · p. 246, Heuristics · pp. 246–247

Supervised Generalization / Reinforcement Learning Generalization

Self-Play … Search-Eval

Self-play couples neural-network learning with search and repeatedly trains on examples generated by the improving player. Recursion, bootstrapping, optimization, and exploration support the broader search-eval approach that combines planning and learning.

Self-Play

  • Self-play combines a neural network with MCTS for UCT node selection and evaluation instead of random playouts, then uses generated examples to train the network iteratively.Source: Self-Play · p. 248
  • Self-play is recursive and can train features efficiently through curriculum learning, but it has stability issues and requires well-tuned exploration methods.Source: Self-Play · p. 248

Recursion and Bootstrapping

  • Recursion reuses a function with different parameters to traverse trees or state spaces, underpinning dynamic programming, self-play, and network weight updates.Source: Recursion and Bootstrapping · p. 249
  • Bootstrapping determines state values from previous values, underlies Bellman’s equation, and lets minimax evaluate the root from child values.Source: Recursion and Bootstrapping · p. 249
  • In AlphaZero self-play, recursion and bootstrapping appear in MCTS move selection, network generalization on example states, and a tournament-generated game curriculum.Source: Recursion and Bootstrapping · p. 249

Optimization

  • Reinforcement learners and game-playing programs are optimizers that seek the best values, actions, examples, architectures, and training hyperparameters.Source: Optimization · p. 249

Exploration

  • Optimization and bootstrapping work together in search-eval, while exploration supports state-space coverage, breaks correlated learning loops, and helps ensure convergent training.Source: Optimization · p. 249, Exploration · p. 249

Search-Eval

  • Search-eval combines exact planning with approximate learning; deep learning can learn evaluation functions but is sample-inefficient, while curriculum helps and self-play adds a bootstrap loop.Source: Search-Eval · p. 250

End-to-End … Detailed Self-Play Training

This section surveys reinforcement-learning game systems, environments, and self-play methods, including AlphaGo’s search, networks, and training. It also considers the limits and challenges of specialized AI, including sample efficiency and human-computer collaboration.

End-to-End

  • End-to-end learning progressed from Samuel’s hand-crafted features to TD-Gammon’s small network and AlphaGo’s deep network, allowing high performance without hand-crafted features and their biases.The text presents this progression as enabled by increasing compute and as producing true but still narrow artificial intelligence.Source: End-to-End · p. 250

8.1.3 On the Importance of Enhancements

  • Game-playing systems depend not only on conceptual frameworks but also on specialized enhancements grounded in deep domain understanding.Examples include transposition tables and singular extensions for Deep Blue, fast playout patterns for AlphaGo, and replay buffers for Atari.Source: §8.1.3 · pp. 250–251

8.1.4 Towards General Intelligence

  • Planning, adaptive sampling, function approximation, and self-play have produced champion-beating Chess and Go systems, but AlphaZero’s transfer across three games still involves separately specialized systems.The section characterizes this as single-domain intelligence: a system trained for Go cannot play Chess, and AlphaGo cannot play Shogi or tell an entertaining joke.Source: §8.1.4 · p. 251

8.2.1 Real-Time Strategy Games

  • Multi-agent imperfect-information games such as DOTA 2 and StarCraft pose challenges including large action and state spaces and long credit-assignment horizons, while systems have achieved strong results in Quake III and DOTA 2 [331] [70].Quake III’s population-learning system avoids MCTS and uses relatively simple, fast RNNs; Poker and Bridge research also addresses negotiation and collaboration, including successful simpler two-player Poker programs and continuing Bridge work.Source: §8.2.1 · p. 252, §8.2.2 · p. 252

8.2.3 Poker

  • In a 20-day, 120,000-hand competition with a $200,000 prize pool, Libratus defeated top human professionals in heads-up no-limit Texas hold’em.Its three modules compute strategies with counterfactual regret minimization, solve finer-grained subgames in real time, and add policies for missing branches using opponents’ actual moves; this narrowed gaps as play proceeded. CFR minimizes exploitability, while later work used deep CFR for Pluribus, and DeepStack trained a deep value network on randomly generated games.Source: §8.2.3 · pp. 253–254

8.2.4 StarCraft

  • In December 2018 test matches, AlphaStar beat two top players in two-player, single-map StarCraft matches after supervised training on anonymized human games and population-based self-play.StarCraft challenges AI with partial visibility, many actions and units, variable legal actions, long games, and delayed consequences for early decisions.Source: §8.2.4 · pp. 254–255

8.2.5 General Game Playing

  • General game playing aims to create one player for games specified by rules, using automatically generated game representations; the general search procedure MCTS proved well suited to this setting.The section contrasts this with AlphaZero, which requires hand-designed input and output layers, while GGP systems generate them from rules; GGP research has yielded advances toward more general AI.Source: §8.2.5 · pp. 255–256

Learning

  • Computers have become capable of learning in image recognition and Go, but their analytical explanations do not establish that they understand what they analyze.The section notes that AlphaGo Zero learns Go in days through curriculum learning, whereas humans take years; a Chess end-game proof likewise does not show computer understanding.Source: Learning · p. 258, Understanding · p. 258

Game Intelligence

  • Game-playing methods have moved from game-specific search and heuristics toward more general learned function approximators and self-play, though performance tuning can reintroduce game specificity.Self-play dispenses with grandmaster-game databases and learns through a curriculum.Source: Game Intelligence · p. 261

Artificial Intelligence

8.3.3 Next Steps: Sample Efficiency and Collaboration

  • Multi-agent games extend beyond zero-sum competition by modeling teamwork and forms of human-machine interaction.The section presents collaboration as a major challenge alongside sample efficiency.Source: §8.3.3 · p. 262, Collaboration · p. 264

Curriculum Learning

  • AlphaZero learns beyond human world-champion level in days, while human champions take years, using self-play that generates training examples from easy to hard.The section says computers in Chess, Shogi, and Go learn faster than humans.Source: Curriculum Learning · p. 263, Faster and Together · p. 264

Sample Efficiency for AGI

  • Sample efficiency remains low because each new task starts from scratch; transfer, meta-learning, hierarchical learning, and model-based learning are described as ways to address this challenge.AlphaZero did not transfer a trained network to another task; MuZero instead learns a latent model and infers game rules from the environment.Source: Sample Efficiency for AGI · p. 263

Collaboration

  • Population-based reinforcement learning has achieved high collaboration in leagues of humans and computers across Poker, StarCraft, Capture the Flag, and DOTA 2.The section identifies negotiation and human-computer team play as further directions for games research.Source: Collaboration · p. 264, Faster and Together · p. 264

System 1 and System 2

Deep Reinforcement Learning Environments

  • The environment and framework landscape includes Atari Learning Environment in Gym, Stable Baselines, Baseline Zoo, Dopamine, RLlib, Bsuite, OpenSpiel, and Meta World.Stable Baselines supports TensorFlow 1.8.0–1.14.0; TensorFlow 2 API support was planned, while Meta World benchmarks multi-task and meta reinforcement learning.Source: Deep Reinforcement Learning Environments · pp. 268–269

Open Reimplementations of AlphaZero Self-Play

  • Open self-play implementations include educational A0G for small games, ELF’s OpenGo reimplementation, Chess and Go versions of Leela, Tencent’s trained PhoenixGo, and PolyGames bots for Hex, Othello, and Havannah.A0G is scaled for smaller resources; Leela does not include trained weights, while PhoenixGo provides a trained network.Source: A0G: AlphaZero General · p. 269, Facebook ELF · p. 270, Leela · p. 270

Search Algorithm

  • AlphaGo’s MCTS uses P-UCT priors, GPU-queued leaf evaluation, and a 50/50 blend of value-network and fast-rollout estimates, with parallel tree updates.Expansion thresholds depend on GPU queue length; parallel search uses virtual loss and lock-free updates.Source: Search Algorithm · pp. 271–272

Network Architecture

  • AlphaGo’s selection policy has 13 layers and its value network 14; inputs comprise 48 feature planes, with softmax policy and tanh value outputs.The fast rollout policy instead uses a hash table based on 3 × 3 patterns and a last-good-reply heuristic.Source: Network Architecture · p. 272, Input/Output Features · p. 272

Performance of the Three Networks

  • The fast rollout policy achieves 24% test accuracy with a 2 μs response time, 1,500 times faster than the slow policy; the supervised selection policy achieves 57% accuracy in 3 ms.The value network was trained on 30 million self-play positions, and its training took 50 GPUs one week.Source: Performance of the Three Networks · p. 273
  • The self-play-trained policy network won 85% of games against Pachi, versus 11% for the supervised-only network; AlphaGo nevertheless used the weaker supervised network for MCTS selection.The text speculates that the supervised network’s greater move variation may explain its use, while noting that more work is needed to understand the choice.Source: Performance of the Three Networks · p. 273

Compute Hardware

  • AlphaGo ran 40 search threads on 48 CPU cores and 8 GPUs; its distributed version ran on 1202 CPUs and 176 GPUs.The system executes simulations on CPUs while computing policy and value networks in parallel on GPUs.Source: Compute Hardware · p. 274

Detailed Self-Play Training

  • AlphaGo Zero self-play stores each MCTS search distribution and game outcome with its state, then trains a network to match search probabilities and predict outcomes.Its combined loss adds mean-squared value error, cross-entropy policy loss, and L2 weight regularization.Source: Detailed Self-Play Training · p. 274

Network Architecture … Index

This section covers AlphaGo Zero’s self-play residual policy/value network and value-guided MCTS, and AlphaZero’s generalization of that architecture across games. It also lists figures on neural-network architectures and reinforcement-learning game methods, followed by index entries for related concepts, systems, and people.

Network Architecture

  • AlphaGo Zero uses one self-play residual network with policy and value heads instead of AlphaGo’s separate value and policy nets, and MCTS uses value lookups rather than rollouts.The supervised and reinforcement-learning position databases and the fast rollout network are also removed.Source: Network Architecture · pp. 274–275
  • AlphaGo Zero’s combined policy/value network improved playing performance by 600 Elo points, while a ResNet comparison with AlphaGo reported over 600 Elo improvement, greater accuracy, and lower errors.Source: Network Architecture · p. 275
  • The network uses convolutional blocks with batch normalization and ReLU; the tournament player used 20 blocks because 40-block complexity did not justify its computational cost.Source: Network Architecture · p. 275

Search Algorithm

  • MCTS uses P-UCT with policy-head priors, no RAVE or leaf rollouts, 25,000 self-play games per iteration, and 1,600 simulations per move; hyperparameters were selected by Gaussian process optimization.Source: Search Algorithm · p. 277

B.3 AlphaZero

  • AlphaZero generalizes the simpler AlphaGo Zero architecture across games, using 19×19×17 Go planes, 8×8×73 Chess planes, and 9×9×139 Shogi planes; alternative encodings somewhat affected training efficiency.Source: §B.3 · p. 277, Input/Output Features · p. 277

Matches of Fan Hui, Lee Sedol, and Ke Jie

3.1 Reinforcement learning:

  • The architecture figures cover biological neurons, shallow and deep networks, convolution and pooling, residual networks, recurrent networks, and LSTMs.They also list overfitting, activation functions, deep fakes, and deep dreams.Source: §3.1 · p. 332
  • The reinforcement-learning figures include agent–environment feedback, Atari and DQN, Rainbow performance, self-play, Monte Carlo Tree Search, AlphaGo, AlphaGo Zero, and AlphaZero.Later entries include model-free and model-based methods.Source: §3.1 · p. 333

Index

  • The index cross-references reinforcement-learning terms and systems, including TD learning, ϵ-greedy, AlphaGo networks, AlphaGo Zero, AlphaZero, and AlphaStar.It also indexes fast rollout and slow selection policy networks and the value network.Source: Index · p. 339
  • Other index entries include feature discovery, function approximation, hierarchical reinforcement learning, value iteration, vanishing gradients, and virtual loss.The index also lists people and topics such as Fei-Fei Li, ImageNet, and VGG.Source: Index · pp. 340, 342

Related papers

Loading 2610.17391v1…