1
$\begingroup$

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.
$\endgroup$

1 Answer 1

2
$\begingroup$

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.
$\endgroup$
5
  • 1
    $\begingroup$ Fantastic answer! Some follow-up comments: "The term $Q + c_{puct} U$ is only used to compare nodes to each other, so any constant offset is irrelevant" I thought that if $Q$ is always in the range $[10, 20]$ for example, then for small $c_{puct}$, UCB score will always prefer $Q$ and ignore $U$ if there's at least one sample (since $U$ is always in $[0, 1]$). $\endgroup$
    – TommyX
    Apr 8, 2023 at 18:28
  • $\begingroup$ "Sometimes AlphaZero just doesn't work because you haven't reached the required scale yet." I am actually following this implementation here, which successfully uses 100 games per iteration and a 2000 game buffer to train Othello. Could you elaborate on the guideline of 100k games? $\endgroup$
    – TommyX
    Apr 8, 2023 at 18:28
  • $\begingroup$ "Newer AlphaZero paper dropped the arena idea" Right, I noticed that MuZero doesn't have arena. Why doesn't this creates training instability where model could gradually become worse and get stuck with degenerate strategies? $\endgroup$
    – TommyX
    Apr 8, 2023 at 18:28
  • $\begingroup$ Maybe wait with accepting answers for a bit, a better one might come along! Your comments addressed in-order: For UCB I'm saying the offset doesn't matter because it's relative and then separately the size of the range doesn't really matter since you could just change $c_{puct}$ to compensate. This may be a more "stable" solution than relying on per-tree normalization. The 100k games guideline is from my own experiments on chess, where eg. the policy head only started to learn interesting things after 160k games (40k on the x-axis, after the stagnation): i.imgur.com/wzhtiWc.png ... $\endgroup$ Apr 8, 2023 at 20:51
  • $\begingroup$ ... This "required" scale is not related to buffer size or generation length, just the raw number of games played. But maybe Othello is simpler, or maybe I'm doing something wrong that's slowing me down. Just don't be discouraged too quickly, A0 can take a while to start showing interesting behavior. The arena isn't necessary because some combination of a large enough buffer + high enough move selection temperature + low enough learning rate + high enough Dirichlet epsilon + ... seems to work well enough against catastrophic forgetting, local minima, ... $\endgroup$ Apr 8, 2023 at 20:55

You must log in to answer this question.

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