Author: Don Dailey
Date: 07:37:00 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. The reason the linear search algorithm is so cheap (even in endgames) is that most chess program try capture moves first in the search. The number of lines where the maximum number of irreversible moves gets high is exceedingly small. The worst case scenario is limited to positions where no captures or pawn moves are possible or ever will be such as locked pawn endgames with no intrusion sqaures. A parallel program cannot use Bruce's method unless you limit the hash table test to the moves that happen BEFORE the search. In this case you still do a linear search for the portion of the move history contained in the current search tree. Also the maximum possible number of tests you will do is 48 due to the 50 move rule. We do what Bob recommends and we have a counter that gives us the number of moves since the last reversible move. We do not allow this counter to exceed 50 due to the 50 move rule. These positions can be immediately scored as draws. - Don
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.