Artificial Intelligence Stack Exchange is a question and answer site for people interested in conceptual questions about life and challenges in a world where "cognitive" functions can be mimicked in purely digital environment. It only takes a minute to sign up.
Sign up to join this community
In AlphaZero, the policy network (or head of the network) maps game states to a distribution of the likelihood of taking each action. This distribution covers all possible actions from that state.
How is such a network possible? The possible actions from each state are vastly different than subsequent states. So, how would each possible action from a given state be represented in the network's output, and what about the network design would stop the network from considering an illegal action?
The output of the policy network is as described in the original paper:
A move in chess may be described in two parts: selecting the piece to move, and then selecting among the legal moves for that piece. We represent the policy π(a|s) by a 8 × 8 × 73 stack of planes encoding a probability distribution over 4,672 possible moves. Each of the 8×8 positions identifies the square from which to “pick up” a piece. The first 56 planes encode possible ‘queen moves’ for any piece: a number of squares [1..7] in which the piece will be moved, along one of eight relative compass directions {N, NE, E, SE, S, SW, W, NW}. The next 8 planes encode possible knight moves for that piece. The final 9 planes encode possible underpromotions for pawn moves or captures in two possible diagonals, to knight, bishop or rook respectively. Other pawn moves or captures from the seventh rank are promoted to a queen.
So each move selector scores the relative probability of selecting a piece in a given square and moving it in a specific way. For example, there is always one output dedicated to representing picking up the piece in A3 and moving it to A6. This representation includes selecting opponent pieces, selecting empty squares, making knight moves for rooks, making long diagonal moves for pawns. It also includes moves that take pieces off the board or through other blocking pieces.
The typical branching factor in chess is around 35. The policy network described above always calculates discrete probabilities for 4672 moves.
Clearly this can select many non-valid moves, if pieces are not available, or cannot move as suggested. In fact it does this all the time, even when fully trained, as nothing is ever learned about avoiding the non-valid moves during training - they do not receive positive or negative feedback, as there is never any experience gained relating to them. However, the benefit is that this structure is simple and fixed, both useful traits when building a neural network.
The simple work-around is to filter out impossible moves logically, setting their effective probability to zero, and then re-normalise the probabilities for the remaining valid moves. That step involves asking the game engine for what the valid moves are - but that's fine, it's not "cheating".
Whilst it might be possible to either have the agent learn to avoid non-valid moves, or some clever output structure that could only express valid moves, these would both distract from the core goal of learning how to play the game optimally.
