Generalising performance of Q-learning agent through self-play in a two-player game (MCTS?)

Question

I'm using Q-learning (off-policy TD-control as specified in Sutton's book on pg 131) to train an agent to play connect four. My goal is to create a strong player (superhuman performance?) purely by self-play, without training models against other agents obtained externally.

I'm using neural network architectures with some convolutional layers and several fully connected layers. These train surprisingly efficiently against their opponent, either a random player or another agent previously trained through Q-learning. Unfortunately the resulting models don't generalise well. 5000 episodes seems enough to obtain a high (> 90%) win rate against whichever opponent, but after > 20 000 episodes, they are still rather easy to beat by myself.

To solve this, I now train batches of models (~ 10 models per batch), which are then used in group as a new opponent, i.e.:

• I train a batch of models against a completely random agent (let's call them the generation one)
• Then I train a second generation of agents against this first generation
• Then I train a third generation against generation two
• ...

So far this helped in creating a slightly stronger/more general connect four model, but the improvement is not as good as I was hoping for. Is it just a matter of training enough models/generations or are there better ways for using Q-learning in combination with self-play?

I know the most successful techniques (e.g. alpha zero) rely on MCTS, but I'm not sure how to integrate this with Q-learning? Neither how MCTS helps to solve the problem of generalisation?

Thanks for your help!

Answer 1

To solve this, I now train batches of models (~ 10 models per batch), which are then used in group as a new opponent,

This seems quite a reasonable approach on the surface, but possibly the agents will still lose generalisation if the solutions in each generation are too similar. It also looks like from your experiment that learning progress is too slow.

One simple thing you could do is progress through the generations faster. You don't need to train until agents win 90% of games before upping the generation number. Yuo could set the target as low as 60% or even 55%.

For generalisation, it may also help to train against a mix of previous generations. E.g. if you use ten opponents, have five from previous generation, two from each of two iterations before that, and one even older one.

Although the setup you have created plays an agent you are training against another agent that you have created, it is not quite self-play. In self-play, an agent plays against itself, and learns as both players simultaneously. This requires a single neural network function that can switch its evaluation to score for each player - you can either make it learn to take the current player into account and make the change in viewpoint itself, or in zero-sum games (which Connect 4 is one) it can be more efficient to have it evaluate the end result for player 1 and simply take the negative of that as the score for player 2. This is also equivalent to using $\text{max}_a$ and $\text{argmax}_a$ for player 1's action choices and $\text{min}_a$ and $\text{argmin}_a$ for player 2's action choices - applying the concept of minimax to Q learning.

You can take minimax further to improve your algorithm's learning rate and performance during play. Essentially what Q learning and self-play does is learn a heuristic for each state (or state/action pair) that can guide search. You can add search algorithms to your training and play in multiple ways. One simple approach during training is to perform some n-step look ahead using negamax with alpha-beta pruning (an efficient variant of minimax in zero-sum games), and if it finds the end of the game:

• when training, use the result (win/draw/lose) as your ground truth value instead of the normal Q-learning TD target.

• when evaluating/playing vs human, prefer the action choice over anything the Q function returns. In practice, only bother with the Q function if look-ahead search cannot find a result.

In the last few months, Kaggle have been running a "Connect X" challenge (which is effectively only Connect 4 at the moment). The forums and example scripts (called "Kernels") are a good source of information for writing your own agents, and if you choose to compete, then the leaderboard should give you a sense for how well your agent is performing. The top agents are perfect players, as Connect 4 is a solved game. I am taking part in that competition, and have trained my agent using self-play Q-learning plus negamax search as above - it is not perfect, but is close enough that it can often beat a perfect playing opponent when playing as player 1. It was trained on around 100,000 games of self-play as I described above, plus extra training games versus previous agents.

I know the most successful techniques (e.g. alpha zero) rely on MCTS, but I'm not sure how to integrate this with Q-learning? Neither how MCTS helps to solve the problem of generalisation?

MCTS is a variant of search algorithm, and could be combined with Q-learning similarly to negamax, although in Alpha Zero it is combined with something more like Actor-Critic. The combination would be similar - from each position in play use MCTS to look ahead, and instead of picking the direct action with the best Q value, pick the one with the best MCTS score. Unlike negamax, MCTS is stochastic, but you can still use its evaluations as ground truth for training.

MCTS does not solve generalisation issues for neural networks, but like negamax it will improve the performance of a game-playing agent by looking ahead. Its main advantage over negamax in board games is a capability to scale to large branching factors. MCTS does work well for Connect 4. Some of the best agents in the Kaggle competition are using MCTS. Howver, it is not necessary for creating a "superhuman" Connect 4 agent, Q-learning plus negamax can do just as well.

Answer 2

MCTS does not help with generalization directly, but it enables the agent to plan ahead (see depth-first search or breadth-first search). Having the state space search embedded in the algorithm is very important for playing zero sum games (we also plan ahead in our head when making moves right?). Now Q-learning is generally good for simple environments, but to achieve superhuman performance on board games you would need HUGE amounts of data without using any planning algorithm. I don't even know if practically achieving superhuman performance by only Q-learning is even possible.