Reproducing AlphaZero/MuZero: Failed to beat initial model in arena

Question

I am trying to reproduce AlphaZero's algorithm on the board game Carcassonne. Since I want to use the final game score differences (i.e. victory point of player 1 - victory point of player 2) as the final and only reward, AlphaZero's UCB score can no longer work since it assumed that the game reward is either 1 or -1. Therefore, I am using the trick from MuZero, which, when computing UCB score, normalizes the child value estimate to the range $[0, 1]$ using the minimum and maximum value estimates in the entire tree.

However, after implementing this, my algorithm almost never get past the first iteration, since the win-rate against last iteration is almost never higher than 50% (I am using an arena threshold of 0.55). If I don't normalize the reward, then the win rate seems to be higher.

My hypothesis is that, in the first few MCTS searches, there are not many estimates in the tree, and a few of the node values will be normalized to 0 or 1, which are very extreme, despite their original model-predicted values being very small in magnitude. This may cause the tree to overfit to these values instead of exploring other nodes.

• Is this a common issue with self-play, or is it indicative of a bug in my implementation?
• What are some common ways to overcome the issue (e.g. increasing data, MCTS iterations, etc)? If the algorithm does not get past the first arena, then it will never progress since it always gets reset to the initial model.

Answer 1

I've tried to organize my answer as best as possible, first answering your specific questions and then giving some higher level thoughts.

Using score as the value

PUCT as used in AlphaZero doesn't actually require that $Q \in [0, 1]$. The term $Q + c_{puct} U$ is only used to compare nodes to each other, so any constant offset is irrelevant. Additionally, scaling Q can be compensated by scaling $c_{puct}$. So you can scale down $Q$ like they did for MuZero, but just tuning $c_{puct}$ should work just as well.

You're trying to use the in-game score as the value instead of just the expected winrate. I'm not sure if this is a good idea, I would start with the winrate: it's constrained to a small range which makes both PUCT and neural network training simpler and more stable.

Debugging AlphaZero

AlphaZero has a lot of moving parts, which can make it hard to debug. How I approach debugging AlphaZero:

1. See if tree search can find the right moves in some states that are very close to the end of a game, ensuring that MCTS is implemented correctly.
   • you can already tell if the value scale is a big problem here
2. Generate a lot of randomly played games (1 million?) and train your NN value head on those. This should already provide some useful signal.
   • See if the value head predicts the right values in positions that are completely winning for one side.
   • Run some games using MCTS with this NN, it should already be better than a randomly initialized one.
3. Only if all of this works start running the full selfplay <-> train loop.
   • Look closely at plots of the train/test loss, average game length, ... to figure out if anything interesting is happening.
   • Inspect some games to see if the quality of play is increasing.

Stochastic games

Carcassonne is a stochastic game, you don't know what tile you're going to draw in the next turn. This is a big obstacle when doing any tree search, how are you handling this right now? Typically this is represented using chance nodes, for example in the Stochastic MuZero paper. Unfortunately for Carcassonne the branching factor of these nodes is very high: you can draw every remaining tile, so up to 84. This seems like a big obstacle to using AlphaZero-like methods here, I'm not sure if there's a good solution to this problem.

Other thoughts

• Newer AlphaZero papers dropped the arena idea and just always use the newest network for training, simplifying things somewhat and perhaps making it easier to get out of local minima.
• Sometimes AlphaZero just doesn't work because you haven't reached the required scale yet. You didn't give much details here, but how many games did you play, how large is the NN, how much training steps are you taking? As a rough guideline for at least 100k games before A0 starts working at all.