GANN-EWN / Part 5 / Applying the Neural Network trained by the Genetic Algorithm to the game EWN

If you haven’t read the previous parts, you should start at part 1.

Now that we have a Neural Network architecture and a Genetic Algorithm, we can apply them to the game “Einstein Würfelt Nicht”.

The Parameters of the Problem

There are several parameters that need to be addressed first:

how to feed information to the NN and how to get a result,
how big should the NN be, how many layers, how many neurons per layer, how many connections between each layer,
how to tune the parameters for the GA (population size, mutation rate, etc.).

There are some precedents for every of these 3 points (NNs as well as GAs have been studied), but there is no existing answer for this particular set of problems.

Feeding Information to the NN

The answer to the first question seems trivial, but it is actually not. The first answer that comes to mind is “just feed it the board and the die and get the stone that has to be played and the move to be played”.

This is of course a valid answer, but there are many more:

don’t feed the whole board, but rather the positions of the stones along with the die,
feed the possible moves instead of the die,
or you could use the network as a “value network”, in other words let the network evaluate how favorable a certain position is for the current player. In that case, the algorithm has to simulate every possible move and apply the network on every resulting board.

There are many other ways of feeding information, including feeding redundant information. For instance, you could feed the number of stones left for each player in addition to the board: that’s an information which is obviously useful and that the network could directly use rather than having to calculate it again.

Getting the NN’s Result

The Neural Network can be used to gather very different results, also depending on which information it was given as inputs. Here are a few ways that the network can be used:

the number of the tile to be played along with the move to be played,
among all the possible moves, get the index of the chosen move,
return one output number for each tile and each move, and play the tile that has the highest number along with the move that has the highest number,
if used as a value network, just return one value: the fitness of the current position.

Again, there are many ways of using a neural network to play. We could even use two networks: one to choose the tile to play, and then a second one to choose the move. Whatever we choose, we have to keep in mind two main points here:

the result can never be an invalid move, which is not always trivial,
make sure that results cannot be incoherent. For instance, a valid possibility would be to have two integer outputs: one for the tile to play on the board, one for the move to play, each of them being applied the mathematical “mod” to make sure that the results are within range. But then there might be a discrepancy between the chosen tile and the chosen move. Maybe the move made perfect sense with another tile, but not with the one that was eventually selected.

The Size of the Neural Network

I tend to reason in terms of complexity of the game to address this problem. Just think about “if I had to code a perfect player for this game, how many rules and cases would I have to take into account”.

The answer also depends on what you feed the network. If you feed it a lot of redundant information (for instance, feed it the board and the number of remaining tiles for each player), then the network will have to extract less metadata from the board.

In the case of the game “Einstein Würfelt Nicht”, I chose not to mostly not give any redundant information to the network. Given the size of the board, I believed that a simple network of just a few layers and a couple of hundred neurons would probably do the trick.

Then comes the number of connections between layers. In order to extract as much information as possible from the board, I believed that a fully connected first layer was needed – although I chose not to enforce it, but I gave a sufficient amount of connections for this to happen. So I started off with a first layer of 20 neurons, along with 500 connections between the board (which is a 25 bytes array, with an additional byte for the die). I have also tried other different variants.

The Parameters of the Genetic Algorithm

Population size, mutation and cross-over rates

I started off with a population of 100 individuals and made some tests with 200. In that population, I chose to keep a fair amount of the best individuals, 10 to 30%, without checking their scores. All the others are discarded and replaced with either new individuals, either top individuals that have been mutated and crossed-over.

As for the mutation rate, I made it randomly chosen between 1/1000 and ten to twenty per 1000. That is to say that to create a mutated individual, 1 to 10/20 random mutations are applied for every 1000 bytes of its DNA. Note that with a network of 10000 elements, that’s just a few mutations in the network. A mutation can be a change in an operation, a connection move or a change in parameters such as weight and offset.

As for the crossover rate, I made it from 0.01% to 1%. As we will see later, it wasn’t that successful in the first versions.

