Changes

Jump to: navigation, search

AlphaZero

18,092 bytes added, 09:27, 17 April 2021
no edit summary
'''[[Main Page|Home]] * [[Engines]] * AlphaZero'''
[[FILE:Krampus 1900s 3.jpg{|border|right- style="vertical-align:top;"|thumb| The Krampus has come '''AlphaZero''',<refbr/>a chess and [https://en.wikipedia.org/wiki/Krampus Krampus[Go]] playing entity by [[Google]] [[DeepMind]] based on a general [[Reinforcement Learning|reinforcement learning]], figure used in threatening children, Image from algorithm with the 1900s, source: [http://wwwsame name.krampus-certi.cz/historie.html Historie čertů Krampus], On [https://commonsen.wikimediawikipedia.org/wiki/Category:Krampus Category:KrampusDecember_5#Holidays_and_observances December 5], [https://en.wikipedia.org/wiki/Wikimedia_Commons Wikimedia CommonsPortal:Current_events/2017_December_5 2017]</ref> <ref>"5th of December - The [https://en.wikipedia.org/wiki/Krampus Krampus] has come" was , suggested by [[Michael Scheidl]] in [http://forum.computerschach.de/cgi-bin/mwf/topic_show.pl?tid=9635 AlphaZero] by Peter Martan, [[Computer Chess Forums|CSS Forum]], December 06, 2017, with further comments by [[Ingo Althöfer]]</ref> , 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|Deep learning]] with [[Monte-Carlo Tree Search]] (MCTS) <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]] ('''2017'''). ''Mastering Chess and Shogi by Self-Play with a General Reinforcement Learning Algorithm''. [https://arxiv.org/abs/1712.01815 arXiv:1712.01815]</ref>. The final [https://en.wikipedia.org/wiki/Peer_review peer reviewed] paper with various clarifications was published almost one year later in the [https://en.wikipedia.org/wiki/Science_(journal) Science magazine] under the title ''A general reinforcement learning algorithm that masters chess, shogi, and Go through self-play'' <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</ref>.
'''AlphaZero''',<br/>
a chess and [[Go]] playing entity by [[Google]] [[DeepMind]] based on a general [[Reinforcement Learning|reinforcement learning]] algorithm with the same name. On [https://en.wikipedia.org/wiki/December_5#Holidays_and_observances December 5], [https://en.wikipedia.org/wiki/Portal:Current_events/2017_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|Deep learning]] with [[Monte-Carlo Tree Search]] (MCTS) <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]] ('''2017'''). ''Mastering Chess and Shogi by Self-Play with a General Reinforcement Learning Algorithm''. [https://arxiv.org/abs/1712.01815 arXiv:1712.01815]</ref> .
=Stockfish Match=A 100 Starting from random play, and given no domain knowledge except the game match versus rules, AlphaZero achieved a superhuman level of play in the games of chess and [[Stockfish|Stockfish 8Shogi]] using 64 as well as in [[Thread|threadsGo]] and . The algorithm is a more generic version of the [[Transposition TableAlphaGo#Zero|transposition tableAlphaGo Zero]] size algorithm that was first introduced in the domain of 1GiB, was won by AlphaZero using a single machine with 4 Go <ref>[https://en.wikipediadeepmind.orgcom/wikiblog/Tensor_processing_unit Tensor processing units] (TPUs) with +28=72alphago-zero-0. Despite a possible hardware advantage of AlphaZero and criticized playing conditions <ref>[http://www.openlearning-chess.orgscratch/viewtopic.php?f=5&t=3153 Alpha AlphaGo Zero: Learning from scratch] by [[Mark Watkins|BB+Demis Hassabis]] and [[David Silver]], [[Computer Chess Forums|OpenChess ForumDeepMind]], December 06October 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, this seems and using the value in conjunction with a fast rollout policy to evaluate positions in the tree. The selection is done by a tremendous achievementvariation of [[Christopher D. Rosin|Rosin's]] [[UCT]] improvement dubbed [[Christopher D. Rosin#PUCT|PUCT]].
| style="width: 30%" | <span style=Description"display: block; text-align: center;"><span style= Starting from random play"font-family: Comic Sans MS,cursive; font-size: 100%;">„Zero<br/>ist die Stille. Zero ist der<br/>Anfang. Zero ist rund. Zero dreht sich.<br/>Zero ist der Mond. Die Sonne ist Zero.<br/>Zero ist weiss. Die Wüste Zero. Der Himmel<br/>über Zero. Die Nacht –, Zero fließt. Das Auge<br/>Zero. Nabel. Mund. Kuß. Die Milch ist rund. Die<br/>Blume Zero der Vogel. Schweigend. Schwebend. Ich<br/>esse Zero, ich trinke Zero, ich schlafe Zero, ich wache<br/>Zero, ich liebe Zero. Zero ist schön, dynamo, dynamo,<br/>dynamo. Die Bäume im Frühling, der Schnee, Feuer,<br/>Wasser, and given no domain knowledge except the game rulesMeer. Rot orange gelb grün indigo blau violett<br/>Zero Zero Regenbogen. 4 3 2 1 Zero. Gold und<br/>Silber, AlphaZero achieved a superhuman level of play in the games of chess and [[Shogi]] as well as in [[Go]]Schall und Rauch. Wanderzirkus Zero.<br/>Zero ist die Stille. Zero ist der Anfang.<br/>Zero ist rund. The algorithm is a more generic version of the [[AlphaGo#Zero|AlphaGo ist<br/>Zero]] algorithm that was first introduced in the domain of Go .“ </span></span> <ref>[https://deepmindde.comwikipedia.org/blogwiki/alphago-zero-learning-scratch/ AlphaGo ZERO#Manifest Zero: Learning from scratchManifesto] by [https://en.wikipedia.org/wiki/G%C3%BCnther_Uecker Günther Uecker], [Demis Hassabis]https://en.wikipedia.org/wiki/Heinz_Mack Heinz Mack] and [https://en.wikipedia.org/wiki/Otto_Piene Otto Piene] of the [David Silverhttps://en.wikipedia.org/wiki/Zero_(art) ZERO][https://en.wikipedia.org/wiki/Art_movement Art group]1963, Translation by [[DeepMindhttps://en.wikipedia.org/wiki/Google_Translate Google Translate]], October 18, 2017<br/ref> "Zero is silence. AlphaZero [[Evaluation|evaluates]] [[Chess Position|positions]] using non-linear function approximation based on a [[Neural Networks|deep neural network]], rather than Zero is the [[Evaluation#Linear|linear function approximation]] as used in classical chess programsbeginning. Zero is round. Zero turns. This neural network takes Zero is the board position as input and outputs a vector of move probabilitiesmoon. The sun is zero. Zero is white. The desert zero. The sky over zero. The MCTS consists of a series of simulated games of selfnight -play whose move selection , Zero flows. The eye zero. Navel. Mouth. Kiss. The milk is controlled by round. The flower zero the neural networkbird. Silently. Pending. I eat Zero, I drink Zero, I sleep Zero, I watch Zero, I love Zero. Zero is beautiful, dynamo, dynamo, dynamo. The search returns a vector representing a probability distribution over movestrees in spring, either proportionally or greedily with respect to the visit counts at snow, fire, water, sea. Red orange yellow green indigo blue violet zero zero rainbow. 4 3 2 1 Zero. Gold and silver, noise and smoke. Zero circus. Zero is silence. Zero is the root statebeginning. Zero is round. Zero is zero."<br/>Zero the new Idealism</ref>|}
==Network Architecture==
The network is a [[Neural Networks#Deep|deepneural 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 body consists of a [https://en.wikipedia.org/wiki/Rectifier_(neural_networks) rectified] [https://en.wikipedia.org/wiki/Batch_normalization batch-normalized] [[Neural Networks#ResidualConvolutional|residualconvolutional layer]] followed by 19 [[Neural Networks#ConvolutionalResidual|convolutional neural networkresidual]] 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 many layers of spatial NxN planes - [[8x8 Board|8x8 boardhttps://en.wikipedia.org/wiki/Stride_of_an_array stride]] arrays for chess1. The input describes These layers connect the [[Chess Position|chess position]] from [[Side pieces on different squares to move|side's each other due to move]] point consecutive convolutions, where a cell of view - that a layer is [[Color Flipping|color flipped]] for black connected to move. Each square cell consists of 12 the correspondent 3x3 [[Pieces#PieceTypeCoding|piece-type]] and [[Color|color]] bits, ehttps://en.gwikipedia. from org/wiki/Receptive_field receptive field] of the current [[Bitboard Board-Definition|bitboard board definition]], and to address [[Graph History Interaction|graph history]] and [[Path-Dependency|path-dependency]] - times eightprevious layer, that is up to seven predecessor positions as well - so that [[En passant|en passant]], immediate [[Repetitions|repetitions]]after 4 convolutions, or some sense of progress is implicit. Additional inputs, redundant inside each square is connected to every other cell to be conform to in the convolution net, consider original input layer <ref>[http://www.talkchess.com/forum/viewtopic.php?t=65937&start=10 Re: AlphaZero is not like other chess programs] by [[Castling Rights|castling rightsRein Halbersma]], [[Halfmove Clock|halfmove clockCCC]], total move count and side to moveDecember 09, 2017</ref>.
The deep hidden layers connect the pieces on different squares to each other due to consecutive 3x3 convolutionspolicy head applies an additional rectified, batch-normalized convolutional layer, where followed by a cell final convolution 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 layers73 filters for chess, each square is connected to every other cell in with 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 final policy 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 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==
AlphaZero was trained in 700,000 steps or mini-batches of size 4096 each, starting from randomly initialized parameters, using 5,000 [https://en.wikipedia.org/wiki/Tensor_processing_unit#First_generation first-generation TPUs] <ref>[https://www.nextplatform.com/2017/04/05/first-depth-look-googles-tpu-architecture/ First In-Depth Look at Google’s TPU Architecture] by [https://www.nextplatform.com/author/nicole/ Nicole Hemsoth], [https://www.nextplatform.com/ The Next Platform], April 05, 2017</ref> to generate self-play games and 64 [https://en.wikipedia.org/wiki/Tensor_processing_unit#Second_generation second-generation TPUs] <ref>[http://www.talkchess.com/forum/viewtopic.php?t=65945 Photo of Google Cloud TPU cluster] by [[Norman Schmidt]], [[CCC]], December 09, 2017</ref> <ref>[https://www.nextplatform.com/2017/05/17/first-depth-look-googles-new-second-generation-tpu/ First In-Depth Look at Google’s New Second-Generation TPU] by [https://www.nextplatform.com/author/nicole/ Nicole Hemsoth], [https://www.nextplatform.com/ The Next Platform], May 17, 2017</ref> <ref>[https://www.nextplatform.com/2017/05/22/hood-googles-tpu2-machine-learning-clusters/ Under The Hood Of Google’s TPU2 Machine Learning Clusters] by Paul Teich, [https://www.nextplatform.com/ The Next Platform], May 22, 2017</ref> to train the neural networks <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]] ('''2017'''). ''Mastering Chess and Shogi by Self-Play with a General Reinforcement Learning Algorithm''. [https://arxiv.org/abs/1712.01815 arXiv:1712.01815]</ref> .
 
=Stockfish Match=
As mentioned in the December 2017 paper <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]] ('''2017'''). ''Mastering Chess and Shogi by Self-Play with a General Reinforcement Learning Algorithm''. [https://arxiv.org/abs/1712.01815 arXiv:1712.01815]</ref>,
a 100 game match versus [[Stockfish|Stockfish 8]] using 64 [[Thread|threads]] and a [[Transposition Table|transposition table]] size of 1GiB,
was won by AlphaZero using a single machine with 4 [https://en.wikipedia.org/wiki/Tensor_processing_unit#First_generation first-generation TPUs] with +28=72-0, 10 games were published. Despite a possible hardware advantage of AlphaZero and criticized playing conditions <ref>[http://www.open-chess.org/viewtopic.php?f=5&t=3153 Alpha Zero] by [[Mark Watkins|BB+]], [[Computer Chess Forums|OpenChess Forum]], December 06, 2017</ref>, this is a tremendous achievement.
 
In the final [https://en.wikipedia.org/wiki/Peer_review peer reviewed] paper, published in [https://en.wikipedia.org/wiki/Science_(journal) Science magazine] in December 2018 <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</ref> along with supplementary materials <ref>[http://science.sciencemag.org/content/suppl/2018/12/05/362.6419.1140.DC1 Supplementary Materials]</ref>, a 1000 game match was reported with about 200 games published, versus various most recent Stockfish versions available at the time of the matches, that is Stockfish 8, a development version as of January 13, 2018 close to Stockfish 9, [[Brainfish]] with [[Cerebellum]] book, and Stockfish 9, in total AlphaZero winning 155 games and losing 6 games.
 
Stockfish was configured according to its [[TCEC Season 9#Superfinal|2016 TCEC Season 9 superfinal]] settings: 44 threads on 44 cores (two 2.2GHz [[Intel]] [https://en.wikipedia.org/wiki/Xeon#E3-12xx_v4_series_%22Broadwell-WS%22 Xeon Broadwell] [[x86-64]] CPUs with 22 cores, running [[Linux]]), a transposition table size of 32 GiB, and 6-men [[Syzygy Bases|Syzygy bases]]. Time control was 3 hours per side and game plus 15 seconds increment per move. AlphaZero used a simple time control strategy: thinking for 1/20th of the remaining time, and selects moves greedily with respect to the root visit count. Each MCTS was executed on a single machine with 4 [https://en.wikipedia.org/wiki/Tensor_processing_unit#First_generation first-generation TPUs].
 
AlphaZero and Stockfish (except Brainfish) used no [[Opening Book|opening book]], 12 common human positions as well as the [[TCEC Season 9#Superfinal|2016 TCEC Season 9 superfinal]] positions were played, originally selected by [[Jeroen Noomen]] <ref>[http://science.sciencemag.org/content/suppl/2018/12/05/362.6419.1140.DC1 Supplementary Materials] S4</ref>. To ensure diversity against opponents (Brainfish) with a deterministic opening book, AlphaZero used a small amount of randomization in its opening moves. This avoided duplicate games but also resulted in more losses by AlphaZero.
=See also=
* [[Learning#Programs|Learning Chess Programs]]
* [[Leela Chess Zero]]
* [[Zeta36]]
=Publications=
==2017==
* [[David Silver]], [[Julian Schrittwieser]], [[Karen Simonyan]], [[Ioannis Antonoglou]], [[Shih-Chieh Huang|Aja Huang]], [[Arthur Guez]], [[Thomas Hubert]], [[Lucas Baker]], [[Matthew Lai]], [[Adrian Bolton]], [[Yutian Chen]], [[Timothy Lillicrap]], [[Fan Hui]], [[Laurent Sifre]], [[George van den Driessche]], [[Thore Graepel]], [[Demis Hassabis]] ('''2017'''). ''[https://www.nature.com/nature/journal/v550/n7676/full/nature24270.html Mastering the game of Go without human knowledge]''. [https://en.wikipedia.org/wiki/Nature_%28journal%29 Nature], Vol. 550, [https://www.gwern.net/docs/rl/2017-silver.pdf pdf]
* [[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''. [https://arxiv.org/abs/1712.01815 arXiv:1712.01815]
==2018==* [[David SilverGeorge Rajna]], ('''2018'''). ''AlphaZero Just Playing''. [[Thomas Huberthttp://vixra.org/abs/1802.0330 viXra:1802.0330]], * [[Julian Schrittwieser]], [[Ioannis Antonoglou]], [[Matthew Lai]], [[Arthur Guez]], [[Marc Lanctot]], [[Laurent Sifre]], [[Dharshan Kumaran]], [[Thore Graepel]], [[Timothy Lillicrap]], [[Karen Simonyan]], [[Demis HassabisMathematician#VGCerf|Vinton G. Cerf]] ('''2018'''). ''[httphttps://sciencecacm.sciencemagacm.org/contentmagazines/3622018/64197/1140 A general reinforcement learning algorithm that masters chess, shogi, and Go through self229041-on-neural-playnetworks/fulltext On Neural Networks]''. [https://en.wikipedia.org/wiki/Science_(journal) Science[ACM#Communications|Communications of the ACM]], Vol. 36261, No. 6419 <ref>7** [[Hermann Kaindl]] ('''2018'''). ''[https://deepmindcacm.comacm.org/blogmagazines/alphazero2018/12/232884-sheddingreclaim-newinternet-light-grand-games-chessgreatness/fulltext Comment -shogi-and-go/ AlphaZero: Shedding new light on the grand games of chess, shogi and GoLookahead Search for Computer Chess] by ''. [[David SilverACM#Communications|Communications of the ACM]], [[Thomas Hubert]]Vol. 61, [[Julian Schrittwieser]] and [[Demis Hassabis]], [[DeepMind]], December 03, 2018</ref>No. 12
* [[Garry Kasparov]] ('''2018'''). ''[http://science.sciencemag.org/content/362/6419/1087 Chess, a Drosophila of reasoning]''. [https://en.wikipedia.org/wiki/Science_(journal) Science], Vol. 362, No. 6419
* [[Murray Campbell]] ('''2018'''). ''[http://science.sciencemag.org/content/362/6419/1118 Mastering board games]''. [https://en.wikipedia.org/wiki/Science_(journal) Science], Vol. 362, No. 6419
* [[Chu-Hsuan Hsueh]], [[I-Chen Wu]], [[Jr-Chang Chen]], [[Tsan-sheng Hsu]] ('''2018'''). ''AlphaZero for a Non-Deterministic Game''. [[TAAI 2018]] » [[Chinese Dark Chess]]
* [[Nai-Yuan Chang]], [[Chih-Hung Chen]], [[Shun-Shii Lin]], [[Surag Nair]] ('''2018'''). ''[https://dl.acm.org/citation.cfm?id=3278325 The Big Win Strategy on Multi-Value Network: An Improvement over AlphaZero Approach for 6x6 Othello]''. [https://dl.acm.org/citation.cfm?id=3278312 MLMI2018]
* [[Yen-Chi Chen]], [[Chih-Hung Chen]], [[Shun-Shii Lin]] ('''2018'''). ''[https://dl.acm.org/citation.cfm?id=3293486 Exact-Win Strategy for Overcoming AlphaZero]''. [https://dl.acm.org/citation.cfm?id=3293475 CIIS 2018] <ref>[https://github.com/LeelaChessZero/lc0/issues/799 "Exact-Win Strategy for Overcoming AlphaZero" · Issue #799 · LeelaChessZero/lc0 · GitHub]</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 <ref>[https://deepmind.com/blog/alphazero-shedding-new-light-grand-games-chess-shogi-and-go/ 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</ref>
==2019==
* [[Matthew Sadler]], [https://www.youtube.com/watch?v=waBxmWI85YI Natasha Regan] ('''2019'''). ''[https://www.newinchess.com/game-changer Game Changer: AlphaZero's Groundbreaking Chess Strategies and the Promise of AI]''. [https://en.wikipedia.org/wiki/New_In_Chess New In Chess]
* [[Marc Lanctot]], [[Edward Lockhart]], [[Jean-Baptiste Lespiau]], [[Vinícius Flores Zambaldi]], [[Satyaki Upadhyay]], [[Julien Pérolat]], [[Sriram Srinivasan]], [[Finbarr Timbers]], [[Karl Tuyls]], [[Shayegan Omidshafiei]], [[Daniel Hennes]], [[Dustin Morrill]], [[Paul Muller]], [[Timo Ewalds]], [[Ryan Faulkner]], [[János Kramár]], [[Bart De Vylder]], [[Brennan Saeta]], [[James Bradbury]], [[David Ding]], [[Sebastian Borgeaud]], [[Matthew Lai]], [[Julian Schrittwieser]], [[Thomas Anthony]], [[Edward Hughes]], [[Ivo Danihelka]], [[Jonah Ryan-Davis]] ('''2019'''). ''OpenSpiel: A Framework for Reinforcement Learning in Games''. [https://arxiv.org/abs/1908.09453 arXiv:1908.09453] <ref>[https://github.com/deepmind/open_spiel/blob/master/docs/contributing.md open_spiel/contributing.md at master · deepmind/open_spiel · GitHub]</ref>
==2020 ...==
* [[Nenad Tomašev]], [[Ulrich Paquet]], [[Demis Hassabis]], [[Vladimir Kramnik]] ('''2020'''). ''Assessing Game Balance with AlphaZero: Exploring Alternative Rule Sets in Chess''. [https://arxiv.org/abs/2009.04374 arXiv:2009.04374]
=Forum Posts=
* [https://groups.google.com/d/msg/fishcooking/ExSnY8xy7sY/_x32q6INCAAJ Open letter to Google DeepMind] by Michael Stembera, [[Computer Chess Forums|FishCooking]], December 12, 2017
* [http://www.talkchess.com/forum/viewtopic.php?t=66005 recent article on alphazero ... 12/11/2017 ...] by Dan Ellwein, [[CCC]], December 14, 2017
* [http://www.talkchess.com/forum/viewtopic.php?t=66013 An AlphaZero inspired project] by [[Truls Edvard Stokke]], [[CCC]], December 14, 2017» [[ZeroFish]]
* [http://www.talkchess.com/forum/viewtopic.php?t=66026 AlphaZero - Tactical Abilities] by [[David Rasmussen]], [[CCC]], December 16, 2017
* [http://www.talkchess.com/forum/viewtopic.php?t=66047 In chess,AlphaZero outperformed Stockfish after just 4 hours] by [[Ed Schroder]], [[CCC]], December 18, 2017
: [http://www.talkchess.com/forum3/viewtopic.php?f=2&t=69175&start=60 Re: Alphazero news] by [[Matthew Lai]], [[CCC]], December 07, 2018
: [http://www.talkchess.com/forum3/viewtopic.php?f=2&t=69175&start=63 Re: Alphazero news] by [[Alexander Lyashuk|crem]], [[CCC]], December 07, 2018
:: [http://www.talkchess.com/forum3/viewtopic.php?f=2&t=69175&start=64 Re: Alphazero news] by [[Matthew Lai]], [[CCC]], December 07, 2018::: [http://www.talkchess.com/forum3/viewtopic.php?f=2&t=69175&start=66 Re: Alphazero news] by [[Alexander Lyashuk|crem]], [[CCC]], December 07, 2018:::: [http://www.talkchess.com/forum3/viewtopic.php?f=2&t=69175&start=72 Re: Alphazero news] by [[Matthew Lai]], [[CCC]], December 07, 2018::: [http://www.talkchess.com/forum3/viewtopic.php?f=2&t=69175&start=75 Re: Alphazero news] by [[Gian-Carlo Pascutto]], [[CCC]], December 07, 2018 » [[Leela Chess Zero]]:::: [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=93 Re: Alphazero news] by [[Matthew Lai]], [[CCC]], December 08, 2018
: [http://www.talkchess.com/forum3/viewtopic.php?f=2&t=69175&start=185 Re: Alphazero news] by [[Jonathan Rosenthal]], [[CCC]], December 11, 2018
:: [http://www.talkchess.com/forum3/viewtopic.php?f=2&t=69175&start=192 Re: Alphazero news] by [[Matthew Lai]], [[CCC]], December 11, 2018
: [http://www.talkchess.com/forum3/viewtopic.php?f=2&t=69175&start=193 Re: Alphazero news] by [[Matthew Lai]], [[CCC]], December 11, 2018 » [[#Stockfish Match|Stockfish Match]]
: [http://www.talkchess.com/forum3/viewtopic.php?f=2&t=69175&start=209 Re: Alphazero news] by [[Milos Stanisavljevic|Milos]], [[CCC]], December 11, 2018
: [http://www.talkchess.com/forum3/viewtopic.php?f=2&t=69175&start=211 Re: Alphazero news] by [[Gian-Carlo Pascutto]], [[CCC]], December 11, 2018
:: [http://www.talkchess.com/forum3/viewtopic.php?f=2&t=69175&start=213 Re: Alphazero news] by [[Matthew Lai]], [[CCC]], December 11, 2018
: [http://www.talkchess.com/forum3/viewtopic.php?f=2&t=69175&start=232 Re: Alphazero news] by [[Kai Laskos]], [[CCC]], December 12, 2018 » [[#Stockfish Match|Stockfish Match]]
* [http://www.talkchess.com/forum3/viewtopic.php?f=7&t=69306 Policy training in Alpha Zero, LC0 ..] by [[Chris Whittington]], [[CCC]], December 18, 2018 » [[Leela Chess Zero#lc0|LC0]]
==2019==
* [http://www.talkchess.com/forum3/viewtopic.php?f=7&t=69668 A0 policy head ambiguity] by [[Daniel Shawul]], [[CCC]], January 21, 2019
* [http://www.talkchess.com/forum3/viewtopic.php?f=2&t=72498 AlphaZero No Castling Chess] by Javier Ros, [[CCC]], December 03, 2019
==2020 ...==
* [http://www.talkchess.com/forum3/viewtopic.php?f=7&t=73772 AlphaZero] by Pawel Wojcik, [[CCC]], April 26, 2020
* [http://www.talkchess.com/forum3/viewtopic.php?f=2&t=75063 Chess variants made with help from alpha zero article] by jmartus, [[CCC]], September 10, 2020
 
=Blog Posts=
* [https://medium.com/oracledevs/lessons-from-implementing-alphazero-7e36e9054191 Lessons From Implementing AlphaZero] by [https://medium.com/@akprasad Aditya Prasad], [https://blogs.oracle.com/ Oracle Blog], June 05, 2018
: [https://medium.com/oracledevs/lessons-from-alphazero-connect-four-e4a0ae82af68 Lessons from AlphaZero: Connect Four] by [https://medium.com/@akprasad Aditya Prasad], [https://blogs.oracle.com/ Oracle Blog], June 13, 2018
: [https://medium.com/oracledevs/lessons-from-alphazero-part-3-parameter-tweaking-4dceb78ed1e5 Lessons from AlphaZero (part 3): Parameter Tweaking] by [https://medium.com/@akprasad Aditya Prasad], [https://blogs.oracle.com/ Oracle Blog], June 20, 2018
: [https://medium.com/oracledevs/lessons-from-alphazero-part-4-improving-the-training-target-6efba2e71628 Lessons From AlphaZero (part 4): Improving the Training Target] by [https://blogs.oracle.com/author/vish-abrams Vish Abrams], [https://blogs.oracle.com/ Oracle Blog], June 27, 2018
: [https://medium.com/oracledevs/lessons-from-alpha-zero-part-5-performance-optimization-664b38dc509e Lessons From Alpha Zero (part 5): Performance Optimization] by [https://blogs.oracle.com/author/anthony-young Anthony Young], [https://blogs.oracle.com/ Oracle Blog], July 03, 2018
: [https://medium.com/oracledevs/lessons-from-alpha-zero-part-6-hyperparameter-tuning-b1cfcbe4ca9a Lessons From Alpha Zero (part 6) — Hyperparameter Tuning] by [https://blogs.oracle.com/author/anthony-young Anthony Young], [https://blogs.oracle.com/ Oracle Blog], July 11, 2018
* [https://deepmind.com/blog/alphazero-shedding-new-light-grand-games-chess-shogi-and-go/ 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
* [http://blog.lczero.org/2018/12/alphazero-paper-and-lc0-v0191.html AlphaZero paper, and Lc0 v0.19.1] by [[Alexander Lyashuk|crem]], [[Leela Chess Zero|LCZero blog]], December 07, 2018
=External Links=
: [https://github.com/suragnair/alpha-zero-general GitHub - suragnair/alpha-zero-general: A clean and simple implementation of a self-play learning algorithm based on AlphaGo Zero (any game, any framework!)]
* [https://deepmind.com/blog/alphazero-shedding-new-light-grand-games-chess-shogi-and-go/ 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
* AlphaZero: Shedding new light on the grand games of chess, shogi and Go, December 06, 2018, [https://en.wikipedia.org/wiki/YouTube YouTube] Video
: {{#evu:https://www.youtube.com/watch?v=7L2sUGcOgh0|alignment=left|valignment=top}}
==OpenSpiel==
* [https://github.com/deepmind/open_spiel GitHub - deepmind/open_spiel: OpenSpiel is a collection of environments and algorithms for research in general reinforcement learning and search/planning in games] <ref>[[Marc Lanctot]], [[Edward Lockhart]], [[Jean-Baptiste Lespiau]], [[Vinícius Flores Zambaldi]], [[Satyaki Upadhyay]], [[Julien Pérolat]], [[Sriram Srinivasan]], [[Finbarr Timbers]], [[Karl Tuyls]], [[Shayegan Omidshafiei]], [[Daniel Hennes]], [[Dustin Morrill]], [[Paul Muller]], [[Timo Ewalds]], [[Ryan Faulkner]], [[János Kramár]], [[Bart De Vylder]], [[Brennan Saeta]], [[James Bradbury]], [[David Ding]], [[Sebastian Borgeaud]], [[Matthew Lai]], [[Julian Schrittwieser]], [[Thomas Anthony]], [[Edward Hughes]], [[Ivo Danihelka]], [[Jonah Ryan-Davis]] ('''2019'''). ''OpenSpiel: A Framework for Reinforcement Learning in Games''. [https://arxiv.org/abs/1908.09453 arXiv:1908.09453]</ref>
** [https://github.com/deepmind/open_spiel/tree/master/open_spiel/algorithms open_spiel/open_spiel/algorithms at master · deepmind/open_spiel · GitHub]
*** [https://github.com/deepmind/open_spiel/tree/master/open_spiel/algorithms/alpha_zero open_spiel/open_spiel/algorithms/alpha_zero at master · deepmind/open_spiel · GitHub]
** [https://github.com/deepmind/open_spiel/tree/master/open_spiel/games open_spiel/open_spiel/games at master · deepmind/open_spiel · GitHub]
*** [https://github.com/deepmind/open_spiel/tree/master/open_spiel/games/chess open_spiel/open_spiel/games/chess at master · deepmind/open_spiel · GitHub]
==Reports==
===2017===
* [https://www.theverge.com/2017/12/6/16741106/deepmind-ai-chess-alphazero-shogi-go DeepMind’s AI became a superhuman chess player in a few hours, just for fun] by [https://www.theverge.com/users/James%20Vincent James Vincent], [https://en.wikipedia.org/wiki/The_Verge The Verge], December 06, 2017
* [http://www.telegraph.co.uk/science/2017/12/06/entire-human-chess-knowledge-learned-surpassed-deepminds-alphazero/ Entire human chess knowledge learned and surpassed by DeepMind's AlphaZero in four hours] by [http://www.telegraph.co.uk/authors/sarah-knapton/ Sarah Knapton], and [http://www.telegraph.co.uk/authors/leon-watson/ Leon Watson], [https://en.wikipedia.org/wiki/Telegraph_Media_Group The Telegraph], December 06, 2017
* [http://www.bbc.co.uk/news/technology-42251535 Google's 'superhuman' DeepMind AI claims chess crown], [https://en.wikipedia.org/wiki/BBC_News BBC News], December 06, 2017 <ref>[http://www.hiarcs.net/forums/viewtopic.php?t=8709 BBC News; 'Google's ... DeepMind AI claims chess crown'] by pennine22, [[Computer Chess Forums|Hiarcs Forum]], December 07, 2017</ref>
* [https://chess24.com/en/read/news/deepmind-s-alphazero-crushes-chess DeepMind’s AlphaZero crushes chess] by [https://chess24.com/en/profile/colin Colin McGourty], [https://en.wikipedia.org/wiki/Chess24.com Chess24.com[chess24]], December 06, 2017
* [http://www.danamackenzie.com/blog/?p=5068 One Small Step for Computers, One Giant Leap for Mankind] by [[Dana Mackenzie]], [http://www.danamackenzie.com/blog/ Dana Blogs Chess], December 06, 2017
* [https://www.chess.com/news/view/google-s-alphazero-destroys-stockfish-in-100-game-match Google's AlphaZero Destroys Stockfish In 100-Game Match] by [https://www.chess.com/member/mikeklein Mike Klein], [https://en.wikipedia.org/wiki/Chess.com [Chess.com]], December 06, 2017
* [https://en.chessbase.com/post/the-future-is-here-alphazero-learns-chess The future is here – AlphaZero learns chess] by [[Albert Silver]], [[ChessBase|ChessBase News]], December 06, 2017
* <span id="Reactions"></span>[https://www.chess.com/news/view/alphazero-reactions-from-top-gms-stockfish-author AlphaZero: Reactions From Top GMs, Stockfish Author] by [http://www.chessvibes.com/?q=peterdoggers [Peter Doggers]], [https://en.wikipedia.org/wiki/Chess.com [Chess.com]], December 08, 2017 » [[Stockfish]], [[Tord Romstad]] <ref>[http://www.talkchess.com/forum/viewtopic.php?t=65934 Reactions about AlphaZero from top GMs...] by [[Norman Schmidt]], [[CCC]], December 08, 2017</ref>
* [https://medium.com/@josecamachocollados/is-alphazero-really-a-scientific-breakthrough-in-ai-bf66ae1c84f2 Is AlphaZero really a scientific breakthrough in AI?] by [https://scholar.google.com/citations?user=NP4KdQQAAAAJ&hl=en Jose Camacho Collados], [https://medium.com/ Medium], December 11, 2017 <ref>[http://www.talkchess.com/forum/viewtopic.php?t=66005 recent article on alphazero ... 12/11/2017 ...] by Dan Ellwein, [[CCC]], December 14, 2017</ref>
* [https://en.chessbase.com/post/alpha-zero-comparing-orang-utans-and-apples Alpha Zero: Comparing "Orangutans and Apples"] by [https://en.chessbase.com/author/andre-schulz André Schulz], [[ChessBase|ChessBase News]], December 13, 2017
* [https://en.chessbase.com/post/kasparov-on-deep-learning-in-chess Kasparov on Deep Learning in chess] by [[Frederic Friedel]], [[ChessBase|ChessBase News]], December 13, 2017
===2018 ...===
* [https://chess24.com/en/read/news/alphazero-really-is-that-good AlphaZero really is that good] by [http://michaelkonik.com/colin-mcgourty-chess-reporter/ Colin McGourty], [[chess24]], December 06, 2018
* [https://en.chessbase.com/post/the-full-alphazero-paper-is-published-at-long-last Inside the (deep) mind of AlphaZero] by [[Albert Silver]], [[ChessBase|ChessBase News]], December 07, 2018
* [https://en.chessbase.com/post/standing-on-the-shoulders-of-giants Standing on the shoulders of giants] by [[Albert Silver]], [[ChessBase|ChessBase News]], September 18, 2019
* [https://www.chess.com/article/view/no-castling-chess-kramnik-alphazero Kramnik And AlphaZero: How To Rethink Chess‎], [[Chess.com]], December 02, 2019 <ref>[http://www.talkchess.com/forum3/viewtopic.php?f=2&t=72498 AlphaZero No Castling Chess] by Javier Ros, [[CCC]], December 03, 2019</ref>
==<span id="StockfishMatch"></span>Stockfish Match==
* [https://lichess.org/study/wxrovYNH AlphaZero vs Stockfish Games • lichess.org]===Round 1===
* [http://www.chessgames.com/perl/chessplayer?pid=160016 The chess games of AlphaZero (Computer)] from [http://www.chessgames.com/index.html chessgames.com]
* [http://www.zipproth.de/Brainfish/Cerebellum_AlphaZero.html Cerebellum AlphaZero Analysis] » [[Cerebellum]] <ref>[http://www.talkchess.com/forum/viewtopic.php?t=65983 Cerebellum analysis of the AlphaZero - Stockfish Games] by [[Thomas Zipproth]], [[CCC]], December 11, 2017</ref>
* <span id="ImmortalZugzwang"></span>[https://youtu.be/lFXJWPhDsSY Deep Mind Alpha Zero's "Immortal Zugzwang Game" against Stockfish] by [https://www.facebook.com/AGADMATOR Antonio Radic], December 07, 2017, [https://en.wikipedia.org/wiki/YouTube YouTube] Video <ref>[http://rybkaforum.net/cgi-bin/rybkaforum/topic_show.pl?tid=32398 AlphaZero reinvents mobility and romanticism] by [[Chris Whittington]], [[Computer Chess Forums|Rybka Forum]], December 08, 2017</ref> <ref>[https://en.wikipedia.org/wiki/Immortal_Zugzwang_Game Immortal Zugzwang Game from Wikipedia]</ref> » [[Zugzwang]]
: {{#evu:https://www.youtube.com/watch?v=lFXJWPhDsSY|alignment=left|valignment=top}}
* [https://youtu.be/pcdpgn9OINs Deep Mind AI Alpha Zero Dismantles Stockfish's French Defense] by [https://www.facebook.com/AGADMATOR Antonio Radic], December 08, 2017, [https://en.wikipedia.org/wiki/YouTube YouTube] Video
* <span id="DanaMackenzie"></span>[http://www.danamackenzie.com/blog/?p=5072 How AlphaZero Wins] by [[Dana Mackenzie]], [http://www.danamackenzie.com/blog/ Dana Blogs Chess], December 15, 2017 <ref>[http://www.talkchess.com/forum/viewtopic.php?t=66349 Article:"How Alpha Zero Sees/Wins"] by AA Ross, [[CCC]], January 17, 2018</ref>
===Round 2, 3===
* [https://chess24.com/en/watch/live-tournaments/alphazero-vs-stockfish AlphaZero vs. Stockfish] from [[chess24]]
* [https://youtu.be/nPexHaFL1uo AlphaZero's Attacking Chess] by [https://en.wikipedia.org/wiki/Anna_Rudolf Anna Rudolf], December 06, 2018, [https://en.wikipedia.org/wiki/YouTube YouTube] Video <ref>[http://www.talkchess.com/forum3/viewtopic.php?f=7&t=69181 Anna Rudolf analyzes a game of AlphaZero's] by [[Stuart Cracraft]], [[CCC]], December 07, 2018</ref>
: {{#evu:https://www.youtube.com/watch?v=nPexHaFL1uo|alignment=left|valignment=top}}
* [https://youtu.be/bo5plUo86BU "Exactly How to Attack" | DeepMind's AlphaZero vs. Stockfish] by [[Matthew Sadler]], December 06, 2018, [https://en.wikipedia.org/wiki/YouTube YouTube] Video
* [https://youtu.be/g0O3QmAhoeA "Bold Sir Lancelot" | DeepMind's AlphaZero vs. Stockfish] by [[Matthew Sadler]], December 06, 2018, [https://en.wikipedia.org/wiki/YouTube YouTube] Video
* [https://youtu.be/2-wFUdvKTVQ "All-in Defence" | DeepMind's AlphaZero vs. Stockfish] by [[Matthew Sadler]], December 06, 2018, [https://en.wikipedia.org/wiki/YouTube YouTube] Video
* [https://youtu.be/JacRX6cKIaY "Long-term Sacrifice" | DeepMind's AlphaZero vs. Stockfish] by [[Matthew Sadler]], December 06, 2018, [https://en.wikipedia.org/wiki/YouTube YouTube] Video
* [https://youtu.be/jS26Ct34YrQ "Endgame Class" | DeepMind's AlphaZero vs. Stockfish] by [[Matthew Sadler]], December 06, 2018, [https://en.wikipedia.org/wiki/YouTube YouTube] Video
: {{#evu:https://www.youtube.com/watch?v=jS26Ct34YrQ|alignment=left|valignment=top}}
==Misc==
* [https://medium.com/applied-data-science/how-to-build-your-own-alphazero-ai-using-python-and-keras-7f664945c188 How to build your own AlphaZero AI using Python and Keras] by [https://www.linkedin.com/in/davidtfoster/ David Foster], January 26, 2018 » [[Connect Four]], [[Python]] <ref>[http://www.talkchess.com/forum/viewtopic.php?t=66443 Connect 4 AlphaZero implemented using Python...] by [[Steve Maughan]], [[CCC]], January 29, 2018</ref>
<references />
'''[[Engines|Up one Level]]'''
[[Category:GPU]]
[[Category:DCNN]]
[[Category:MCTS]]
[[Category:Can]]
[[Category:Videos]]

Navigation menu