Computer Chess Club Archives


Search

Terms

Messages

Subject: Futility Pruning (I think) Question

Author: Brian Richardson

Date: 13:11:18 04/02/00


I have changed Tinker to update material values incrementally (instead of in the
eval function each time).  This saved at most about 5%.  I did this to enable
futility pruning (I think this is what it is called).

In the q-search, the net material is found from the perspective of the side on
move.  Then, BEFORE doing the usual:
    x=eval();
    if(x>=beta) return(beta);
    if(x>alpha)alpha=x;
    FindCaptureMoves(); ...

I quickly check:
    if ((x - 2*Pawn) >= beta) return(beta);
assuming 2 pawns is about largest positional score (LPS). And then
    if ((x + 5*Pawn) <= alpha) return(alpha);
assuming that if winning a rook doesn't help more than alpha, just return.

Next, in the loop trying each capture move, before actually making the capture
move and calling x = -quiesce(-beta,-alpha), I see what the expected material
gain would be (taking into account promotions and enpassant).  If that plus
3 pawns is <= alpha then skip actually doing this capture, and try the next one.
In this case, I assume the LPS is about 3 pawns.  I know, it is not consistent,
but when i tried 2 pawns here, the search results would change, and I really
don't know what the LPS actually is.

Together these two "improvements" yield about 15% faster search times to a given
depth (in some cases >50%).

So, my question is does this all seem "reasonable".  I know implementing a SEE
would probably be better, but I'm not up to that yet.  I also tried some of
these cuts in the normal search routine, but that seemed to hurt things.

Thanks again for any feedback.
Brian



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.