Author: Robert Hyatt
Date: 05:32:26 10/01/98
Go up one level in this thread
On October 01, 1998 at 05:10:30, Dan Newman wrote: >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. One other trick... if you handle the 50-move rule, is that you search backward from the current repetition entry, but you only go back for as many entries as the value of your 50-move rule counter indicates... since many captures or pawn pushes occur in the search, this cuts off this "loop" very quickly most of the time...
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.