Computer Chess Club Archives


Search

Terms

Messages

Subject: Re: Futility Prune question

Author: Stuart Cracraft

Date: 21:38:34 10/18/04

Go up one level in this thread


On October 17, 2004 at 17:23:23, Bas Hamstra wrote:

>On October 17, 2004 at 12:07:24, Stuart Cracraft wrote:
>
>>Futility prune at depth == 1, extended futility prune at depth == 2, and razor
>>at depth == 3....
>>
>>Are the above depths *before* or *after* the makemove?
>>
>>I implemented the above (with depths calculated before the makemove)
>>and although my total nodes is reduced 30%, for me it is about the
>>same runtime and result.
>>
>>Not sure why this is so as I took extra care to avoid any extra calls to
>>incheck(). My eval() is simply lazy-eval level so nothing expensive there
>>either.
>>
>>I profiled both runs and there are not more incheck()'s in any amount
>>in the version with futility pruning turned on vs. not.
>>
>>Note -- my Extensions() routine calculates whether the move is a checking
>>move but does this last and only if all the extensions together don't
>>add up to 1.
>>
>>Likewise Reductions() which calculates Futility pruning initial status (parent
>>in check, depth = 1 2 3, whether futility, extended, or razor, and alpha status
>>in relation to evaluation+MARGIN) only calculates incheck() status if
>>not already done.
>>
>>A profiled run shows no great difference in incheck() calls. My
>>Futility pruning implementation must simply be wrong. Plese have
>>a look.
>>
>>Here is the code:
>>
>>int Reductions(int alpha, int depth, int *bd)
>>{
>>  int reduction=0;
>>  if (FUTIL_R != 0.0) {
>>    if (depth == 1) {
>>      if (parentincheck || alpha < eval(bd,QUIET)+3000)
>>        reduction = 0;
>>      else
>>        reduction = 1;
>>    }
>>    else if (depth == 2) {
>>      if (parentincheck || alpha < eval(bd,QUIET)+5000)
>>        reduction = 0;
>>      else
>>        reduction=1;
>>    }
>>    else if (depth == 3) {
>>      if (parentincheck || alpha < eval(bd,QUIET)+9000)
>>        reduction = 0;
>>      else
>>        reduction=1;
>>    }
>>  }
>>  return(reduction);
>>}
>>
>>mainsearch()
>>:
>>:
>>  parentincheck=incheck(bd);
>>:
>>  reduction=Reductions(alpha, depth, bd);
>>:
>>  make first move
>>:
>>    extension=Extensions(alpha,depth,bd,sml[mvi],threat,bmext,&checked,ply,qentr
>>y);
>>  ^^ perhaps the above alpha should be -beta?
>>      prune = 1;
>>      if (extension || !reduction || sml[mvi].cap) prune = 0;
>>      else {
>>        if (checked status not yet known) checked=incheck(bd);
>>        if (checked) prune = 0;
>>      }
>>      if (!prune)
>>        best = -search(bd,depth-1+extension, ply+1,-beta,-alpha);
>>:
>>  for main move loop
>>  :
>>  similar to above
>>:
>>
>>Thanks,
>>
>>Stuart
>
>Be careful with that. It's easy to claim it saves nodes, as Heinz did. However
>does your program effectively search deeper? That's the question. Remember that
>with lazy eval most of the futile nodes are cut anyway (but then they *do* count
>as nodes!) in a more accurate way.
>
>
>Bas.

No deeper. Here is without and with:

- 6.18/22.59 83% 250/300 ha=36 246.80 37344500 124482/1/151313 60036/122695/5822
17/1295146/13510622/165914/0
- 6.13/22.69 82% 246/300 ha=37 247.52 36066188 120221/1/145708 60414/121199/4968
93/1326052/12829848/171715/582147-DFUTIL

Nodes nearly identical at 37M and 36M. Depth nearly same in main search
6.18 and 6.12 and q-search 22.59 and 22.69. Scores on WAC are 250/300
and 246/300.

Something is wrong with the implementation or Heinz was smoking.



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.