Computer Chess Club Archives


Search

Terms

Messages

Subject: Re: Futility Pruning

Author: Vincent Diepeveen

Date: 07:54:01 12/20/02

Go up one level in this thread


On December 20, 2002 at 08:23:59, Russell Reagan wrote:

No futility is 100% different from lazy evaluation.

Futility in fact selects less moves (in qsearch)
based upon alfa or beta and lazy evaluation gives
back a quick score a lot of the times.

If you search a ply deeper a futile pruned move should not
get pruned, whereas a lazy evaluated position will give problems
no matter what depth you search.

In contradiction to draughts where everything is seen fullwidth,
in computerchess the effect of futility can be very bad too,
because last 3 to 4 plies (R=2 versus R=3) the qsearch is returning
back a score instead of a full search.

If that misses major problems then you are in trouble.

The argumentation of Heinz that futility is correct, is using the
assumption that an evaluation doesn't get a big score for positional
matters. The problem is that todays top programs do give big scores
though.

With regard to lazy evaluation there is more problems.

The importance of those positions with big scores to solve even
tactical testsets (by matter of evaluation!!) is very important.

A good example is that with months of work i managed to make
a quick evaluation function
which could predict a score within 3 pawns
accurate in 99% of the cases.

though completely technically spoken that is not a real lazy
evaluation but a quick evaluation that's used to enhance lazy
evaluation, the outcome was also a big surprise to me.

My expectation was that i would search 2 times faster and that
problems would be found quicker because the number of nodes would
be not that much more.

Secondly i assumed that the hard thing to investigate would be
the positoinal influence at games of lazy evaluation.

When i started extensive testing after months of work the
resutls were amazing.

  a) many trees i needed more than twice the number of nodes
  b) assumption that it was 2 times faster was correct
  c) somehow for many positions i needed a few ply more to find it.

After some investigations it appeared quickly that
the 1% that the quick evaluation mispredicted was
solving many positions in difficult
testsets by means of evaluatoin. Not because of seeing material win.
Usually you can delay such material wins by many moves...

And do not forget that majority were testset positions as people use
them in postings here. We do not even talk about normal difficult game
situations where that 0.001 difference can cause losing or winning a game.

So the lazy evaluating diep already was tactical weaker than the non
lazy evaluating DIEP. Basically because of needing plies more to find
tricks. What also disturbed me is that i needed a lot of nodes more
to get to the same depth. 20-30% was no coincidence.

Where lazy evaluation was easy for me to proof incorrect, with regard to
futility pruning it is harder to judge. What i know is that it doesn't
work for me to use alfa and beta values to judge.

Instead i use a lot of chessknowledge to judge which is alfabeta independant.

Note that in Napoleon lazy evaluation seems to speed me up 50% in speed.

I do not know whether it is a good thing to do though there, i am a too
bad draughtsplayer to judge that.

Best wishes,
Vincent

>On December 20, 2002 at 08:11:34, Nicolas GUIBERT wrote:
>
>>Just checking :
>>
>>"Futility pruning" means "use of lazy evaluation", right ?
>
>Yes and no, depending upon how you view it. Futility pruning means, "this is
>really bad, I'm not going to waste my time to find out how bad." Futility
>pruning is a search topic. Lazy evaluation is generally an evaluation topic.
>However, futility pruning could be a kind of lazy evaluation of the search. I
>see how you can make that connection.

>Technically speaking, they are different things, but in more general terms, it
>is ok to say that futility pruning is a kind of lazy evaluation, IMO.
>Russell



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