Answers.Body: <p>The evaluation function of a chess engine, whether instantiated as a neural net or explicit code, is always able to assign a value to any board position. If you give it a board position, even absurd ones that would never occur in a game, it will be able to spit out a number representing how favorable it is to one player or another. Since the number of board positions in chess is unmanageably gigantic, the training can only occur on an infinitesimal sample of the game tree. The engine is not simply recalling previously calculated values of board positions, but is performing calculations based on the arrangement of the pieces. For a non-neural-net example, part of a chess engine's evaluation might be to add up the value of each piece on its side and subtract the total value of the opponent's pieces. Then, one set of parameter that would be adjusted while training would be the value of each piece.</p>
  
  <p>When the engine is untrained, the values assigned to a position might as well be random since the parameters of the evaluation function start out with (usually) random values. The goal of a training phase is to adjust the parameters of the engine so that it assigns high scores to board positions that are probable winning states for the player.</p>
  
  <p>From <a href="https://arxiv.org/pdf/1712.01815.pdf" rel="noreferrer">the paper on AlphaZero</a> (page 3):</p>
  
  <blockquote>
    <p>The parameters of the deep neural network in AlphaZero are trained by self-play reinforcement learning, starting from randomly initialised parameters. Games are played by selecting moves for both players by MCTS. At the end of the game, the terminal position is scored according to the rules of the game to compute the game outcome: −1 for a loss, 0 for a draw, and +1 for a win. The neural network parameters are updated so as to minimise the error between the predicted outcome and the game outcome, and to maximise the similarity of the policy vector to the search probabilities.</p>
  </blockquote>
  
  <p><em>[math symbols removed from quote]</em></p>
  
  <p>In summary, during training, AlphaZero played a game against itself. When the game is over, the result of the game and the accuracy of its predictions in how the game would proceed were used to adjust the neural net so that it would be more accurate during the next game. AlphaZero is not keeping a record of every position it has seen, but is adjusting itself so that it can more accurately evaluate any board it sees in the future.</p>
  
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-12-12T16:53:23.787Z
Answers.Text: I completely understand your explanation at the algorithmic level, but I am still astounded that it works. I would have thought that the early games would be so random that they would have no learning value. It seems impossible to evaluate the outcome of a move at that stage except by playing it out to checkmate, because that is the only thing that you've been told about. But that checkmate will only happen after a large number of other essentially random stuff has gone on. My gut feeling is that there just is not sufficient meaningful data to draw any conclusions.
  Why am I wrong?
Answers.UserDisplayName: Philip Roe
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-12-12T20:12:00.527Z
Answers.Text: @PhilipRoe You're right, each game only provides a little bit of information. I've actually written my own chess engine that learns by an evolutionary algorithm. Randomly modified copies of the engine play each other; the losers are deleted and the winners produce more modified copies. It usually takes between 10,000 to 20,000 games for it to figure out just the proper order of piece values (queen, rook, bishop/knight, pawn). It took AlphaZero 44 million games to achieve its skill (table on page 15 of the linked paper).
Answers.UserDisplayName: Mark H
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-12-12T20:36:45.520Z
Answers.Text: Thanks for responding! But Im still astounded. There is the huge space of possible positions to evaluate. But there is also the huge space of possible questions to ask. Anthropomorphically I imagine myself with zero prior knowledge except the rules, and a huge database of games that are played at an almost inconceivable level of incompetence (although I dont suppose all of get remembered) At what point does it occur to me "Hey maybe I should count the pieces" Then how long before counting the pieces seems to a good idea?
Answers.UserDisplayName: Philip Roe
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-12-12T20:46:54.033Z
Answers.Text: I find it very hard to imagine, even if some strong hints were provided about "What constitutes a good question?" But without even that, Im impressed that a heirarchy of pieces can be established in 20,000 games. So I find it very hard to accept that the tabula is really rasa. Some minimal instruction about the process of generating and revising your rules (how many, how often?) still seems essential.
Answers.UserDisplayName: Philip Roe
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-12-12T21:28:22.737Z
Answers.Text: @PhilipRoe In my program, I tell the engine to count the pieces, but not how much each piece is worth. So, I do tell the engine what to look at, but not how to weight what it sees. AlphaZero is much more tabula rasa. If you're curious: https://github.com/MarkZH/Genetic_Chess
Answers.UserDisplayName: Mark H
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-12-12T21:40:20.030Z
Answers.Text: And in those 44 million games, do we have any idea how many total positions it looked at?  I figure the learning could be made more efficient if, e.g. it was tuned to always find forced mates in less than 5 moves.
Answers.UserDisplayName: Roy Koczela
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-12-12T22:07:19.873Z
Answers.Text: Right - it would not qualify as totally self-trained if you told it that one of the key parameters was the value of the pieces.  It has to "figure that out" itself - and it does seem like 44 million games would be way too few to do that - although again, I suspect that those "44 million" games included a whole lot of evaluations of "moves" that didn't get "played". I note the paper says that "thinking time" was 40 ms during evaluation.
Answers.UserDisplayName: Roy Koczela
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-12-12T22:54:59.617Z
Answers.Text: @PhilipRoe "What constitutes a good question?" is a good question. One of the annoying things about the study of neural nets is that it's still very difficult to determine how the trained net makes decisions. Until these things learn to talk, studying the trained net is as useful as opening up a human chess player's skull to see what they are thinking.
Answers.UserDisplayName: Mark H
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-12-12T23:01:25.787Z
Answers.Text: @RoyKoczela Given about a hundred ply per game plus multiple variations when choosing moves, I wouldn't be surprised if the number of positions seen during training was on the order of 10 or 100 billion. This is an estimate, I'm sure there are papers (probably on arXiv) by the AlphaZero team that goes into detail.
Answers.UserDisplayName: Mark H
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-12-13T03:05:54.277Z
Answers.Text: @Mark, Roy I’m finding this fascinating! Not least for the broader implications. How long has it taken (by which I mean how many generations) for natural selection to produce us, who on a good day might manage a reasonable game of chess, among our other talents? But Im not sure how close the parallel is. Nature gets to start with something very simple that has already evolved for some purpose. She wants to make it either a bit better for that purpose, or to slightly redirect the purpose. But AlphaZero is not initially good at anything.
Answers.UserDisplayName: Philip Roe
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-12-13T03:07:13.000Z
Answers.Text: On the other hand, I suppose, it does know what it wants to become good at.
  I suspect the moderators would like us to move to chat. I would be OK with that?
