Chess will never be solved, here's why

Sort:
Avatar of ifemo

اثممخ

 

Avatar of tygxc

#1989

Dear @haiaku,

"If I understand you well, to find those 4 candidate moves for a colour and be sure the best move is among them, you would leave SF analyse 60 hours. Then, you should leave SF analyse the position for each of those candidates to find the best 4 options for the other colour, and so on." ++ No, not exactly. I do 4 candidate moves for white only, I do 1 candidate move for black. I store intermediate results for later reference so as not to duplicate the same calculation.
"So to move from depth n to depth n+1 (in plies) you should use 4*60 hours. How many hours to reach the endgame after, let's say, 20 moves?"
++ I do not start at move 1, but rather at the 26-men tabiya. 1 hour = 3600*10^9 positions. Based on ICCF games I guess that most positions terminate in a draw by 3-fold (or 2-fold) repetition before. You can see data on table base hits and nodes/s in the TCEC superfinals.

Avatar of tygxc

#1990
"Just let the strongest computer find one best move for each position - play itself that way - and play the game through to conclusion and see what the result is.
If it turns out to be draw - then many can raise both hands very high and proclaim "You see??  This proves chess is a Draw with best play.  It is Written !"
++ That is not proof yet, that is begin of proof. The autoplay game ending in a draw is a candidate ideal game. Black's moves are optimal, as the result is a draw. It rests to prove that white's moves are optimal too. That is done by retracting all white moves from the last to the first and replacing them with the 2nd choice, then the 3rd choice, and finally the 4th choice so as to ascertain that all white's moves are optimal too.
#1993
"If computers isolate just two candidate best  moves at each ply (half move) - and then go ahead and play both - in separate games ...
to see where the results lead ...  then after fifteen full moves you're going to have 2 raised to the 30th power ...  games !   "
++ As explained before, I only go for 4 white alternatives and 1 black alternative.
Moreover, in chess there are many transpositions: different games that lead to the same position. E.g. 1 e4 e5 2 Nf3 Nc6 = 1 e4 Nc6 2 Nf3 e5 = 1 Nf3 Nc6 2 e4 e5

Avatar of haiaku
tygxc wrote:

I do 4 candidate moves for white only, I do 1 candidate move for black. I store intermediate results for later reference so as not to duplicate the same calculation.
I do not start at move 1, but rather at the 26-men tabiya. 1 hour = 3600*10^9 positions. Based on ICCF games I guess that most positions terminate in a draw by 3-fold (or 2-fold) repetition before. You can see data on table base hits and nodes/s in the TCEC superfinals.

I didn't imply you have to start at move 1, but from a 26-men position you would need some moves to reach the endgame, right? So, you check only one candidate move for Black... and that should be enough to find her optimal strategy?

tygxc wrote:

 It rests to prove that white's moves are optimal too. That is done by retracting all white moves from the last to the first and replacing them with the 2nd choice, then the 3rd choice, and finally the 4th choice so as to ascertain that all white's moves are optimal too.

The question still remains: even with only one option for Black and 4 for White, but 60 hours spent to determine those 4 candidates when White has to move, how many hours to build the proof tree?

Avatar of MARattigan
playerafar wrote:
MARattigan wrote:

@playerafar

A position with e.p. and a position with not e.p. is still uniqueness on the board if they have the same diagram. Chess works by positions, not diagrams.

 

...
What isn't contributing to board uniqueness and solving is how many repetitions of position have occurred - and how many 'moves of 50' have happened.
If there's a mate available then there's a mate available.
If there isn't there isn't.  

...

That is exactly where your'e going astray. Did you try mating in the position here?

Try it again here


Same diagram, same player to move, but under competition rules, which the analysis board enforces, there's a mate available in one and there isn't a mate available in the other. 

A position in the competition rules game is a FEN (board layout, side to move, castling rights, possible e.p. square and ply count - which must be 0) plus the moves from the ply count=0 FEN. (That is also what SF requires to function correctly).

