Author: Omid David Tabibi
Date: 10:45:52 06/12/03
Go up one level in this thread
On June 12, 2003 at 02:40:10, Walter Faxon wrote:
>On June 10, 2003 at 19:19:41, Omid David Tabibi wrote:
>
>>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
>
>
>Hello, Omid.
>
>First, thanks for you thoughtful response to my recent post. I have been from
>time-to-time disappointed that there is not more AI content on CCC. It very
>much seems to be a hobbyist board, playing with the current programs and
>building duplicates of them, albeit with minor differences in emphasis and
>implementation. I've been guilty of this myself in the bitscan threads. But
>the few times I have tried to raise the level of discussion have been met with,
>mostly, silence. My last post was to an extent, a "last gasp".
>
>My response viz. Go. In my opinion, tackling Go is a mistake for one reason and
>one reason only: very few Westerners play Go at better than a weak amateur
>level, and most don't play at all. In contrast, in the West chess is well-known
>as an "intellectual" pastime, and hundreds of thousands of people play it well
>enough to at least appreciate much of the practice of the masters. Chess is a
>good AI testbase because chess exhibits many understandable problems amenable to
>AI methods while eliciting non-AI interest -- in both the readers and writers of
>AI papers.
>
>I have not reread Andreas Junghanns' 1998 "Are There Practical Alternatives To
>Alpha-Beta in Computer Chess?" but there is one obvious objection to the thesis
>("no"): a small number of human beings can (still) play chess at least as well
>as the best chess computers. That amounts to an existence proof that brute
>force is not the only way. And finding out how to emulate the best human
>techniques in chess may be reasonably expected to have applicability in other
>areas of problem solving -- maybe even Go!
>
>But of course we now know that chess can be effectively tackled using
>(relatively smart) brute-force techniques. Using any more complicated AI
>methods tends to lose vs. the finely-tuned fast searchers, so the papers
>experimenting with new methods tend to be of the "one-shot" variety, with no
>follow-ups.
>
>Thus, my solution (mentioned in a CCC post some months ago): a competition in a
>new field of study: Limited Search Computer Chess (LSCC), with rules similar to
>that of the "RoboCup" international robot soccer competitions, the most
>important of which is: all code is made public after the tournament is over.
>First cut: 100 positions per second, max.
>
>Some sort of prize (a little money, even) would be a great incentive for such a
>competition. I might offer it myself except that right now I am literally
>broke. Maybe in a few months.
>
>Thoughts?
>
I think _any_ research in computer chess should be welcomed. Whether it is a
practical selective search algorithm, or a more theoretical one like B*, etc.
Frankly I'd rather see _any_ computer chess paper instead of all those Go
articles which I will probably never read in the ICGA (I hardly know the rules
of Go). For me chess is a whole life's experience, and Go?! An eccentric game
played on the other side of the world...
Published articles in computer chess should not necessarily introduce an
innovation; I would greatly appreciate reading an article about experiments
conducted on algorithm X and Y which _didn't_ work. At least I prefer this kind
of papers to the Go ones.
>-- 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.