Mastering the game of Go with deep neural
networks and tree search
[Link]
Hieu Nguyen – Godaddy Inc.
2022-02-18
Reinforcement Learning Overview
• Data: from interacting with the environment {s,a}t
• Model:
• Goal: maximize expected future rewards
Steve Brunton, Data Driven Science & Engineering, Chapter 11
Value and Policy – Main Idea
+1 0.81 0.88 0.95 +1
-1 0.69 0 0.218 -1
Start 0.28 0.03 0.008 -0.2
The Game of Go
Game of Go:
• 19x19 grid ancient board game
• Search space complexity: ~10^170
AI Challenge:
• How to effectively search through
an intractable space?
AlphaGo
Defeated 18x Go Champion Lee Sedol in 2016
AlphaGo – High Level Training Pipeline
AlphaGo – SL Policy Network
• Arch: 12-layer CNN
• Training data: 30M positions from expert games
• Input: 19x19x48
• Objective function: max. likelihood by SGD
• Training time: 4 weeks on 50 GPUs
• Results: 57% accuracy on test set (44% state of the art)
AlphaGo – Rollout Policy
• Usage: fast rollout enables narrower search for
moves during simulation
• Arch: more simple linear softmax classifier
• Training data: 8M positions from expert games
• Objective function: max. likelihood by SGD
• Training time: N/A
• Results: 24.2% accuracy on test set
• Speed: 2us vs 3ms in SL policy network (1500x faster)
Policy Gradient Theorems
Main idea:
- Compute how much the expected rewards changes
wrt to how much each P changes
- Backprob these partial derivatives to the NN, the
weights will update to produce new Ps such that the
E[R] is maximized
[Link]
AlphaGo – RL Policy Network
• Usage: reinforce current SL policy and will be used
for self-play to generate training data for value
network
• Arch: 12-layer CNN
• Training data: 10,000 mini-batches of 128 self-play
games between policy networks
• Objective function: max. rewards zt by policy
gradient reinforcement learning
• Training time: 1 week on 50 GPUs
• Results: 80% win rate over SL policy network
• Notes:
• They don’t play each other on the same policy
AlphaGo – Value Network
• Usage: quantify how good a board position is
• Arch: 12-layer CNN
• Training data: 30 million games of self-play
generated from RL policy network
• Input: 19x19x(48 + 1) (colour to play)
• Objective function: min. MSE by SGD
• Training time: 1 week on 50 GPUs
AlphaGo – Quick Recap
• Policy network: guides us to the next best moves
• Value network: quantify the quality of a board position
• Next, they complement these networks to help with search priorities
during game simulations.
AlphaGo – Why Simulation?
With sufficient games are simulated till the end from current
position, we will get an idea which moves likely lead to the most
wins. In the process, they build a search tree recording sequences
of moves and their corresponding winning rates.
Exhaustive Search
Monte Carlo Tree Search (MCTS)
Monte Carlo Tree Search (MCTS) consists of 4 main steps:
MCTS is run on 48 CPUs in 40 threads; the policy and value evaluation
run on 8 GPUs.
MCTS – Selection & Expansion
Goal: to prioritize most promising moves for further simulations.
This allows finding good moves with fewer games played
- Q: exploitation; u: exploration
- Policy Network: Probability taking action a in state s
- Number of time action a has been selected in state s
- The quality of being in state s and taking action a
- Value Network: how advantageous is it to be in this position
MCTS – Evaluation & Backup
• In the evaluation, simulate the rest of the game
using rollout policy starting from the leaf node until
the end of the game to see whether it loses or
wins.
• After the evaluation, we know our moves win/lose
statistics. In the backup phase, update Q(s,a) to
remember how well to make a move from the
game results and the leaf node’s value function.
MCTS – Results
References/Resources:
- David Silver RL Series, DeepMind
- Steve Brunton, uWashington – Data Driven Science & Engineering
- Pascal Poupart, uWaterloo – CS885: Reinforcement Learning
- Martin Lysy, uWaterloo – Stats946: Advanced Computational Statistics