Chess will never be solved, here's why

I think I can foresee a counter-objection to that, in @tygxc style, but I will leave it up to him .

@Elroch

Why do you say the blunder rate will become small as the think time increases? 

SF is not thinking. It's following an algorithm with an imperfect evaluation function. How do you prove its blunder rate will uniformly decrease with increased depth if the depth doesn't reach the minimum forced mate depth for some candidate moves?

When I tried it out it had nearly 16 times the blunder rate at four and a half minutes think time than it did at 1 second's think time from the same position under basic rules (though only 1.75 times the rate in the competition rules game for which the evaluation function is designed).

I used to have a version of Rybka running on office surplus kit around 2005. It had an 'e' on the end of its version number meaning they'd gone to special lengths to strengthen its play in various endgames without using a tablebase. It could do KNNKP mates in 50. The stockfishes crap out at a maximum of between 30 and 35 moves depending on the pawn position and SF version.

The evaluation function is, I believe, far more important than the machine speed.  You can't make a silk purse out of a sow's ear, as my father used to say.

I don't understand that empirical claim if it is assumed to be general. More computing time should typically be better if used sensibly. The reason is simply that you replace the bare evaluation function by an evaluation based on some exploration of moves that are likely to be good. Generally this increases the accuracy of the evaluation.

(A minor point is that traditional chess engines use a silly scale for evaluation, based on pseudomaterial. Obviously better is to use outcome probabilities. In this case the future exploration should reduce the cross entropy loss in general, according to all common sense.

Note that the fact that using the bare evaluation function to pick moves is inferior to using a little time to explore future possibilities, and that that the improvement should be monotone in the amount of time for a small amount of time seems to directly imply the result that more time is always better. My loose reasoning is that what adding more time does is add more exploration to little explored nodes (especially leaf nodes).  Of course it also includes exploring low ranking candidates for nodes nearer to the root, but again it is difficult to see how this could ever not be an improvement.

If your claim was true in general (rather then, as I believe, in extremely long mating endgames) when Stockfish played with 4 minutes a move, it would do better to use 1 second.

But the truth is that giving Stockfish more time helped it against AlphaZero (not perfect, but a pretty good detector of blunders).

[Note that it could be that having a very long mate might be associated with some odd characteristics of the optimal line which made it very untypical in the view of Stockfish. I am not sure exactly how, but some way that makes more time detrimental!]

If I had an engine which was designed to beat other engines, I would wish it to create complex positions, with as few forcing moves as possible and to aim for positions where always a high percentage of the opponent's moves will create a tiny weakness. They aren't forcing moves, because the weaknesses will be imperceptible and available only to a faster engine with a broader search, which typically goes two ply further in a broader search. That can only be achieved by using better assessment algorithms, which are designed to detect lines where there's a tendency towards complexity, rather than a brute force search which prioritises the obvious.

That's how it would be designed to win, anyhow. If the opponent made a slight error every ten moves, a winning advantage would eventually appear. Just like in human play.

GUYS JUST STOP

What is at least intuitively feasible is that this is a sort of bias-variance trade-off. A bare evaluation is wrong (it misses stuff that happens later), but it has low variance - there is no error due to selecting future analysis lines. Analysis of future lines provides you with a sample from which you might, for example, extract the critical line, a min-max and evaluate its terminus.

This would increase the variance of your estimate of value because of the incompleteness of the sample from future lines which will presumably have terminal values which have scatter (and a mean which on average would be similar to the bare evaluation).   If the analysis was thorough (think tablebase), it would always be an improved evaluation, but when it is a sample, it has randomness in the value provided. We have seen this in the curiosity of Stockfish believing the evaluations of promotion to rook or queen are different, despite also believing the best response is to capture the promoted piece.

IMHO, this problem can only occur as a result of the suboptimality of the algorithms used by Stockfish.  When it would go wrong is when the analysis of a node is inadequate, and the random selection of future lines happens to have a misleading fluke.  The way this could be corrected is that the algorithm for evaluation only gives slight credit to such an analysis. Instead of using the min-max value (which would later turn out to be based on believing the wrong move is the best one), the algorithm would use some weighted combination of the bare evaluation and the evaluation of the deeper lines. With sufficient weight to the bare evaluation, the variance would be reduced because halving the weight for the deeper evaluation reduces the variance due to this by a factor of 4. Some weight would still achieve a better evaluation than either the bare one or the min-max one.

It is possible that Stockfish already does something like this - I really don't know. (Another possibility is that the evaluations of all nodes are incorporated in a way related to how likely they are to be critical).

If so, it could simply be that it was doing it in a way which is on average good but deals badly with the sorts of position you analysed (one of which was a very deep tablebase mate, I believe?)

@Elroch

I chose the endgame because of the number of zugzwangs. I didn't think I'd see any effect on my desktop otherwise. So, yes, it was chosen to provoke SF into dealing badly with it.

On the other hand I think the majority of @tygxc's processing time would eventually be spent in such positions. The mate is not very long even for KNNKP in the basic rules game at 85 moves, but I thought with @tygxc's Schrödinger's 50 move rule, I should keep it possible in the competion rules game. Three trillion moves - now that would be long.

By the way, the minimax pathology is not specific to chess. Nau demonstrated it in some specially constructed games where it was possible to prove the effect. It's apparently a potential problem with the algorithm in general as far as I know. But I'm no expert - I've only just started looking at this stuff.

Are you aware of the algorithms used by Stockfish? I would find it much easier to develop an improvement to min-max with an evaluation which is probability based (essentially with the aim of finding the best compromise between bias and variance).

For anyone who has no idea what all this "bias-variance" stuff is, it comes from machine learning algorithms, but I believe I am correct in saying that the concept applies to the ad hoc evaluation algorithms used to generate a tree of variations and then derive an evaluation from that tree. Such an algorithm can be viewed as a model which tries to estimate the true value with optimal play and which uses the empirical data which comprises (some subset of) the legal continuations (plus another ad hoc model which provides bare evaluations of positions).

If you look at an article on the bias-variance trade-off, it's worth noting that chess has no irreducible error because it is a game of perfect information with a definite result.

from @Elroch
 "In truth, @tygxc is assuming incorrectly that he knows how much time Stockfish needs to achieve perfection. Far more likely is that this is the amount of time needed to blunder P% of the time, where P is small but non-zero."

That looks well said.  Key.

We also got this - from @MARattigan
"SF is not thinking. It's following an algorithm with an imperfect evaluation function."
Also key.  With the central word there being 'imperfect'.

If one compares the two assertions -
they appear to be in agreement with each other. 
'blunder' and 'imperfect'.

I imagine many of the supercomputer or super-engine 'blunders and imperfections' are actually inferior positional moves - rather than tactical blunders.

60 hours or 72 hours of chess @ifem`s is right

or 94 or 83 mins of chess with @ifemo

#2035

"You think that Stockfish makes no more than one losing error in every 100,000 moves"
++ I infer that by extrapolation from the peer reviewed Alpha Zero paper. I know the published error rate at 1 s/move and 1 min/move and extrapolate to 1 h/move and 60 h/move and thus arrive at 1 error of the top 1 move per 10^5 positions. Thus I conclude that including the top 2, top 3, top 4 moves should lower this to 1 error per 10^20 positions, which is more than the expected search space of 10^17 positions.

yeah

#2052

"I chose the endgame because of the number of zugzwangs."
"the majority of @tygxc's processing time would eventually be spent in such positions."
++ Zugzwang is typical for endgames and thus happens more after the table base is hit. There are a few famous Nimzovich games with middle game Zugzwang, but those are rare exceptions.
As said earlier the errors are because of the failure of the evaluation function. Winning the pawn in KNN vs. KP is drawing.
"Three trillion moves - now that would be long."
++ There is less evidence that a 3 trillion move checkmate exists than that the Loch Ness monster, the Spaghetti Monster, or Martians exist. From GM and ICCF games I rather tend to believe that a forced 3-fold repetition or table base draw can be reached in 50 moves.

By including three more candidate moves -
errors thus get divided by 1000 trillion ??
looks like another Leap !  

"error" might be poorly defined too.
Does a supercomputer really 'know what its doing' in chess ?
Its a paradox.
People would say yes - because it beats the world's best human players.
But its also no - because the computer is only following formulaic instructions from human programmers.
In tactical situations - supercomputers would be great.  Fantastic.
But what about 'positional' ?
Insisting the computer - in picking 'best move' only makes a 'mistake' once every 100,000 moves ?   In relatively 'positional positions' ?
Doesn't make sense.
There may be several 'best' moves in such positions.
And several 'second rate' moves.  
The computer is assigning numerical differences to evaluate positional moves according to obscure minor technical points which may have little to do with 'best move'.  

Edited moderator SB 

No advertising 

And I repeat - finding 'best move' in unsolved positions - is dubious at best.
The opening position is unsolved.
Computers cannot solve it at millions of 'nodes per second' ...
the positions generated from it are also unsolved. - also cannot be 'solved' at whatever 'nodes per second'.  And so on.

Arguing that 'best move' is found accurately in 99,999 out of 100,000 unsolved positions is ridiculous.
That might work in some short already-solved tactics puzzles ....
But if a position isn't solved - it can also be argued that much of the time if not most of the time - the best move just isn't known.
Nor the best four moves.
Especially since most unsolved positions - continue to be Just That !
Unsolved !  

"Circular argument" 
"oh the computer finds best move in an unsolved position - so therefore since it 'found that move' it follows that the position is therefore now 'solved"  (in positions where the best move can't be known because it isn't solved)