[computer-go] Tactics statistics part 2

[Łukasz Lew]

Thanks for publicizing this knowledge.
I believe that similar experiments could have been made before,
but the results not made to the public.

Mails like Yours make a real progress, I hope that if we will publish
our best ideas with results the progress in computer Go will be much
faster and we will be able overcome the tradition of competition.

You may say I'm a dreamer, but I'm not the only one :)
So thanks again.
Lukasz



On 9/25/06, Mark Boon <tesujisoftware at gmail.com> wrote:
> 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
>
> _______________________________________________
> computer-go mailing list
> computer-go at computer-go.org
> http://www.computer-go.org/mailman/listinfo/computer-go/
>