Answers.UserDisplayName: Philip Roe
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-12-13T04:22:47.367Z
Answers.Text: @PhilipRoe The problem with natural selection is that the game of chess plays no part in which organisms live, die, or reproduce (*The Seventh Seal* notwithstanding). Plus, AlphaZero is not a genetic or evolutionary algorithm. It is a neural net that mimics a brain that learns by making and breaking connections between simple elements by comparing what it currently thinks to what actually happens on the board. It is a much more active and direct process than evolution.
Answers.UserDisplayName: Mark H
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-12-13T18:55:36.987Z
Answers.Text: So 100 billion.. 10^11 positions.  So for every position it looked at, there are 1 with 35 zeroes positions that it didn't.  And yet, apparently that was good enough.  It makes me wonder how good it would be if it had to play 960 without re-training.
Answers.UserDisplayName: Roy Koczela
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-06-06T07:30:29.323Z
Answers.Text: We now have some evidence due to Allie (a leela derivative that now can play 960). It's about 100 elo worse, mainly due to being very confused by castling in 960
Answers.UserDisplayName: Oscar Smith
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-12-12T11:46:19.650Z
Answers.LastActivityDate: 2017-12-12T11:46:19.650Z
Answers.UserDisplayName: Mark H
Answers.Body: <p>Here, it is crucial that AlphaZero is based on a <em>Deep Neural Network (DNN)</em> which essentially means that the network consists of many layers of, mostly, different types (regarding how the information is collected and processed). This allows such networks to subdivide the evaluation problem to a large (and flexible) number of elements it can process separately and then combine the results to a final answer.</p>
  <p>If the Network was too flat (standard NN with small number of layers) it would simply smoothly extrapolate the knowledge it has learned from the examples. While this works fine (for over 30 years alredy) in simple tasks like recognition of hand-written letters it fails in more subtle problems when many details must be put together in a complex way. Think of animal recognition. Sometimes you have a large cat positioned frontally but in bad light or shadow, sometimes a small cat rolling on its back, and so on. You must learn which elements are crucial for deciding that &quot;it is a cat&quot;.</p>
  <p>This requires the subdivision of the problem into many small pieces and subsequent gathering of the pieces of information to reach a conclusion. This process (division, gathering) can be repeated several times. In DNNs both these functions can be guaranteed both automatically by suitable learning algorithms and manually by choosing special types of layers and their connections by the designer. It is the power of DNNs that they can organize their information flow very flexibly -- as this is usually not possible to a priori define which subtasks should be performed.</p>
  <p>AlphaZero does the same: it analyses not only the full position itself of which there are so many possibilities that it would never learn to reach proper conclusions by simply extrapolating its limited knowledge. It analyses also subgroups of pieces, local configurations and learns to understand features like e.g. pin, fork, etc. Then, it combines plenty of such pieces of information to obtain a global picture and find the total position estimate. The way AZ does it is pretty flexible and dynamical.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-06-01T14:07:23.767Z
