Computer Chess Club Archives


Search

Terms

Messages

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

Author: martin fierz

Date: 03:25:28 03/29/04

Go up one level in this thread


On March 28, 2004 at 18:55:53, Artem Pyatakov wrote:

hi artem,

[snip]

>>>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.

[snip]

>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%?

>4) This seemed to be an underdeveloped area (I only found research by Schaeffer,
>and then everyone else uses these same several heuristics - killer move, history
>heuristic, following the previous PV in Iterative Deepening)

perhaps much is just not published. for example, an idea which seems promising
is to use much more expensive move ordering when not close to the leaf nodes.
for example, you can do a SEE evaluation of every non-capturing move which is
expensive but pays off according to those who do it (crafty does not do this).
many people also report that history heuristic isn't helping them much. not too
suprising: if you have no move ordering, you gain a lot by history. if you have
lots of other good heuristics, you will not gain much more with history.

>My main research interested was motivated by the question: if the history
>heuristic works so well, then why hasn't anyone made any enhancements to this
>very simple and limited method?? Schaeffer says that combined with the
>transposition table, this leads to 99% of the gains of all other heuristics such
>as killer move and aspiration window (interesting sidenote: I did not notice
>searching the old PV first during IDA* in the list of heuristics, and that one
>actually results in very big gains for me).

without knowing too well: i don't think phoenix is a very good chess program. i
would take schaeffer's statement on this with a grain of salt. many things that
are true for one program are not true for other programs. i would tend to be
more interested in experiments done by authors of really strong programs.


>
>What is the idea behind the history heuristic? The basic idea is that similar
>moves will work in different parts of the tree. However, the history heuristic's
>big limitation (in my opinion) is that it absolutely does NOT take context (the
>board) into account. Ideally, we would want the same BEST move to be tried on
>similar boards, but probably would not want to try the same move on totally
>different boards. (In addition, the amount by which to increment the area and
>when to "forget" things seemed very arbitrarily chosen to me.)

the history heuristic's big limitation IMO is that it is a very simple heuristic
which works reasonably well if you have nothing or little else. i'm not sure
whether it helps anything at all if you use more sophisticated move ordering
schemes.

>history[from][to] += 1 << depth;

BTW; i never saw 1<<depth used yet. i use depth^2 myself. perhaps your approach
is better, i'll have to try :-)

cheers
  martin



This page took 0.03 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.