Chess will never be solved, here's why

You're probably asking the wrong person.

I only came across minimax pathology since the thread started and I've never studied game theory or AI.

I'll think about it but don't expect a quick answer.

@MARattigan
I've got a question about that nice graph - but first ...
as usual - you make the best posts !   Really !  

Do/did you notice that on the left side of the graph -
in your post #2522
it heads up to '120%'   ?
There's probably a fully rational explanation - but it escapes me for now.

It's just the Wolfram widget doesn't know I'm giving it percentages. 

It chooses the axes according to some clever algorithm.

(But at 0 it would be 0/0 so you could take that as 120.)

OK.  I think I get it.  The graph didn't come from the Namilov site.
You constructed it from their figures.
Which is very impressive.  Especially to a layman like me.
The shape of the curve looks significant.
Conjures up in my mind:
is it hyperbolic?  logarithmic?  doesn't look very parabolic -
and not asymptotic either.  Wouldn't be that last one anyway.

(and I put the Szygy link you kindly posted - into my Home page notes.  (they're Choked with links.  Lol ! )

It's exponential (with negative index). Logarithmic if you look at it the right way. Definitely not a conic.

Interesting bit of analysis.  Is the variation across the 4 to 7 man tablebases mostly explained by the increasing variance of the material difference?

Intuitively, I would say the uncertainty in the extrapolation would be well over 10% long before 32 pieces  at that level and a reasonable model would tell you no more than that the value is fairly low and very uncertain past not much more than 12 pieces. (I am basing this on doing things like Baysian extrapolation using simple models like a polynomial.  Extrapolation is generally hazardous and especially with small data. This is exacerbated because odd and even numbers differ enough to make the points noticeably wiggle in the range you have data for.

The variation is, to me, counter intuitive. A pawn difference is a smaller percentage of the total material value as the number of men increases.

It does fit in with the accepted situation in pawn endings though.

I'd agree with your last para.

It would be my best guess, but it is a wild guess.

Exponential !  And not a conic section.  More progress.
That whole business of how the draw ratio varies might be worth more attention !  
I was specifically thinking of the tablebases of course -
but anyway - this area of inquiry ... is it a 'heuristic'?
I don't think so.  I think its a kind of progress.

@playerafar

But the exponential bit is only a guess. I put that bit in, not Nalimov or Wolfram.

?

I posted a reply to this.  But it refused to post.
So I'll try to post again.
Yes - if there's only a few figures to form the graph - then its hardly 'representative'.
But I'm thinking the Nalimov people and the other tablebase people would be monitoring the draw percentage very closely versus other variables.
Not 'games that ended in draws' - but tablebase positions solved as 'won' positions whether checkmate or not - versus 'drawing' positions whether drawn yet or not.  
Up to and including all 7 piece positions.
There would also be 8 piece.  Maybe some categories are finished already.
Regarding those that aren't - it could be remarkable how the ratios work on those positions that have been 'solved'.   
Could be - but also could be Misleading.
Because with only some of the positions solved at each piece level - then the win ratio would be tainted.  'Arbitrary'.
But there's a workaround for that.
Solve as MARattigan suggested.
With minimal differences of material.
That's a nice Cutdown !
But another one - is to select particular piece/pawn arsenals for each side - and then the computer completely solves all of those in that category ! 

But can even that be done ??

Note that with 8-piece - you couldn't have a difference of one in number of pieces Each !!
So how many years would it take for example to solve All knight and two pawns versus two knights and a pawn ?
We wouldn't have the foggiest idea from whoever talking about 'nodes per second' combined with 'consider'.  

But maybe Nalimov has already solved some.
Or maybe we can look up various situations in 7 piece and see what the drawing/drawn ratio is  (no not 'agreeing to a draw').  Real drawing drawn.
That 'nodes per second/'consider' is a big turn-off ...
it could be discouraging to go to websites that use cosmetic terms.
but if the information is directly available ...

Shorter reply this time.
Maybe one could look up percentage of drawing/drawn  in say ...
knight and two pawns versus knight and one pawn?
That's a seven piece situation.

#2519

"Do you not mean 0%?"
++ No, I mean 99% of ICCF WC drawn games are ideal games with optimal moves.
0% of these games reach 50 moves without capture or pawn move.

"SF14 didn't manage any ideal games from the much simpler starting position here."
++ The evaluation function of SF14 is no good for KNN, or fortresses.
The purpose of the evaluation function is to calculate and hit its endgame table base.
Stockfish defeated LC0 with a simpler evaluation function because it hit the table base earlier.

"The moves in the ICCF games are probably all by either SF14 or something that would usually lose to SF14." ++ No, a player who just copies SF14 moves would lose all games in an ICCF WC. We are talking about human ICCF grandmasters working 5 days/move with several engines.

"You don't say what percentage of the ICCF games consisted solely of ply count 0 positions."
++ I say 100% of ICCF WC games consist of games with a 50 moves counter < 50.

"Which specific rules would those be?" ++ The FIDE Laws of Chess.

"no winning positions under basic rules that are not also won under competition rules"
++ It does not matter.
The 50 moves rule gets never invoked before the 7-men endgame table base is reached.

"With 6 men on the board 0.86% of such basic rules winning positions cannot be won under competition rules." ++ That is irrelevant: positions of 7 men or less are looked up in the 7-men endgame table base.

"With your unique gift you can extrapolate from those two data points to prove the figure is 0% with 8 or more men on the board." ++ You cannot extrapolate like that. Nobody says your positions can be reached from the initial position by a reasonable game with > 50% accuracy in the first place.

"as long as Haworth's law holds good."
Haworth's law is no law at all, but rather a wild and erroneous speculation.
1) per Gourion and Tromp chess is most complicated at 26 men so you cannot extrapolate to 32.
2) If you extrapolate likewise the total number of positions in the Syzygy endgame table base for 2, 3, 4, 5, 6, and 7 men towards 32 or 26, then you get a number much more than there are positions.
3) There is no proof or even indication that those hypothetic unicorn positions with long checkmates can result from the initial position by a game with >50% accuracy.
Who was/is Haworth anyway? Steinitz, Lasker, Capablanca, Fischer, Adorjan, Kramnik all said the contrary: "chess is a draw"

