chapter6.pdf

Notes on Chapter 6: Self-Play and Two-Agent Zero-Sum Problems 1 Core Concepts Self-Play: A training method where an agent learns by playing against itself. This technique is particularly effective in two-agent zero-sum games. Two-Agent Zero-...

Notes on Chapter 6: Self-Play and Two-Agent Zero-Sum Problems 1 Core Concepts Self-Play: A training method where an agent learns by playing against itself. This technique is particularly effective in two-agent zero-sum games. Two-Agent Zero-Sum Game: A game where one player’s gain is exactly equal to the other player’s loss. Examples include chess, Go, and backgammon. Perfect Information Game: A game where all players have access to all information about the game state. 2 Core Problem Core Problem: The main challenge is to develop agents that can learn to play complex two-agent zero-sum games from scratch, without relying on human knowledge or heuristics. This involves creating algorithms that can effectively explore, learn, and plan in these environments. 3 Core Algorithms Core Algorithms: Key algorithms used in self-play include Minimax, Monte Carlo Tree Search (MCTS), Policy and Value Networks, and various curriculum learning techniques. 4 Self-Play in Games Example: Learning to play backgammon through self-play. This involves the agent playing against itself, gradually improving its strategy through repeated games. 5 6.1 Two-Agent Zero-Sum Problems Zero-Sum Perfect-Information Games: Games where one player’s gain is another player’s loss, and all information is available to both players. 5.1 6.1.1 The Difficulty of Playing Go Playing Strength in Go: Go is a highly complex game with a vast number of possible moves, making it difficult for traditional algorithms to achieve high playing strength. 5.2 6.1.2 AlphaGo Achievements AlphaGo Achievements: AlphaGo was the first program to defeat a world champion Go player, using a combination of deep neural networks and Monte Carlo Tree Search (MCTS). 1 6 6.2 Tabula Rasa Self-Play Agents Cycle of Virtuous Improvement: A self-reinforcing cycle where self-play leads to continuous improvement in an agent’s playing ability. AlphaGo Zero Self-Play in Detail: AlphaGo Zero learned to play Go from scratch using only self-play, without any human input or heuristics. Algorithm 1 AlphaGo Zero Self-Play Cycle 1: Initialize neural network θ 2: for each iteration do 3: Generate self-play games using current policy πθ 4: Train neural network θ using self-play data 5: Update policy πθ based on new neural network parameters 6: end for 6.1 6.2.1 Move-Level Self-Play Minimax: A decision rule used for minimizing the possible loss for a worst-case scenario. In games, it is used to find the optimal move by assuming the opponent also plays optimally. Equation: Minimax Minimax(s) = max min ′ Utility(s′ ) a s Monte Carlo Tree Search (MCTS): An algorithm that uses random sampling of the search space to make decisions in game playing. It balances exploration of new moves and exploitation of known good moves. 6.1.1 6.2.1.2 Monte Carlo Tree Search The Four MCTS Operations: 1. Selection: Starting from the root, recursively select optimal child nodes until a leaf node is reached. 2. Expansion: If the leaf node is not terminal, expand it by adding one or more child nodes. 3. Simulation: Run a simulation from the new nodes to obtain an outcome. 4. Backpropagation: Update the values of all nodes on the path from the leaf to the root based on the simulation result. Algorithm 2 Monte Carlo Tree Search (MCTS) 1: Initialize root node N0 2: for each iteration do 3: Nl ← Selection(N0 ) 4: Nc ← Expansion(Nl ) 5: z ← Simulation(Nc ) 6: Backpropagation(Nc , z) 7: end for 8: return arg maxa Q(N0 , a) Policies: In MCTS, policies guide the selection and expansion steps. The Upper Confidence bounds applied to Trees (UCT) is a common policy used. Equation: UCT Selection s Q(s, a) ln N (s) U CT = +c N (s, a) N (s, a) 2  P-UCT: A variant of UCT that incorporates prior probabilities from a neural network to guide the search. Equation: P-UCT p Q(s, a) N (s) P − U CT = + c · P (a|s) · N (s, a) 1 + N (s, a) Exploration/Exploitation: Balancing the exploration of new actions with the exploitation of known rewarding actions. Applications: MCTS has been successfully applied in games like Go, Chess, and Shogi, particu- larly in programs like AlphaGo and AlphaZero. 6.2 6.2.2 Example-Level Self-Play Policy and Value Network: Neural networks used to approximate the policy (probability dis- tribution over actions) and the value function (expected outcome from a state). Equation: Policy Network π(a|s; θ) Equation: Value Network V (s; θ) Stability and Exploration: Ensuring stable learning through regularization and encouraging exploration to avoid local minima. 6.3 6.2.3 Tournament-Level Self-Play Curriculum Learning: A method where the agent learns tasks in a sequence of increasing difficulty, which helps in better generalization and faster learning. Algorithm 3 Self-Play Curriculum Learning 1: Initialize curriculum C with tasks of increasing difficulty 2: for each task c ∈ C do 3: Train agent on task c using self-play 4: end for Self-Play Curriculum Learning: Gradually increasing the difficulty of self-play tasks to improve the agent’s performance. Supervised and Reinforcement Curriculum Learning: Combining supervised learning with reinforcement learning in a curriculum to leverage the strengths of both methods. Procedural Content Generation: Automatically generating tasks or environments to train the agent. Active Learning: Allowing the agent to choose the most informative examples to learn from. Single-Agent Curriculum Learning: Applying curriculum learning techniques in a single-agent context to improve performance. 7 6.3 Self-Play Environments How to Design a World Class Go Program?: Discussing the architectural and algorithmic components needed to create a top-performing Go program. AlphaGo Zero Performance: Highlighting the performance metrics and achievements of Al- phaGo Zero, which learned to play Go from scratch using self-play. 3  AlphaZero: A generalization of AlphaGo Zero that achieved superhuman performance in Chess, Shogi, and Go using the same architecture. General Game Architecture: The architecture used in AlphaZero and similar programs, com- bining neural networks with MCTS. Open Self-Play Frameworks: Discussing open frameworks and tools for developing self-play agents. Hands On: Hex in Polygames Example: A practical example using the Polygames framework to create a self-play agent for the game of Hex. 8 Summary and Further Reading Summary: A recap of the key points covered in the chapter, emphasizing the benefits and chal- lenges of self-play in two-agent zero-sum games. Further Reading: Suggested literature and resources for a deeper understanding of self-play methods and their applications. Questions 1. What are the differences between AlphaGo, AlphaGo Zero, and AlphaZero? AlphaGo used supervised learning from human games and reinforcement learning, AlphaGo Zero learned purely from self-play without human data, and AlphaZero generalized the approach to Chess and Shogi, learning from self-play alone. 2. What is MCTS? Monte Carlo Tree Search (MCTS) is a search algorithm that uses random sampling of the search space to make decisions, balancing exploration and exploitation. 3. What are the four steps of MCTS? The four steps of MCTS are Selection, Expansion, Simulation, and Backpropagation. 4. What does UCT do? Upper Confidence bounds applied to Trees (UCT) selects actions in MCTS by bal- ancing the value of known rewards with the exploration of less-visited actions. 5. Give the UCT formula. How is P-UCT different? UCT Formula: s Q(s, a) ln N (s) U CT = +c N (s, a) N (s, a) P-UCT incorporates prior probabilities from a neural network: p Q(s, a) N (s) P − U CT = + c · P (a|s) · N (s, a) 1 + N (s, a) 6. Describe the function of each of the four operations of MCTS. Selection: Select the optimal child node recursively until a leaf node is reached. Expansion: Add one or more child nodes to the leaf node if it is not terminal. Simulation: Run a simulation from the new nodes to obtain an outcome. Backpropagation: Update the values of all nodes on the path from the leaf to the root based on the simulation result. 4  7. How does UCT achieve trading off exploration and exploitation? Which inputs does it use? UCT achieves trade-off by using the formula that balances the average reward (exploitation) with the exploration term that favors less-visited actions. It uses the number of visits to the state-action pair N (s, a) and the total number of visits to the state N (s). 8. When Cp is small, does MCTS explore more or exploit more? When Cp is small, MCTS tends to exploit more. 9. For small numbers of node expansions, would you prefer more exploration or more exploitation? For small numbers of node expansions, more exploration is generally preferred to gather more information about the search space. 10. What is a double-headed network? How is it different from regular actor critic? A double-headed network has two output heads, one for the policy (action probabilities) and one for the value (expected return). It differs from regular actor-critic which typically has separate networks for policy and value functions. 11. Which three elements make up the self-play loop? (You may draw a picture.) The three elements are Self-Play, Training the Neural Network, and Updating the Policy. 12. What is tabula rasa learning? Tabula rasa learning refers to learning from scratch without any prior knowledge or data. 13. How can tabula rasa learning be faster than reinforcement learning on top of super- vised learning of grandmaster games? Tabula rasa learning can be faster as it avoids the constraints of biased data and explores the search space more freely, potentially discovering novel strategies. 14. What is curriculum learning? Curriculum learning is a method where an agent learns tasks in a sequence of increasing difficulty to improve generalization and learning speed. In class Question 1. In what year did AlphaGo beat Lee Sedol? AlphaGo beat Lee Sedol in 2016. 2. How many AlphaGos are there? There are three main versions: AlphaGo, AlphaGo Zero, and AlphaZero. 3. What is the difference between AlphaGo and AlphaGo Zero? AlphaGo used supervised learning from human games and reinforcement learning, while Al- phaGo Zero learned purely from self-play without any human data. 4. What are the two architectural elements of AlphaGo Zero? The two architectural elements are the policy network and the value network. 5. What is self-play? Self-play is a training method where an agent learns by playing against itself. 6. How many levels of self-play are there in AlphaGo Zero? 5  There are three levels: move-level, example-level, and tournament-level self-play. 7. What is Minimax? Minimax is a decision rule used for minimizing the possible loss for a worst-case scenario in zero-sum games. 8. What is the estimated size of the state in Go? The estimated size of the state space in Go is 10170. 9. What are the two architectural elements of conventional Chess programs? The two architectural elements are the search algorithm and the evaluation function. 10. How does MCTS work? MCTS works by selecting nodes to explore based on a balance of exploration and exploitation, expanding new nodes, simulating outcomes from those nodes, and backpropagating the results to update the tree. 11. What does the UCT formula determine? The UCT formula determines the action selection in MCTS by balancing the average reward and the exploration term. 12. Explain the AlphaGo Zero self-play loop. The AlphaGo Zero self-play loop involves generating self-play games using the current policy, training the neural network with self-play data, and updating the policy based on the new neural network parameters. 13. What is the biggest problem that was overcome in AlphaGo Zero? The biggest problem overcome was the reliance on human knowledge and heuristics, allowing the system to learn entirely from self-play. 14. Why is AlphaGo Zero faster than AlphaGo? AlphaGo Zero is faster because it does not rely on human data, which simplifies the learning process and reduces the computational overhead associated with supervised learning. 15. What is curriculum learning? Curriculum learning is a method where an agent learns tasks in a sequence of increasing difficulty to improve generalization and learning speed. 16. What is AlphaZero? AlphaZero is a generalization of AlphaGo Zero that achieved superhuman performance in Chess, Shogi, and Go using the same architecture and learning from self-play alone. 6