Author: David Eppstein
Date: 14:33:58 06/04/99
Go up one level in this thread
I am wondering if there is some specialized algorithm we should be using to
detect certain deep repetition or perpetual-check draws, e.g. the famous
Kasparov resignation. I'm envisioning a program that does the usual alpha-beta
search, but
adds a few lines before the main loop:
if (depth > threshhold && alpha < 0.0 && repetition()) {
alpha = 0.0;
if (alpha >= beta) return alpha;
}
i.e. if the repetition detector says that the side on move can force at least a
draw, then return a draw score rather than anything lower. The repetition
detection routine can be moderately expensive if we set the threshhold
appropriately.
For instance, maybe you could detect (some fraction of) repetitions by a very
deep search, in which you restrict the side that's attempting to force the
repetition to only checking moves, and you stop and evaluate whenever you run
out of checks. Sort of like a specialized quiescence search... Since these
repetition sequences would typically involve only a few pieces moving, the
transposition table should let the repetition search go much deeper than you
could in a full-width search.
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.