Difference between revisions of "AlphaZero"

From Chessprogramming wiki
Jump to: navigation, search
Line 10: Line 10:
  
 
=Description=  
 
=Description=  
−
Starting from random play, and given no domain knowledge except the game rules, AlphaZero achieved a superhuman level of play in the games of chess and [[Shogi]] as well as in [[Go]]. The algorithm is a more generic version of the [[AlphaGo#Zero|AlphaGo Zero]] algorithm that was first introduced in the domain of Go <ref>[https://deepmind.com/blog/alphago-zero-learning-scratch/ AlphaGo Zero: Learning from scratch] by [[Demis Hassabis]] and [[David Silver]], [[DeepMind]], October 18, 2017</ref> . AlphaZero [[Evaluation|evaluates]] [[Chess Position|positions]] using non-linear function approximation based on a [[Neural Networks|deep neural network]], rather than the [[Evaluation#Linear|linear function approximation]] as used in classical chess programs. This neural network takes the board position as input and outputs a vector of move probabilities. The MCTS consists of a series of simulated games of self-play whose move selection is controlled by the neural network. The search returns a vector representing a probability distribution over moves, either proportionally or greedily with respect to the visit counts at the root state.
+
Starting from random play, and given no domain knowledge except the game rules, AlphaZero achieved a superhuman level of play in the games of chess and [[Shogi]] as well as in [[Go]]. The algorithm is a more generic version of the [[AlphaGo#Zero|AlphaGo Zero]] algorithm that was first introduced in the domain of Go <ref>[https://deepmind.com/blog/alphago-zero-learning-scratch/ AlphaGo Zero: Learning from scratch] by [[Demis Hassabis]] and [[David Silver]], [[DeepMind]], October 18, 2017</ref>. AlphaZero [[Evaluation|evaluates]] [[Chess Position|positions]] using non-linear function approximation based on a [[Neural Networks|deep neural network]], rather than the [[Evaluation#Linear|linear function approximation]] as used in classical chess programs.  
 +
This neural network takes the board position as input and outputs a vector of move probabilities (policy) and a position evaluation. Once trained, these network is combined with a [[Monte-Carlo Tree Search]] (MCTS) using the policy to narrow down the search to high ­probability moves, and using the value in conjunction with a fast rollout policy to evaluate positions in the tree. The selection is done by a variation of [[Christopher D. Rosin|Rosin's]] [[UCT]] improvement dubbed [[Christopher D. Rosin#PUCT|PUCT]].
  
 
==Network Architecture==
 
==Network Architecture==
−
The network is a [[Neural Networks#Deep|deep]] [[Neural Networks#Residual|residual]] [[Neural Networks#Convolutional|convolutional neural network]] <ref>The principle of residual nets is to add the input of the layer to the output of each layer. With this simple modification training is faster and enables deeper networks, see  [[Tristan Cazenave]] ('''2017'''). ''[http://ieeexplore.ieee.org/document/7875402/ Residual Networks for Computer Go]''. [[IEEE#TOCIAIGAMES|IEEE Transactions on Computational Intelligence and AI in Games]], Vol. PP, No. 99, [http://www.lamsade.dauphine.fr/~cazenave/papers/resnet.pdf pdf]</ref> <ref>[http://www.talkchess.com/forum/viewtopic.php?t=65923 Residual Networks for Computer Go] by Brahim Hamadicharef, [[CCC]], December 07, 2017</ref> with many layers of spatial NxN planes - [[8x8 Board|8x8 board]] arrays for chess. The input describes the [[Chess Position|chess position]] from [[Side to move|side's to move]] point of view - that is [[Color Flipping|color flipped]] for black to move. Each square cell consists of 12 [[Pieces#PieceTypeCoding|piece-type]] and [[Color|color]] bits, e.g. from the current [[Bitboard Board-Definition|bitboard board definition]], and to address [[Graph History Interaction|graph history]] and [[Path-Dependency|path-dependency]] - times eight, that is up to seven predecessor positions as well - so that [[En passant|en passant]], immediate [[Repetitions|repetitions]], or some sense of progress is implicit. Additional inputs, redundant inside each square cell  to be conform to the convolution net, consider [[Castling Rights|castling rights]], [[Halfmove Clock|halfmove clock]], total move count and side to move.  
+
The [[Neural Networks#Deep|deep neural network]] consists of a “body” with input and hidden layers of spatial NxN planes, [[8x8 Board|8x8 board]] arrays for chess, followed by both policy and value “heads” <ref>[[David Silver]], [[Thomas Hubert]], [[Julian Schrittwieser]], [[Ioannis Antonoglou]], [[Matthew Lai]], [[Arthur Guez]], [[Marc Lanctot]], [[Laurent Sifre]], [[Dharshan Kumaran]], [[Thore Graepel]], [[Timothy Lillicrap]], [[Karen Simonyan]], [[Demis Hassabis]] ('''2018'''). ''[http://science.sciencemag.org/content/362/6419/1140 A general reinforcement learning algorithm that masters chess, shogi, and Go through self-play]''. [https://en.wikipedia.org/wiki/Science_(journal) Science], Vol. 362, No. 6419, [http://science.sciencemag.org/content/suppl/2018/12/05/362.6419.1140.DC1 Supplementary Materials] - Architecture</ref> <ref>[http://www.talkchess.com/forum3/viewtopic.php?f=2&t=69175&start=93 Re: Alphazero news] by [[Matthew Lai]], [[CCC]], December 08, 2018</ref>. 
 +
Each square cell of the input plane contains 6x2 [[Pieces#PieceTypeCoding|piece-type]] and [[Color|color]] bits of the current [[Chess Position|chess position]] from the current player's point of view, plus two bits of a [[Repetitions|repetition counter]] concerning the [[Draw|draw]] rule,
 +
and to further address [[Graph History Interaction|graph history]] and [[Path-Dependency|path-dependency]] issues - these 14 bits times eight, that is up to seven predecessor positions as well - so that [[En passant|en passant]], or some sense of progress is implicit.  
 +
Additional 7 input bits consider [[Castling Rights|castling rights]], total move count and [[Side to move|side to move]], yielding in 119 bits per square cell for chess.  
  
−
The deep hidden layers connect the pieces on different squares to each other due to consecutive 3x3 convolutions, where a cell of a layer is connected to the correspondent 3x3 [https://en.wikipedia.org/wiki/Receptive_field receptive field] of the previous layer, so that after 4 layers, each square is connected to every other cell in the original input layer <ref>[http://www.talkchess.com/forum/viewtopic.php?t=65937&start=10 Re: AlphaZero is not like other chess programs] by [[Rein Halbersma]], [[CCC]], December 09, 2017</ref>. The output of the neural network is finally represented as an 8x8 board array as well, for every [[Origin Square|origin square]] up to 73 [[Target Square|target square]] possibilities ([[Direction#MoveDirections|NRayDirs]] x [[Rays|MaxRayLength]] + [[Direction#KnightDirections|NKnightDirs]] + NPawnDirs * [[Promotions|NMinorPromotions]]), encoding a probability distribution over 64x73 = 4,672 possible moves, where illegal moves were masked out by setting their probabilities to zero, re-normalising the probabilities for remaining moves.
+
The body consists of a [https://en.wikipedia.org/wiki/Rectifier_(neural_networks) rectified] [https://en.wikipedia.org/wiki/Batch_normalization batch-normalized] [[Neural Networks#Convolutional|convolutional layer]] followed by 19 [[Neural Networks#Residual|residual]] blocks. Each such block consists of two rectified batch-normalized residual convolutional layers with a skip connection <ref>The principle of residual nets is to add the input of the layer to the output of each layer. With this simple modification training is faster and enables deeper networks,  see [[Tristan Cazenave]] ('''2017'''). ''[http://ieeexplore.ieee.org/document/7875402/ Residual Networks for Computer Go]''.  [[IEEE#TOCIAIGAMES|IEEE Transactions on Computational Intelligence and AI in Games]], Vol. PP, No. 99, [http://www.lamsade.dauphine.fr/~cazenave/papers/resnet.pdf pdf]</ref> <ref>[http://www.talkchess.com/forum/viewtopic.php?t=65923 Residual Networks for Computer Go] by Brahim Hamadicharef, [[CCC]], December 07, 2017</ref>. Each convolution applies 256 filters (shared weight vectors) of kernel size 3x3 with [https://en.wikipedia.org/wiki/Stride_of_an_array stride] 1.
 +
These layers connect the pieces on different squares to each other due to consecutive convolutions, where a cell of a layer is connected to the correspondent 3x3 [https://en.wikipedia.org/wiki/Receptive_field receptive field] of the previous layer,  
 +
so that after 4 convolutions, each square is connected to every other cell in the original input layer <ref>[http://www.talkchess.com/forum/viewtopic.php?t=65937&start=10 Re: AlphaZero is not like other chess programs] by [[Rein Halbersma]], [[CCC]], December 09, 2017</ref>.  
 +
 
 +
The policy head applies an additional rectified, batch-normalized convolutional layer, followed by a final convolution of 73 filters for chess,
 +
with the final policy output represented as an 8x8 board array as well, for every [[Origin Square|origin square]] up to 73 [[Target Square|target square]] possibilities ([[Direction#MoveDirections|NRayDirs]] x [[Rays|MaxRayLength]] + [[Direction#KnightDirections|NKnightDirs]] + NPawnDirs * [[Promotions|NMinorPromotions]]), encoding a probability distribution over 64x73 = 4,672 possible moves, where illegal moves were masked out by setting their probabilities to zero, re-normalising the probabilities for remaining moves. The value head applies an additional rectified, batch-normalized convolution of 1 filter of kernel size 1x1 with stride 1, followed by a rectified linear layer of size 256 and a [https://en.wikipedia.org/wiki/Hyperbolic_function tanh]-linear layer of size 1.
  
 
==Training==
 
==Training==
Line 85: Line 94:
 
: [http://www.talkchess.com/forum3/viewtopic.php?f=2&t=69175&start=82 Re: Alphazero news] by [[Matthew Lai]], [[CCC]], December 07, 2018
 
: [http://www.talkchess.com/forum3/viewtopic.php?f=2&t=69175&start=82 Re: Alphazero news] by [[Matthew Lai]], [[CCC]], December 07, 2018
 
: [http://www.talkchess.com/forum3/viewtopic.php?f=2&t=69175&start=86 Re: Alphazero news] by [[Matthew Lai]], [[CCC]], December 07, 2018 » [[Giraffe]]
 
: [http://www.talkchess.com/forum3/viewtopic.php?f=2&t=69175&start=86 Re: Alphazero news] by [[Matthew Lai]], [[CCC]], December 07, 2018 » [[Giraffe]]
 +
: [http://www.talkchess.com/forum3/viewtopic.php?f=2&t=69175&start=93 Re: Alphazero news] by [[Matthew Lai]], [[CCC]], December 08, 2018
  
 
=External Links=  
 
=External Links=  

Revision as of 13:03, 9 December 2018

Home * Engines * AlphaZero

The Krampus has come [1] [2]

AlphaZero,
a chess and Go playing entity by Google DeepMind based on a general reinforcement learning algorithm with the same name. On December 5, 2017, the DeepMind team around David Silver, Thomas Hubert, and Julian Schrittwieser along with former Giraffe author Matthew Lai, reported on their generalized algorithm, combining Deep learning with Monte-Carlo Tree Search (MCTS) [3] .

Stockfish Match

A 100 game match versus Stockfish 8 using 64 threads and a transposition table size of 1GiB, was won by AlphaZero using a single machine with 4 Tensor processing units (TPUs) with +28=72-0. Despite a possible hardware advantage of AlphaZero and criticized playing conditions [4], this seems a tremendous achievement.

Description

Starting from random play, and given no domain knowledge except the game rules, AlphaZero achieved a superhuman level of play in the games of chess and Shogi as well as in Go. The algorithm is a more generic version of the AlphaGo Zero algorithm that was first introduced in the domain of Go [5]. AlphaZero evaluates positions using non-linear function approximation based on a deep neural network, rather than the linear function approximation as used in classical chess programs. This neural network takes the board position as input and outputs a vector of move probabilities (policy) and a position evaluation. Once trained, these network is combined with a Monte-Carlo Tree Search (MCTS) using the policy to narrow down the search to high ­probability moves, and using the value in conjunction with a fast rollout policy to evaluate positions in the tree. The selection is done by a variation of Rosin's UCT improvement dubbed PUCT.

Network Architecture

The deep neural network consists of a “body” with input and hidden layers of spatial NxN planes, 8x8 board arrays for chess, followed by both policy and value “heads” [6] [7]. Each square cell of the input plane contains 6x2 piece-type and color bits of the current chess position from the current player's point of view, plus two bits of a repetition counter concerning the draw rule, and to further address graph history and path-dependency issues - these 14 bits times eight, that is up to seven predecessor positions as well - so that en passant, or some sense of progress is implicit. Additional 7 input bits consider castling rights, total move count and side to move, yielding in 119 bits per square cell for chess.

The body consists of a rectified batch-normalized convolutional layer followed by 19 residual blocks. Each such block consists of two rectified batch-normalized residual convolutional layers with a skip connection [8] [9]. Each convolution applies 256 filters (shared weight vectors) of kernel size 3x3 with stride 1. These layers connect the pieces on different squares to each other due to consecutive convolutions, where a cell of a layer is connected to the correspondent 3x3 receptive field of the previous layer, so that after 4 convolutions, each square is connected to every other cell in the original input layer [10].

The policy head applies an additional rectified, batch-normalized convolutional layer, followed by a final convolution of 73 filters for chess, with the final policy output represented as an 8x8 board array as well, for every origin square up to 73 target square possibilities (NRayDirs x MaxRayLength + NKnightDirs + NPawnDirs * NMinorPromotions), encoding a probability distribution over 64x73 = 4,672 possible moves, where illegal moves were masked out by setting their probabilities to zero, re-normalising the probabilities for remaining moves. The value head applies an additional rectified, batch-normalized convolution of 1 filter of kernel size 1x1 with stride 1, followed by a rectified linear layer of size 256 and a tanh-linear layer of size 1.

Training

AlphaZero was trained in 700,000 steps or mini-batches of size 4096 each, starting from randomly initialized parameters, using 5,000 first-generation TPUs [11] to generate self-play games and 64 second-generation TPUs [12] [13] [14] to train the neural networks [15] .

See also

Publications

Forum Posts

2017

Re: AlphaZero is not like other chess programs by Rein Halbersma, CCC, December 09, 2017

2018

Re: Alphazero news by Matthew Lai, CCC, December 07, 2018
Re: Alphazero news by Matthew Lai, CCC, December 07, 2018
Re: Alphazero news by Larry Kaufman, CCC, December 07, 2018
Re: Alphazero news by Kai Laskos, CCC, December 07, 2018
Re: Alphazero news by Matthew Lai, CCC, December 07, 2018
Re: Alphazero news by crem, CCC, December 07, 2018
Re: Alphazero news by Matthew Lai, CCC, December 07, 2018
Re: Alphazero news by crem, CCC, December 07, 2018
Re: Alphazero news by Matthew Lai, CCC, December 07, 2018
Re: Alphazero news by Gian-Carlo Pascutto, CCC, December 07, 2018 » Leela Chess Zero
Re: Alphazero news by Matthew Lai, CCC, December 07, 2018
Re: Alphazero news by Matthew Lai, CCC, December 07, 2018 » Giraffe
Re: Alphazero news by Matthew Lai, CCC, December 08, 2018

External Links

GitHub - suragnair/alpha-zero-general: A clean and simple implementation of a self-play learning algorithm based on AlphaGo Zero (any game, any framework!)

Reports

2017

2018

Stockfish Match

Round 1

Round 2, 3

Misc

lineup: Irmin Schmidt, Michael Karoli, Holger Czukay, Damo Suzuki, Jaki Liebezeit

References

  1. ↑ Krampus, figure used in threatening children, Image from the 1900s, source: Historie čertů Krampus, Category:Krampus, Wikimedia Commons
  2. ↑ "5th of December - The Krampus has come" was suggested by Michael Scheidl in AlphaZero by Peter Martan, CSS Forum, December 06, 2017, with further comments by Ingo Althöfer
  3. ↑ David Silver, Thomas Hubert, Julian Schrittwieser, Ioannis Antonoglou, Matthew Lai, Arthur Guez, Marc Lanctot, Laurent Sifre, Dharshan Kumaran, Thore Graepel, Timothy Lillicrap, Karen Simonyan, Demis Hassabis (2017). Mastering Chess and Shogi by Self-Play with a General Reinforcement Learning Algorithm. arXiv:1712.01815
  4. ↑ Alpha Zero by BB+, OpenChess Forum, December 06, 2017
  5. ↑ AlphaGo Zero: Learning from scratch by Demis Hassabis and David Silver, DeepMind, October 18, 2017
  6. ↑ David Silver, Thomas Hubert, Julian Schrittwieser, Ioannis Antonoglou, Matthew Lai, Arthur Guez, Marc Lanctot, Laurent Sifre, Dharshan Kumaran, Thore Graepel, Timothy Lillicrap, Karen Simonyan, Demis Hassabis (2018). A general reinforcement learning algorithm that masters chess, shogi, and Go through self-play. Science, Vol. 362, No. 6419, Supplementary Materials - Architecture
  7. ↑ Re: Alphazero news by Matthew Lai, CCC, December 08, 2018
  8. ↑ The principle of residual nets is to add the input of the layer to the output of each layer. With this simple modification training is faster and enables deeper networks, see Tristan Cazenave (2017). Residual Networks for Computer Go. IEEE Transactions on Computational Intelligence and AI in Games, Vol. PP, No. 99, pdf
  9. ↑ Residual Networks for Computer Go by Brahim Hamadicharef, CCC, December 07, 2017
  10. ↑ Re: AlphaZero is not like other chess programs by Rein Halbersma, CCC, December 09, 2017
  11. ↑ First In-Depth Look at Google’s TPU Architecture by Nicole Hemsoth, The Next Platform, April 05, 2017
  12. ↑ Photo of Google Cloud TPU cluster by Norman Schmidt, CCC, December 09, 2017
  13. ↑ First In-Depth Look at Google’s New Second-Generation TPU by Nicole Hemsoth, The Next Platform, May 17, 2017
  14. ↑ Under The Hood Of Google’s TPU2 Machine Learning Clusters by Paul Teich, The Next Platform, May 22, 2017
  15. ↑ David Silver, Thomas Hubert, Julian Schrittwieser, Ioannis Antonoglou, Matthew Lai, Arthur Guez, Marc Lanctot, Laurent Sifre, Dharshan Kumaran, Thore Graepel, Timothy Lillicrap, Karen Simonyan, Demis Hassabis (2017). Mastering Chess and Shogi by Self-Play with a General Reinforcement Learning Algorithm. arXiv:1712.01815
  16. ↑ AlphaZero: Shedding new light on the grand games of chess, shogi and Go by David Silver, Thomas Hubert, Julian Schrittwieser and Demis Hassabis, DeepMind, December 03, 2018
  17. ↑ AlphaZero explained by one creator by Mario Carbonell Martinez, CCC, December 19, 2017
  18. ↑ A Simple Alpha(Go) Zero Tutorial by Oliver Roese, CCC, December 30, 2017
  19. ↑ BBC News; 'Google's ... DeepMind AI claims chess crown' by pennine22, Hiarcs Forum, December 07, 2017
  20. ↑ Reactions about AlphaZero from top GMs... by Norman Schmidt, CCC, December 08, 2017
  21. ↑ recent article on alphazero ... 12/11/2017 ... by Dan Ellwein, CCC, December 14, 2017
  22. ↑ Cerebellum analysis of the AlphaZero - Stockfish Games by Thomas Zipproth, CCC, December 11, 2017
  23. ↑ AlphaZero reinvents mobility and romanticism by Chris Whittington, Rybka Forum, December 08, 2017
  24. ↑ Immortal Zugzwang Game from Wikipedia
  25. ↑ Article:"How Alpha Zero Sees/Wins" by AA Ross, CCC, January 17, 2018
  26. ↑ Connect 4 AlphaZero implemented using Python... by Steve Maughan, CCC, January 29, 2018

Up one Level

Retrieved from "https://www.chessprogramming.org/index.php?title=AlphaZero&oldid=9089"