Re: [gnugo-devel] possible reading.c speedups

[Tristan Cazenave]

> - Iterative deepening:
> This means the following: The search algorithm is called repeatedly with
> increased search depth until the default depth is reached (or a time limit
> or similar exceeded). Due to the exponential growth, the additional cost
> is not big, and the results of the previous search can be used for the
> improved move ordering. I think that this idea could prove very useful if
> the reading functions would return not just WIN or LOOSE but the
> number of liberties during the "test searches". This takes some effort to
> implement, however.

this is not so hard to implement, you just have to iterate over the
depth
limit.

> 
> - Transposition table:
> This means result caching.

and reusing the transposition move to maximise alpha beta cuts. It works
hand in hand with iterative deepening.

> - Null move heuristic:
> This idea seems very weird and, given its proven succes, quite cool.
> (Try a pass first; if the position you obtain that way is good enough,
> you assume that there will be a move that gets an even better result and
> you save the effort of trying which one this might be.)
> However, this is certainly not useful in go.

I think it can be very useful in Go.
You can view Abstract Proof Search and Lambda Search as a generalization
of the null move pruning, even if they have something more to select
interesting moves... In my experiments, Null move pruning makes my
capture algorithm faster, and it is quite easy to implement.

> 
> - Quiescense search, selective extension, interior-node recognizers:
> I don't think these apply to the reading code. These should be left for
> a global alpha-beta reader once GNU Go is dan level :-)
> 

quiescence search is already done in tactical settings, the most simple
one is hte reading of ladders...

> - futility pruning:
> This summarizes, if I understood correctly, a couple of heuristics to
> cut the search one or two levels below the set search depth, if the
> position is egregiously good or bad.
> The variety of search depth limits used in GNU Go seems to be s.th.
> analogous.
> 
> Some of these techniques should be applicable to owl as well, where
> they might enable us to increase the maximal number of moves tried.
>