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.

Wednesday, June 14, 2006

Quick Merging Coordinate Lists

I've been struggling with a fast way to merge coordinate lists that have duplicates between them.

I now have a way that takes literally only a handful of clock cycles per coordinate, on average. As usual I'm not going to tell you how it works, but what's at least as interesting - and useful for you - is how I arrived at the algorithm.

This afternoon I had been dozing off and just as I entered that twilight zone of pre-REM sleep, it just popped into my head. Like my own voice telling me in a short and simple sentence how to merge coordinate lists and filtering duplicates. It's very cool. It does not involve checking in the result list whether a coordinate already occurs in it. That's why it's so fast :)

I am amazed at the human brain. Because I haven't conciously been pondering the problem. I originally coded a solution that took about 15 cycles per coordinate and all I did was occasionally wondering: "Shouldn't there be a faster way?". My subconscious gave me the answer as soon as I gave it a chance.