Author: Robert Hyatt
Date: 05:27:06 10/01/98
Go up one level in this thread
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...
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.