Author: Omid David Tabibi
Date: 16:19:41 06/10/03
Go up one level in this thread
On June 09, 2003 at 04:01:12, Walter Faxon wrote:
>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.
A nice post.
Junghanns gives a good overview of all the alternatives to alpha-beta at:
Are There Practical Alternatives to Alpha-beta?"
ICCA Journal, Vol. 21, No. 5, 1998. pp. 14--32.
http://citeseer.nj.nec.com/junghanns98are.html
Just take a look at all the chess related research published in ICGA in the last
year:
ICGA 25(1):
Alpha-Beta Conspiracy Search
(McAllester & Yuret)
[an interesting, but old article]
A Lockless Transposition-Table Implementation for Parallel Search
(Hyatt & Mann)
[a smart transposition table idea]
ICGA 25(2):
Nothing!
ICGA 25(3):
Verified Null-Move Pruning
(David Tabibi & Netanyahu)
ICGA 25(4):
Nothing!
ICGA 26(1): [haven't received the issue yet, just looked at
http://www.cs.unimaas.nl/icga/journal/contents/content26-1.htm]
Nothing!
I believe that all this lack of research stems from the Deep Blue - Kasparov
match. Deep Blue's victory convinced many that nothing is left to be done in
chess, so let's move on. The new trend seems to be Go; just take a look at the
two latest ICGA issues: it's all about Go. Maybe that's the reason why the name
ICCA was changed to ICGA ;)
>
>-- Walter
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.