Computer Chess Club Archives


Search

Terms

Messages

Subject: Re: A New Approach to Draw Detection by Move Repetition in Computer Ches

Author: Gerd Isenberg

Date: 03:23:37 07/30/04

Go up one level in this thread


On July 29, 2004 at 16:32:11, Robert Hyatt wrote:

>On July 29, 2004 at 14:09:13, Gian-Carlo Pascutto wrote:
>
>>On July 29, 2004 at 14:07:10, Robert Hyatt wrote:
>>
>>>On July 29, 2004 at 06:26:52, Gian-Carlo Pascutto wrote:
>>>
>>>>http://arxiv.org/ftp/cs/papers/0406/0406038.pdf
>>>>
>>>>I stumbled onto this when doing a search for Axon.
>>>>Not seen it mentioned here yet.
>>>>
>>>>They also have a paper about hashing out which I can't
>>>>download.
>>>>
>>>>--
>>>>GCP
>>>
>>>
>>>Doesn't strike me as particularly interesting.  IE it almost seems that they
>>>don't realize that most programs store positions in a repetition list as 64 bit
>>>Zobrist integers...
>>
>>Look at the hasing paper abstract, do some quick math, and you'll see they
>>apparently don't know or don't use 64 bit hashing ;-)
>>
>>--
>>GCP
>
>I know.  If this was published, I wonder where the referees were?  ;)


I found the algorithm rather smart. A few aspects:

1. They mention hash keys or part of hash keys at page 4/5.

2. They don't need hashkeys in game history as well in current searched move
string as well. Only 16-bit moves.

3. The algorithm only needs a local concatination list of 25 16-bit words and is
therefore much more memory friendly.

4. They don't have any problems with rare collisions, where the zobrist xor-sum
of 2*N reversible moves is zero, but without a repetition.


I use the idea of Ronald de Man as a precondition for a possible repetition, a
small hashtable (2**12..14 bytes) indexed by some bits of the zobrist hashkey,
see Van Kervinck's thesis:

http://brick.bitpit.net/~marcelk/2002/marcelk-thesis.pdf
2.7 Implementation delails page 39.

Gerd





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.