Author: Dan Newman
Date: 02:10:30 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. > This is what I currently do. I too don't really understand why it's so cheap--it doesn't even show up when I do a profile. I suspect that most of the time there's an irreversible move not so far back. It should be really bad in those pathological cases though... I once either saw or read about a trick to make this technique a bit less expensive. The idea is to maintain a small array of counts (say 256 elements or so) indexed by a portion of the hashcode. Every time you enter a node you increment the array element that is selected by the current hashcode (and decrement it when you leave). If the resultant count after incrementing is 2 or more, then you *may* have a repetition and can do the usual scan of the hashcode list to confirm it. If the resultant count is only 1, then you know you don't have a repetition and can forgo the more expensive test. The counts should be reset when irreversible moves are made at the root. >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. > It would, wouldn't it... Add to that the weird way pawns move and capture, pawn promotion, and the notion of being "in check". >You will get bugs no matter what you do. > >bruce > Dang. I suspected as much. -Dan.
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.