Bad Pruning

Discussion of chess software programming and technical issues.

Moderators: hgm, Rebel, chrisw

User avatar
Onno Garms
Posts: 224
Joined: Mon Mar 12, 2007 7:31 pm
Location: Bonn, Germany

Bad Pruning

Post by 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
Posts: 88
Joined: Wed Mar 25, 2009 12:49 pm

Re: Bad Pruning

Post by Teemu Pudas »

Last edited by Teemu Pudas on Sun Mar 13, 2011 9:34 pm, edited 1 time in total.
zamar
Posts: 613
Joined: Sun Jan 18, 2009 7:03 am

Re: Bad Pruning

Post by 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...
Joona Kiiski
mcostalba
Posts: 2684
Joined: Sat Jun 14, 2008 9:17 pm

Re: Bad Pruning

Post by mcostalba »

Onno Garms wrote: 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
Posts: 3026
Joined: Wed Mar 08, 2006 9:57 pm
Location: Rio de Janeiro, Brazil

Re: Bad Pruning

Post by Albert Silver »

mcostalba wrote:
Onno Garms wrote: 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.
"Tactics are the bricks and sticks that make up a game, but positional play is the architectural blueprint."
Jorge Garcia
Posts: 61
Joined: Thu Oct 22, 2009 1:50 am
Location: Barcelona Spain

Re: Bad Pruning

Post by 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.
--------------------------------------------------
Jorge García de Andrés
http://dynchess.blogspot.com.es
http://www.bitacoradelasalud.blogspot.com.es
http://www.mytechit.blogspot.com.es
User avatar
Kempelen
Posts: 620
Joined: Fri Feb 08, 2008 10:44 am
Location: Madrid - Spain

Re: Bad Pruning

Post by Kempelen »

Onno Garms wrote: 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.
Fermin Serrano
Author of 'Rodin' engine
http://sites.google.com/site/clonfsp/
Ferdy
Posts: 4840
Joined: Sun Aug 10, 2008 3:15 pm
Location: Philippines

Re: Bad Pruning

Post by Ferdy »

Kempelen wrote:
Onno Garms wrote: 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.
User avatar
Onno Garms
Posts: 224
Joined: Mon Mar 12, 2007 7:31 pm
Location: Bonn, Germany

Re: Bad Pruning

Post by Onno Garms »

zamar wrote: 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.
User avatar
Onno Garms
Posts: 224
Joined: Mon Mar 12, 2007 7:31 pm
Location: Bonn, Germany

Re: Bad Pruning

Post by Onno Garms »

Kempelen wrote: 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.