Learning to Play: Reinforcement Learning and Games

In plain words

This is a book, not a single method. It explains how computers learned to play games such as Go, Chess and Shogi well, and how the ideas behind that fit together. It starts from old game-playing programs that searched ahead through possible moves and scored positions with hand-written rules, then moves on to learning systems that improve their own scoring from experience.

The central idea is a search that looks ahead through possible futures, paired with a learned judgement of how good a position is. A Monte Carlo tree search plays many random or guided games from the current position, keeps counts of what worked, and steers future play toward the promising moves. Neural networks then replace hand-written rules, and the programs train by playing against themselves.

The book also covers the history: the famous match results and the research steps that led there.

TL;DR

Textbook covering reinforcement learning in games, from MDPs and heuristic search through MCTS with UCT, deep Q-learning and self-play. It is a teaching resource, not a reproducible training recipe. Its concrete numbers for AlphaGo, AlphaGo Zero and AlphaZero are taken from the original papers and cited to the appendix, so an implementer still needs those papers for full training details. Compiled from the arXiv LaTeX source; no official code repository was found.

Problem

Full search of a game tree is infeasible for games such as Go, so programs need to decide which parts of the tree to examine and how to score positions without searching to the end §4.1 §5.2. Earlier strong programs for Chess and Shogi relied on alpha-beta search with domain-specific heuristics, and the book argues that a learned, self-play-based approach beat them without such heuristics §7.3.1. For Go, the book describes AlphaGo's progress as ten years ahead of what most experts had expected §7.2.1.

Imperfect-information games such as Poker and real-time strategy games are discussed as separate challenges §8.2.

Method

The book organises its material as a search-evaluation architecture: a search procedure looks ahead, and an evaluation function scores positions where the search stops §4.1. The main chapters are:

• Chapter 3, reinforcement learning: Markov decision processes, policy, state-value and action-value functions, and solution methods such as Bellman recursion, exploration, actor-critic and sample efficiency §3.1 §3.2 §3.3.
• Chapter 4, heuristic planning: the search-eval architecture, and search enhancements such as alpha-beta, iterative deepening and transposition tables §4.1 §4.3.
• Chapter 5, adaptive sampling: Monte Carlo evaluation and Monte Carlo tree search (MCTS), including UCT and enhancements such as RAVE §5.1 §5.2 §5.3.
• Chapter 6, function approximation: deep supervised learning, network architectures, deep Q-learning (DQN), and enhancements such as prioritized replay and distributional DQN §6.1 §6.2 §6.3 §6.4.
• Chapter 7, self-play: the self-play architecture, the AlphaGo, AlphaGo Zero and AlphaZero case studies, and self-play enhancements §7.1 §7.2 §7.3.
• Chapter 8, conclusion: AI in games, future research domains and general intelligence §8.1 §8.2.
• Appendices: environments app. A, technical details of AlphaGo, AlphaGo Zero and AlphaZero app. B, tournament records app. C, and resources app. D.

MCTS loop

The book describes MCTS as four operations repeated for a fixed number of iterations (typically 1,000 to 10,000) or until time runs out: select, expand, playout and backpropagate §5.2 §5.2.1. The tree stores a visit count v and a win count w per node §5.2. The selection rule is UCT §5.2.4:

\mathrm{UCT}(j) = \frac{w_j}{n_j} + C_p \sqrt{\frac{\ln n}{n_j}}

Here w_j is the wins of child j, n_j its visits, n the visits of the parent, and C_p >= 0 a tunable constant §5.2.4.

# One MCTS search from the root state  [§5.2] [§5.2.1]
# Input:  root state, iteration budget (typically 1000-10,000)  [§5.2]
# Output: the root action with the highest visit count  [§5.2.2]

def mcts_search(root_state, iterations):
    # Each node keeps a visit count and a win count  [§5.2]
    root = new_node(root_state)
    for _ in range(iterations):
        # 1. Select: walk down by UCT to a node with an unexplored child  [§5.2.4]
        node = root
        while fully_expanded(node) and not is_terminal(node):
            node = best_child_by_uct(node)
        # 2. Expand: add one child to the tree  [§5.2.1]
        if not is_terminal(node):
            node = add_child(node)
        # 3. Playout: play moves to the end of the game  [§5.2.1]
        result = playout(node.state)
        # 4. Backpropagate: update counts on the path back to the root  [§5.2.1]
        for n in path_to_root(node):
            n.visits += 1
            if result_is_win_for(n, result):
                n.wins += 1
    # Return the root action with the most visits  [§5.2.2]
    return action_with_most_visits(root)

The book's playout reward is +1 for a win by the first player, 0 for a draw and -1 for a loss §5.2.1.

AlphaGo (2016)

AlphaGo is presented as a combination of existing techniques rather than one new invention §7.2.1. Its search is MCTS, and it uses three neural networks trained with four methods §7.2.1 app. B:

• a slow selection policy network, pre-trained by supervised learning on expert games and then refined by reinforcement learning from self-play;
• a value network trained on self-play positions, giving a leaf evaluation;
• a fast rollout policy network trained by supervised learning from human games, used for playouts in place of random moves app. B.

The slow policy's prior probabilities are used in the UCT selection step through a P-UCT variant that adds prior information to the formula app. B. Leaf values mix the value-network output with the result of a fast rollout, with the mixing weight set to 0.5 app. B. The book does not write out the mixing formula.

