Bad Pruning

[Onno Garms]

But obviously the effect of "bad pruning"/multi-prob-cut will depend on which other prunings are there. Unlike razoring and futility pruning, "bad pruning" is also done when remaining depth is large. Nonetheless I would expect that engine that do aggressive razoring or futility pruning, gain less from "bad pruning"

[uaf]

Indeed. I tested your "bad pruning" with different margins without luck. Chiron already does aggressive pruning, maybe that's the reason.

[Onno Garms]

Indeed. I tested your "bad pruning" with different margins without luck. Chiron already does aggressive pruning, maybe that's the reason.

Do you distinguish CUT nodes from ALL nodes? Might be important to prune only on ALL nodes as this prohibits aggressive recursive application.

[uaf]

No, I only distinguish between PV nodes and non PV nodes.

[Onno Garms]

I checked various versions of Prob-Cut in Stockfish now. I could not get statistical significant results, but results don't look bad. Maybe someone (Marco?) is interested in testing the idea further.

I've uploaded the version that looks most promising here:
http://www.onnochess.com/files/sf-211-og-1-0.zip
(Note that, apart from the required changes, I removed some auto definition of IS_64BIT and USE_BSFQ because that conflicts with syntax highlighting in Visual Studio, which distracted me.)
In my tests @0+1 this did +8 Elo (+1 percent point) over Stockfish 2.1.1 (which already has a limited probcut, recently added), which does not prove anything as the error bar is +-17 Elo in my 1140 games.

First attempt was of course to introduce node types ALL/CUT as described here:
http://talkchess.com/forum/viewtopic.ph ... 11&t=38408
This scheme works in the sense that CUT nodes have much fewer children than ALL nodes.
(I verified in Onno that doing ProbCut also on CUT nodes makes the engine weaker.)

It should be noted that razoring is almost the same like probcut when depth<=probcut_reduction. Stockfish already has razoring, Onno had not. So it is plausible that Stockfish profits less from probcut than Onno.
(I verified in Onno that both probcut for depth<=probcut_reduction and depth>probcut_reduction are useful and have the best effect if used together.)

Moreover, probcut should be done only for depth>RazorDepth in Stockfish. So a straightforward implementation of probcut in Stockfish looked like this:

Code: Select all

  // At ALL nodes, we try ProbCut with beta reduced by ProbCutMargin
  const Value ProbCutMargin = Value(0x180);

  // We reduce depth by this value.
  const Depth ProbCutReduction = ONE_PLY * 3;

  // Do ProbCut only for large depths
  const Depth ProbCutMinDepth = 4 * ONE_PLY;

 // ...

    if (    nodeType==ALL
        && !value_is_mate(beta)
        && depth >= ProbCutMinDepth)
    {
        Value rbeta = beta - ProbCutMargin;
        Value v = search<false>&#40;CUT, pos, ss, rbeta-1, rbeta, depth-ProbCutReduction, ply&#41;;
        if &#40;v<rbeta&#41;
          return v;
        else
          ss->bestMove = MOVE_NONE;
    &#125;

This did +0.7 percent points, which might be a mere coincidence.

I have no explanation why Stockfish profits so much less from probcut than Onno. Maybe because it does more heavy lmr, so it is less important to prune ALL nodes.

Marco told me that the Stockfish team got +5 Elo by doing probcut only on bad captures (added in SF 2.1.0).

Improvements are always nice of course, but doing probcut only on bad captures does not reflect the original idea well. When you do probcut on ALL nodes, positions get pruned when my previous move was bad and my opponent's reply was the obvious one. Bad captures are just one way to do very bad moves.

So I extended probcut to the positions after very good captures. The recapture after a bad capture is a special case of them. To create these captures, I modified MovePicker to create only captures with large enough see.

Code: Select all

  MovePicker(const Position&, Move, const History&, int bad_capture_threshold);

The core of the implementation is this:

Code: Select all

    // Step 6.5 ProbCut
    // If we have a very good capture (i.e. SEE>seeValues[captured_piece_type])
    // and a reduced search returns a value much above beta,
    // we can (almost) safely prune the previous move.
    if (   !PvNode
        &&  depth >= RazorDepth + ONE_PLY     // if we will razor children, the normal move loop should detect very good captures as easily as ProbCut
        && !inCheck                           // losing checks might be sacrifices, so better search them at full depth
        &&  abs&#40;beta&#41; < VALUE_MATE_IN_PLY_MAX
        &&  excludedMove == MOVE_NONE         // with an excluded move, ProbCut is very unlikely to be successful
      )
    &#123;
      Value rbeta = beta + 200;
      Depth rdepth = depth - 3*ONE_PLY/*reduction*/ - ONE_PLY/*as we play one ply*/;

      MovePicker mp &#40;pos, ttMove, H, Position&#58;&#58;see_value&#40;pos.captured_piece_type&#40;))+1&#41;;
      while ( &#40;move=mp.get_next_move&#40;)) != MOVE_NONE )
      &#123;
        pos.do_move&#40;move, st&#41;;
        Value v = -search<NonPV>&#40;pos, ss+1, -rbeta, -rbeta+1, rdepth&#41;;
        pos.undo_move&#40;move&#41;;
        if &#40;v >= rbeta&#41;
          return v;
      &#125;
    &#125;

This is in the version that I put on my site for download.

One might think of reducing by 2 rather than 3 plies. Results were about the same in my tests.

[mcostalba]

Maybe someone (Marco?) is interested in testing the idea further.

Hi Onno, yes I will put your patch on our test queue.

Thanks
Marco

[Don]

Maybe someone (Marco?) is interested in testing the idea further.

Hi Onno, yes I will put your patch on our test queue.

Thanks
Marco

Please let us all know how it turns out.

[mcostalba]

Maybe someone (Marco?) is interested in testing the idea further.

Hi Onno, yes I will put your patch on our test queue.

Thanks
Marco

Please let us all know how it turns out.

Of course

[mcostalba]

Please let us all know how it turns out.

Of course

Match still running, but results seem promising after 6253 games at 10"+0.1

Code: Select all

SF Onno ProbCut vs SF original: 1280 - 1120 - 3852 +8 (+- 5.4) LOS 98%

Great Onno !! Congratulations !! You are very close to succeed in improving SF search, this is a _big_ achievement

[Onno Garms]

I'm happy to hear that you can confirm my results of +8 Elo.

But I hope you also test against other engines? (My tests were run against a set of 14 engines with Noomen A-D.)