Author: Roberto Waldteufel
Date: 04:58:57 10/01/98
Go up one level in this thread
On October 01, 1998 at 03:18:58, Bruce Moreland wrote: > >On October 01, 1998 at 00:25:44, James Robertson wrote: > >>How do programs detect draws by repetition in a search? I can think of many >>possible ways, but they all seem really slow. How do most programs quickly >>detect draws by repetition? > >You have a hash key. You have a transposition table. > >1) You can set a flag in your transposition table when you enter a node, and >clear it when you leave the node. If you encounter a flag that's already set, >it's a rep draw. You have to be careful not to kill your hash entry somehow, >there is tremendous potential for bugs. > >2) You can make a new hash table, a small one, and store the hash key in that >when you enter a node, and clear it when you leave. > >3) You can create a list of hash keys that represent positions that have >occurred between now and between the capture or pawn move, and iterate. This >isn't as slow as it sounds, for reasons that I don't understand, but it may get >really bad in some pathological cases such as when you are near a 50-move draw. > >You have to be careful to take into account the en-passant square and the >castling flags in some circumstances. > >Without castling and en-passant, chess would be a lot simpler to program. > >You will get bugs no matter what you do. > >bruce Hi Bruce, I use method 2, except I am a bit extravagent in the size, and make my draw table with the same number of entries as the other tables, so I can access it faster by not needing to mask any bits off the hash key or maintain a second key separately. This means that my draw table is very sparse, but it is probed so many times during the search that I wanted to make it as fast as possible, so using the same key made some sense to me. I switched to this from method 1 after encountering all sorts of problems with erased entries and hash collisions etc. The only problem I have encountered with method 2 is that draws correctly identified by the draw hash table will have an adverse affect on the scores of ancestor nodes in the tree when they are entered into the transposition table later on, and so a later hit on one of these ancestor nodes may give misleading information. I don't really see a way to avoid this - it seems at least to be a rare event. Best wishes Roberto
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.