Engines can't solve this puzzle (even not Stockfish 5)

Discussion of anything and everything relating to chess playing software and machines.

Moderators: bob, hgm, Harvey Williamson

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
Uri Blass
Posts: 8789
Joined: Wed Mar 08, 2006 11:37 pm
Location: Tel-Aviv Israel

Re: Engines can't solve this puzzle (even not Stockfish 5)

Post by Uri Blass » Thu Jul 24, 2014 11:20 am

hgm wrote:
vittyvirus wrote:I wonder why does Stockfish completely give up at this position? And why don't engines find the mate in 18 at 36 ply?
Because when strong engines such as Stockfish say they searched 36 ply, it only means they searched one selected branch 36 ply. Almost all other branchess in the tree will have been searched to only 9 ply or so. If the mate is in there (which it will be, if the branch leading to it will not in some way achieve something very good in these first 9 ply), it is still very far beyond the horizon indeed.
Not exactly.

Strong engines also have extensions so 36 plies can mean more than 36 plies in the longest selected branches.

lech
Posts: 1082
Joined: Sun Feb 14, 2010 9:02 pm

Re: Engines can't solve this puzzle (even not Stockfish 5)

Post by lech » Thu Jul 24, 2014 11:35 am

vittyvirus wrote:
lech wrote:
vittyvirus wrote:
lech wrote:
vittyvirus wrote:
hgm wrote:
vittyvirus wrote:I wonder why does Stockfish completely give up at this position? And why don't engines find the mate in 18 at 36 ply?
Because when strong engines such as Stockfish say they searched 36 ply, it only means they searched one selected branch 36 ply. Almost all other branchess in the tree will have been searched to only 9 ply or so. If the mate is in there (which it will be, if the branch leading to it will not in some way achieve something very good in these first 9 ply), it is still very far beyond the horizon indeed.
I get it now... You are a great person. Seriously. I'd love to meet you someday and talk about Micro-max and other things... :)
It means Stockfish needs 36 / 9 * 36 = 144 plies to solve it.
Why?
Stockfish has a very poor tool (code) for zugzwang positions.
And the MAX_PLY for stockfish is probably set to 120, isn't it?
Indeed, but such a high level is probably out of range for today computers to find and display a difficult solution.
Maybe the next generations of people will be able to enjoy the Stockfish's full abilities.
If you want be strong you don't need to be nice. The Elo gain (top) doesn't mean: I can solve each position now.

People love horses with tails even if it don't help to be fastest.
:D
Yes! But Stockfish 'thinks' he (or she?) has figured out 120 plies in less than a second or two on my system.
This position is full of zugzwangs, after each sacrifice of Knights, delaying by pawn moves. Practically stalemates eliminate any threats. Stockfish has a problem with value draw for zugzwang positions. It leads to such a strange result in solving (120 plies in a few seconds). In Sting (based on Stockfish 211) I solved it. Sockfish team can only use a code for ELO gain.
Maybe, I can't be friendly, but let me be useful.

User avatar
RolandoFurioso
Posts: 55
Joined: Sat Feb 22, 2014 6:29 pm
Location: Frankfurt

Re: Engines can't solve this puzzle (even not Stockfish 5)

Post by RolandoFurioso » Thu Jul 24, 2014 2:01 pm

Uri Blass wrote: Not exactly.

Strong engines also have extensions so 36 plies can mean more than 36 plies in the longest selected branches.
Sure. Typically, the search depth reported by an engine represents a "base" search depth which, however, is variation-locally modified by numerous extensions and reductions as well as a mandatory quiescence search. Hence, it is quite probable that an engine that reports a depth of 36 plies might search even somewhat deeper for selected lines of play, while, for the broad majority of variants, it will perform merely a quite shallow search significantly below 36 (or even 10) plies.

As far as I see, Stockfish doesn't find the solution in the discussed position simply because it doesn't consider underpromotion in its selective lines of search; there are no zugzwang / null-move-pruning-related issues here.

That Stockfish doesn't succeed in this very position while various other not-so-strong engines quickly find the mate in 18 does definitely *not* mean that we should consider this a weakness that should be eliminated in follow-up versions of Stockfish. Precisely the highly optimized extension / reduction strategy enables Stockfish to play as strong in regular matchplay as it does. It probably wouldn't be a big issue to alter Stockfish in a way that it solves such positions in a few seconds; the price, however, would be high in terms of a significantly reduced playing strength in "usual" matchplay positions.

S.Taylor
Posts: 8461
Joined: Thu Mar 09, 2006 2:25 am
Location: Jerusalem Israel

Re: Engines can't solve this puzzle (even not Stockfish 5)

Post by S.Taylor » Thu Jul 24, 2014 3:31 pm

I now watched the whole thing. I like it!!!!

I don'y know which colour is israel and which colour is Hamas or which colour is the human shields, but for chess it is fine.

I want to know, if there IS enough depth of search by an engine, either now, if left for long enough to search to the right depth, or, in a future time,
then will the engine surely find it?
If it does, are we sure it won't find something better also?

