GANN-EWN / Part 3 / building a Neural Network from scratch

Welcome to the third part of the GANN-EWN (Genetic Algorithms for Neural Networks applied to the game “Einstein Würfelt Nicht”) series! If you haven’t read it yet, it’s probably time to read the first part and/or the second part.

In this part, we’ll start building a Neural Network from scratch.

I assume that you’re familiar with Neural Networks, which are basically a simplified stereotype of what people thought neurons in the brain were like in the 1950’s. 🙂 Since then, biological research has evolved a lot and we know now that real neurons and their interactions are much more complex than the general models of Computer Neural Networks that are around.

Anyway, there are many types of neural networks around, all used for different tasks. My attempt is to build a very generic neural network structure that can then be used in various environments, typically to play different games.

Important structural decisions

Since the early days of neural network research, the transfer functions used in artificial neurons have been carefully chosen to enable backpropagation. In here, though, we want to use our neural network through Genetic Algorithms by selecting the best neural networks within a population, and we won’t necessarily be using backpropagation to make the network “learn”. So we can use any kinds of transfer functions we want.

At first, I also wondered if I would be using totally random graphs for my network structure, but it poses problems such as cycles which require more computational power to deal with so I stayed with a “simple” layer architecture. But because I wanted to code a network that would be as generic as possible, the only constraints I kept was to have a structure with layers: links between neurons of different layers can be as random as possible, with the only requirement that every neuron should have at least one input and one output (a neuron without any input or output would simply be useless and would waste resources unnecessarily). On the other hand, I didn’t put any restrictions on duplicate links from one neuron to another. After all, it could be useful to have the sinus of something and combine it with its raw value.

Another important decision was to limit to the strict minimum the manipulation of floating point values. There are two reasons for this, which are both linked to the projected use of GPUs for my research, and based on my own experience of using GPUs. The first one is that GPUs in general are not so great, performance-wise, with floating point values. The second is that the results of floating point operations may differ between CPU operations and GPU operations, due to rounding and approximating some functions on the GPU. Besides, most GPUs have limited support for double floating point operations, which makes portability some kind of a pain. We will actually discuss that in more detail in another article.

So I decided to take only integers as neuron and link input and output values, as well as the weights and shifts that could be applied on all operations. However, some operations will need some floating point numbers, such as sigmoid and tangent functions, but the results will be transformed back into integers as soon as possible so that floats are used as little as possible.

Description of neurons and links

Besides, as I didn’t stick with “simple” linear or sigmoid functions for my neurons, the links themselves also have interesting properties. Here is a simple figure showing the basics of my neurons and links:

So the output of every link is of the form: out = unary_op ( (in + shift) x weight )

As for computing the result of a neuron, I used what is generally referred to as “genetic programming” where the genetic algorithm doesn’t mutates “parameters” for a program, but rather a tree of instructions (a program). So in my case, a neuron contains a tree of mathematical operations to be applied on the inputs.

So the output of a neuron having n inputs is:

  • the input itself if n==1
  • the result of a tree of n-1 binary operations

For instance, the tree for the previous picture is the following:

The unary operations I have chosen are: id (identity), sinus, log, square, square root, tan, and negative.

The roughly described binary operations are:

  • add (actually average, we’ll see why later),
  • divide (leave numerator unchanged if denominator is 0),
  • subtract,
  • multiply (with an adjusting weight),
  • max and min,
  • an hyperbolic paraboloid and its reverse.

With this in mind, it is actually not difficult to switch this network to any type of network, including simple linear functions. Just limit the allowed operations to “+” and we’re pretty good to go. The same goes with links, just restrict them to use “identity” as their unary operations and set the weights as desired, just leave the offset (often called “bias” in neural network computing).

Besides, as the link structure is not constrained either, we can create any type of network we want by forcing the links to be in a certain way when we build the network.

Integers and range

There is one remaining problem here: if you store everything as integers and never stop adding and multiplying numbers, you’ll overflow at some point.

So I kept all operations to be within a certain range and added weights and min/max to make sure that all numbers would be kept within that range. How to define the range? It has to be as big as possible to allow for enough precision (obviously if we keep only integer values from -10 to 10, we won’t be able to store Pi using a good precision, but if we go up to a million, then we can store 3.14159, which is already not that bad). On the other hand, the range should allow not to lose precision while doing operations such as multiplying integers. Integers in Java or OpenCl have a rough range of -2 billion to 2 billion so 10.000 should do it (the square is 100 million, perfectly in range).

So within the network, all values circulating should be within the -10.000 to 10.000 range, which means that some adjustments had to be made on the different binary and unary operations, in order to always keep results within that range. For instance, adding is converted to an average, to make sure the result is still within the desired range.

