[computer-go] Rotate the dog or the tail?

[Mark Boon]

I've been off-line for quite a bit longer than I liked, so this may  
come a bit late. I haven't been able to catch up with all the  
messages yet. My intention to start working on computer-Go has had a  
bit of a false start due to housing problems. But we have a house  
now, and a wonderful one at that, so I hope I'll be able to  
contribute again soon. Still a lot to do around the house, one of  
them getting a satellite dish for internet, so I'm not making any  
predictions this time about when that will be.

Maybe I can clarify my pattern-matcher experiences. I used the 243- 
bin approach in the original Goliath. It actually rarely happens that  
a useful pattern has more than one don't cares among the five center  
points. So I didn't mind having 9 patterns for those few. A single  
don't care happened a lot because of patterns starting on the 1st  
line, so those were always stored three times. Still those were a  
minority.

Indeed I used 8 boards with the stone information and I did the  
matching 8 times for each pattern. This was explained in the Computer  
Go article, storing the board information 8 times is cheaper than  
storing the patterns 8 times.

In my later pattern-matcher, a Java version of which can be found in  
my library that is available on SourceForge, I use a 4-way decision  
tree. I found that the performance of such a pattern-matcher comes  
close to my original one and it provides more flexibility in the  
patterns stored.

In the latter I also don't store the patterns 8 times, just the one  
single time. But the decision-tree is built with the 8 orientations  
in it. This makes finding the patterns faster in one iteration  
instead of eight. This doesn't increase memory very much, as the only  
thing that increases in size is the decision-tree. On average it  
takes about one node per pattern stored. Still it takes a bit more  
memory than the original approach in Goliath, but for computers  
nowadays memory doesn't come at such a premium as at the time.

Hopes this helps the discussion. And I hope to be able to post more  
soon.

Mark Boon