Chess will never be solved, here's why

Sort:
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.

 

Avatar of ifemo

chess is good draw.png and fun

Avatar of MARattigan
playerafar wrote:


@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.   

At this point I'm joining @Optimissed in failing to understand what you mean by uniqueness. I thought it referred to diagram/side to move pairs where there are positions having different possible forward play. 

Perhaps you could explain again.

Avatar of ifemo

اه

ذغث

اخص شقث غخع؟

Avatar of ifemo

so

Avatar of ifemo

ifemo

is here

Avatar of ifemo

e4 e5 e6 e7 e8 Re5 Hf3 Kn f3 are good moves 

Avatar of Elroch

There are several interesting partial orders on the set of positions.  These are based on 3 different properties of moves:

(1) legality

(2) non-blunder (i.e. keep the value the same)

(3) efficient optimality (i.e. non-blunder that wins fastest against most resilient defense if winning or loses slowest against optimal play if losing). This condition only differs from (2) when the result is not a draw.

A chosen one of these properties can be required for the moves of each of the two players in a sequence of moves (9 possibilities in total, of varying interest), and each of these 9 choices gives a partial order on the positions where:

P >=Q means there is a sequence of moves between the positions that satisfies the two chosen conditions for the two sides.

Thus each of those 9 choices leads to an equivalence relation on positions where

P == Q  if and only if P >= Q and Q >= P (i.e. there are sequences of moves in both directions with the chosen properties.

As an example, if the condition for white is efficient optimality and the condition for black is legality, you have the right criteria for seeking an efficient optimal strategy for white.

Such a strategy behaves very differently in winning positions to drawing ones. In the former, every move by either player moves between equivalence classes of positions (based on the distance to the objective). In the latter moves can dither around in an equivalence class indefinitely, but can also move irreversibly between equivalence classes. It is impossible, by definition, ever to return to an equivalence class even when drawing.

Of course when at least one player is not blundering, the repetititions of positions occur during the wandering within an equivalence class.

Avatar of haiaku
tygxc wrote:

#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.

Don't repeat the same thing over and over, as if we don't read your posts or we were stupid, just answer the questions, please.

tygxc wrote:

"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.

You have stated that countless time, no need to repeat yourself. You stated that you expect to search only 10¹⁷ positions out of 10³⁷ and in order to do that, you want to search only 4 candidates for White and one for Black at any move. Now, how do you determine those 4 top candidates and be sure the optimal move is among them? You invoked best-first algorithms as if they were some sort of magical tools. They are not. You stated that to be sure the optimal move is among those candidates, you would just leave SF calculate 60 hours per move. If I understand you well, it should do that at any increment of depth; otherwise, you cannot be sure that the top 4 candidates generated in leaf positions before the endgame tablebase are the best, since the engine did not calculate for 60 hours those positions, right? The closer the endgame, the less reliable would be those 4 candidates. So how many hours to select those 4 best options at any increment of depth? 1 position = 1 nanosecond is not the right answer, and neither 1 nanosecond per candidate move.

Avatar of tygxc

#2016

"So all you need to do now is decide whether you're going to have a 2 or 3 fold repetition rule."
++ It does not matter. I would use 2-fold for simplicity, but 3-fold is basically the same.

"That is rather like saying you can take the size of the state space to be 1, just check if there's a mate."
++ No, checking for checkmate, stalemate or 3-fold repetition is fast.
Generating daughter FEN from the mother FEN takes more time.

"If you're looking for a solution you need to provide an algorithm for perfect play."
++ Yes, the algorithm is brutal force calculation towards the table base.

"the moves the algorithm provides may necessarily be different" ++ No, it is the same.

"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."
++ Both: most GM and ICCF games are over before move 50. Even in those games that go beyond move 50 the 50-moves rule is almost never invoked as there is some compelling reason to capture or move a pawn. Even in those cases where the 50-move rule is invoked, it is nearly always while already within the 7-men endgame table base. I do not know any GM or ICCF game drawn by the 50-moves rule with 8 or more men. Do you know of any?

"If the latter what possible relevance is there to solving chess?"
++ The relevance is that GM and ICCF games at least look like ideal games with optimal moves. Some GM and ICCF games may in fact be ideal games that form part of the solution of chess.

"The Troitzky line concept is meaningless with the 50 move rule in effect."
++ The Troitzky line is very useful even in practice: when the blocked pawn is too far, there is no win.

"It makes a vast difference to the size of the state space and results in different solution algorithms for all three cases." ++ No, the state space stays the same.

"Well take it up with D.S.Nau and the other people producing papers on the subject."
++ It goes against all logic.
If you can do a task in x time, then you can do the same task in x+1 time.
If you can do a task in x+1 time, then you may be unable to do the same in x time.
The problem here is dependence on an evaluation function. KNN vs. KP is essentially +5. When the engine sees a way to win the pawn, it will evaluate that +6, though KNN vs. K is a draw. An engine will also prefer a +3 fortress draw over a +1 win. That highlights the inadequacy of an evaluation function: only brute force calculation to the end does it.

"Bully for the human! What's the relevance?"
++ The relevance is that if an unaided human can calculate 20-30 moves in a few hours, then it is plausible that a cloud engine in 5 years can calculate all the way to the end.

"There are 557914624 basic rules KNNKP positions"
++ So that is 0.557914624 seconds.

"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"?"
++ You cannot check more positions than there are positions, unless you check the same position a billion times, which would be a waste. It is easy to compare a new FEN to the previously considered FEN.

"A solution is something theoretical."
++ The solutions to Losing Chess, Checkers, Nine Men's Morris, Connect Four are practical.

"Grandmaster games or ICCF games do not give you one."
++ GM and ICCF games are the closest we have to ideal games with optimal moves.
Some GM and ICCF games may be ideal games and thus part of the solution of chess.