Encoding and storing the networks

Because the ultimate goal is to run this on GPUs, the networks cannot be programmed as Objects. Instead, plain arrays of integers are used. One other advantage is that it is very simple to store an array of integers and it could be manipulated in any programming language (provided that we code the program that would interpret this array).

Here is the description of the array describing a network so far:

  • [0]: the number of layers L, including the output which is considered as a layer, but excluding the input,
  • [1 : L]: the number of neurons in each layer (including the output layer, but excluding the input),
  • [L+1 : 2xL]: the number of links between each layer (at position L+1, we have the number of links between the input and the first hidden layer),
  • [2xL+1:…]: all link parameters (we will go over them shortly),
  • after the links: all binary operations for the links, for every layer connectivity there are as many as links minus one.

Every link contains 5 integers and is described as follows:

  • the number of the source neuron in the source layer (this number is unique within the network, so the number of the first neuron of the first hidden layer is equal to the number of inputs),
  • the number of the destination neuron in the destination layer,
  • the applied offset on incoming values,
  • the applied weight applied on the result of the offset,
  • the code for the unary operation applied to that result.

Let’s calculate the size of an array needed to encode the following network: 20 connections between inputs and the first hidden layer, 10 neurons in the first hidden layer, 30 connections from the first hidden layer to the second hidden layer, 4 neurons in the second hidden layer, 10 connections from the second hidden layer to the 2 outputs.

1 + 2 x 2 + 5 x 50 + 19 + 29 = 303 elements

For now, the networks are stored within a simple local H2 database.

Watching it in action

Finally, I built a small UI to watch how the network behaves when its inputs change. Later, it might come in handy to see how the network behaves during a real game:

The inputs are on the left, and can be entered either numerically or from sliders, and the outputs are read on the right (this one has only two outputs). The two hidden layers (containing 4 and 3 neurons) are clearly visible. Besides, every link has the offset represented as a bar (red means negative, green means positive, full gray is 0) and the weights are represented as filled circles.

In the next article, we’ll build the genetic algorithm part of the project.

The next post of the series is here.

GANN-EWN / Part 2 / Building a Hand-Crafted Player For EWN

Welcome to this second part of the GANN-EWN (Genetic Algorithms for Neural Networks applied to the game “Einstein Würfelt Nicht”) series! If you haven’t read it yet, it’s probably time to read the first part.

The game is quite simple: at the beginning of the game every player has 6 pieces labeled from 1 to 6, and every player throws a die at every turn. Depending on the result of the throw, the player may move one or two of his own pieces. The goal is to reach the opposite side of the board (diagonally) or capture all opponent’s pieces.

The rules with the dice are simple as well. If the die corresponds exactly to one of his pieces, he has to play that piece in any direction forward (the three squares: up, up left, or left), like in here where the die shows “5”:

If no piece with the same number are on the board, then one of the two pieces that are the closest to the die can be played. For instance, if the die was “2”, then the “1” and “3” can be played here:

Again, if the die is “3” then on this board the “2” or the “5” can be played:

Note that if there was no “2” on this board, then only the “5” could be played since there is no lower number than “3” on the board.

The first thing to do was to code a simple board implementing the rules of the game, which is quite straightforward. I chose Java, which is probably the programming language I’m most comfortable with, but also for another reason, which I will develop later.

To have something to compare my neural networks to, and also to test my implementation of the EWN Board and game logic, my first first step was to implement a simple (and I can call it quite “naive”) implementation of a player, based on my very limited experience of the game. Remember that I just discovered EWN, so after having a look at some games from the best players, I realized that one common strategy is to “eat up” some of your own pieces early in the game, to give momentum to your remaining pieces. Although this is a “classic” strategy, it does have one drawback: you opponent may be able to take all your remaining pieces and you lose. Nevertheless, I decided to implement this rule, along with a few others. Here is the list of rules that are hard-coded in this first player:

  • if one move is a winning move (capture the last opponent’s piece or reach the opposite side of the board), then play it,
  • if an opponent piece is close to winning (basically at a certain distance from the goal), always take it,
  • always take your own pieces if they are within a certain number (typically from 2 to 5) if you have more than a certain amount of pieces (you don’t want to take your pieces if you have too few of them, that could be suicide in some situations),
  • move forward always the most advanced piece (rushing towards the goal),
  • preferably move forward-up rather than simply forward or up.

And that’s it!

So yes, this is a very simple player, but one funny fact is that this player beats me consistently! That’s how weak I am at EWN as a player.

