#Pixel Art
I added a pixalart board and peices, and added a timer for ai move so it doesnt move too fast
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.
I followed learn pytorch to make my first Convolutional Neural Network in pytorch! I have it sucessfully trained on the black and white mnist fashion dataset so it can identify fashion objects. Now I think I have enough foundations to build my final classification project.
I tried to make a classifier on skit-learns moon dataset that creates 2 classes of blobs in a cresent shape. Using my knowledge on how to create a binary classifer with ReLu and Binary cross entropy loss, I created a classifier that sucessful ‘solved’ the toy dataset. After completing this, I began to work on learnpytorch’s Computer vision module. My vision is to use my knowledge of computer vision and classification to build an interactive CNN visualiser.
I removed my old colour stuff and implemented conways game of line my changing the update code. I also made it screen size.
Loading more…