[computer-go] Tactics statistics part 2

[Mark Boon]

I got a few more numbers in. The results surprised me, so this was a  
useful excercise.

As I wrote in a previous post I found that on average there are on  
average 2.3 one-liberty chains on the board at any give point in the  
game, and 7.7 two-liberty chains. The tactical module spends on  
average 4.5 move reading these, so that means 45 tactical moves per  
position. That would limit the maximum number of positions I could  
'evaluate' to a little over 30K pos. per sec. And that only involves  
tactics, so this way it's never going to be close to 10K pos. per  
sec. for full evaluation.

Previously I used a bit of a heuristic approach to determining which  
ladders needed to be read again after each move. This cut down the  
amount of tactical search considerably, but I don't remember exactly  
by how much. It had the drawback that it didn't detect ladder- 
breakers a little further away. I didn't mind as 'lookahead' is  
usually local in nature anyway, so I did't care much if a ladder on  
the other side of the board gets broken. After each real move I  
simply re-read all tactical problems once to catch ladders broken  
remotely.

Since I have decided to try to stay away from heuristics as much as  
possible, I implemented a simple method of marking the area of a  
ladder while its reading. I think others have done something  
simliarly with bitmaps. And then try to compare it with reading all  
tactical problems after each move without trying to be clever. I also  
verify that in both cases I get the same results.

I used a collection of 38K games with exactly 8 million moves in it.  
(I had to clean out some junk from the original 40K games). Running  
this with the first straightforward version that reads all ladders I  
get the following numbers:

8 million positions
362 million tactical moves
375 seconds eval time (hmmm... just under 1 million moves/sec. or  
half the speed I'm used to)

Next I tested the version that keeps a map of affected area with each  
tactical situation. For each position it only reads those tactical  
situations that it thinks need to be updated.

8 million positions
63.5 million tactical moves
98 seconds eval time.

So the number of tactical moves it reads per second drops by a third.  
This is due to the overhead created by tracking the dirty maps and  
the checking process. But the number of tactical moves required per  
position dropped from 45 to 8. I still have to see if I can find out  
why the number of moves/sec. dropped so much in the first example  
compared to the number I'm used to seeing in smaller test-sets.

So what I thought previously, that it would be (almost) just as fast  
to re-read all ladders in every position turned out to be false. This  
is contrary to a result I remember getting many years ago, but I must  
admit that this time I paid a bit closer attention to making it  
efficient.

I think this is useful information. I may store in in my project- 
pages somewhere.

	Mark Boon