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

[Gunnar Farneback]

Arend wrote:
> I wondered which search engine algorithms from chess programs might be
> adaptable to the reading code in GNU Go. I browsed a little through the
> web, and here is a sample of what I found with comments.

Interesting reading, thanks.

> - Dynamic move ordering: killer/history heuristic.
> Killer heuristic means trying obvious captures etc. first to try to refute
> a variation. I think the algorithm used in GNU Go is already fairly
> sophisticated. However, a history heuristic (i.e. applying moves first that
> have been successful in other positions in the same search tree) might
> be worth experimenting with. This might be easy to implement.

I made a crude experiment with history heuristic once but without any
measurable success. Might have been because the implementation was too
bad.

> Some of these techniques should be applicable to owl as well, where
> they might enable us to increase the maximal number of moves tried.

I don't think you mean what you're saying here. More sophisticated
move selection should reduce the *number of moves* that can be tried
within a given amount of time, since each move takes more time to
generate. What it increases is rather the size of the tree which is
analyzed.

Tristan wrote:
> 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.

I don't think our read result caches would work well at all with
iterative deepening.

> Null move is making the opponent pass (that is playing its worst
> possible move) to see if the attack can succeed even when the
> opponent plays this bad pass move. If the attack cannot succeed even
> when the opponent pass, it is very unlikely to succeed when the
> opponent plays a good move. So you can cut. The reasoning is
> symmetric, so you can prune both for the attacker and for the
> defender. The trick is that you only search a small tree after the
> null move instead of the full tree, so it saves time.

Even so, I doubt this would be effective in GNU Go's tactical reading.

/Gunnar