11

Following up from answers to:

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?

7

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 (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.

14
  • 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? – Philip Roe Dec 12 '17 at 16:53
  • @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). – Mark H Dec 12 '17 at 20:12
  • 1
    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. – Philip Roe Dec 12 '17 at 20:46
  • 2
    @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: github.com/MarkZH/Genetic_Chess – Mark H Dec 12 '17 at 21:28
  • 2
    @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. – Mark H Dec 12 '17 at 22:54
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.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.