Author: James Robertson
Date: 07:07:45 10/01/98
Go up one level in this thread
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
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.