Stockfish depth vs. others; challenge

Discussion of chess software programming and technical issues.

Moderators: bob, hgm, Harvey Williamson

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
Ryan Benitez
Posts: 719
Joined: Thu Mar 09, 2006 12:21 am
Location: Portland Oregon

Re: Stockfish depth vs. others; challenge

Post by Ryan Benitez » Tue Nov 26, 2013 5:56 am

I thought the reason Stockfish gets higher depth was somewhat obvious but either I am wrong on the reason or wrong that it is obvious.

Part 1
In PV:
if check or if castle or if passed pawn push extend one ply

Not in PV:
if check and see_score >= 0 extend half ply

if not extended check for singular extension

It seems that a half ply extension is sufficient to not search for a potential full ply extension. Unless a lot changes in the last 4 years this few extensions in not normal.

Part 2
Futility pruning that goes down to about a half pawn in later moves in move ordering.

Part 3
LMR that is so aggressive that it makes search look 2 ply deeper than normal LMR.

Part 4
Fast evaluation that does not over dominate CPU time.

lkaufman
Posts: 4072
Joined: Sun Jan 10, 2010 5:15 am
Location: Maryland USA
Contact:

Re: Stockfish depth vs. others; challenge

Post by lkaufman » Tue Nov 26, 2013 1:55 pm

Ryan Benitez wrote:I thought the reason Stockfish gets higher depth was somewhat obvious but either I am wrong on the reason or wrong that it is obvious.

Part 1
In PV:
if check or if castle or if passed pawn push extend one ply

Not in PV:
if check and see_score >= 0 extend half ply

if not extended check for singular extension

It seems that a half ply extension is sufficient to not search for a potential full ply extension. Unless a lot changes in the last 4 years this few extensions in not normal.

Part 2
Futility pruning that goes down to about a half pawn in later moves in move ordering.

Part 3
LMR that is so aggressive that it makes search look 2 ply deeper than normal LMR.

Part 4
Fast evaluation that does not over dominate CPU time.
If we compare to Ivanhoe, the extension rules are mor stingy in Stockfish, but not way more. Maybe this accounts for a quarter ply or so. The futility pruning seems fairly similar to Ivanhoe in terms of net effect, I doubt that they differ by more than a quarter play anyway. I'll accept your estimate that SF LMR adds 2 ply. Regarding evaluation, stockfish is certainly faster than Komodo, but probably not faster (certainly not much faster) than Ivanhoe. More aggressive null move (which you didn't mention) might add another ply. So maybe we have accounted for 3.5 plies difference. But we typically see differences around 10 plies, and much more than that in endgames! So there is still a lot to explain.

User avatar
Steve Maughan
Posts: 1074
Joined: Wed Mar 08, 2006 7:28 pm
Location: Florida, USA
Contact:

Re: Stockfish depth vs. others; challenge

Post by Steve Maughan » Wed Nov 27, 2013 4:59 pm

Hi Larry,

This may or may not be related.

I have noticed Stockfish's maximum depth searched is usually much lower than other engines for any give depth of search.

For example, in this random position:
[D]r1bq1b1r/pp4pp/2p1k3/3np3/1n6/1BN2Q2/PPPP1PPP/R1B1K2R w KQ - 0 10
After 3 minutes of "thinking" Stockfish has reached the 31st ply and it's maximum depth of search is only 51 ply. This is less than double the main search depth.

In comparison Houdini 4 reaches 24 ply, with a maximum depth of 65 ply. This is about 3 times the main search depth and in-line with most engines.

Also my engine Maverick reaches (a meager) 13 ply, with a maximum depth of 45 ply. This being over three times the main search depth. I know Maverick's extensions are really quite minimal. There is only a check extensions in the main search and on the first ply of the qsearch it does captures and one reply to check, followed by winning captures after the first ply of qsearch.

So why is Stockfish's maximum depth so much less, as a multiple, than other engines? Is it better move ordering in general? Or is Stockfish somehow limiting the maximum search depth when searching high above the main search depth.

From this I conclude the shapes of Stockfish's search is a little different to most.

Any insights?

Steve
http://www.chessprogramming.net - Maverick Chess Engine

Henk
Posts: 6364
Joined: Mon May 27, 2013 8:31 am

Re: Stockfish depth vs. others; challenge

Post by Henk » Wed Nov 27, 2013 5:07 pm

In my chess program the fastest way to reach huge search depths is to increment R in both LMR and Null move. But that makes my program only play worse.

lkaufman
Posts: 4072
Joined: Sun Jan 10, 2010 5:15 am
Location: Maryland USA
Contact:

Re: Stockfish depth vs. others; challenge

Post by lkaufman » Wed Nov 27, 2013 7:50 pm

Steve Maughan wrote:Hi Larry,

This may or may not be related.

I have noticed Stockfish's maximum depth searched is usually much lower than other engines for any give depth of search.

For example, in this random position:
[D]r1bq1b1r/pp4pp/2p1k3/3np3/1n6/1BN2Q2/PPPP1PPP/R1B1K2R w KQ - 0 10
After 3 minutes of "thinking" Stockfish has reached the 31st ply and it's maximum depth of search is only 51 ply. This is less than double the main search depth.

