Author: Vincent Diepeveen
Date: 06:39:10 01/31/01
Go up one level in this thread
On January 31, 2001 at 08:13:52, martin fierz wrote:
>hi,
>
>i recently corrected some code in my connect 4 program and now it is able to
>solve connect 4 in less than a day on a fast PC with a large hashtable (of
>course, connect 4 has been solved long ago). i tried again with a smaller
>hashtable and
>got some strange results, for very long searches (billions of nodes) i don't get
>the same value for
>the root position. for not-so-deep searches i get the same values for both
>versions. i am wondering, [if this is not just a bug :-)] could this be some
>hashcollision-problem? can anybody give me a probability for a hash collision
>occuring when using B-byte key & lock, with a hashtable with S entries after
>searching N nodes? (i am using 4 byte ints for the key and the lock)
You're using 32 bits to hash?
I think there are like 7x6 rows or so = 2^42 possibilities which you
hash in 32 bits.
Easier is to store the entire position. This fits easily in 64 bits
as with are 7 rows (?) at most 7 open spots are there.
you can do next: white = 0, black = 1.
open spots also 0.
Now also describe how far each row is open. That's 3 bits for 7 rows = 21
bits.
So in 42 + 21 bits you can store the entire position. That's not hashing
but a true hash.
For solving a game you definitely need to store the entire position!
With just 32 bits you ask for trouble!
>also, i think i remember somebody mentioning here that one can choose the random
>numbers for the XORs in a clever way making hashcollision probabilities
>smaller - can somebody tell me how?
You don't need XOR. You need a bitmap:
#define BITBOARD unsigned _int64
in windows (new ansi-C convention also long long)
#define BITBOARD unsigned long long
for gcc compiler
by making a few tables you can quickly update the true hash. Should
update that incremental of course!
Not as fast as a 32 bits XOR, but you'll see a lot of problems in your
prog are solved!
>cheers
> martin
This page took 0.01 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.