Author: Dann Corbit
Date: 21:19:21 11/21/03
Go up one level in this thread
On November 21, 2003 at 23:50:52, Edward Seid wrote: >Dann, since you seem to be in the mood to answer questions, I hope you don't >mind if I squeeze one in. > >I understand that the bigger problem with hashing is that it's (remotely) >possible for 2 positions to generate the same hash signature. > >Is anything ever done about this remote possiblility, or do programmers simply >ignore this? Mostly, they ignore it. You can easily deal with it by storing the entire position (24 bytes or so) and then you can know if it is an exact match or not. However, the extra space consumed means you get a lot less hash entries. For that reason, it is not popular. If you consider a 64 bit hash, then the odds of a collision are about 5.4e-20. So you can make collisions absurdly unlikely by dividing your hash into hash_slot_bits + remainder. In general, hash collisions are a tempest in a teapot unless you have a bad hashing algortithm or a hashing bug. Then they can make your program totally stink. >I've heard of something called a hash "lock", but I'm not sure how >it's related to this. Something else entirely. If you have multiple threads of execution writing to a hash table, then you may wish to lock the hash entry before update. It's my understanding that Dr. Hyatt has figured out a way to get around this, but I have not really studied it. > >Another, more general, question. >I understand that a full board scan is done in the starting position, then every >incremental XORs are performed to get a new hash key. Consider a position, say >after 10 moves. Will the hash keys of the original scan + incremental XORs be >the same as a full-board scan of the current position? Yes. You can build the hash all at once, but the Zobrist algorithm (which nearly every program uses) is very handy because it can incrementally update the hash. For make/unmake move it is a lifesaver. >Finally, you've demonstrated a lot of knowledge about chess programming. Is >there any chance for 1) a Dann Corbit FAQ on Chess Programming or I doubt I would do very well at it. I might write an article or two some day, but there are already some excellent tutorials available. >2) a 100% Dann >Corbit engine? I have a chess engine I have been working on since the 1990's. I rip it apart and put it back together. I completely redo it from scratch. I change the fundamental algorithms in the guts. Someday, I may make it public. I have a plan to enter a contest some day. After the contest, I am going to give a copy of the source code to my chess programming friends. My chess engine is nothing like the chess engine of other people. I don't use traditional alpha-beta. I do incremental eval. Lots of other perverse things. But it's bitboard based. So it is traditional in that sense. >TIA.
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.