1
$\begingroup$

I'm trying to train a RL agent to play the game of checkers (AlphaZero style) and so far I've managed a proof of concept training a connect 4 agent up until perfection. However, unlike connect 4, checkers moves pieces rather than placing them and sometimes even multiple times. I think I understand how I would do this for chess: I have an output size of 80 (16+8*8) and have the first 16 outputs represent the piece that will move and the other 64 represent the position it will move to. I'm not sure if this is a valid solution though. The real problem arises when considering checkers with multiple jumps. Is there any solution to this and am I thinking about it the right way? I've pondered not changing the player turn whenever a double jump is available but I feel like this will screw with the MCTS.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

Correction regarding policy encoding

The policy encoding you propose for Chess is not the one used by the original AlphaZero and would not work. The network needs to output a policy distribution over the possible moves, so there needs to be a dedicated output value for each move. Your encoding only allows the network to express a single move, or at best some low-rank approximation of the full distribution.

The AlphaZero paper (free access) has a section Representation, which explains the policy encoding they used. It has shape 73x8x8. Of course in a chess position there are never actually that many moves, so invalid moves are masked out.

Complex move representations in AlphaZero

As you also note there are two possible solutions to representing these types of compound moves:

  • Figure out all possible moves and some reasonable way to encode them in a policy head. AlphaZero can still train quite well with a large, sparsely used policy head as shown by their chess results.

  • Represent the game differently, with moves split up into submoves that don't always change whose turn it is, and then find an encoding for this smaller set of moves. AlphaZero and more generally MCTS doesn't require alternating players, for example the followup work MuZero (free access) works just fine on the Atari games with only a single player.

Practical advice for checkers

I think both solutions would work fine for checkers. Even including compound moves I think checkers still has less than 73*8*8 = 4672 possible moves, although I don't know for sure. If it's in the same ballpark or lower the first method should work. The first solution also has the advantage that it's simpler to implement and that you can achieve deeper search with a fixed number of neural network evaluations.

The second solution is in some sense more general and scalable, so it could be interesting to experiment with as well.

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ I think I will end up separating multi moves into sub moves since trying to encode multi jumps in several different directions and including king moves jumping will be unworkable. I appreciate your detailed response $\endgroup$
    – Anik Patel
    Oct 29, 2022 at 18:21
  • 1
    $\begingroup$ @AnikPatel You could also go for a hybrid where you encode some compound moves as a single move. (and disallow the sequence of single moves that would lead to the compound move to prevent duplication). I've seen this work for the game Arimaa for example. $\endgroup$
    – Todd Sewell
    Oct 29, 2022 at 19:02

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .