3
$\begingroup$

I am a beginner in AI. I'm trying to train a multi-agent RL algorithm to play chess. One issue that I ran into was representing the action space (legal moves/or honestly just moves in general) numerically. I looked up how Alpha Zero represented it, and they used an 8x8x73 array to encode all possible moves. I was wondering how it actually works since I got a bit confused in their explanation:

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 $\pi(a \mid s)$ by a $8 \times 8 \times 73$ stack of planes encoding a probability distribution over 4,672 possible moves. Each of the $8 \times 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 under-promotions 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.

How would one numerically represent the move 1. e4 or 1. NF3 (and how would the integer for 1. NF3 differ from 1. f3) for example? How do you tell what integer corresponds to which move? This is what I'm essentially asking.

$\endgroup$
2
$\begingroup$

Let's do the code, so all the details are down.

Encoding dictionary:

codes, i = {}, 0
for nSquares in range(1,8):
    for direction in ["N", "NE", "E", "SE", "S", "SW", "W", "NW"]:
        codes[(nSquares,direction)] = i
        i += 1

You'll see that the codes dictionary will have 56 entries in it for each (nSquares,direction) pair.

The knight moves we'll encode as the long "two"-cell edge move first and the short "one"-cell edge second:

for two in ["N","S"]:
    for one in ["E","W"]:
        codes[("knight", two, one)] , i = i , i + 1
for two in ["E","W"]:
    for one in ["N","S"]:
        codes[("knight", two, one)] , i = i , i + 1

Now we should have 64 codes. As I understand, the final 9 moves are when a pawn reaches the final rank and chosen to be underpromoted. It can reach teh final rank either by moving N, or by capturing NE, NW. Underpromotion is possible to three pieces. Writing the code:

for move in ["N","NW","NE"]:
    for promote_to in ["Rook","Knight","Bishop"]:
        codes[("underpromotion", move, promote_to)] , i = i , i + 1

We get 73 codes as described.

Policy

The distribution over actions is a (8,8,73) tensor (it is not formally a "policy", since policy should also depend on state, but lets cut this corner for this discussion):

policy = np.zeros((8,8,73))

Let's also do codes for columns for convenience:

columns = { k:v for v,k in enumerate("abcdefgh")}

How would one numerically represent the move 1. e4

The first two dimensions choose the figure you are moving. So, that'd be e2 pawn. And we move north 'N' by 2 cells.

So, we put 1 into the tensor at the appropriate indices. Note that you have to subtract 1 from the row index, to make it zero-based.

e4policy = np.zeros((8,8,73))
e4policy[ columns['e'] , 2 - 1 , codes[(2 , "N")]] = 1

How would one numerically represent the move 1. NF3

The first two dimensions choose the figure you are moving. So, that'd be g1 knight. And we perform north-west N,W knight jump.

NF3policy = np.zeros((8,8,73))
NF3policy[ columns['g'] , 1 - 1 , codes[("knight", 'N' , 'W')]] = 1

Generally, the policy is a probability distribution over all possible moves, so the policy tensor would have several non-zero probability values in it. For example an opening policy that does 1.e4 or 1.Nf3 with 50/50 probability would be:

openingPolicy = (e4policy + NF3policy) / 2 

Hope this clears things up.

$\endgroup$
2
  • $\begingroup$ Thanks for such a detailed explanation! I assume in order to make this more appropriate to sample, we could flatten the 8x8x73 array into a 1d 4762 array with each integer representing it's respective move? This would make more sense in the context of training via self play, correct? $\endgroup$ – Akshay Ghosh Apr 14 at 21:14
  • $\begingroup$ @Akshay There are quite a lot of details there. This tensor is an output of Policy Network, that gets trained by the whole MCTS machinery. You also have to make sure that probabilities of invalid moves are zero and that all probabilities sum to one. For more detailed explanation I suggest studying the paper and asking more questions. $\endgroup$ – Kostya Apr 14 at 21:46

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.