Answers.LastActivityDate: 2021-06-01T14:07:23.767Z
Answers.UserDisplayName: Nikodem
Body: <p>Following up from answers to:</p>
  
  <p><a href="https://chess.stackexchange.com/questions/19353/understanding-alphazero">Understanding AlphaZero</a></p>
  
  <p>My question would be how the neural net "learns" what to do in a position it hasn't encountered. Saying the actual AZ executes an MCTS using the bias + weights from the trained neural net just pushes it back a step to how the neural net calculates these values. If it was through random self-play, with no human knowledge, then how does it decide how to weight a position it has never seen?</p>
  
Tags: <alphazero>
Title: How does AlphaZero learn to evaluate a position it has never seen?
ThreadText: # How does AlphaZero learn to evaluate a position it has never seen?
  
  (Asked by: username_0 on 2017-12-11)
  
  Following up from answers to:
  
  [Understanding AlphaZero](https://chess.stackexchange.com/questions/19353/understanding-alphazero)
  
  My question would be how the neural net "learns" what to do in a position it hasn't encountered. Saying the actual AZ executes an MCTS using the bias + weights from the trained neural net just pushes it back a step to how the neural net calculates these values. If it was through random self-play, with no human knowledge, then how does it decide how to weight a position it has never seen?
  
  **Tags:** alphazero
  
  
  ---
  
  ## 2 answers
  
  ### Answer by username_1 on 2017-12-12. Score: 8
  
  The evaluation function of a chess engine, whether instantiated as a neural net or explicit code, is always able to assign a value to any board position. If you give it a board position, even absurd ones that would never occur in a game, it will be able to spit out a number representing how favorable it is to one player or another. Since the number of board positions in chess is unmanageably gigantic, the training can only occur on an infinitesimal sample of the game tree. The engine is not simply recalling previously calculated values of board positions, but is performing calculations based on the arrangement of the pieces. For a non-neural-net example, part of a chess engine's evaluation might be to add up the value of each piece on its side and subtract the total value of the opponent's pieces. Then, one set of parameter that would be adjusted while training would be the value of each piece.
  
  When the engine is untrained, the values assigned to a position might as well be random since the parameters of the evaluation function start out with (usually) random values. The goal of a training phase is to adjust the parameters of the engine so that it assigns high scores to board positions that are probable winning states for the player.
  
  From [the paper on AlphaZero](https://arxiv.org/pdf/1712.01815.pdf) (page 3):
  
  > The parameters of the deep neural network in AlphaZero are trained by self-play reinforcement learning, starting from randomly initialised parameters. Games are played by selecting moves for both players by MCTS. At the end of the game, the terminal position is scored according to the rules of the game to compute the game outcome: −1 for a loss, 0 for a draw, and +1 for a win. The neural network parameters are updated so as to minimise the error between the predicted outcome and the game outcome, and to maximise the similarity of the policy vector to the search probabilities.
  
  *[math symbols removed from quote]*
  
  In summary, during training, AlphaZero played a game against itself. When the game is over, the result of the game and the accuracy of its predictions in how the game would proceed were used to adjust the neural net so that it would be more accurate during the next game. AlphaZero is not keeping a record of every position it has seen, but is adjusting itself so that it can more accurately evaluate any board it sees in the future.
  
  > **Comments:**
  > **username_2**: I completely understand your explanation at the algorithmic level, but I am still astounded that it works. I would have thought that the early games would be so random that they would have no learning value. It seems impossible to evaluate the outcome of a move at that stage except by playing it out to checkmate, because that is the only thing that you've been told about. But that checkmate will only happen after a large number of other essentially random stuff has gone on. My gut feeling is that there just is not sufficient meaningful data to draw any conclusions. Why am I wrong?  
  > **username_1**: @username_2 You're right, each game only provides a little bit of information. I've actually written my own chess engine that learns by an evolutionary algorithm. Randomly modified copies of the engine play each other; the losers are deleted and the winners produce more modified copies. It usually takes between 10,000 to 20,000 games for it to figure out just the proper order of piece values (queen, rook, bishop/knight, pawn). It took AlphaZero 44 million games to achieve its skill (table on page 15 of the linked paper).  
  > **username_2**: Thanks for responding! But Im still astounded. There is the huge space of possible positions to evaluate. But there is also the huge space of possible questions to ask. Anthropomorphically I imagine myself with zero prior knowledge except the rules, and a huge database of games that are played at an almost inconceivable level of incompetence (although I dont suppose all of get remembered) At what point does it occur to me "Hey maybe I should count the pieces" Then how long before counting the pieces seems to a good idea?  
  > **username_2**: I find it very hard to imagine, even if some strong hints were provided about "What constitutes a good question?" But without even that, Im impressed that a heirarchy of pieces can be established in 20,000 games. So I find it very hard to accept that the tabula is really rasa. Some minimal instruction about the process of generating and revising your rules (how many, how often?) still seems essential.  
  > **username_1**: @username_2 In my program, I tell the engine to count the pieces, but not how much each piece is worth. So, I do tell the engine what to look at, but not how to weight what it sees. AlphaZero is much more tabula rasa. If you're curious: https://github.com/MarkZH/Genetic_Chess  
  > **username_0**: And in those 44 million games, do we have any idea how many total positions it looked at?  I figure the learning could be made more efficient if, e.g. it was tuned to always find forced mates in less than 5 moves.  
  > **username_0**: Right - it would not qualify as totally self-trained if you told it that one of the key parameters was the value of the pieces.  It has to "figure that out" itself - and it does seem like 44 million games would be way too few to do that - although again, I suspect that those "44 million" games included a whole lot of evaluations of "moves" that didn't get "played". I note the paper says that "thinking time" was 40 ms during evaluation.  
  > **username_1**: @username_2 "What constitutes a good question?" is a good question. One of the annoying things about the study of neural nets is that it's still very difficult to determine how the trained net makes decisions. Until these things learn to talk, studying the trained net is as useful as opening up a human chess player's skull to see what they are thinking.  
  > **username_1**: @username_0 Given about a hundred ply per game plus multiple variations when choosing moves, I wouldn't be surprised if the number of positions seen during training was on the order of 10 or 100 billion. This is an estimate, I'm sure there are papers (probably on arXiv) by the AlphaZero team that goes into detail.  
  > **username_2**: @Mark, Roy I’m finding this fascinating! Not least for the broader implications. How long has it taken (by which I mean how many generations) for natural selection to produce us, who on a good day might manage a reasonable game of chess, among our other talents? But Im not sure how close the parallel is. Nature gets to start with something very simple that has already evolved for some purpose. She wants to make it either a bit better for that purpose, or to slightly redirect the purpose. But AlphaZero is not initially good at anything.  
  > **username_2**: On the other hand, I suppose, it does know what it wants to become good at. I suspect the moderators would like us to move to chat. I would be OK with that?  
  > **username_1**: @username_2 The problem with natural selection is that the game of chess plays no part in which organisms live, die, or reproduce (*The Seventh Seal* notwithstanding). Plus, AlphaZero is not a genetic or evolutionary algorithm. It is a neural net that mimics a brain that learns by making and breaking connections between simple elements by comparing what it currently thinks to what actually happens on the board. It is a much more active and direct process than evolution.  
  > **username_0**: So 100 billion.. 10^11 positions.  So for every position it looked at, there are 1 with 35 zeroes positions that it didn't.  And yet, apparently that was good enough.  It makes me wonder how good it would be if it had to play 960 without re-training.  
  > **username_3**: We now have some evidence due to Allie (a leela derivative that now can play 960). It's about 100 elo worse, mainly due to being very confused by castling in 960  
  
  ---
  
  ### Answer by username_4 on 2021-06-01. Score: 1
  
  Here, it is crucial that AlphaZero is based on a *Deep Neural Network (DNN)* which essentially means that the network consists of many layers of, mostly, different types (regarding how the information is collected and processed). This allows such networks to subdivide the evaluation problem to a large (and flexible) number of elements it can process separately and then combine the results to a final answer.
  
  If the Network was too flat (standard NN with small number of layers) it would simply smoothly extrapolate the knowledge it has learned from the examples. While this works fine (for over 30 years alredy) in simple tasks like recognition of hand-written letters it fails in more subtle problems when many details must be put together in a complex way. Think of animal recognition. Sometimes you have a large cat positioned frontally but in bad light or shadow, sometimes a small cat rolling on its back, and so on. You must learn which elements are crucial for deciding that "it is a cat".
  
  This requires the subdivision of the problem into many small pieces and subsequent gathering of the pieces of information to reach a conclusion. This process (division, gathering) can be repeated several times. In DNNs both these functions can be guaranteed both automatically by suitable learning algorithms and manually by choosing special types of layers and their connections by the designer. It is the power of DNNs that they can organize their information flow very flexibly -- as this is usually not possible to a priori define which subtasks should be performed.
  
  AlphaZero does the same: it analyses not only the full position itself of which there are so many possibilities that it would never learn to reach proper conclusions by simply extrapolating its limited knowledge. It analyses also subgroups of pieces, local configurations and learns to understand features like e.g. pin, fork, etc. Then, it combines plenty of such pieces of information to obtain a global picture and find the total position estimate. The way AZ does it is pretty flexible and dynamical.
  
  
  ---
  
  