Author: Robert Hyatt
Date: 08:01:29 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) >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? > >cheers > martin First, it is important to realize that the thing you search for othello, chess or anything else is _not_ a "tree". It is a "graph". This is because there are multiple ways to get to the same node. Once you notice that, then transposition tables become somewhat unsafe in their use. It is possible that an entry found at point A in the search will be used to influence the score at point B. But _only_ if the entry survives long enough to be used at point B. In chess engines this can be seen by trying fine#70. As you change the hash table size, you will change the depth at which this position gets solved. It is just part of the "fun" of hashing. The hash scheme you are describing is the 'Zobrist' algorithm. If you search the net for that, you should find a detailed and easy-to-understand description. Most everybody uses it in today's chess engines.
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.