Author: Dan Newman
Date: 13:16:24 10/01/98
Go up one level in this thread
On October 01, 1998 at 08:32:26, Robert Hyatt wrote:
>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...
I use the 50 move rule counter trick as well. I also do another thing
(which I think is correct): I skip over the immediately preceding
entry of the repetition list. The idea is that you need at least
two moves (on each side) before you can get a repetition, so I look
back two moves at first and then one move thereafter.
Here is a sequence of moves by black and white:
w1 b1 w2 b2 w3 b3 w4
If we are at the position reached by white's 4th move (w4) we
don't need to look at the hashcode for the position reached
by w3 because it can't be the same position. So we skip to
w2 and then w1.
-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.