"slightly worst" pruning

[stegemma]

Anybody has never tried this kind of pruning:

Code: Select all

val = -Alphabeta(...
if (val >= beta - valPawn/4) return val;

The idea is that we can loose a little of the precision if we could get a better branching factor.

Of course we could do the same lowering beta when we call AlphaBeta:

Code: Select all

#define delta (valPawn/4)
val = AlphaBeta(-beta, -(alfa + delta), depth - 1);
if (val >= beta) return val;

I'm experimenting with Satana and it seems to gives a better branching factor, as expected, without loosing in strength (but Satana is a weak engine).

[jdart]

When you get a score >=beta, if you have done a limited window search then you need to re-search with a wider window to get an accurate score.

If the score is still >= beta you cut off the search because your move is "too good," and the opponent will not play into that node of the tree - he/she/it has a better move.

--Jon

[elcabesa]

Hi Stefano,
I can't understood where your algorithm should be inserted in a normal search.

can you explain?

my algorithm looks like this:

Code: Select all

alphabeta()
{
  before doing any move try to decide whether this node could be pruned or not ( null move pruning, razoring etc etc)

  main loop move
  { 
    do the futility pruning ( you can decide that some move are not good before doing them
   do move
   val =  -alphabeta // here yuo can do PVS and lmr
   undo move

   decide whter continuoe or return based on the val result
  }
  
}

[stegemma]

Hi Stefano,
I can't understood where your algorithm should be inserted in a normal search.

can you explain?

my algorithm looks like this:

Code: Select all

alphabeta()
{
  before doing any move try to decide whether this node could be pruned or not ( null move pruning, razoring etc etc)

  main loop move
  { 
    do the futility pruning ( you can decide that some move are not good before doing them
   do move
   val =  -alphabeta // here yuo can do PVS and lmr
   undo move

   decide whter continuoe or return based on the val result
  }
  
}

You should implement it in the part named "decide whter continuoe or return based on the val result". Here you compare the val with beta and then cut if val>=beta. We can cut a node if value >= beta, because this means that the opponent already have found a move that give us that value and he never choose the actual sub-node. For sample:

ply P:
a: white move: does nothing
aa: black moves: does nothing
aaa: white move: captures a pawn = 100 cp

has the value 100 centipawn for white at ply P and -100 cp at ply P+1 for black. We can analyze next move at ply P+1:

a: white move: does nothing
ab: black moves: does nothing
aba: white move: slightly worst for white: 95 cp

in normal alfabeta we don't cut now, in "slightly worst" pruning we can cut the node, even if the value is not >=100. We don't have to evaluate abb, abc, abd... moves. Of course, we get a value of 100 for move a, while we would have a real value of 95 or a little less but we have pruned more nodes than before, paying only with a little error in evaluation.

Maybe my implementation in alphabeta is not very correct, because I always think in the context of my alfagemma, that is similar to alfabeta (alphabeta) but it is not recursive.

[tpetzke]

Hi Stefano,

you should not trust the result of search to much if it is outside the window. Basing pruning decisions on it seems a bit random.

[stegemma]

Hi Stefano,

you should not trust the result of search to much if it is outside the window. Basing pruning decisions on it seems a bit random.

Thanks but maybe I haven't explained exactly what I mean, surely because of my bad english but even do to my low knowledge of true alphabeta.

In some further test i've seen that the program doesn't get stronger, this way.

Now I'm experimenting with classical alphabeta windows, instead of the binary search that I was explaining in another thread.