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

[Tristan Cazenave]

Arend Bayer a écrit :
> 
> > > - Iterative deepening:
> >
> > this is not so hard to implement, you just have to iterate over the
> > depth
> > limit.
> So how would the results of the previous search get used? Via the results
> cache? I think that would at least require the reading functions to be able
> to return s.th. like UNKNOWN instead of WIN or LOOSE if the depth limit
> is reached before a definite result is known.
> 
> > >
> > > - Transposition table:
> > > This means result caching.
> >
> > and reusing the transposition move to maximise alpha beta cuts.
> Can you explain what you mean by that?
> 

Transposition tables (TT) work with iterative deepening, the possible
values
in tactical Go are Lost=-Infinity, Unknown=0 and Won=+Infinity. (plus
some
values for Ko if you want handle kos).
When the depth limit is reached and the siutation is unclear (for
example
two liberties for the string to capture), the evaluation is Unknown.
In the TT, you store for each node, the evaluation of the node, and
the move that made the cut if any (the best move for this node).
When you get back to this node in the next deeper search, you try the
stored move first, as this is probably the best.

> >
> > > - Null move heuristic:
> > > This idea seems very weird and, given its proven succes, quite cool.
> > > 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.
> 
> That really surprises me. Do you pass as attacker or defender or both?
> I would have guessed that if you play an arbitrary move (that is not a
> self-atari or s.th. like that) would still be better than a pass, so that
> there would be no gain (whereas in chess, any move needs to carefully avoid
> direct threats/forks/...). This reasoning looks so convincing to me that
> I would very much like to understand why I am wrong.
> 

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.

> >
> > quiescence search is already done in tactical settings, the most simple
> > one is hte reading of ladders...
> Ah, yes, thats a way to look at it.
> 
> Arend
> 
> _______________________________________________
> gnugo-devel mailing list
> address@hidden
> http://mail.gnu.org/mailman/listinfo/gnugo-devel