Since castling involves one player moving two pieces in one move, was AlphaZero just given this move, in the same way it was told that players take turns and a win is better than a loss? In other words, it didn't learn it on its own. (I guess it must have been; the range of possible two, three, four, or five piece moves, for all it knows, would just be too big to learn on its own.)
29All the answers below make an unnecessary hash of a very simple misconception. You believe that AlphaZero deduced what the legal moves are in chess. This is not the case. AlphaZero was provided the full game rules. It is, effectively, given what the legal moves are every turn.– Mobeus ZoomNov 25, 2021 at 22:46
3@MobeusZoom is correct. In the book Game Changer by Sadler and Regan when discussing AlphaZero's learning, they clearly state that A0 began knowing the "rules of the game." Further reading in the book and the more academic papers makes this explicitly clear. AlphaZero started its training knowing how to castle.– SecretAgentManDec 2, 2021 at 4:14
Other answers are right in that AlphaZero was implicitly told that castling is a move that exists, I'll elaborate on how exactly that happens by explaining the inputs and outputs of the neural network.
Note: The exact details and screenshots are from my own implementation, which is broadly similar to AlphaZero. At the end of this answer I note the differences between this input format and the one the real AlphaZero uses.
At the core of AlphaZero is a neural network, which gets as an input the current board state. This board state is encoded as a stack of images, from the point of view of the current player. For the starting position, this looks like this:
From left to right:
- 2 planes: Is it whites turn, is it blacks turn
- 4 planes: Castling rights for us left and right, castling rights for the opponent left and right
- 2 planes: Binary digits for the repetition counter
- 6 planes: The side to move's pieces
- 6 planes: The opponent pieces
- 1 plane: The en-passant square if any
In this context castling rights means whether the king or rooks have moved in the past, not whether castling is currently available as a move.
The network is never explicitly told that the 3rd to 6th planes have anything to do with castling or even moving the king, it has to figure that out itself during training.
Output move format
The network has two outputs, the first is the estimated value of the position and the second is an estimation of how good each possible move is, called the policy head. This second output is again a stack of images, and looks like this:
In reality this is a stack of 72 images, I cut out a bunch of them in the center. The encoding here is that the square within the image is the square the move starts from, and the plane means what kind of move it is. For example, the first plane means "move one square forward", the second "move two squares forward", the 10th plane counting from the end means "do a knight move forward and left". As a full example, in this position the bottom left square in the first image means "move the rook on A1 to A2".
This encoding does not include which piece actually makes the move. Pushing the e pawn two squares looks the same as moving a hypothetical queen from e2 to e4.
The first row is the actual output of the network without any post processing. As you can see this output is full of nonsensical moves with starting squares on top of opponent pieces. To fix this only available moves are considered, the rest are set to zero and the output is re-normalized. The result is shown in the second row. As you can see in the starting position the network likes pushing the 4 center pawns two squares forward, and also moving the kingside knight to the center of the board.
Importantly this step of ignoring of invalid moves and renormalizing is the only place where knowledge of chess moves is put into the AlphaZero training process! The valid moves are not actually given as a network input or anywhere else, they're only considered when computing the network output. The network is not discouraged from suggesting invalid moves, these suggestions are simply ignored.
Of course this question was actually about castling, so let's look at a position where the network wants to castle (and can). Like all other moves castling is encoded as moving from one square (e1) in certain way (two squares to the right for kingside castling).
r1bqkb1r/1ppp1ppp/p1n2n2/4p3/B3P3/5N2/PPPP1PPP/RNBQK2R w KQkq - 2 5
The first row is the board input, the second row the policy before removing the invalid moves and the last row is the final policy output. The bright white pixel in the bottom center encodes "e1, two squares to the right" which means castle kingside. Other moves the network is considering are pushing more center pawns and moving the f3 knight again.
It's also possible to visualize the full network internals in this way, here are some examples:
I don't think much insight can be gained from this but it looks cool!
Most of what is in this answer is also explained pretty well in the AlphaZero paper itself, specifically the "Representation" section.
The images were generated by my own work-in-progress implementation attempt, kZero. The network shown matches the actual AlphaZero network very closely, but was trained on the lichess database instead of by real selfplay.
Differences with the real AlphaZero input format
- In the real AlphaZero, the position of the pieces is given for each of the 8 previous board states. Chess is not fully described by the current board state, see eg. the Fifty-move rule or Threefold repetition. Adding 8 steps of history helps, but it's still not really enough.
- AlphaZero doesn't need an en-passant plane since the network can just compare the previous two board states to see if en passant is possible.
- The are some slight differences around player colour and move counter planes, but these are not very significant.
All together this means AlphaZero had 8 * 14 + 7 = 119 planes, whereas I only talked about 21 for most of this answer.
Wonderful answer! Could you provide some sources? I'm very interested in learning more. In particular, where did the images come from? Nov 27, 2021 at 19:12
1@BenMares Thanks! I've added a section about my sources and how I made the images. Nov 27, 2021 at 19:47
Is one of the depicted frames "move knight 2 forward and 1 right"? If so, it's interesting that AZ seems to have completely rejected 1. Nc3 as an opening move. Nov 30, 2021 at 14:39
@eyeballfrog No that one got cut out, the last 9 planes are for underpromotions and the eight before that are for knight moves. Here's how much it likes all possible opening moves: pastebin.com/raw/yU9yDGUF. Keep in mind that this is not the real AZ network, I just trained it to imitate high-elo lichess games. The linked paper does contain some details about what openings the real AZ likes. Nov 30, 2021 at 15:12
1@zjeffer You're right, I chose to simplify things somewhat (both for my implementation and this answer). I've added a note and some more details. Apr 17, 2022 at 17:14
was AlphaZero just given this move
It was given this move in the same way that it was given all other moves. It started with complete knowledge of the rules of the game. In machine learning terms, castling would be part of its baseline knowledge of state transitions.
The AlphaZero paper "Mastering Chess and Shogi by Self-Play with a General Reinforcement Learning Algorithm" by David Silver et al. contains this explanation
Knowledge of the rules is also used to encode the input planes (i.e. castling, repetition, no-progress) and output planes (how pieces move, promotions, and piece drops in shogi).
(An input and output plane are the terms of art for how the board and possible moves are represented to the AlphaZero model.)
was AlphaZero just given this move, in the same way it was told that players take turns and a win is better than a loss?
Actually you've hit upon 3 very distinct ways that AlphaZero was programmed. Castling is a potential move that's built into the algorithm; AlphaZero doesn't need to learn how to do it, just when to do it. The authors list the all the knowledge encoded into the algorithm on page 12 of their paper:
- The input features describing the position, and the output features describing the move, are structured as a set of planes; i.e. the neural network architecture is matched to the grid-structure of the board.
- AlphaZero is provided with perfect knowledge of the game rules. These are used during MCTS, to simulate the positions resulting from a sequence of moves, to determine game termination, and to score any simulations that reach a terminal state.
- Knowledge of the rules is also used to encode the input planes (i.e. castling, repetition, no-progress) and output planes (how pieces move, promotions, and piece drops in shogi).
- The typical number of legal moves is used to scale the exploration noise (see below).
- Chess and shogi games exceeding a maximum number of steps (determined by typical game length) were terminated and assigned a drawn outcome; Go games were terminated and scored with Tromp-Taylor rules, similarly to previous work (29).
AlphaZero did not use any form of domain knowledge beyond the points listed above.
In short, at every turn the neural network at the core of AlphaZero receives information about every piece on the board and outputs a number for every possible move allowed in chess. On top of that neural network there is an algorithm that controls the gameplay, and that zeroes out all currently impossible moves (like the neural net wanting to move a queen despite having no queen) then it picks the valid move with the highest number outputted by the neural net (sort of, the actual move is probabilistic). In this sense it was pre-programmed how to castle, and in fact at the beginning of training it has an equal chance of castling as it does moving a pawn (assuming the board state at that turn allows castling). During training the neural net will learn when castling leads to winning the game.
The other answers already said as much, but I want to add to the other 2 things you mentioned. Taking turns is actually built into the algorithm that manages the game and it's such a central feature that the neural network was designed around it. It's actually quite hard to move away from turn based decision making when designing neural networks, and it's one of the features they address in their AlphaStar paper. AlphaStar plays Starcraft, a real time strategy based game where both players can make as many decisions as they want at any time. They actually don't really solve the continuous decision problem in AlphaStar, they just make the "turns" have a variable duration so the neural net can choose to make decisions every millisecond during intense battles or every 10 seconds if there's not much going on.
Finally the win/loss thing is programmed into the optimizer side of AlphaZero's algorithm. The neural network at the core of AlphaZero is a mathematical function with lots of parameters, the value of the parameters determine what moves it thinks it's best. In essence you want to keep the parameters when it wins and you want to change parameters when it loses; but the exact way they make those changes is explained in the paper and it's quite ingenious. In any case it's actually quite easy to change the desired outcome (compared to the difficulty of moving away from turn based games). The authors desire the neural net to win at chess for obvious reasons, but they could very easily encode the desire to maximize pawn promotions, as an example.
1"In this sense it was pre-programmed how to castle, and in fact at the beginning of training it has an equal chance of castling as it does moving a pawn (assuming the board state at that turn allows castling)." I think a more precise statement would be "each castling move has the same probability as each pawn move." If there is one castling move and three pawn moves, I would expect the p(pawn move) =3 p(castling). If there are two castling moves and one pawn move, I would expect p(pawn move) = p(castling)/2. Nov 25, 2021 at 8:09
4Todd Sewell's answer claims that machine doesn't get as an input the possible moves but just spits out a number of actions which are filtered for validity. Nov 25, 2021 at 16:01
1@akostadinov yes that's right. The input is the board state, and the neural network output structure is fixed and is meant to encode every possible move. The layer on top of the neural net filters what moves are valid.– csizNov 30, 2021 at 16:47
I do not understand your point. It may be that you don't understand how engines work. AlphaZero is nothing special to be honest. Let me explain.
Engines do three things while searching for a move.
- Find out the possible moves.
- Trim out searching for moves which seem useless(in AlphaZero's case, it also trims out any invalid moves)
- Evaluate the position.
(The neural network can actually evaluate any position but invalid moves are ignored and it figures out that those moves are not worth searching; so the neural network is never explicitly told that some moves are invalid and it has to figure it out itself but the engine itself is informed; this doesn't actually change anything because eventually illegal moves are trimmed out, just at a later stage)
The first two things that AlphaZero does is the same as any other engine. Castling, is a possible move, so the way that it is generated is the same as any other non neural network engine.
The thing is that when evaluating a position, other engines used to use a fixed tuned set of values. They would calculate king safety, space, mobility, etc using hardcoded values which were generated by years of tuning values. AlphaZero, on the other hand, uses neural networks for evaluating positions. It's all the difference. AlphaZero is no alien.
2Inefficient in comparison to what? They got pretty good results with their method, and it's not obvious how to do it "more efficiently". Nov 26, 2021 at 12:43
2AlphaZero does use a search tree. The neural networks outputs probabilities for every move, and these probabilities are used to decide how to explore the tree. Illegal moves are ignored when searching the tree. But the neural network isn't really aware of that. Although it probably learns very fast that illegal moves are bad, just like it eventually learns that bad moves are bad. Nov 26, 2021 at 12:53
3What difference between what and what? I don't understand what you're asking. Nov 26, 2021 at 13:26
2Also note there is a difference between asking "how is the neural network used to explore the search tree during a game" and "how does the neural network learn". Nov 26, 2021 at 13:29
2This is still wrong. AlphaZero uses a totally different search algorithm than traditional engines. PUCT and AB have major differences. Dec 23, 2021 at 14:49