Now try these two positions in analysis. Same board layout, same side to move (and both fully specified from ply count 0)


 

So, is there a mate available?

Or is there isn't?

Avatar of Elroch

In my "simplified rules", reaching a repeated position is an automatic draw. This seems not to remove anything game theoretically significant, as if you have a win there is no point in repeating a position or giving your opponent the opportunity to do so unless you have been inaccurate up to that point.

Avatar of mercatorproject

What is the point of your last caveat? You are usually crystalline in your clarity.

Avatar of Elroch

Nothing deep.

It simplifies the understanding of the role of 3-fold repetition in solving chess. Basically a repetition of a position is admission of a draw (or grabbing of a draw - technically the same thing). There is also some redundancy in the drawing rules for theoretical purposes. Any analog of the 50 move rule will suffice without a repetition of position rule (since any number of moves will be exceeded by optimal play that has no better than to repeat). The reverse is only true when the N-move rule does not interfere with it being possible to achieve all basic rules tablebase wins.

Just stating simple facts (I hope) out loud.

Avatar of mercatorproject

"or giving your opponent the opportunity to do so unless you have been inaccurate up to that point."

I was asking about that bit.

Avatar of playerafar


@MARattigan -
I don't think I'm 'going astray' -
but - I don't get it - what you're trying to say here.
If there's a mate available - in whatever number of moves - then its mate available.  Mate is mate.
And mate available - is 'solved'.

You can argue that it isn't if you want.
Because of 'moves of 50' but if you're going to do that - 
then you may as well argue "well if one player's flag is down - or he only has a millisecond left - and its mate in ten - then he's going down and mate is not available'

But I don't think you're saying that.
You're claiming something else it seems.
Suggestions:   don't say 'competition rules'.
If you're talking about the 50 move rule - say 50 move rule.
If you're talking about some other rule - say what the rule is.

Lol.   

Avatar of MARattigan
tygxc wrote here:

#1960

"Can you make up your mind what game you're proposing to solve, please?"
++ Laws of Chess, but without the 50-moves rule.
The 3-fold repetition rule stays and could even be simplified to a 2-fold repetition rule.

Well that's progress. All you need to do now is decide whether you're going to have a 2 or 3 fold repetition rule, because it makes an enormous difference in the size of your state space.

SF14 evaluates and plays assuming the 50 move and triple repetition rules, so you shouldn't expect too much accuracy.

Also you might not get much interest, because then you have a game that isn't chess.

"If you read the post you will see that SF14's blunder rate doesn't improve with increased think time, rather the opposite."
++ OK, but your longest thinking time is still short and your hardware inferior.

Works OK for me. But the point of the post is that SF14 appears to blunder more with longer think times, so short is beautiful.

"If you give SF14 60 hours/move on a 10^9 nodes/s cloud engine it could well turn out to be little more than a random legal move generator."
++ I disagree. At 60 h / move and 10^9 nodes / s it goes right through to checkmate.

Er, no. The search will still take exponential time with the depth even if you're alpha beta pruning, if the pruning factor stays constant.

I ran the SF14 kibbitzer on the starting position of the games in the post mentioned above and measured the time in seconds the ply depths 30, 35, 40, 45 and 50 first appeared. Then I ran it through an exponential fit in the Wolfram regression widget.


Its a mate in 85 moves (170 ply) without the 50 move rule, so I plugged 170 into Wolfram's formula and divided by 3,600,000 to convert from seconds on my machine to hours  on something 1000 times as fast. 

To get it to go right through to the correct checkmate from that 5 man position, you'd need to give it about 640,399,741 hours (73,105 years) on your supercomputer. But if the minimax pathology is real it's vanishingly unlikely that it would actually get there.

Since you've banished the fifty move rule there's no longer an upper bound of 5898.5+50 moves on forced mates. Deeper mates than that could need a bit longer, of course.