"I have to choose positions that are tablebased otherwise I can't prove the SF14 choices are errors." ++ Yes, that is right. But if you want to say something about positions with 8 - 26 men, then chose a position with 7 (or even 8) men at the boundary.

"SF14 does worse with more men." ++ No SF14 is optimised for more men, for 7 men or less it just consults its endgame table base. It is like a human who does not know any endgames, but is allowed to consult an endgame manual.

"It's "misjudging" them under your new rules" ++ I have no new rules, I use Laws of Chess as they are. I just remark that the 50-moves rule is never invoked in ICCF WC games considered ideal games with optimal moves and thus that rule can be ignored.

"Representative of what? Games at your local chess club or perfectly played games?"
++ Representative for ideal games with optimal moves, like ICCF WC draws.

"If the starting position is a win for one side, as seems likely"
++ That is not likely at all.

"perfect play could easily be a game of millions of moves" ++ That is an erroneous fantasy.

"You probably don't see many of those at your local chess club either."
++ All ICCF WC games are over in at most 100 moves. 

Imperfect player guesses that game is perfect (and claims guess to be completely reliable).

Now I think I understand it, your graph casts doubt on an intuitive claim of mine about how often random positions are draws.  It would be very useful to do one more piece of analysis - break the results down further by who has the first move. It could be that as the piece numbers increase in random positions, the value of the move grows because there is usually something to capture or win.

Would it be easy to refine your analysis in this way?

Only writ smaller. I suspect that  the participants in this epic debate know their stuff, at least some of them anyhow. 

Interesting question. I don't expect to do better than you, MARattigan or anybody else in answering that (as you know, DeepMind researchers have hypothesized that MCTS is not affected by the minimax pathology, because to weight nodes it averages on many outcomes). The question raises other two, though, as you point out: how much an evaluation based on heuristics can be close to the true value of a node? If the evaluation is coupled with a search, can the evaluation become closer to the true value of the root node, increasing the depth and/or the number of nodes searched?
I think we should differentiate between evaluation accuracy and decision accuracy, in the way Bratko et al. did. "Better" could have two distinct meanings: 1) closer to the true value of the node; 2) giving a better expected score in a non-weakly-solved game starting from the node. The two values might not be necessarily identical, but for sure increasing the number of nodes searched makes an engine stronger (about 50 rating points, doubling the number of nodes). There are different hypotheses on why that happens even with pathological trees; I have mine, but still need to work on it.