Evaluating players

Another important parameter is the accuracy of the evaluation for every individual. In the case of a game, it can be measured by having this individual play many games against other players. Other players may be other individuals of the population and/or a fixed hard-coded player. The more games are played, the more accurate the rating of a player. And this is getting more and more critical as the player improves: at the beginning, the player just needs to improve very basic skills and moves, it is failing often anyway, so it is easy to tell the difference between a good player and a bad one. As it improves, it becomes more and more difficult to find situations in which players can gain an advantage or make a slight mistake.

In the case of EWN, as it is a highly probabilistic game, the number of matches that are required can grow exponentially. Note that there are even a large number of starting positions: 6! x 6! which is roughly 500 thousand permutations. With symmetries we can remove some of them, but there is still a large number of starting positions despite the very simple placing rules. So even if you play 100.000 games for a player, it is still not covering the wide variety of openings. What if your player handles well those 100.000 openings but is totally lame at playing the rest? Not even mentioning the number of possible positions after a few turns.

A good indicator to check whether we have played enough games to correctly rate players is the “stability” of the ranking of players as we continue playing games. As the rankings stabilize (eg for instance the top player remains at the top for quite a long time) we are getting better and better accuracy.

Individuals selection and breeding

As I developed this and started testing it, I realized that the evolution was going very slowly: new individuals were bad in general, with only a few of them reaching the “elite” of the population. That’s because of the randomness of the alterations. We will see later how I tackled that problem.

As I was going forward in this and observing how slow the process was on a CPU, I also started planning to switch the whole evaluation process to the GPU.

GANN-EWN / Part 4 / Developing a Genetic Algorithm from scratch

Welcome to this fourth part of building Neural Networks evolved by Genetic Algorithms. If you haven’t done so yet, I would advise to read the first, second and third parts before reading this article.

Basics about Genetic Algorithms

So, what exactly is a Genetic Algorithm? The name applied to Computer Science sounds both scary and mysterious.

However, it is actually quite simple and refers to Darwin’s theory of evolution which can be summed up in one simple sentence: “The fittest individuals in a given environment have a better chance than other individuals of surviving and having an offspring that will survive”. Additionally, the offspring carries a mutated crossover version of the genes of the parents.

Given this general definition, the transposition to Computer Science is the following:

design “individuals” to solve a particular problem, whose parameters are in the form of a “chromosome”, most of the time a simple array of bits,
create a “population” of these individuals,
evaluate all individuals in the population and sort them by their fitness (e.g. how close they get to solving the problem well),
create new individuals by making crossovers and mutations on the best individuals of the current generation,
replace the worst individuals in the population by those new individuals,
rinse and repeat: go back to evaluating all individuals in the population.

With this in mind, the choice in part 3 to store our neural networks in simple arrays comes into a new light: those arrays are the chromosomes of our individuals.

Our Genetic Algorithm

The genetic algorithm I built went through several phases already.

Here is the first phase:

generate n individuals, each representing a player, note that players may also be non Neural-Network-driven players or players using different types of NNs, we can actually mix players of different types in the population,
make them play against each other a certain number of games,
select the ones with more wins and discard the others,
replace the discarded players either by new random players, either by mutations and crossovers of the best players.
go back to step 2.

Still, with this simple algorithm, there are many possible parameters:

the population size,
how many individuals to keep? Keep the top x %? Or all the ones managing to have a certain score?
how much mutation and crossover percentage should be applied?
how many games to play to get a good confidence score on every player?

The supporting UI

To evaluate the impacts of these parameters, I then built an UI on top of this to observe the evolution of the population and see how the best individuals evolve. The UI is made of a simple table, sorted by “performance” (that’s to say the percentage of wins). Every row shows one individual, its ranking, its age (since a single individual can survive for multiple generations), its original parent, and the number of total mutated generations it comes from.

Later, I also added at the bottom of the screen the progression of the score of the best individuals.

Here is a simple screenshot:

