I created a simple pygame program where you can drop an image into a box to show it.

Palette Swap (1NN-algorithm)

I created a simple algorithm that can take in an image and change the colours of the image to fit a palette in python using NumPy.

How it works

The 1- Nearest Neighbour (1-NN) algorithm is a classical machine learning algorithmn, therefore, like all ML it uses Linear Algebra.

K - NN

The K Nearest Neigbour algorithm is a simple algorithm for classification. It takes an vector of an unkown, a list of values, and compares it the vectors of classes it does know. This works as vectors can be imagined as positions in a high dimentional space. It looks to the nearest K classes closest to the unkown vector, and assigns it the class of the most popular class found it the nearst K class. In my case, since each of the known vectors are their own class, pixels in a pallete, it just looks to the nearest vector and turns into the vector, essentially turning a random pixel into the pixel of the pallete most similar to it.

Pixels

Using the pillow library from my last post, I turned the png into RGB, and then from there converted it into a NumPy tensor of shape [Height, Width, RGB]. This means that the tensor is a 2d array where tensor[n][m] stores the RGB values / vectors in the form [R,G,B]. But to make this more simple for calculations, I collapsed height and width into a long list of [Pixels, RGB]

I also made a palette list containing some [R,G,B] pixel values. Initially I just used the engesda 64 pallete.

Broadcasting and Normalisation

Now that I had my 2 tensors (palette and pixels), I can employ the algorithm. Before I calculate the distances, I need to first change these two tensore using broadcasting. Broadcasting is a NumPy mechanic where you add extra dimentions to operate with. Currently I have 2 tensors, pixels [pixel, RGB] and pallete [colour, [RGB] and I want the combined tensor to be in the shape [pixel, colour, RGB], so for each pixel I calculate the distance from the pixel’s RGB to the RGB of each of the palletes colour. To make this happen I used broadcasting, adding one extra dimention to both the pallete and pixel tensors, before subtracting the values.

Now that I had the distance vectors, I converted each [R,G,B] values into its magnitude (sqrt(R^2 + G^2 + B^2)) to turn the distance of a pallete colour to the pixel into one number. Then I chosed the pallete colour with the lowest distance and converted the initial pixel to this colour.

Conclusion

In this part I learnt a lot about how to use NumPy and it’s broadcasting feature and changed the palette of the bird image from my last post to these 3 images:

I learn how to use pythons Pillow library and set up a virtual enviornment, and changed the colours to this cute bird image.

#Pixel Art
I added a pixalart board and peices, and added a timer for ai move so it doesnt move too fast

Checkboxes

I implemented checkboxes so that you can choose which model to play against.

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.

Made UI transparent if not usable, and improved the draw mechanic.

Monte Carlo Tree Search

The UCB is a good algorithmn, until you realise that it can only see 1 move into the future. A strong player for any project has the ability to stratagise, by predicting into the future. Monte Carlo Tree Search takes this UCB algorithm and gives it the ability to see into the future, creating a stronger AI opponent at the cost of compute.

How it works

Monte Carlo tree search, as it’s name suggests, builds a tree of future states to calculate which state is the best. The algorithm works in 4 steps - Selection, Expansion, Simulation and Backpropogation

Selection

At the start of the search, the parent node looks to its children node, which consist of the legal connect 4 moves, e.g 7 children for each column you can place a piece in. If each child has already been simulated at least once, the child with the highest UCB score is chosen and the process repeats until you reach a node where not all future moves have been simulated.

Expansion

Once you reach a new unexplored node, you fist expand the node, creating children for each of the possible states the next move can take.

Simulation

Once you have reached a node where all the children aren’t explored, one of these children are chosen, and a random rollout takes place, similiarly to the UCB algorithm

Backpropogation

After simulation, the results of the simulation (win or loss or draw) go back up the tree, updating each parent node with the updated win score.

Decision making

After enough simulations, the child of the original state with the highest run count is chosen - as this is deemed to be the most promising node by the algorithm

Implementation

Implementing this algorithm from scartch was harder than expected, but also fun! The only problem was that for higher simulation counts, such as 1,000 or 10,000, it takes a good few seconds for the algorithm to make a decision. I also somehow broke my original connect 4 code when trying to implement this program. I ran 100 simulations of MCTS vs UCB, both with 1000 simulations each, and MCTS only won 20 more games than ucb. I moved MCTS simulation count to 10000 and it won most of the games played.

I remade the PvP mode so now the game is fully playable, added a purple background for the gameboard and made the background black for empty peices.

This update was a revamp of my old code, I remade everything but the PVP section and made the screen resizable.

Added easy, medium and hard mode - each being UCBs but with different runtimes. Also updated the buttons as they were outdated code

UCB - Upper Confidence Bound

The UCB algorithm is an algorithm that I created to play connect 4.

How it works

The philosphy of UCB is doing random simulations of the game, and the move with the highest winrate in the random simulations is the best move.

The problem UCB solves is given a set amount of simulations - called rollouts, how do you allocate the amount of rollouts each move gets? You want to spend more time on promising moves, and less on unpromising moves, but you still need to try these unpromising moves because they may be good, but have low winrates just due to random chance. This is decided by the UCB rule:

UCBᵢ = avg(Xᵢ) + √( 2 ln(T) / nᵢ )

Which is the average winrate of the move i plus an optimism score. The more times you play a move, the chance that it is secretely a good move decreases. This ensures that you spend more time on good moves (high average) but also spend some times on worse moves that may turn out to be better by investing more rollouts on them.

Implementation

I implemented this into my connect 4 game I made, and allocated rollouts to 1000, so it makes 1000 random simulations to choose each move, and it kept on beating me. I had to reduce rollouts to 250 so I had a chance of winning.

I added a clear button so you can clear the board and try out you own creations.

Life Like Cellular Automata

Cellular Automata is a discrete grid based system which consists of cells that update themselves following a certain ruleset over discrete time chunks called generations. Conway’s game of life is the most famous one of these, but is only 1 subset of a larger set of life-like cellular automata.

In Conways game of life, each cell can either be one of 2 states, dead or alive. Its’s updating ruleset is:

• A node is ‘born’ if it has 3 neighbours, changing state from dead to alive
• A node survives if it is alive and has either 2 or 3 neighbours, else it reverts back to a dead state

This ruleset can be written in the form of B3/S23 and is just one of many other rules that can exist in life-like Cellular Automata.

In this update, I have added boxes that you can turn on or off to customise the cellular automa to any rule you want.
My next goals are to:

• Make the grid editable so you can create your own systems
• Make a rewind button so you can see how different structures are formed
• Create a slider to control simulation speed

Mainly, I just added checkboxes. The vision is to have these boxes control at what numbers nodes spawn and die.

Now that I had a drawable grid, i converted that grid to a pytorch tensor, that I plugged into my MNIST classifer that I made 2 devlogs ago, to create an AI number guesser! Honestly, while it does ocassionally slip up and make a few mistakes, especially confusing 7s and 2s and 6s and 0s, it is amazing!

I created a pygame grid that you can draw on, left click to add, right click to remove.

Using my knoeledge on classification I created a convolutional neural network classifier on the Mnist numbers dataset:

Added a Mouse scroll to make the zoom mechanic more intuitave - and its much less laggy than a slider. Programming a scroll wheel was both easier and harder than I expected, but I have now added a new tool to my pygame toolkit.

I Implemented the slider mechanic I was working on before in order to make it so that you can scale the simulation, as can be seen in this video.