Failing to follow the argument, I'm afraid.

I downloaded the Syzygy JSON files then selected only endgames with a notional difference of less than a pawn, totalled the number of positions that are draws, frustrated wins and wins into separate buckets for each number of men, then, for the basic rules game, calculated, for each number of men, n, the ratio (Σwinsₙ+Σfrustrated winsₙ)/(Σdrawsₙ+Σwinsₙ+Σfrustrated winsₙ) with the sums taken over the selected endgames with n men (the contents of the buckets).

That gave me

USING UNCORRECTED SYZYGY POSITION COUNTS:

Game BR
Endgames with material difference at most 1 pawn(s)

# men additional to kings=0
total ESMs: 1
win % =0.00

# men additional to kings=1
total ESMs: 1
667692 winning out of 994056
win % =67.17

# men additional to kings=2
total ESMs: 6
20096412 winning out of 73668036
win % =27.28

# men additional to kings=3
total ESMs: 34
15031957290 winning out of 36932117436
win % =40.70

# men additional to kings=4
total ESMs: 52
1262729602320 winning out of 2598590952432
win % =48.59

# men additional to kings=5
total ESMs: 238
423497287507506 winning out of 730124977157238
win % =58.00

The total number of positions shown is the total of only positions that have at most a pawn discrepancy.

The number of wins naturally increases with the number of men, but I don't follow why you would expect the ratio of wins to increase.

Edit: @Elroch - Interleaved this with reading your post here. Yes, we are in agreement (piece values as you surmised). I'll do the further analysis.

The weighting of nodes instead of pure minimax is the way I was thinking of dealing with it. The problem is how much to prefer moves.

A popular modern reinforcement learning paradigm that is distinct from the Q-learning used by DeepMind is the Actor-Critic paradigm.  In this you would have two classes of output. The first is the value of a position or move - the expected score. The second is the policy, which indicates the probability that you will play a particular move.  Minimax effectively uses a policy which is determined by always playing the move with highest expected score, which fails to allow well for uncertainty about what move is best.

Such models are trained in tandem, with the policy network being adjusted to increase the expected evaluation -  to be expected to be wrong less often - and the evaluation network being adjusted so each evaluation is closer to the evaluation found by applying the policy and generating a weighted sum of the evaluations of the positions reached after the various moves.

EDIT: actually DeepMind used something more like this than Q-learning - they did compare the results with Q-learning,  but they used a policy based an analysis tree that looked deeper than one step at each iteration.  I presume they randomly sample from the tree based on the policy.

Mmmh... The evaluation may be less biased than Q-learning, but if the evaluation is less biased, you need more training and/or more search after the training, so it's always a trade-off. Idk wether it would be more effective to solve chess. It's always the bias-variance dilemma, NFL... you know .

The paper you reference is about MuZero, which is based on A0 (but it does not outperform the latter). For A0, It seems that Q-learning is not suited for NN, right? So they replaced the discount factor γ and a temporal-difference learning, with a learning based on a modified MCTS search. The Lc0 team calls this search PUCT (Predictor + Upper Confidence bound Tree search), rather than MCTS. Basically, "each search consists of a series of simulated games of self-play that traverse a tree from root state sᵣₒₒₜ until a leaf state is reached" ¹ (italic mine). Moves for each simulation are selected according to the current NN, which uses two parameters: a probability vector for the moves to be played (the policy) and the predicted value for the node. The search returns another vector of probabilities for the moves to be played. During learning, these games are played until a terminal node (the end of the game) is reached, where a definitive score is assigned to the root node. At this point the parameters used by the NN (the policy vector p and the predicted outcome v) are updated to minimize respectively the difference with the probability vector resulting by the search and the outcome of the terminal node. So at the beginning the search is random, but every time a terminal node is reached, the parameters are refined. During the search, moves with a combination of high probability, high value and low visit count are selected more.

So it does resemble very much an Actor-Critic learning.

But choosing a move because it has a higher probability to be played, or an average better score, is nevertheless an heuristic.

¹ https://arxiv.org/pdf/1712.01815.pdf