Computer Chess Club Archives


Search

Terms

Messages

Subject: Re: Extended futility pruning and hashtables

Author: Ernst A. Heinz

Date: 17:32:19 01/01/00

Go up one level in this thread


Hi Gian-Carlo,

>>Please also note that normal futility pruning at frontier nodes with
>>a remaining depth = 1 and extended futility pruning at pre-frontier
>>nodes with a remaining depth = 2 are two different flavours of futility
>>pruning in the main search.
>
>The most important difference being that one is sound and the other isn't,
>right ?

Yes -- the following little table summarizes the according properties.

------------------+-------------------+------------------------------
Futility Pruning  |  Remaining Depth  |     Theoretically Sound?
------------------+-------------------+------------------------------
quiescence        |        -/-        |  iff margin >= max_posn_score
------------------+-------------------+------------------------------
normal            |         1         |  iff margin >= max_posn_score
------------------+-------------------+------------------------------
extended          |         2         |             no
------------------+-------------------+------------------------------

Of course, the soundness properties only hold for the cases of main
searches being backed by a quiescence searches with stand-pat cutoffs
(which chess programs generally adhere to).

>[...]
>>Just treat the selective score as a lower bound. Because you did not
>>search some moves at all, the real score might actually be better.
>
>Thanks for the help. I've added the whole bunch to Sjeng and it seems
>to give *big* gains with no noticable loss of tactical strength.

Fine, independent confirmation is always nice to receive!

=Ernst=

P.S.
"Scalable Search in Computer Chess" now available at MKP online
http://www.mkp.com/books_catalog/3-52805-732-7.asp :-)

Visit http://supertech.lcs.mit.edu/~heinz/node1.html for more
information about the book.



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.