But as those rules can have parameters (how far must an adversary piece so that we capture it? etc.), I ran a simple computer simulation using a range of possible parameters (including totally disabling a rule). And those simulation showed me that, by far, the best parameters are:

  • capture pieces that are at most at a distance of 2 from the goal, but actually this rule is not very important,
  • take your own pieces from 2 to 5 until you have only 2 pieces left,
  • move always forward-up,
  • do advance the most advanced piece.

Of course, every single rule taken on its own may have some exceptions, but my “simple player” doesn’t go that far.

I also created a “random” player which picks moves at random, again to have something to compare to that doesn’t vary much in its crappiness. 🙂 And indeed my simple player was definitely better than the random one, at least.

I published this first player on the littlegolem site, with a different user than my regular user.

This is when I discovered that the site was actually crawling with bots playing EWN! Nice, the challenge was getting interesting! That’s when I met with a German researcher who also wrote a bot to play EWN on littlegolem. He even made part of his PhD on this project, so needless to say that my own simple player was quite ridiculous compared to his, and got a very bad beating!

This is when I realized that EWN is actually a statistics-driven game, since you make a choice depending on the probabilities of the next dice throws. You have a “2” ahead and want to give it momentum to reach the opposite side of the board faster? Capture your own “1”, “3” and possibly “4” and “5” pieces. The enemy has one piece slightly ahead but that piece has a 1/6 chance to be picked by the dice? Just ignore it. But you will capture that piece if it has a 1/2 chance of being played. As the Wikipedia page points out, one of the first approach is to calculate probability tables for each piece to reach the goal. All the dynamics of that game are based on probabilities. Well, almost. So that makes it a very good candidate for a Monte-Carlo type approach.

As a reminder, the general principle behind the Monte-Carlo approach is: “at a given turn, for each possible move play as many random games as possible and play the one that leads to victory more often than the others.”

Brutal. But very effective and the easiest “AI” to program. I guess. At least on a CPU.

So I implemented a simple Monte-Carlo (that I will abbreviate as “MC” now on) algorithm and launched it against my simple player. And sure enough, the MC player won, even if it was just playing 1000 games with random moves to decide which move to pick. And I’m not speaking about a “little better” here. The MC player won almost 70 games out of 100.

Then I thought: picking random moves is not really a likely outcome for a normal game, so the results for the MC player are somehow skewed. What if I use my simple player instead of a random player to play the games?

No surprise, using the simple player within the MC player improved the results against the simple player by quite a bit. But against the random MC player, the difference was not that big, it just improved it slightly, but not really significantly, only by 2.5 to 3% which is not bad but not as much as I would have expected. Note that running this simulation on a CPU is costing a lot of cycles. 1000 games with each roughly 15 to 20 moves. And at each turn, play 1000 games for every possible move (there are 1 to 6 possible moves). That’s a lot of moves to run! I’ve accelerated that to run on a GPU, but that will come later.

And still, the MC player lost to the German PhD’s carefully hand-crafted player. Well if a simple MC approach would do it, that’s what he would have picked in the first place!

This is it for this part. Next, we’ll start building a Neural Network with its associated Genetic Algorithm.

Part 3 is here.

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.

Introduction to this blog and who I am

Welcome to my blog!

To understand where this blog will be going, you have to get to know me first. Let me introduce myself briefly. I’m a poly-faceted and multi-interest person.

