Author: Don Dailey
Date: 08:41:52 10/01/98
Go up one level in this thread
On October 01, 1998 at 10:07:45, James Robertson wrote: >On October 01, 1998 at 08:27:47, Robert Hyatt 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. >>> >>>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 >> >> >> >>I did this in an early version of Cray Blitz, but it has one *huge* problem >>when you go to a parallel search. Such a table of "active" positions >>becomes useless when you have multiple threads that can reach these >>positions independently of each other, so that suddenly you can't tell >>what has actually been seen before in reality and what has only been seen >>once before by a different processor. >> >>I had to toss this out when Cray Blitz went parallel in 1983, and have >>used a simple "list" of repeated positions ever since... > >Yeah..... this sounds terribly slow, but it seems really a lot eaisier to >program. How much of the search time does it take to do this repetition search >if you have a list? > >James Read the rest of this thread which talks about this. The point is that for some reason (which I think I explain) it is not slow at all. - 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.