Evolution of a Go program

About the development of Moyo Go Studio, software to (help) play the Oriental game of Go. Go is a two-player zero-sum game of perfect information. It is considered much harder than Chess. Currently, in spite of enormous effort expended, no computer program plays it above the level of a beginner.

Saturday, January 07, 2006

Evolvable Domain Knowledge

Some regulars at rec.games.go think I am a stark raving, barking mad insane lunatic nutcase.

Because when I said I was going to focus on a "genetical" approach to comp. Go, one of its residents said that it was (I paraphrase) "a bad idea to try to evolve a flower, because a flower does not play Go well". It sounded as if he thought Darwin was crazy too.

This comes from someone who says he used to be paid for trying to write a Go program, and he failed. Now he likes to tell folks that making a strong Go program is "impossible".

I checked out some GA pages, and what I found strengthened my resolve: Several recently patented inventions (antennæ, methods of solving equations, digital and analog circuits etc.) have been SURPASSED by GA's, in relatively short amounts of running time. Even better: those GA's are being optimized with a factor 100 as we speak, while Moore's Law keeps on going (we'll see massively parallel computing being mainstream in about ten years).

When I explained our dear friend on rec.games.go that I obviously did not intend to test fitness on flowers but would steer evolution towards correctly solving Go problems or finding Pro moves, he said (I paraphrase) "AHA! Now you're more sensible!".

According to him and others, genetic evolution of a Go program would take "longer than the age of the universe", yada, yada and more of the usual "armchair expert" opinions.

As if I would start with 1 + 1 = 2 and try to let it evolve into a Go program..

Why would I do that? Of course, I would START with the cream of the crop of existing domain knowledge, like a good area estimator, an efficient search algorithm, some fast string property pattern matching code, my own 37 million pattern library, etc. String it together with evolvable weighing factors and make this domain knowledge evolvable. That is the secret to evolving a strong Go program. You have to and tell it how to approximately find the important stuff first. The GA does the rest. The task of the programmer is to find the important domain knowledge and encode this in an "evolvable" way. This code needs to be able to execute very fast, so good coding skills are required otherwise it will indeed take a long time. Optimization techniques will be crucial.

So, instead of endlessly tweaking a carefully weighed hierarchy of elaborate domain knowledge algorithms, you roughly code them up and haphazzardly string them together, but you spend extraordinary attention, effort and time on the efficient evolvability of those modules. It it totally unimportant to get things properly implemented, the only thing that counts is that they are able to evolve towards a good enough solution.