Bad Pruning

[Onno Garms]

I have named this idea "bad pruning".

With this idea, Onno made one of its biggest leaps. I did not find
this idea in Stockfish. But of course it is possible that the
Stockfish search does implicitly something somewhere. Then Stockfish
might not profit from this idea as Onno did. Try it out!

The idea is not to search bad looking moves. To determine what a bad
looking move is, we search the move with reduced depth and reduced
alpha/beta. That is, if a search at depth d-3 says that you lose more
then a pawn, do not search the move with current depth d.

Here is the code from Onno:

Code: Select all

  // bad pruning
  // ------------------------------------------------------------
  if (SearchInnerRc::bad_enable && node->type==NodeType::all && node->beta>=-ValueNode::max_eval )
  {
    // setup child
    child->depth  = node->depth - SearchInnerRc::bad_reduction;
    child->height = node->height;
    child->alpha  = node->alpha - SearchInnerRc::bad_margin;
    child->beta   = node->beta  - SearchInnerRc::bad_margin;
    child->type   = NodeType::cut;
    child->ret_addr = Label::after_bad_pruning;

    // goto child
    node->move = Move::none;
    ++node;
    ++child;
    goto recurse;
      
    // evaluate
  after_bad_pruning:
    if &#40;child->pv.value&#40;) < node->beta - SearchInnerRc&#58;&#58;bad_margin&#41;
    &#123;
      node->pv = child->pv;
      log_finish &#40;1, "bad pruning");
      goto node_done;
    &#125;
  &#125;

"goto recurse" runs the search that was set up in child (i.e. what was
child before ++child and is node after++node), stores the result in
child->pv, decrements node and child, and finally has a huge case switch on
child->ret_addr to jump back to after_bad_pruning.

Note that Move::none is different from Move::null.

Useful values are 150 centipawns for bad_margin and 3 for bad_reduction.

Obviously the downside of bad pruning is Onno's well known tactical
blindness, especially for double sacrifices. Bug over all bad pruning
made Onno much stronger.

[Teemu Pudas]

This is Multi-ProbCut. http://www.cs.ubc.ca/~jiang/papers/mpc_main.pdf

[zamar]

The idea is not to search bad looking moves. To determine what a bad
looking move is, we search the move with reduced depth and reduced
alpha/beta. That is, if a search at depth d-3 says that you lose more
then a pawn, do not search the move with current depth d.

The idea is interesting, although I'm afraid that this will result in clear tactical oversights. It takes 3 more plies to see winning sacrifise. And if idea is implemented recursively, it might take six more plies to see double sacrifise and so on...

Anyway extra speed-up might compensate this, so perhaps we'll try sth like this in near future...

[mcostalba]

The idea is not to search bad looking moves. To determine what a bad
looking move is, we search the move with reduced depth and reduced
alpha/beta. That is, if a search at depth d-3 says that you lose more
then a pawn, do not search the move with current depth d.

If I have understood correctly this is a kind of LMR launched on (beta - margin) instead of just beta....


BTW thanks for your posts, I will need some weeks to fully understand them, anyhow far less than what it took you to find them .....can I ask why did you gave up with your engine ?

[Albert Silver]

The idea is not to search bad looking moves. To determine what a bad
looking move is, we search the move with reduced depth and reduced
alpha/beta. That is, if a search at depth d-3 says that you lose more
then a pawn, do not search the move with current depth d.

If I have understood correctly this is a kind of LMR launched on (beta - margin) instead of just beta....


BTW thanks for your posts, I will need some weeks to fully understand them, anyhow far less than what it took you to find them .....can I ask why did you gave up with your engine ?

He posted his reasons in the general forum.

[Jorge Garcia]

Hi all,
I saw something similar in the Probcut search approach, but I agree that the risk of tactical oversight is high. Anyway it could be interesting see if the Onno enhancement could work on other engines.

[Kempelen]

The idea is not to search bad looking moves. To determine what a bad
looking move is, we search the move with reduced depth and reduced
alpha/beta. That is, if a search at depth d-3 says that you lose more
then a pawn, do not search the move with current depth d.

wouldn't be the same if you do a SEE evaluation of the move (assuming your SEE function can also works with noncapture moves) and see that you loose more than a pawn? that would be faster and probably very similar.

[Ferdy]

The idea is not to search bad looking moves. To determine what a bad
looking move is, we search the move with reduced depth and reduced
alpha/beta. That is, if a search at depth d-3 says that you lose more
then a pawn, do not search the move with current depth d.

wouldn't be the same if you do a SEE evaluation of the move (assuming your SEE function can also works with noncapture moves) and see that you loose more than a pawn? that would be faster and probably very similar.

Basically SEE can only handle static eval, whereas searching a move at a reduced depth will be able to handle dynamic evaluation. For example the position might contain mate threats or a position might have promotion threats.

To improve the idea, and if SEE is available at that point, then try a combination of SEE and search with reduced depth. For example if SEE is bad then search this with a reduced depth as a verification, if it losses material or losses position value then prune/reduce.

[Onno Garms]

The idea is interesting, although I'm afraid that this will result in clear tactical oversights. It takes 3 more plies to see winning sacrifise. And if idea is implemented recursively, it might take six more plies to see double sacrifise and so on...

Perfectly true, see last paragraph of my original post. However, as I wrote, overall the playing strength increased considerably.

[Onno Garms]

wouldn't be the same if you do a SEE evaluation of the move (assuming your SEE function can also works with noncapture moves) and see that you loose more than a pawn? that would be faster and probably very similar.

Though not having tried that, I am pretty sure that using SEE instead of a reduced search is absolutely fatal for the playing strength. Using SEE would mean that you NEVER search sacrifices.