Here is a short list of my top interests:

  • Science in general. I have a variety of interests in Science and Technology, including Astronomy, Geology, Climatology, Nanotechnologies, 3D printing, and many others.  Along with the philosophical aspects that come with science, which are getting trickier every day (AI – Singularity, anyone? Trans Humanism, Genetic Tampering etc.).
  • Computer Science in particular. I’m a Computer Engineer, so Computer Science is definitely on my top list. As a child, I was always attracted to computers and especially how they can be programmed to do an endless number of things. My main area of interest, though, is Artificial Intelligence. I made a PhD in the 1990’s in that domain, and I’ve always kept myself up-to-date since then. In the recent years, we’ve seen quite a number of breakthroughs in that area. So for sure, this blog will contain a lot of articles about technology. One other area of interest is storage of data and how to keep it safe, which is a topic most people disregard too often until some irreparable damage happens. Not only should your data be safe, but also kept private. On this topic, I have been introduced to Cryptography at an early age by my father, who was giving me coded messages to decipher, so I know the technology and its thrilling history.
  • Libre Money. Blockchain technology can free us from the limitations and flaws of the current banking system. Not with Bitcoin or many other cryptocurrencies, but with a unique type of currencies called “Libre Currencies”. In fact, one such currency already exists, it is called Ğ1 and is powered by Duniter. I’m participating in the effort to translate some of the material there, including the Relative Theory of Money, which is the underlying theory for Libre Currencies. I have also written a program to help animators of the game Ğeconomicus (which is a good introduction to Libre Money).
  • Board Games. I have been playing Chess since age 5, and I’m a big fan of board games. The main point here is to never keep the brain still, and always learn from playing. I know a large variety of games, from Shogi to Checkers and from Go to Hex. You can see me regularly at littlegolem and I sometimes play Arimaa as well. I used to play RPG games (and was leading big teams in some) but I’m past that now. 🙂
  • Foreign Languages. I’m French and I’ve been in a bilingual school at an early age. I speak French (obviously), English (obviously again!), Spanish and German quite good, and I’ve studied a number of other languages to various degrees. These include Japanese, Italian, Portuguese, Esperanto, Russian, Turkish, Danish, Arabic, Chinese, and some Irish, which I find the most difficult of all. You can find me on duolingo. I’ve started an effort to help English speakers to learn French.
  • Cultures and Geography. Learning other languages is opening doors to other cultures. So I love to learn about different cultures all around the world.
  • History. Knowing a culture (including the one that came to me at birth) needs some knowledge about history. I love to learn about the history of the world.
  • Genealogy. Knowing your history comes with the search for your roots. I have worked on my genealogy tree, it goes back to the 18th century in many branches, and one branch goes as far as the 15th century.
  • Music. Cultures and history are filled with music. I love music, especially classical European music, but also folk music from all over the world, Ireland and Scotland, Flamenco (¡Olé!), Indian Ragas, South American music, Chinese Traditional (Guzheng and Ehru), and many more. As an amateur pianist I play mostly music from the Classical and Romantic eras but as a harpsichordist I focus on Baroque music. I do have recordings on the Internet, ask me where to find them! I’ve also recently started composing. I also know how to play a number of other instruments but I don’t practice much.
  • Movies. My wife and I watch a lot of movies. We don’t watch TV, but we do sometimes watch a couple of selected TV series. It’s always interesting to see how stories are designed.
  • Reading. Of course, I also read books, both fiction and non-fiction. I’ll probably post here some summaries of my readings along with my impressions.
  • This leads to a long lasting passion: writing. Actually I don’t understand why I didn’t start this blog earlier. I have written several (unpublished) novels during my teenage years and more in my 20’s, which I’m currently publishing on Wattpad (under a pen name). I have gone back recently to writing and am a published author (also under a pen name).
  • Rubik’s Cube. I have a strange history with this thing. 🙂 I’ll write about it later.
  • Psychology. I’m not a psychologist, but I’ve been learning a lot about it from my wife. It’s a fascinating subject.
  • Health. I’m definitely not a doctor, but I also gained quite some knowledge from my wife in that area.  Pesticides and GMOs vs Permaculture is something I know quite a lot about, even though I can’t call myself a specialist. I have a feeling that these subjects will be at the heart of public debate in the years or decades to come.
  • Ecology. We have to take care of our planet. If not for the planet itself, at least for the sake of our species. I try to reduce my environmental impact as much as I can, but I’m no extremist either.
  • This brings me to one of my life’s motto : extremes are always bad, whatever they are. It is never black and white. It’s not gray either. It’s a rainbow.
  • Self Improvement. Although there is a common hoax that tells us that when we’re past our 20’s we start decaying (I’m exaggerating a little, but not that much), I believe we can always improve ourselves. This comes with a deep understanding of who we currently are, and that life is always changing. Accepting change and embracing change is at the core of my life. This is why I like meditation and the Buddhist philosophy. I also use tools to enhance my memory. Back in the 1990’s, I invented for myself a spaced-repetition learning program to learn vocabulary in other languages, although I had no idea that it was actually called a spaced-repetition learning program! Then Anki appeared and I’ve been using it since then. I strongly believe that tools like Anki and others such as the Loki Memory Palace (to memorize series of words) or the Major System (to memorize numbers) should be taught in school at an early age. As an advanced species, we should also get rid of the “Qwerty” keyboard (or “Azerty” in France), especially on touch screen devices, I’ll write an article about this.
  • Teaching. Sharing my knowledge with others has always been a passion. In my University years, I spent a lot of time teaching to children who had problems in school. I was also a teacher during my PhD. This blog is definitely about sharing knowledge with you.
  • Many more subjects that I would like to develop. I have found out that every subject becomes more and more interesting as soon as you learn more about it. Even football teams or cars can get interesting, but I still try to keep some priorities and those are not in my list. 🙂

As you can understand, my main problem in life is that days only have 24 hours and I get to do only what I can do within that limited time frame. 🙂

Finally, you can find me on Diaspora, Mastodon, LinkedIn, Facebook and Twitter but I’m rarely active there.

Enjoy!