Goia v2.2 : modification of the tournament rules

As was suggested by Oliver Lewis, I changed the rule of the game to the following :
- The games are played until the end, with only superko forbiding infinite loop (I have implemented the eye rule but I chose not to use it for now, because I feel detecting eyes is a good starting point at training players, thus I'd rather have it not given a priori).
- The rule to score the game is the Tromp-Taylor rule : every stone present on the board at the end of the board are considered alive, and chinese scoring is used.

GnuGoia.2.2 9x9 for Windows
GnuGoia.2.2 9x9 for Linux

Linux Release

I could finally figure out how to compile the program for Linux. I am releasing the Linux binaries as well as the source code, which should compile with the ./configure; make command.

The instructions for running the tournament and playing versus any goia player are in the README_GOIA file :

• To play the tournament, run "/MyFolder/gnugo --goia-tournament --komi 6.5"
• To play versus goia, run "./gnugo --goia-white PlayerFilePath.gop"

Since Gnugo supports GTP, you can also use it to play with advanced GUI, such as GoGui. The command line you have to provide to GoGui would be "./gnugo --mode gtp --goia-white myplayer.gop"

Goia v2.1 source code.

Goia v2.1 binaries for Linux.

goia v2.1

Here is goia v2.1, with different information displayed that should make following the tournaments more enjoyable. 

I also added an argument when launching the tournament allowing to chose the numbers of players involved in your tournament.

This will permit to change the memory used by the program, which was starting to become quite huge, and could be a problem with 100-players tournaments. See Readme file for instructions.

Goia 9x9 for Windows v2.1

Release of goia v2, progress of the players

I have finished moving goia to the gnugo engine. It is now working fine, and, although it is much slower than the old version, it seems to be also far more efficient : the bunch of players I evolved on my computer during the last week is already far better than the players that were evolved with the old version in the same period. The differenc lie in the way game is scored : GnuGo provides a far more reliable way to assess game situation, were OpenGo only counted stones and territory without trying to figure out living and dead stones (every stone being regarded as "living").

As an example, here is what happens when the last Goia-GnuGo (white) plays against the last Goia-OpenGo :

For what I could figure out seeing the two play against each other, it rather makes sense : Goia 1 as ended up trying mainly a simple strategy consisting in playing diagonals, which is the most efficient way to obtain territory easily. Now that big chunk of territory can be assigned to the players if they manage to get it (as it is the case in the game shown), Goia2 tries to do this also, mainly here by drawing a vertical line in the middle of the board to clain one half of the board.

This seems pretty encouraging to me, although of course there is much progress to be done. My first serious opponent I am using as a benchmark to test real go playing skills of my players is Joshua, my 5 years old son. He learned the rules of go 3 months ago, and doesn't play very often. No need to say he is objectively pretty bad at the game. Still, he beat Goia2 with ease (he was playing black here) : 

So, here is the new Goia v2 :

Goia 9x9 for Windows v2.0

I will release very soon a slightly modified version that provides more relevant information in the console.

Also, I still have much difficulties to compile this for Linux, so I am begging for anyone who could use some time trying to help me figure out how I could achive this. I have submitted the whole source code here : http://code.google.com/p/goia/source/browse/#svn/trunk

version 1.17

While testing the future version using GnuGo as a base program to handle the game, I could unveil a major bug in the way games were handled up now. During the transcription of the board, the program would set the value of any given intersection to the same number regardless of the color played. This would lead to the same decision fo black and white players, which is obviously generally wrong. Here is the new version cerrecting this : 

Goia 9x9 1.17 for Windows

Goia for GnuGO

I have tweaked GnuGo to allow it to run goia players. It is only working on windows for the moment, I will first find a way to use it for the tournaments, and then adapt it to linux.

Here is the program, see attached readme for information about what has been added: 

GnuGo for goia

For more informations about GnuGo, see the main website: GnuGo Documentation

Version 1.16

This version changes the description of the players, so this update is mandatory. 

I have changed the way neural input are described in the program, from std::vector<> to std::map<>. It allows to remove unused inputs without corrupting the network. This was necessary because much of the disk space occupied by the players was unused inputs. A couple of mutation bugs have been corrected also.

Goia 9X9 1.16 for Windows

GUI for playing against Goia 1.16

I am almost done making goia compatible with GnuGo. This weekend I should release a gnugo/goia version, I will do my best to release a linux version also.

Another major bug fix

/edit : another bug corrected, prevent another kind of crash, v1.14.4

Correcting the previous bug, I saw another one, leading to some weird scoring, ergo probably making the selection not very relevant.

I beg you to keep silent to my boss about the reliability of my release, and please use now this version :

Goia 9x9 1.14.4 for Windows

Version 1.14 : putting an end to the hyper-inflation

/edit : upgraded to 1.14.1 due to a major bug introduced in the previous release...

As you may have seen this week, the overall population has grown to a point where it became very slow. It would be ok if the increasing size came with an increased complexity of the players, but it was not the case. What happened was that, to strengthen some connections, the neural network made additionnal connections between neurons instead of increasing the weigth of the existing connection. It led to a neural network where connections where duplicated up to 10 000 times. I think it happened on the 9x9 program because of the limited number of neurons and goban input, which makes duplicating connections more easy. I have added a cleaning function to the program, removing those extra connections and replacing them with one strong connection.

It works far better now, at least on my computers.

I won't be able to deliver a linux version though, I tried to make some cleaning in my project I can't get it back to a working version. I am currently working on adapting the whole thing to GTP, using GnuGo functions for go rules enforcement and scoring. It will be far easier to maintain when it will work, and will bring many interesting functionalities.

However, for the moment, here is what I suggest :

• for windows users, download the new program and run it as usual : Goia 9x9 1.14.1 for Windows.
• for linux users, probably the most effective way of running the program will be to erase every players on your local drive, and continue running 1.13. As long as there is enough windows client running in parallel, the players will be cleaned regularly and there should not be the same kind of inflation as we saw last week. I hope I will be able to realease a GTP version in two weeks from now, and this one will be rather easy to compile for linux.

GOIA opens

This quick note to say I published the source of the program on google code. Anyone is welcome to help, share and give his opinion about the design. In advance, sorry to anyone bold enough to take a peek : it is not very good programming, and to top it all, it is written in french.

http://code.google.com/p/goia/

Playing against GOIA

Here is some instruction and download material to help you set up a game against one of your favorite players. It only works on windows currently, and one might find it cumbersome, thats yet another feature to improve.

Here is the way for the moment :

1. Download and unzip the opengo binary client.
2. Copy the player you want to play against in your c:\ drive as "c:\joueur.gop" (that's the cumbersome part).
3. Launch opengo.exe.
4. Create a new game, chosing "person" as white or black and GOIA or GOIA9 as the other player, with a board size respectively 19x19 or 9x9. The player you put in your disk must match the kind of game played.

Unfortunately, opengo has some bug left, and any configuration involving 2 artificial players don't work, so you won't be able to watch GOIA play against himself, or WALLY, or any other computer.

Version 1.13

The release of the 9x9 version was the occasion to reveal a couple of bugs. One of them was a major bug causing the program to crash or the player to become corrupted when deleting a gene composed of more than one neuron. This is the reason why the players evolved in the 19x19 version are made with 1 neuron genes. I was thinking it was for some obscure performance reason.

So here it is, version 1.13 with a few bugs fixed, should be far more stable especially concerning the 9x9 version :

(/edit : corrected link to 9x9 for windows)

GOIA for Windows, 19x19
GOIA for Windows, 9x9

GOIA for Linux, 19x19
GOIA for Linux, 9x9

9x9 version

As I have been told, go is hard enough that I should not start by trying to train a good 19x19 go player. This is undoubtedly wise, and very probably true. Whereas I still think that in an evolutionary approach, evolution is not linear thus evolution time does not grow exponentially with size, it can only be faster on a 9x9 board compared to 19x19 board. And I really don't have much to lose in the process of starting anew with 9x9 players.

So, here you are with the new goia program for 9x9 boards :

GOIA9x9.1.12 for Windows
GOIA9x9.1.12 for Ubuntu-Linux

Note that this version should not be installed in the same folder as the 19x19 one since players have the same name on the local drive. Hope this will save everyone some valuable memory too.

Version 1.12 available

Here is the new version of the program :

------------------------------------------------
v1.12
Changed : neuron inputs are now removed if no longer used and if their removal doesnt affect overall coherence of the neural network
Changed : endgame score is now used to sort player with the same number of victories in the tournament
Bug fix : only players 0 to 29 are now used on the distant server.

GOIA 1.12 for windows
GOIA 1.12 for Ubuntu-LINUX

Progress so far

The program has been running for about two months on various computers. Despite the numerous updates, the process involved has stayed quite the same across all versions. I will try to keep track of the advance of my players every two weeks from now, starting today. Each time I will dowload the players on the server, put them in "ThePit" with some of the past winners, and see who finishes first after a few generations (ThePit is a closed ecosystem where player mutate but dont travel). I will then examinate the winner. The evolution is followed using three criterions :

• Genealogy : Each player keeps track of every places he has been through and how long he has stayed in each place. This gives an indication about how old any given player is, although there is no guarantee that this is directly linked to its ability to play go. It is also a good way of letting everyone know wether their work has been useful or not.
• Size : The size of each player tends naturally to shrink since every mutation is skewed toward the disappearance of neurons versus creation of new ones. Beside, whereas this is meant to change soon, until now ties in tournament points were discriminated considering the size on disk to reflect the cost of having a big neural network. Increasing size is consequently a sign that positive mutation occured.
• Actual play : I play regularly against the winner of the final tournament. For the moment, I play by myself, I have never had any difficulty so far to beat the players, I rather try to see how the player is trying to win. There will soon be a way to let it play against other computer programs using Go Text Protocol. I will try to let you know about any interesting features the players are showing up.

And the winner is...

Weigth : 2.112 ko

Age : 710 generations

Welcome to Madison, and thanks to StIsmier/BuenosAires who made a great start only one week ago. If you wonder, the "." are linux players who start the program from the folder where it is situated using the command "./goia_ecosysteme.1.11.1". 

As for go skill ability, they are close to zero thus far, whereas not zero since it consistently beats random. It manages to make a few eyes and don't play in them. It seems at first glance weaker than the players from a few weeks ago. Interestingly, it plays lines, I can't figure why... Here is a game exemple, I am playing black and GOIA is playing white :

Version 1.11.1 for Linux

Here is the last version for linux. For some reason, it crashes at the end of the first and/or second tournament, I couldn't reproduce the crash in debug mode. It works fine after that though...

Goia 1.11.1 for Ubuntu-Linux

Version 1.11 for windows

------------------------------------------------

v1.11.1

Changed : notation mode, was 3pts per victory. Now, takes into account the score difference at the end of the game. reverted back in 1.11.1

Changed : mutation probability skewed in favor of diminishing the size of the player (on average).

Bug fix : added some exception handling in the mutation process to prevent the program from crashing.

Bug fix : don't crash anymore on the first launch.

Changed : added komi rule of 6.5.

Goia 1.11.1 for Windows

New version available

A new version is available, and can be downloaded here :

GOIA for Windows

GOIA for Linux

Changelog :

------------------------------------------------

v 1.9

changed : metamutation coefficient set at 0.002 (was: 0.05).

changed : duplication/deletion probability of any gene set at 1/2000 (was: 1/32000)

changed : Tournament result display changed, only display the winner ID with it's history and it's species.

changed : transfer method with the ftp server, only one player travel to and from the server for each tournament.

------------------------------------------------

v 1.10

bug fix : Player's memory (=input values for each neuron) is emptied before each game. Used to be emptied only when the player was loaded from the disk.

changed : players are randomly created when not present on disk.

changed : players are replaced by a random new player when error occur while loading the file. Prevents the program from crashing when downloading corrupted files.

Details about the way it works

Here are some detailled information about the realisation of this project. The program has been developped using Visual C++ Express, and I can share source code with anyone interested.

Description of a player. 

Every player consists of :

• A 19x19 array of vector of input neural adresses, telling where each value of each case on the board goes. Every case goes to at least one neural input.
• A 19x19 array of output neural adress, telling from where information should be retrived do decide the move of the player.
• A Neural network processing the input information and providing a value for each case of the goban. The higher value decides the chosen move.

Description of the neural network.

The neural network consists in a map of genes ; each gene is a map of neurones. Each neurone is conceived as a classical artificial neuron and is defined by :

• It's type : linear, sigmoid, fully linear or piecwise linear.
• Two parameters defining its transfer function : threshold and global weight.
• A vector of output adresses telling where the inputs are connected. 
• An associated vector of weights defining the weight of each input.
• A vector of input adresses telling where the output of the neuron goes.
• A mutation probability for every one of these values, ranging from 1/10 to 1/32000.
• A species tag.
• An historical log telling where the player's ascendants have been.

The Tournament

The tournament is organized as follow : each player 0-49 plays against a randomly chosen player 50-99, playing black twice and white twice. A win earns 3 points, a tie earns 1 point and a loss 0 points. By the end of the tournaments, players are sorted , players with as many points are sorted according to their file size.

The 50 highest ranked survive, and the other are killed.

Reproduction

Players who are in the top half of the population get the right to reproduce. Every one of them follow this procedure .

• First, they try to mate with another winner : they search the population for another member with the same species tag. If found, the achive sexual reproduction twice. Sexual reproduction consists in swapping random genes from the two reproductors. Generally, the results is a non valid neural networks. When its the case, the reproducing player is chosen a new species tag and proceeds as if it had not found a suitable partner. 
• If sexual reproduction failed, a simple cloning is achieved.

Mutation

After reproduction is achieved, every player suffers a random mutation :

• Every neural properties can randomly mutate.
• Every adresses can mutate.
• Genes can split, merge, grow, shrink, duplicate or disappear.
• Every mutation probability can mutate, according to a driving metamutation probability factor arbitrarilly set at 0.002 for the moment.

Journey

By the end of every tournament, some genetic mixing is assured with the other ecosystems through the transfer of players via a web hosted ftp server.

• The hishest ranked in the tournament is sent to the ftp server, and assigned a new number ther from 0 to 29. 
  
• One of the 30 players available on the ftp server is randomly chosen and replaces one of the 100 players in the local ecosystem.

GOIA : How to participate

This message is meant to explain how anyone can try to help me evolve an artificial go player. I will explain in details later how the program works, and how the players are defined. All you need to know to participate is the following :

- The program consists in a never-ending tournament, featuring 100 players.

- Each player is represented on the computer with a file named "joueur0.gop" to "joueur99.gop" (joueur is french for player).

- At the end of each tournament, the 50 losers are erased, and the 50 winners reproduce and mutate, making a whole new ecosystem. Then, migration occurs in which 2 players are automatically sent on a ftp server, and 2 players are retrieved from it. Thus, positive innovation can propagate thoughough every ecosystem .

It takes about 10 minutes to complete a generation with 100 players on a reasonnable modern computer. No parallelization is implemented yet, so if you wish to use avery core you have available, you have to run as many instances of the program .

To download the program, go there and dowload either archive :

• GOIA for Windows
• GOIA for Linux
• Unzip in the folder of your choice, provided it doesn't contain any space. 
  

• If you are running under windows XP, you might need to install the microsoft visual c++ redistributable package. Then execute goia_ecosysteme.1.10.exe.
• If you are using linux, execute goia_ecosysteme.1.10 from your console.

Then, learn french if needed, and enjoy !

GOIA : What for ?

Welcome on my blog. Before I enter the real subject, let me introduce myself and the reasons I created this blog.

My name is Ernest Galbrun. I was once a physicist, I graduated as a doctor es fluid mecanics a few months ago. Science is my passion, but I officially turned my back on scientific research, and I am now project leader in optic engineering, doing mostly computer programs and elctronic devices.

The present project has stemed from various readings, especially from the Dawkins-Dennett team, among other great contemporary and past thinkers. I, like many others before, have been wondering for long how we could use the principle of evolution through natural selection to create something bigger than ourselves. There have been many succesful attempts in the past to use this principle in order to show that interesting properties can emerge from a simple set of rules carefully chosen. So far, though, only minor practical goals have been achieved with this methods, goals that can rather easily be achieved with clever design.

My intent is not to prove that natural selection is a powerful tool. That has been done already. I want to use that tool and beat every Intelligent Designer who tried before on a task where they are clearly better than I am. So I have chosen to try evolvin AI playing one of the most difficult game for computers to play, which is go game. I think go is the battlefield of choice for such an experiment, because of its combined properties of being utterly simple to play and very difficult to play well. At least for us poor human beings.

I will use this blog to describe the evolution of my artificial go players, and to explain the work I have done. Every one is invited to participate if they wish to share some of their computer power evolving a small population, and of course if they would like to help me improve my program.