DEEP Monte Carlo Tree search (AlphaZero)

In this update, I combined MCTS with a Deep learning model, mimicking that of AlphaZero. Why? Because I like deep learning and wanted to understand how reinforcement learning can work. Unfortunately the final model that came out wasn’t the best, but it is still stronger than a simple UCB algorithmn, if just barely, winning 60% of the time against UCB.

The CNN

Cnns are Deep learning networks - machine learning networks consisting of layers of neurons that process an input to an output, transform it and pass it to the next layer. CNNs are a type of network that performs a convolution operation when reading an image, reading the image in chunks, (4x4 in this case) and transforming the data into useable information for later layers, before finally deciding on a move.

Features

I used pytorch to code my network, and hence had to convert my image, a list of 1s,-1s and 0s representing a connect 4 board into a tensor. But before I can pass the board to the model (CNN) for prediction, I need to break the board up into features. To ensure that the model has enough information to learn the rules of the game, I broke the board into 4 feature boards. The first board contains 1s for free spots and 0s for occupied spots. The second board only shows player 1 peices and the third board only shows player 2 peices and the final board just shows 1s or -1s depending on whose turn it is. I converted these 4 boards into tensors and fed them into my network.

Model Architecture

The model architecture consists of 3 convolution blocks each which consists of a CNN, a reLu activation function and a batch normaliser. Finally, I have 2 heads, a value head and a policy head.
The value head is a prediction of who is winning the game, whereas the policy head is the probabilities of the next best move. By choosing the highest probabilty, you can get the model’s next move.

DMCTS

To actually train and use the model, we combine it with the MCTS algorithm from my last devlog. During the MCTS simulation, whenever we reach a node which has already been explored, we choose the move using a rule that combines what the model recommends is best (via the policy head) and the average score of the node. When we reach a new node, instead of doing random rollouts to see who would win, we trust the model’s value head.

Training

Training occurs during self play where the model plays itself. At the start, each move is random, and the model predicts bad moves. But since the model is combined with MCTS, the model;s bad moves are eventually overwritten by better moves. At every move, the board and the model prediction are recorded. When we reach the end of the game, all the models values are replaced with the real results of the training, and each board state is stored in a databank. After every 10 games of self play, the model trains on a sample of these board states, updating the policy prediction by comparing the model’s policy values to MCTS’s run values and updating the model’s values by comparing who it thought was winning compared to who won.

Post training

After training around 12 generations of models, with each generation taking a few hours of training time, and bugfixing flawed models and architecture, I finally produced a model that can outmatch UCB. The real bottleneck was the MCTS, to train a better model, I would need more rollouts, but increasing rollouts increased the time each training run took. I trained the model with 500 rollouts, which isn’t the best, but was all I could afford. To make a better model I would need faster code and much more compute. In the end of the day, this was a very informative experiance on Reinforement Learning for me, and while the model isn’t the smartest, it isn’t incompetant either.