"I didn't look at SF14's alternative evaluations. What's the relevance? It plays the top move."
++ So the top move was an error. Was the top 2 move correct or an error too? Was the top 3 move correct or an error too? Was the top 4 move correct or an error too? I do not depend on the top move only. I run through 3 verification passes where I retract all white moves one by one and replace them with the top 2 move. If it is still a draw, then I retract all white moves again and replace them with the top 3 move. If it is still a draw, then I retract all white moves again and replace them with the top  4 moves. If it is still a draw, then I conclude it solved.

I got the result in this post at the first try (though the position wasn't entirely random). I think you'll find it happens rather a lot during the course of your computation.

 

Avatar of playerafar


Worry about extras.

Throughout the discussion - the terms 'positions' and 'games' have been coming up.
Is solving more likely if the 'positions' aspect is prioritized ?
Definitely.  Hence the endgame tablebases.  
The more the projects corrupt into 'games' the more hopeless the task of 'solving' becomes.
The number of possible games is much too prohibitive.
It gets up over 10 to the hundredth power !   

Positions versus games doesn't digitalize into A or B though.
There's a grey area in between.  
And that's where so much of the discussion has 'resided'.
In that 'grey area'.  
A checkmate position has become very 'non-gamelike'.  Its one position.
Over.  Solved.  But it had to get there somehow.  

Even in regular chess - rather than computer projects -
things get 'solved' by checkmate.  Or by stalemate.  Or by hopeless draws made hopeless because there isn't enough material on the board for checkmate.  
They get 'solved' because of a position !  

Avatar of ifemo

 

Avatar of ifemo

impossibe!!!

Avatar of tygxc

#2007

"All you need to do now is decide whether you're going to have a 2 or 3 fold repetition rule, because it makes an enormous difference in the size of your state space."
++ I would take the 2-fold repetition for simplicity, but the 3-fold works just as well. No, it does not need a larger state space. For 2-fold repetition just check if the new FEN already has occured earlier. For 3-fold repetition check if the new FEN has occured twice earlier.

"SF14 evaluates and plays assuming the 50 move and triple repetition rules, so you shouldn't expect too much accuracy."
++ It makes no difference. The 50-moves rule is almost never invoked except when already in the table base. Most chess games (World Championship, ICCF) do not even get to 50 moves, except when they get into the table base.

"then you have a game that isn't chess."
++ It stays just the same game. Without 50-moves rule it will become slightly more decisive, as e.g. the Troitzky line shifts a bit in KNN vs. KP, but even that occurs rarely. 2-fold or 3-fold repetition makes no difference: it is also the same as 5-fold repetition: just a few more moves.

"But the point of the post is that SF14 appears to blunder more with longer think times, so short is beautiful."
++ This is an anomaly. Of course more time = less mistakes. If you can get a certain performance in a certain time, then adding time can only increase performance.

"The search will still take exponential time with the depth even if you're alpha beta pruning, if the pruning factor stays constant."
++ With increased depth positions get less men and thus become simpler. I gave examples above where a human grandmaster calculated 22 moves deep over the board and where a human second without engine analysed an adjourned position 42 moves deep in one night.

"To get it to go right through to the correct checkmate from that 5 man position, you'd need to give it about 640,399,741 hours (73,105 years) on your supercomputer."
++  640,399,741 hours = 10^21 positions, that is way too much.
There are only 25,912,594,054 positions with 5 men and far less KNN vs. KP.

"Since you've banished the fifty move rule there's no longer an upper bound of 5898.5+50 moves on forced mates."
++ This 5898 is purely theoretical; in practice grandmaster games or ICCF games do not even reach 50 moves, and if they do they already are in the 7-men table base. The nature of the game leads to faster draws, most often by 3-fold repetition, or by trades into a table base draw.

Avatar of tygxc

#1999

"So, you check only one candidate move for Black... and that should be enough to find her optimal strategy?"
++ Yes. Black tries to draw, white tries to win.
If a game ends in a draw, then black has succeeded and none of black's moves need to be changed, but on the contrary white has failed, so improvements for white must be investigated. If all (reasonable) alternatives for white also lead to draws, then it is proven that the game is a weakly solved to a draw and that all black moves were in retrospect optimal: fit to reach the draw.
If on the contrary the game would end in a white win, then none of the white moves need changeing and it would be necessary to look at all reasonable alternatives for black and if all those also lead to a white win, then chess would be solved to be a win for white and that in retrospect all white moves were optimal: fit to win.

"how many hours to build the proof tree?"
++ For that we must count the number of legal, sensible, reachable, and relevant positions.
1 position = 1 nanosecond. So far we have not reached agreement on that. For the people who think in games: chess has a high transposition rate: same positions reached by different games. The proof that "Losing Chess" is a win applied some transition tables for that. It also used heuristics like best first.

Avatar of playerafar

There's probably some math available for what percentages of move sequences transpose.  Or an upper bound on such.
Every time you introduce a new move not played before - then it automatically can't transpose back?
That would also go for pawn moves and captures.  You can't transpose back to any position before the capture or pawn move.  Nor to before the new move?  Some would say yes.  A knight goes back where it came from.  But you still can't transpose back to that particular position with the new move played and not reversed.  
Some positions could still transpose forwards though ....
but then it could get Very Silly.

Many positions that are wins or draws just keep 'transposing' to King and Queen versus King.  Win.  Or 'transpose' to  King and bishop versus King.  Draw.
Sillinesses regarding 'transpositions'.   happy.pngevil.png

Avatar of ifemo

 

Avatar of tygxc

#2013
There are many, many transpositions. There are trillions of games that lead to the same position after 1 e4 e5, most of them not sensible. There is a troll game above #1919.
There are also many, many sensible transpositions.
1 e4 e5 2 Nf3 Nf6 3 Nxe5 d6 4 Nf3 Nxe4 5 d3 Nf6 6 d4 d5
= 1 e4 e6 2 d4 d5 3 exd5 exd5 4 Nf3 Nf6
1 e4 c5 2 Nf3 Nc6 3 d4 cxd4 4 Nxd4 Nf6 5 Nc3 e5 6 Ndb5 d6 7 Bg5
= 1 e4 c5 2 Nf3 e6 3 d4 cxd4 4 Nxd4 Nf6 5 Nc3 Nc6 6 Ndb5 d6 7 Bf4 e5 8 Bg5
It is not about percentages: there are many, many more games than positions.
Any position can be reached by trillions of different games.

Avatar of MARattigan
tygxc wrote:

#2007

"All you need to do now is decide whether you're going to have a 2 or 3 fold repetition rule, because it makes an enormous difference in the size of your state space."
++ I would take the 2-fold repetition for simplicity, but the 3-fold works just as well.

So all you need to do now is decide whether you're going to have a 2 or 3 fold repetition rule.

No, it does not need a larger state space. For 2-fold repetition just check if the new FEN already has occured earlier. For 3-fold repetition check if the new FEN has occured twice earlier.

That is rather like saying you can take the size of the state space to be 1, just check if there's a mate.

If you're looking for a solution you need to provide an algorithm for perfect play.

If a 2-fold repetition rule is part of your game definition, then, for the two positions Q₁, Q₂, Q₃, ... P and R₁, R₂, R₃, ... P, where the Qs, Rs and P are basic rules positions from the start of the game or the last irreversible move, the moves the algorithm provides may necessarily be different. 

Any mate by either side must avoid stepping into the basic rules positions Q₁, Q₂, Q₃, ... P in the first case or R₁, R₂, R₃, ... P in the second and either side can draw by a forced sequence that reaches one of Q₁, Q₂, Q₃, ... P in the first case or R₁, R₂, R₃, ... P in the second.

This means the game state is different in the two cases and therefore they are separate nodes in your state space. The state space must cater for all such legal sequences, but permutations of the Qs or Rs give the same node.

In the 2-fold rule game each of the Qs and each of the Rs must be distinct basic rules positions or the game terminates before reaching P. In the 3-fold repetition, up to two repeats are allowed, which hugely alters the state space size.

The Syzygy generation process avoids any consideration of the 3-fold repetition rule by building up a hierarchy of positions in which no corresponding basic rule position is repeated.

You plan to use SF14 which will happily produce 2-fold repetitions even where the player making the repetition is evaluated as winning. So, for example, with your 2-fold repetition rule in effect, the 8 second/ply and 256 second/ply games shown here would both have terminated in a draw on White's third move.

"SF14 evaluates and plays assuming the 50 move and triple repetition rules, so you shouldn't expect too much accuracy."
++ It makes no difference. The 50-moves rule is almost never invoked except when already in the table base. Most chess games (World Championship, ICCF) do not even get to 50 moves, except when they get into the table base.

Are you saying that in all possible chess games there are almost no games that reach 50 moves without the capture of a piece or a pawn move, or are you saying that in practice players (who are invariably out of their depth in frustrated mates with more than 5 men on the board if tablebase access is not available) almost never invoke it. 

If the latter what possible relevance is there to solving chess?

"then you have a game a game that isn't chess."

++ It stays just the same game. Without 50-moves rule it will become slightly more decisive,

You already contradicted yourself.

as e.g. the Troitzky line shifts a bit in KNN vs. KP, but even that occurs rarely.

I think you might be referring to an out of date copy of your Wikipaedia article. I already deleted the "second Troitzky line" section. The Troitzky line concept is meaningless with the 50 move rule in effect.

2-fold or 3-fold repetition makes no difference: it is also the same as 5-fold repetition: just a few more moves.

It makes a vast difference to the size of the state space and results in different solution algorithms for all three cases.

"But the point of the post is that SF14 appears to blunder more with longer think times, so short is beautiful."
++ This is an anomaly. Of course more time = less mistakes. If you can get a certain performance in a certain time, then adding time can only increase performance.

Well take it up with D.S.Nau and the other people producing papers on the subject. My example in #1879 may be very far from exhaustive, but the results are entirely consistent with what I said. Try it out yourself a few hundred times if you want to get more data.

There's no "of course" about it. 

"The search will still take exponential time with the depth even if you're alpha beta pruning, if the pruning factor stays constant."
++ With increased depth positions get less men and thus become simpler.

White takes the pawn usually then SF14 evaluates KNNK indefinitely.

I gave examples above where a human calculated 20 moves deep over the board and where a human analysed an adjourned position 30 moves deep in one night.

Bully for the human! What's the relevance?

"To get it to go right through to the correct checkmate from that 5 man position, you'd need to give it about 640,399,741 hours (73,105 years) on your supercomputer."
++  640,399,741 hours = 10^21 positions, that is way too much.
There are only 25,912,594,054 positions with 5 men and far less KNN vs. KP.

There are 557914624 basic rules KNNKP positions in 139487656 equivalence classes with Q side - K side and Black to move - White to move symmetry. SF14 doesn't evaluate basic rules positions, it varies the evaluations according ply count and doesn't consider stepping back into a position whose corresponding basic rules position has already occurred twice from a position with a positive evaluation.

I think there are probably more nodes in the state space for KNNKP under competition rules (which is what SF14 assumes) than Tromp's estimate for the whole of chess under basic rules.

Are you saying that SF14 checks whether it's exhausted all positions when it's evaluating and comes back with a message saying, "not going to do any more evaluating I've run out of positions"? It won't reach them all anyway because it'll prune a fair percentage.

"Since you've banished the fifty move rule there's no longer an upper bound of 5898.5+50 moves on forced mates."
++ This 5898 is purely theoretical; in practice grandmaster games or ICCF games do not even reach 50 moves, and if they do they already are in the 7-men table base. The nature of the game leads to faster draws, most often by 3-fold repetition, or by trades into a table base draw.

A solution is something theoretical.

Grandmaster games or ICCF games do not give you one.