S.Taylor
Posts: 8461
Joined: Thu Mar 09, 2006 2:25 am
Location: Jerusalem Israel

Re: Engines can't solve this puzzle (even not Stockfish 5)

Post by S.Taylor » Thu Jul 24, 2014 3:34 pm

But come to think of it, this chess problem was not ALL that difficult and unimaginable.
Black was totally paralyzed, so it was 100% dictated where he had to move.

I wonder if there are any positions as great looking as that, but where black is NOT paralyzed? (which would be a million times greater).

Uri Blass
Posts: 8789
Joined: Wed Mar 08, 2006 11:37 pm
Location: Tel-Aviv Israel

Re: Engines can't solve this puzzle (even not Stockfish 5)

Post by Uri Blass » Thu Jul 24, 2014 6:37 pm

RolandoFurioso wrote:
Uri Blass wrote: Not exactly.

Strong engines also have extensions so 36 plies can mean more than 36 plies in the longest selected branches.
Sure. Typically, the search depth reported by an engine represents a "base" search depth which, however, is variation-locally modified by numerous extensions and reductions as well as a mandatory quiescence search. Hence, it is quite probable that an engine that reports a depth of 36 plies might search even somewhat deeper for selected lines of play, while, for the broad majority of variants, it will perform merely a quite shallow search significantly below 36 (or even 10) plies.

As far as I see, Stockfish doesn't find the solution in the discussed position simply because it doesn't consider underpromotion in its selective lines of search; there are no zugzwang / null-move-pruning-related issues here.

That Stockfish doesn't succeed in this very position while various other not-so-strong engines quickly find the mate in 18 does definitely *not* mean that we should consider this a weakness that should be eliminated in follow-up versions of Stockfish. Precisely the highly optimized extension / reduction strategy enables Stockfish to play as strong in regular matchplay as it does. It probably wouldn't be a big issue to alter Stockfish in a way that it solves such positions in a few seconds; the price, however, would be high in terms of a significantly reduced playing strength in "usual" matchplay positions.
I think that you simply do not understand stockfish.

