Author: Walter Faxon
Date: 01:01:12 06/09/03
Musings on nonstandard computer chess techniques. What's new on the computer chess front? I note that Sergei S. Markoff's new program SmarThink (http://www.aigroup.narod.ru/detailse.htm) is supposed to use (among many other things) some of former world chess champion M.M. Botvinnik's ideas. Botvinnik's "Computers, Chess and Long-Range Planning" (Springer, 1970) and "Chess: Solving Inexact Search Problems" (Springer, 1983) described a method that apparently only Botvinnik's programmer/protege Boris Stilman believed would work, which Stilman later generalized in his own book "Linguistic Geometry: From Search to Construction" (Kluwer, 2000). Markoff's own on-line writings on chess algorithms (http://www.aigroup.narod.ru/indexe.htm) are only in Russian, so far. (I am assuming that the SmarThink download doesn't include source.) Markoff also writes that his first program included ideas from the authors of "Kaissa". Those authors published papers in the 1970's on "the method of analogies" to reduce search work, but they did not use it in their competitive program. If you recall, Hsu wrote in "Behind Deep Blue" (Princeton Univ. Pr., 2002) that he had implemented a stripped-down version of the analogies method for Deep Blue. It is the unpublished intellectual property of IBM. Sometimes I wonder if chess program authors mention intriguing nonsense just to throw their competitors off the track. I recall someone once letting slip that he had used Botvinnik's method for an early hardware-limited microcomputer program. That seems unlikely. Nearly 15 years ago an author (Kittinger?) dropped hints that he had adopted McAllester's 1988 method "conspiracy number search" (aka conspiracy search) for his program, using the term "nodulation". Published results indicate that plain conspiracy numbers don't work very well for chess. As far as I know, today only experiments on multiprocessor machines are being conducted; no competitive microcomputer program uses it at all. So was it a mirage -- or a trick? David McAllester and Deniz Yuret did finally publish their revised work (Alpha-Beta-Conspiracy Search. ICGA Journal, Vol. 25, No. 1 (March 2002), pp. 16--35), nearly ten years after their initial experiments with the multiprocessor program Star-Socrates. And ten years from now?... And what about Berliner's B* algorithm? (Actually Palay's probabilistic B* using a probability distribution for evaluation instead of a simple range, today suggestive that techniques from fuzzy logic might be applied.) The chess machine Hitech was originally built for it in the early 1980's (equal first on points but second on tiebreak, WCCC 1986) -- and finally began using it. As of mid-1993 it was "almost as good as regular Hitech". In mid-1995 it was still "not quite as good as brute force searching." In the abstract of his last word on the subject (Hans J. Berliner and Chris McConnell. B* probability based search. Artificial Intelligence, Volume 86, Issue 1, September 1996, Pages 97-156) Berliner writes, "Analysis of the data indicates that should additional power become available, the B* technique will scale up considerably better than brute-force techniques." Berliner is now retired. More power is available. Where are the later papers? Where is B* today? My suggestion: you are writing a chess program. Go ahead, put in negascout, null-move pruning, IID, everything everybody is already doing. Then, look to the literature and find some method that everybody is _not_ doing. Implement it, experiment with it, and _publish_ your results. Please. -- Walter
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.