Genetic Programming and Go

The idea of evolving programs by analogy with natural selection has been around for a long time. John Holland pioneered genetic algorithms in the 70s. Other forms of genetic programming have arisen since.

There is a description of genetic algorithm with multiple agents here https://www.ittc.ku.edu/research/thesis/documents/todd_blackman_thesis.pdf

Without adding domain knowledge, these are weak methods, and have not so far been successfully applied to go. However, Russell Wallace has devised Lithos and applied it to go. It is fun to watch the programs evolve.

Bisqwit: I once made a tetris-playing bot that analyzed the field and had values for different features of the playing field, like the stack heights, number of windows. It was difficult to adjust those values by hand, so I made a genetic algorithm to automatically adjust those values towards better gaming results. It worked remarkably well.

In computer go, it's difficult to make a good evaluation function for board positions (for deciding what move is the best move). There are many factors affecting the value, and it's not easy to decide how should they be put to balance. I think a genetic algorithm would work here too: It could adjust the balances between different things affecting the evaluation of a board position. Values which result best win/lose ratio are mutated less, and values which result in more losing than winning, are mutated more.

Unfortunately it's difficult to say how efficient the engine is. With go, an opponent is needed. Computer can't measure its own strength by playing against itself. It could however measure its strength by evaluating random positions from pro games and testing how many moves it gets the same way as the pros do.

Note that this is not a magic solution: It does not invent new algorithms. It only finetunes parameters we humans are too lazy (or unskillful) to put the right way. In the case of the tetrisbot though, the finetunes made the bot 100 times stronger than with my initial careful settings.

Bill: I have been having fun with Lithos. Here is the final board of a game between the 2 fittest individual programs out of 100 after 300 generations.

Evolved go  

After a few generations one player discovered a good trick: the diagonal rows one space apart. If you can get away with it, you can score some solid territory. Note that White is trying a greedy mutation. The play stopped early because the players do not know where the stones are on the board and play on top of them, producing passes. Sooner or later some reply to the good trick will emerge. (Note the spoilers in the middle of the board and top right corner.) Meanwhile, it's not a bad strategy against a blind novice -- if you are also a blind novice. ;-)

BTW, the best program consists of only 21 instructions in virtual assembler. ;-)

Phelan: Just found this page through google, and it seems lithos' page is no longer working. I found an archived version, but the program I downloaded doesn't work on XP, or on Dosbox. The zip file with the C code is apparently not working either. Does anyone still have a working version of this?

Bill: I think that Lithos shows that dropping down to a low level language does not give enough of a speed advantage to overcome a lack of domain knowledge. For instance, I never had a program come up with avoiding a play on top of another stone by checking to see if a prospective play was on an occupied point, even though I added checking to see the status of a point as a primitive. If any program had come up with that, however, the mutation would have spread like wildfire, I think.

As I recall, I compiled the C code on ME and ran it on XP in a "DOS" window.

Good luck!

Phelan: Thanks for the quick reply, Bill! I managed to get the zip file working by using a zip file fixer on it. I'm now messing around with it. I will try your suggestion for the new primitive. My objective with this is not to get a world winning Go program, or even a novel approach to a Go AI. :p I've been fascinated by genetic algorithms for some time, and this is an interesting way to learn more about it, and to try some ideas out. :)

Phelan: Just added a GTP mode to lithos.

dkiller: I have an evil plan basing on GTP mode to lithos:

• add an opcode TRY which will just try to play a move and play it only if it's legal
• add to the fitness function the ratio num try / num play (counting last pass)
• make it work with emscripten
• make it work distributed
• making the bot on kgs
• profit