Stockfish does not see it because of very aggresive null move pruning and the problem is not only zugzwangs(so even with zugwang detection it has no chances.

The problem of null move pruning prevent stockfish to see even mate in 6 in a reasonable time because even at depth 100 it may search some line of

move A null move B null move C null move D null move E prune when practically you need also move F to see the mate.

The problem is that stockfish reduce 1/4 of the nominal depth+some plies after every null and it means that you easily can get from depth 100 only depth 100*3/4-10 after the first null that is 65 plies

If you continue by this formula you get

100
100*3/4-10=65 plies after null A
65*3/4-10=38.75 let say 39 plies after null B
39*3/4-10=19.25 let say 19 plies after null C
19*3/4-10=4.25 let say 4 plies after null D


There is also the zugwang problem because if black has the right not to move and has the right to claim draw by stalemate if it has no legal moves then I do not see how white wins.

How do you win after 1.axb8=N c3 2.Na6 null?

Edit:
I can add that I also disagree with you that it is not a weakness of stockfish not to solve the position.

It is clearly a weakness of stockfish.
The fact that fixing it by using the same chess algorithm of weak chess engines cost elo does not mean that it is impossible to fix the problem in a productive way that only earn elo.

I feel sure that it is possible and people simply did not find the right way.

User avatar
RolandoFurioso
Posts: 55
Joined: Sat Feb 22, 2014 6:29 pm
Location: Frankfurt

Re: Engines can't solve this puzzle (even not Stockfish 5)

Post by RolandoFurioso » Thu Jul 24, 2014 11:14 pm

Uri Blass wrote:
RolandoFurioso wrote:
Uri Blass wrote: Not exactly.

Strong engines also have extensions so 36 plies can mean more than 36 plies in the longest selected branches.
Sure. Typically, the search depth reported by an engine represents a "base" search depth which, however, is variation-locally modified by numerous extensions and reductions as well as a mandatory quiescence search. Hence, it is quite probable that an engine that reports a depth of 36 plies might search even somewhat deeper for selected lines of play, while, for the broad majority of variants, it will perform merely a quite shallow search significantly below 36 (or even 10) plies.

As far as I see, Stockfish doesn't find the solution in the discussed position simply because it doesn't consider underpromotion in its selective lines of search; there are no zugzwang / null-move-pruning-related issues here.

That Stockfish doesn't succeed in this very position while various other not-so-strong engines quickly find the mate in 18 does definitely *not* mean that we should consider this a weakness that should be eliminated in follow-up versions of Stockfish. Precisely the highly optimized extension / reduction strategy enables Stockfish to play as strong in regular matchplay as it does. It probably wouldn't be a big issue to alter Stockfish in a way that it solves such positions in a few seconds; the price, however, would be high in terms of a significantly reduced playing strength in "usual" matchplay positions.
I think that you simply do not understand stockfish.

Stockfish does not see it because of very aggresive null move pruning and the problem is not only zugzwangs(so even with zugwang detection it has no chances.

The problem of null move pruning prevent stockfish to see even mate in 6 in a reasonable time because even at depth 100 it may search some line of

move A null move B null move C null move D null move E prune when practically you need also move F to see the mate.

The problem is that stockfish reduce 1/4 of the nominal depth+some plies after every null and it means that you easily can get from depth 100 only depth 100*3/4-10 after the first null that is 65 plies

If you continue by this formula you get

100
100*3/4-10=65 plies after null A
65*3/4-10=38.75 let say 39 plies after null B
39*3/4-10=19.25 let say 19 plies after null C
19*3/4-10=4.25 let say 4 plies after null D


There is also the zugwang problem because if black has the right not to move and has the right to claim draw by stalemate if it has no legal moves then I do not see how white wins.

How do you win after 1.axb8=N c3 2.Na6 null?

Edit:
I can add that I also disagree with you that it is not a weakness of stockfish not to solve the position.

It is clearly a weakness of stockfish.
The fact that fixing it by using the same chess algorithm of weak chess engines cost elo does not mean that it is impossible to fix the problem in a productive way that only earn elo.

I feel sure that it is possible and people simply did not find the right way.
Thanks a ton for these kind and educated instructions, Mr. Blass! I am absolutely convinced that your numerological exercises will prove illuminative and truly helpful to the vast majority of us.

Now that it's totally clear to all of us who is the unchallenged expert in this very field, let me just humbly ask whether this very expert could proceed and devise the appropriate minor enhancements that fix this unexcusable "weakness" of our top-scoring engine Stockfish while not touching any other aspects of its strength.

Just one further modest hint: in doing so, this expert might be well advised not to recur to the well-documented standard algorithms at any circumstance, as these techniques are presumably employed by "weaker" chess engines as well, which might negatively interfere with the overall lustre of his efforts ... .

zullil
Posts: 6442
Joined: Mon Jan 08, 2007 11:31 pm
Location: PA USA
Full name: Louis Zulli

Re: Engines can't solve this puzzle (even not Stockfish 5)

Post by zullil » Fri Jul 25, 2014 10:43 am

Uri Blass wrote: I think that you simply do not understand stockfish.

Stockfish does not see it because of very aggressive null move pruning
Can you post output from Stockfish (with null move pruning modified) that shows the mate being found. I assume you can modify the source code as needed to make the null move pruning less aggressive, and then compile your own binary.

zullil
Posts: 6442
Joined: Mon Jan 08, 2007 11:31 pm
Location: PA USA
Full name: Louis Zulli

Re: Engines can't solve this puzzle (even not Stockfish 5)

Post by zullil » Fri Jul 25, 2014 10:59 am

Uri Blass wrote:
The problem of null move pruning prevent stockfish to see even mate in 6 in a reasonable time because even at depth 100 it may search some line of

move A null move B null move C null move D null move E prune when practically you need also move F to see the mate.

The problem is that stockfish reduce 1/4 of the nominal depth+some plies after every null and it means that you easily can get from depth 100 only depth 100*3/4-10 after the first null that is 65 plies

If you continue by this formula you get

100
100*3/4-10=65 plies after null A
65*3/4-10=38.75 let say 39 plies after null B
39*3/4-10=19.25 let say 19 plies after null C
19*3/4-10=4.25 let say 4 plies after null D
Is seldepth = 4 in the following output from Stockfish evidence that supports your explanation? It seems to mean that even at depth 120, no line was searched to more than depth 4.

Code: Select all

info depth 120 seldepth 4 score cp 0 nodes 6891549 nps 3233950 time 2131 multipv 1 pv a7b8q c4c3 b8b7

Uri Blass
Posts: 8789
Joined: Wed Mar 08, 2006 11:37 pm
Location: Tel-Aviv Israel

Re: Engines can't solve this puzzle (even not Stockfish 5)

Post by Uri Blass » Fri Jul 25, 2014 11:12 am

zullil wrote:
Uri Blass wrote:
The problem of null move pruning prevent stockfish to see even mate in 6 in a reasonable time because even at depth 100 it may search some line of

move A null move B null move C null move D null move E prune when practically you need also move F to see the mate.

The problem is that stockfish reduce 1/4 of the nominal depth+some plies after every null and it means that you easily can get from depth 100 only depth 100*3/4-10 after the first null that is 65 plies

If you continue by this formula you get

100
100*3/4-10=65 plies after null A
65*3/4-10=38.75 let say 39 plies after null B
39*3/4-10=19.25 let say 19 plies after null C
19*3/4-10=4.25 let say 4 plies after null D
Is seldepth = 4 in the following output from Stockfish evidence that supports your explanation? It seems to mean that even at depth 120, no line was searched to more than depth 4.

Code: Select all

info depth 120 seldepth 4 score cp 0 nodes 6891549 nps 3233950 time 2131 multipv 1 pv a7b8q c4c3 b8b7
No

After modifying the code and changing line 473 and deleting PvNode from the following code I get seldepth 60 at depth 120 so stockfish searchs 60 plies in the longest line when I do not include qsearch nodes

if (PvNode && thisThread->maxPly < ss->ply)
thisThread->maxPly = ss->ply;

Post Reply