Computer Chess Club Archives


Search

Terms

Messages

Subject: Re: Futility Cutoff futile?

Author: Koundinya Veluri

Date: 07:30:53 08/30/01

Go up one level in this thread


On August 30, 2001 at 08:46:32, Ulrich Tuerke wrote:

>On August 30, 2001 at 02:43:17, Pham Minh Tri wrote:
>
>>On August 29, 2001 at 22:09:20, Stuart Cracraft wrote:
>>
>>>So here is a pseudo-code fragment the attempts to implement
>>>futility cutoff but fails. The result is 2.67% less time for the
>>>same search and 4.35% fewer nodes, a far cry from what I heard
>>>it would do. So what's wrong with it?
>>>
>>>for all moves (sorting, etc.)
>>>  make move (backup if move leaves king in check and proceed to next move)
>>>  # Futility code follows
>>>  if side that moved was not in check before move AND
>>>    depth == 1 (i.e. 1 move until quiescence search, the "frontier") AND
>>>    no extensions so far at this node AND
>>>    this is not a principal variation node AND
>>>    this move was not a capture AND
>>>    side now on move is not in check AND
>>>    ((material difference between side on move before move and side now on move
>>>      PLUS the maximum of (maximum positional score of side not now on move,
>>>      value of a knight) <= alpha) then
>>>     unmake the move just made
>>>     continue with next move (bypassing this move, i.e. the futility cutoff)
>>>  endif
>>>:
>>>  search move normally as usual
>>>end
>>>
>>>Stuart
>>
>>I did not see where your qsearch is after pruning. You seem to prune too much.
>>You should prune the last depth, but not qsearch, IMO.
>
>" depth==1 " above means that he only prunes the last ply of the full search (in
>qsearch you'd have depth <= 0).

But here he's pruning not only the last ply of the search, but also the qsearch
that comes after the last ply. I think a qsearch should be done before the
"unmake move". I do something different.

This code comes before any moves have been searched at the last ply, but after
the null move is done.

IF depth == 1 && not extended for check && not extended for mate threat && not a
forced position (according to hash table) && not following pv THEN
    window = ???;
    qscore = Quiesce(alpha - window, beta + window);
    if(qscore <= alpha - window)
        return alpha;
    if(qscore >= beta + window)
        return beta;
END IF

Seems to be safe and improves speed on tactics a lot, when the correct window is
chosen. Although it may look like a waste doing qsearch for every position at
depth == 1, this does a lot more pruning than it does add to the tree. I tried
the other futility pruning mentioned in the original post, but it didn't work as
well for me.

Koundinya

>
>I think that this kind of pruning as suggested above is reasonable; I do
>something very similar. Although the benefit is rather modest, it may be
>worthwhile.
>
>Uli
>
>>
>>BTW, I prefer use Eval function to use material only (learn from Crafty 1.5x).
>>It is safer.



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