Author: Ernst A. Heinz
Date: 05:37:17 09/30/98
Go up one level in this thread
On September 30, 1998 at 00:39:30, Don Dailey wrote:
>
> [...]
>
>My program actually does a null move search with a zero width window
>around beta, so I don't actually get to raise alpha. In lots of testing
>I did this was more efficient, I don't know if anyone else has tried
>this or finds it useful.
Yes, I think most everybody does the null-move search with a zero window ...
>The code is something like this:
>
> 1. make update move
>
> 2. repetition testing
>
> 3. check hash table and return if possible
>
> 4. NULL MOVE TEST
>
> 5. try first move serially
>
> 6. spawn rest of sibling moves.
>
> 7. return best move found
Let me quote from my article about "How DarkThought Plays Chess" as published
in the ICCA Journal Vol. 20(3) and available electronically from our WWW page
at URL <http://wwwipd.ira.uka.de/Tichy/DarkThought/>.
******************************************************************************
Node Expansion
DARKTHOUGHT implements a standard node-expansion procedure whose structure
probably
does not differ much from that of other chess programs. It executes the
following successive steps
as suggested by several authors and excellently summarized in [62,64].
Extension decisions related to incoming move (U),
internal iterative deepening (U),
transposition-table lookup (L/U),
interior-node recognizer decision (L/U),
endgame database lookup (L/U),
null-move search with deep extension decision (U),
single-reply extension decision (U),
futility pruning decision (F/L),
static evaluation (F/L),
search of all outgoing moves (L/U).
The letters in parantheses behind each step explain where in the search tree it
is actually applied:
F means ``frontier'' (depth = 1), L ``lower part'' (depth <= 0), and U ``upper
part'' (depth >= 1)
where depth denotes ply distance from the quiescence horizon. The last node
expansion step
achieves good move ordering by arranging the sequence of recursive search calls
as listed below.
1. Hashed move from transposition table (L/U),
2. capture moves in MVV/LVA order (L/U),
3. killer moves (U),
4. history moves (U),
5. statically pre-sorted remaining moves (U).
This ordering scheme enjoys wide-spread use in computer chess because it
represents the best
currently known according to many independent researchers. An unintended yet
nice side effect
thereof is that it also saves precious memory bandwidth because it does not
require the creation of
a move list prior to history-move selection.
In contrast to most other chess programs, DARKTHOUGHT uses a single
node-expansion routine
to handle both full-width and quiescence-search nodes. Because of better code
reuse (see above
lists of steps), a single node expansion routine can be made smaller than two
separate ones and it
is much easier to reconfigure. The complexity of the implementation, however,
increases
considerably as compared to the solution with two separate routines.
*******************************************************************************
=Ernst=
This page took 0 seconds to execute
Last modified: Thu, 15 Apr 21 08:11:13 -0700
Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.