[computer-go] Caching of local search in NeuroGo?

[Chrilly]

----- Original Message ----- 
From: "Markus Enzenberger" <compgo at markus-enzenberger.de>
To: <computer-go at computer-go.org>
Sent: Wednesday, August 09, 2006 2:37 AM
Subject: Re: [computer-go] Caching of local search in NeuroGo?


> On Tuesday 08 August 2006 12:08, Chrilly wrote:
>> I would also prefer a discussion about caching of local search in 
>> NeuroGo.
>> Up to my knowledge NeuroGo is also one of the few conventional searchers 
>> in
>> Computer-Go. Would be interesting to hear about it.
>
> there is not much I can contribute. The only local searches NeuroGo does 
> for
> its input features are ladders, which are not worth caching, because they 
> are
> fast and have a branching factor of close to 1. The search, that NeuroGo 
> does
> using the neural network as an evaluation function, is a global search.
>
> - Markus
> _______
Suzie searches at the moment also only ladders. But somewhat generalized, 
there can be a branching. The criterion is that the prey has 2 liberties if 
the attacker is to move. In a classical ladder there is one liberty which - 
if the prey would move there - the prey would get more than 2 libs. So there 
is no branching. But on 19x19 even under this restriction one gets a 
considerable amount of moves. Additionally I have a fast recognition which 
does not make the moves, but tries to decide statically if the prey dies or 
lives. Only if this fast recognition returns unknown (e.g. the 
ladder-breaker has only 2 libs or is near the edge of -the board) the full 
ladder is run. But even with this restrictions the ladder routine generates 
10-20 nodes per evaluation. The ladder code runs at about 1.5 MegaPos/sec on 
a 3 GHz Pentum. So the ladder code alone reduces the speed of the eval to 
75-150 KNodes. A more evolved local search which handles also 3-Liberty 
problems would make things worse.
Currently Suzie makes 20KNodes/sec. This is very far away from my initial 
goal of 100KNodes and already quite close to the 10KNodes mentioned by Mark 
Boon some time ago. But there are currently no optimizations like the local 
cache.

I assume in case of a Neural Net the relations are different and the local 
search consumes only a small fraction of the time.

Chrilly