The green part represents the individuals that will be selected for the next generation. All individuals in red will be discarded. The gray ones are non NN implementations that can be used as “benchmarks” against the NN implementations. When the first population is created randomly, they are generally beaten very easily by those standard implementations, but we can see that after some iterations, the NNs selected one generation after the other end up beating those standard implementations. We’ll dig into that in the next post, along with the choice of the different parameters.

Next comes part 5.

GANN-EWN / Part 1 / GANNs (Genetic Algorithms applied to Neural Networks)

Combining Genetic Algorithms and Neural Networks is an idea that has been troubling my mind for the last 20 years. Unfortunately, life went in the way and I didn’t have a real chance of putting this idea into practice. Neural networks are very often used to do some “classifying” jobs, and they are very good at it. At least they got far beyond what we humans could program ourselves. However, as I have ideas for developing very interesting games, I also had in mind to have an AI play those games, and an AI that would actually learn how to play them, rather than programing it myself. This is exactly what the guys at DeepMind have been doing in the recent years. From Atari games to Go and Chess (and Shogi), they have amazed us all.

As I’m going back to my original interest in AI, I have taken upon myself to build an AI from scratch that would do exactly what I had in mind 20 years ago: learn how to play games.

In the meantime, things in the AI field have evolved. Graphics cards have opened new horizons for training bigger and faster Neural Networks. I have had some graphics cards that I used at some point to mine some cryptocurrencies for fun. Those cards were AMD cards, and they were getting hot very easily (the 7970 was going up to 100 degrees Celsius, I suspect that the fitting of the radiators were poorly made). I set up a watercooling system for the whole miner. Although it was a very interesting experience, it came to an end rather quickly. since ASICs kicked in and rendered graphics cards useless.

At the time, I started a project for handwriting character recognition (more on this project later…), and I used one of those cards to apply some graphics transformations (Hough transform and such). But they also consume a lot of electricity. So, sorry AMD, but I switched to Nvidia (I don’t own any stocks of either of those companies… or any other company, by the way, but I do believe that AMD is seriously losing ground here), which also has some great support with tools to build Neural Networks like TensorFlow.

So I wanted to start with a simple game and a simple goal:

create a neural network framework from scratch, with NNs as generic as possible, including non linear functions, spikes, max and many operations, the ones that will be best will be selected by the genetic algorithm,
a genetic algorithm to make those NNs evolve,
all this should be able to run both on CPUs and GPUs (at least the most power-consuming parts), and I originally planed to learn some Cuda although I had prior OpenCl experience.

But everything had to start somewhere. And I didn’t want to tackle Chess or Go as my first GANN project. Anyway, the DeepMind guys have done that already!

So I had to aim for something simple for a start, and at the same time some game that I didn’t know well so that I wouldn’t be tempted to direct the algorithm and make “Stockfish for game XXX”. On the same note, another strong criteria was also that it shouldn’t be a game that had been solved by mainstream software, like Chess, Checkers or Reversi/Othello. At the website littlegolem on which I play board games, there are some games that I don’t know well (yet) and also many games for which mainstream software is not really available. One of them is called “Einstein Würfelt Nicht” (which I will call EWN in the future) and is actually a dice game, played on a 5×5 board. When I started this project, I had never played that game but the rules seemed quite simple and I decided to have a go at it. This was of course the first attempt, the first prototype, basically some starting point, but certainly not the end point.

There are also two variants of the game on the site, which would be also nice to tackle. My initial goal there was to defeat human players and become a top player on the site. Note that this particular site is also very flexible with its players, and doesn’t ban anyone. If you don’t like playing against cheaters or robots, then that site is definitely not for you. But personally I learn a lot by playing with any kind of opponent, it doesn’t matter if I win or if I lose.

I will develop that story in the next articles, and I will also post some of the code soon on my gitlab account. However, I will not post the full code, don’t expect to be able to have a running bot that would play for you at EWN from there. But the generic code will be there and will be adaptable to other games as well.

The next part is here.