Author: Tord Romstad
Date: 05:02:06 12/27/03
Go up one level in this thread
On December 27, 2003 at 06:53:51, José Carlos wrote:
> Sorry but I don't get the idea. Let's see it with some pseudocode:
>
>/////////////////////////////////////////////////////////
>CheckDraws();
>CheckHashTable();
>TryNullMove();
>
>for all moves
>{
> MakeMove();
> CalculateExtensions();
> Search();
>}
>StoreInHash();
>/////////////////////////////////////////////////////////
>
> That's how I do it. I assume most do like this.
Yes, I think so.
> So I enter the node with depth d, try moves and one of them is a recapture, so
>I search that move with d (instead of d - 1). When I enter the search in that
>node, I do it with d, check that hash table with d and store the result with d.
>So where's the problem? (Sorry if I missed something obvious).
OK, I'll try to explain. In your depth d node, most of the child nodes will be
searched
to depth d-1. The exception is the recapture move, which will be searched to
depth d.
When all moves have been searched, the search result will be stored in the hash
table
with depth d.
This is all fine. The problem appears when an identical node has been searched
to depth
d earlier in the search, but in this previously searched node the same move is
*not* a
recapture. At this node, *all* child nodes were searched to depth d-1, because
there
was no recapture move. Here, too, the search result will be stored with depth
d. When
you later reach the recapture node, you may get a hash table cutoff by using the
search
result from the previously examined node. But this is wrong, because in the
second
node one of the child nodes should have been searched deeper.
Let's make a very concrete (but somewhat artificial) example: A program
analyses the
opening position, and examines the line 1. e4 d5 2. exd5 Nf6 3. d4. The node
after
3. d4 is searched to depth d. Because there are no recapture moves in this
position,
all child nodes are searched to depth d-1. When the search for this node is
finished,
the result is stored in the hash table with depth d.
Later in the search, at the same iteration, the program examines the line 1. d4
d5 2.e4 Nf6
3. exd5. The position is looked up in the hash table, and because it has
previously been
searched with the same search depth, a hash table cutoff may occur. No search
is done.
This is clearly wrong. The search result from the first node is not valid in
the second node,
because in the second node the moves Nxd5 and Qxd5 are recaptures and should be
searched with depth d rather than d-1.
Tord
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.