Computer Chess Club Archives




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

Author: Dan Andersson

Date: 21:16:07 07/29/04

Go up one level in this thread

 A Bloom filter is a set representation that allows for a membership query. And
the rate of false positives can be set arbitraily low.
 Basically a Bloom filter is a bit array of length M where you use N different
hash functions in the range 1..M to set bits.
 For each new reversible move you compute the hash set. Check if it is already
set and if not add it.
 There is plenty of scope for experiments in implementation techniques here. But
the main bother is the hashing functions. But it should be possible to piggyback
on the Zobrist hash  since any bit string value should be independent of any
other disjunct string.
 It seemed too much of a bother to me. But there might be some gain to be had
for a small filter since it would short circuit some if not all unnecessary
checks for repetition.

MvH Dan Andersson

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.