In comparison Houdini 4 reaches 24 ply, with a maximum depth of 65 ply. This is about 3 times the main search depth and in-line with most engines.

Also my engine Maverick reaches (a meager) 13 ply, with a maximum depth of 45 ply. This being over three times the main search depth. I know Maverick's extensions are really quite minimal. There is only a check extensions in the main search and on the first ply of the qsearch it does captures and one reply to check, followed by winning captures after the first ply of qsearch.

So why is Stockfish's maximum depth so much less, as a multiple, than other engines? Is it better move ordering in general? Or is Stockfish somehow limiting the maximum search depth when searching high above the main search depth.

From this I conclude the shapes of Stockfish's search is a little different to most.

Any insights?

Steve
Stockfish does less extensions than other top engines, which would explain this. This does contribute to the high SF search depths, but I don't think we can account for the extraordinary gap just by things mentioned so far.

bob
Posts: 20896
Joined: Mon Feb 27, 2006 6:30 pm
Location: Birmingham, AL

Re: Stockfish depth vs. others; challenge

Post by bob » Wed Nov 27, 2013 8:59 pm

Steve Maughan wrote:Hi Larry,

This may or may not be related.

I have noticed Stockfish's maximum depth searched is usually much lower than other engines for any give depth of search.

For example, in this random position:
[D]r1bq1b1r/pp4pp/2p1k3/3np3/1n6/1BN2Q2/PPPP1PPP/R1B1K2R w KQ - 0 10
After 3 minutes of "thinking" Stockfish has reached the 31st ply and it's maximum depth of search is only 51 ply. This is less than double the main search depth.

In comparison Houdini 4 reaches 24 ply, with a maximum depth of 65 ply. This is about 3 times the main search depth and in-line with most engines.

Also my engine Maverick reaches (a meager) 13 ply, with a maximum depth of 45 ply. This being over three times the main search depth. I know Maverick's extensions are really quite minimal. There is only a check extensions in the main search and on the first ply of the qsearch it does captures and one reply to check, followed by winning captures after the first ply of qsearch.

So why is Stockfish's maximum depth so much less, as a multiple, than other engines? Is it better move ordering in general? Or is Stockfish somehow limiting the maximum search depth when searching high above the main search depth.

From this I conclude the shapes of Stockfish's search is a little different to most.

Any insights?

Steve
I think this is a good thing. There is a well-documented position that Crashes Fruit and makes Rybka versions misbehave, because a simple 7 ply search blows up out to 200+ plies. I posted a fix to fruit 2.1 to fix this, although no Rybka fix is possible since we have no source to modify. But 200+ plies on a 7 ply search? Nonsensical and a lot of wasted search effort. With the depths we reach today, excessive extensions are not needed at all, quite the opposite in fact.

lkaufman
Posts: 4072
Joined: Sun Jan 10, 2010 5:15 am
Location: Maryland USA
Contact:

Re: Stockfish depth vs. others; challenge

Post by lkaufman » Thu Nov 28, 2013 6:13 am

Henk wrote:In my chess program the fastest way to reach huge search depths is to increment R in both LMR and Null move. But that makes my program only play worse.
Same for Komodo. Presumably if Stockfish decreased R to Ippo-like levels in both LMR and Null move it would get weaker, else they would do that. So why can Stockfish get away with reductions that everyone else finds to be quite bad?

Ryan Benitez
Posts: 719
Joined: Thu Mar 09, 2006 12:21 am
Location: Portland Oregon

Re: Stockfish depth vs. others; challenge

Post by Ryan Benitez » Fri Nov 29, 2013 6:20 pm

I maintain that the check extension that is used in almost every chess program is a bigger overhead than people think. Even so most programs would be much weaker without it. If you reduce enough though a do not reduce is like an extension would have been only without the possibility of a search tree explosion. Some programs add search extension limits as a bandaid but Stockfish is more consistent with the idea of LMR.

lkaufman
Posts: 4072
Joined: Sun Jan 10, 2010 5:15 am
Location: Maryland USA
Contact:

Re: Stockfish depth vs. others; challenge

Post by lkaufman » Fri Nov 29, 2013 6:28 pm

Ryan Benitez wrote:I maintain that the check extension that is used in almost every chess program is a bigger overhead than people think. Even so most programs would be much weaker without it. If you reduce enough though a do not reduce is like an extension would have been only without the possibility of a search tree explosion. Some programs add search extension limits as a bandaid but Stockfish is more consistent with the idea of LMR.
I think your point is that since SF reduces more (LMR, Null move) than other engines it should also extend less to be consistent. I agree. However SF still extends non-losing checks, so this isn't radically different from other engines. I would also point out that captures are much more important in the search than checks, so even a total elimination of check extensions wouldn't justify too much more LMR unless captures are also handled differently.

elcabesa
Posts: 829
Joined: Sun May 23, 2010 11:32 am
Contact:

Re: Stockfish depth vs. others; challenge

Post by elcabesa » Fri Nov 29, 2013 9:30 pm

when you talk about selective depths what do you means?
I have always used the deepest node searched by qsearch function, but I have just noticed Stockfish uses the deepest node searched by the main search function.

Post Reply