Bad Pruning
Moderators: hgm, Rebel, chrisw
-
- Posts: 224
- Joined: Mon Mar 12, 2007 7:31 pm
- Location: Bonn, Germany
Re: Bad Pruning
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"
-
- Posts: 98
- Joined: Sat Jul 31, 2010 8:48 pm
- Full name: Ubaldo Andrea Farina
Re: Bad Pruning
Indeed. I tested your "bad pruning" with different margins without luck. Chiron already does aggressive pruning, maybe that's the reason.
-
- Posts: 224
- Joined: Mon Mar 12, 2007 7:31 pm
- Location: Bonn, Germany
Re: Bad Pruning
Do you distinguish CUT nodes from ALL nodes? Might be important to prune only on ALL nodes as this prohibits aggressive recursive application.uaf wrote:Indeed. I tested your "bad pruning" with different margins without luck. Chiron already does aggressive pruning, maybe that's the reason.
-
- Posts: 98
- Joined: Sat Jul 31, 2010 8:48 pm
- Full name: Ubaldo Andrea Farina
Re: Bad Pruning
No, I only distinguish between PV nodes and non PV nodes.
-
- Posts: 224
- Joined: Mon Mar 12, 2007 7:31 pm
- Location: Bonn, Germany
Re: Bad Pruning
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:
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.
The core of the implementation is this:
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.
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>(CUT, pos, ss, rbeta-1, rbeta, depth-ProbCutReduction, ply);
if (v<rbeta)
return v;
else
ss->bestMove = MOVE_NONE;
}
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);
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(beta) < VALUE_MATE_IN_PLY_MAX
&& excludedMove == MOVE_NONE // with an excluded move, ProbCut is very unlikely to be successful
)
{
Value rbeta = beta + 200;
Depth rdepth = depth - 3*ONE_PLY/*reduction*/ - ONE_PLY/*as we play one ply*/;
MovePicker mp (pos, ttMove, H, Position::see_value(pos.captured_piece_type())+1);
while ( (move=mp.get_next_move()) != MOVE_NONE )
{
pos.do_move(move, st);
Value v = -search<NonPV>(pos, ss+1, -rbeta, -rbeta+1, rdepth);
pos.undo_move(move);
if (v >= rbeta)
return v;
}
}
One might think of reducing by 2 rather than 3 plies. Results were about the same in my tests.
-
- Posts: 2684
- Joined: Sat Jun 14, 2008 9:17 pm
Re: Bad Pruning
Hi Onno, yes I will put your patch on our test queue.Onno Garms wrote:Maybe someone (Marco?) is interested in testing the idea further.
Thanks
Marco
-
- Posts: 5106
- Joined: Tue Apr 29, 2008 4:27 pm
Re: Bad Pruning
Please let us all know how it turns out.mcostalba wrote:Hi Onno, yes I will put your patch on our test queue.Onno Garms wrote:Maybe someone (Marco?) is interested in testing the idea further.
Thanks
Marco
-
- Posts: 2684
- Joined: Sat Jun 14, 2008 9:17 pm
Re: Bad Pruning
Of courseDon wrote:Please let us all know how it turns out.mcostalba wrote:Hi Onno, yes I will put your patch on our test queue.Onno Garms wrote:Maybe someone (Marco?) is interested in testing the idea further.
Thanks
Marco
-
- Posts: 2684
- Joined: Sat Jun 14, 2008 9:17 pm
Re: Bad Pruning
Match still running, but results seem promising after 6253 games at 10"+0.1mcostalba wrote:Of courseDon wrote: Please let us all know how it turns out.
Code: Select all
SF Onno ProbCut vs SF original: 1280 - 1120 - 3852 +8 (+- 5.4) LOS 98%
-
- Posts: 224
- Joined: Mon Mar 12, 2007 7:31 pm
- Location: Bonn, Germany
Re: Bad Pruning
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.)
But I hope you also test against other engines? (My tests were run against a set of 14 engines with Noomen A-D.)