Author: Bruce Moreland
Date: 00:18:58 10/01/98
Go up one level in this thread
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
This page took 0.01 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.