# AlphaGo leaf evaluation  [app. B, Rollout]
# value_net: one tanh output  [app. B, Network Architecture]
# lam = 0.5 weights the rollout against the value network  [app. B]

def leaf_value(leaf_state, value_net, fast_policy, lam):
    # Estimate from the value network  [app. B]
    value = value_net(leaf_state)
    # Result of one playout with the fast rollout policy  [app. B]
    outcome = fast_rollout(leaf_state, fast_policy)
    # Combine the two estimates; the mixing rule is not written out  [app. B]
    return mix(value, outcome, weight=lam)

AlphaGo Zero

AlphaGo Zero replaces the three networks by one residual network with a policy head and a value head, trained purely by self-play from random weights. It uses no rollouts, so the fast policy network is gone app. B, AlphaGo Zero. The self-play loop generates games with MCTS guided by the previous network, stores (state, search probabilities, outcome) triples, and trains the next network on samples from recent games app. B, Detailed Self-Play Training.

# AlphaGo Zero self-play loop  [app. B, Detailed Self-Play Training]
# Start from a randomly initialised network theta_0  [app. B]

def self_play_iteration(network, games_per_iteration):
    # Generate a batch of self-play games  [app. B]
    examples = []
    for _ in range(games_per_iteration):
        state = initial_state()
        history = []
        while not is_game_over(state):
            # MCTS guided by the previous network  [app. B]
            probs = mcts(state, network, simulations=1600)
            move = sample_move(probs)
            history.append((state, probs))
            state = apply_move(state, move)
        # Outcome z in {-1, +1} for every position of the game  [app. B]
        z = outcome(state)
        for position, probs in history:
            examples.append((position, probs, z))
    return examples

Training minimises a combined loss: squared error between predicted value and outcome, cross-entropy between the policy head and the search probabilities, and an L2 weight penalty app. B:

l = (z - v)^2 - \pi^{\mathsf T} \log p + c \lVert \theta \rVert^2

where c controls L2 regularisation. Its value is not stated app. B. The network input is a 19x19x17 stack of binary planes: the current board and the previous eight moves for each colour, plus the colour to play app. B.

AlphaZero

AlphaZero applies the same search-eval architecture, with MCTS and a 20-block residual network, to Go, Chess and Shogi §7.3.1. The input and output planes differ per game. Chess uses an 8x8x73 move encoding, Shogi uses 9x9x139, and Go keeps the 19x19x17 Go planes app. B, AlphaZero. The book notes that the trained networks do not transfer between games §7.3.1.

Hyperparameters

Results

Author-reported. Setup: the games are Go, Chess and Shogi. The book reports the results of the original papers and does not rerun them §7.2.2 §7.3.1 app. B.

Paper vs code

No official code. Searched: the book's companion site learningtoplay.net (linked from the text in §1.2 §1.2) lists only PDFs and no repositories; a GitHub repository search for the title returned nothing; and the author's GitHub account lists no repository for this book. Its repositories (baselines, keras, MPIAB, ParAB, hexviz, and others) are unrelated or lack a license, so none was used.

The arXiv source includes Python listings under python/ and in python/sunfish/. They carry no license for the book's own code, and the sunfish directory is a third-party project, so none of it is used or cited. The book's MCTS listing is attributed to an external blog example and to the Browne et al. survey §5.2.1.

Pitfalls

• No single method. The book explains many algorithms at textbook depth. An implementer needs the original AlphaGo, AlphaGo Zero and AlphaZero papers for complete training details, which the book defers to app. B.
• Win counting is under-specified. The book increments the win count only on a win and leaves it unchanged on a loss §5.2.1. It does not say how draws are counted, nor from which player's perspective a "win" is recorded, even though playouts give +1, 0 or -1 §5.2.1. Implement the perspective explicitly.
• Reward scale for C_p. The UCT win-rate term is w/n §5.2.4, but the book does not give the reward scale for which C_p = 5 was chosen app. B. Changing between [0, 1] and [-1, 1] rewards changes the exploration balance.
• Value target conventions differ. AlphaGo's value network is a single tanh output that the book describes as a probability of winning app. B. AlphaGo Zero trains the value against an outcome z in {-1, +1} app. B. The book does not reconcile the two.
• Block counts. The book describes a "20-block" and a "40-block" network, and also "19 or 39 residual blocks" plus one convolutional block app. B. The explicit counts are 39 or 79 parameterised layers in total app. B.
• Decorrelation of training data is required. The book says the value network's positions were made uncorrelated with a small self-play search, and the fast policy was trained on positions from separate games to avoid overfitting app. B. These steps are not optional details.
• Hidden compute cost. Each position evaluation requires several networks, which costs far more compute than a heuristic evaluation. The search runs asynchronously on CPUs while networks are evaluated on GPUs app. B.
• Values not stated. The loss coefficient, learning rates and batch sizes for AlphaGo Zero, and the numeric AlphaZero Elo values, are not in the text app. B §7.3.1.
• Section numbers. The cited section numbers were derived from the book's LaTeX source order. Check them against the compiled PDF before relying on them.

Lineage

• Builds on: Browne et al.'s MCTS survey §5.2.1, Kocsis and Szepesvári's UCT rule (2006) §5.2.4, and the three Silver et al. papers on AlphaGo, AlphaGo Zero and AlphaZero app. B. None of these is a card in this wiki, so the book's descriptions were used without their content.
• Compared against: Stockfish, Elmo, Pachi and AlphaGo Lee §7.2.2 §7.3.1 app. B.
• Superseded by: not known from content in this wiki.