Computer Chess Club Archives




Subject: Re: Artificial Intelligence in Computer Chess - *DETAILS* as promised

Author: martin fierz

Date: 05:54:09 03/29/04

Go up one level in this thread

On March 29, 2004 at 07:04:13, Uri Blass wrote:

>On March 29, 2004 at 06:25:28, martin fierz wrote:
>>On March 28, 2004 at 18:55:53, Artem Pyatakov wrote:
>>hi artem,
>>>>>On the other hand, I think a lot of researchers have been overly ambitious and
>>>>>have tried to replace Alpha-Beta & tricks with a neural network or some totally
>>>>>different approach. I think that with the current state of AI tools, these
>>>>>efforts are bound to fail.
>>>>A lot of researchers?  Other than myself, I don't know of any other workers who
>>>>are attempting a complete and competitive chess playing program that doesn't
>>>>tread the oft traveled A/B bag-of-tricks road.
>>>That's good a point (will probably include in paper) - not many are working on a
>>>complete chess program, since most just address a particular section, like the
>>>evaluation function. But one old effort - MORPH - comes to mind, and I think I
>>>noticed a couple of other failed Neural Net efforts (don't have references
>>>handy, but I can look).
>>steven is doing a completely radical departure from A/B. but many others are
>>applying more gradual changes to the A/B-model, with reasonable success
>>(smarthink, kaissa, gothmog come to mind, and probably most commercial engines
>>too). at least these engines make considerably larger attempts to shape their
>>game tree than a "classic" A/B searcher like crafty does.
>>>As I mentioned before, I decided to concentrate my research on move ordering for
>>>a couple of reasons:
>>>1) Move ordering promises big payoffs if done right.
>>how much deeper can you search if you reach 95% move ordering success (defined
>>as cutoff @ 1st / all cutoffs) instead of ~90% that most get today? how much if
>>you reach 100%?
>I cannot answer the 95% question but I can answer the 100%.
>If you reach 100% then always choosing the first move is enough because if the
>first move does not generate a cutoff no move is going to generate a cutoff so
>you can finish to search to the end of the game very quickly because you search
>only one move in every ply.

you do not answer the question here - and what you answer is wrong too :-)
always choosing the best move first to search means you search sqrt(N) moves per
ply on average, not 1 move per ply. the real question is this: given a test set
with M positions searched to a certain depth D, what do you gain by improving
your move ordering from 90% 1st cutoffs to 90+x% cutoffs? i suspect that it is
not all that much, but i'm not willing to do the math right now :-)
i was hoping there is some theoretical formula for this that somebody might know
and be able to answer this question. of course the answer depends on when you
find the best move in the remaining cases when you don't find it first, but you
could make a sensible assumption for this and then do the math.


This page took 0.04 seconds to execute

Last modified: Thu, 07 Jul 11 08:48:38 -0700

Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.