Computer Chess Club Archives




Subject: Re: Detecting Draws using a Small Hash Table?

Author: Robert Hyatt

Date: 08:23:55 02/20/02

Go up one level in this thread

On February 20, 2002 at 08:25:54, Steve Maughan wrote:

>The draw detection in Monarch uses a small hash table (65535 entries) to store
>the path since a pawn move or capture.  When the search finds the current
>position in the table it returns a draw score; if it's not found it store the
>hash signiture carries on searching all the child positions and when complete
>resets the hash entry to zero on exit.  This type of approach is outlined on
>Bruce Moreland's excellent web page.  It seems to work well and detects draw
>quite nicely.  However, I have been sent a game where Monarch allows a
>repetition when it is clearly winning.  Having looked at the position, Monarch
>sees the draw then 'loses' it.  Clearly this is unacceptable.  The problem crops
>up when the draw is based upon positions already played in the game.  Monarch
>usually sees the draw but since (many) other positions are also searched there
>is a high likelihood that these historic board positions will be overwritten
>with other search positions - hence Monarch loses the draw.
>Has anyone else had the same problem?  Any obvious solutions?

These "hash entries" are critical.  You can not overwrite an "active" one,
which is probably what is going on in your case.  You _must_ find a way to
handle the collision on table entry addresses, otherwise it just doesn't work.
With 64K entries, and the longest possible path being 100 moves due to the 50
move rule, this should not be a problem if done correctly.

>My current thoughts are to only store the position in the table if the hash
>entry is currently blank; and to only set it to blank if the stored hash is the
>same as the current position.  This still allows for the possibility of not
>detecting draws deeper in the tree but I guess the risk is greatly reduced.
>Any thoughts appreciated!
>Steve Maughan
>PS I used 0.5 Mb for this table any it doesn't seem to matter if I increase this
>to 4 MB.  Is this sufficient?

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.