Chess will never be solved, here's why

Sort:
Avatar of Elroch

You can add very few 9 piece positions to an 8 piece tablebase without covering a LOT of 9 piece positions that can be reached before it transitions to an 8 piece position.  There is no reason to believe in significant shortcuts.

Avatar of Optimissed
Elroch wrote:

"Extrapolation"? Not a concept that seems to fit in here.

Monsieur Rattigan's idea. I was just being accepting, since I get enough criticism from some, for not being accepting of ideas of other people, which may seem not to work.

Avatar of MARattigan

So You're talking about in the context of an EGTB generator.

As I said, I wouldn't like to implement such a routine.

But I do, strangely, agree agree with @Optimissed that if chess is solved, old fashioned organic computers will play the major part. Why I said not impossible.  If someone has an idea that could solve chess in a more elegant way than the BFI methods proposed to date, it could rely on information extracted from an initial set of EGTBs and need silicon (or some such material) to complete . In that case you would be more inclined to say that the EGTB generators are subroutines of of the solving program rather than vice versa, but either way.  

There is some reason to believe in shortcuts. Many of the EGTBs could currently be replaced by prescriptive routines requiring no (or little) look ahead. You just need to find a way of replacing the rest.

Avatar of Elroch

I have at some point sketched my views on the way a quantum computer could be used to solve chess. Fundamentally it's like constructing an endgame tablebase while dealing with every possible position in parallel. This is technologically challenging, for sure, but not, for any identifiable reason, impossible.

Avatar of MARattigan

Interesting to see whether humans or computers get there first. But I probably need to improve my lifestyle if I want to see the answer.

Avatar of Elroch

It is very safe to say unassisted humans can't solve chess!

Avatar of MARattigan

Probably can't prove Fermat's last theorem either.

But I think you're probably right.

Unassisted computers most certainly can't solve chess.

Avatar of tygxc

#88
Fermat's last theorem was proved by a human.
The Riemann Hypothesis and the Goldbach Conjecture will probably be proved by a human.
The Four Color theorem was solved by a computer guided by humans.
Checkers was solved by a computer guided by humans.
Sveshnikov said 5 years for modern computers and human assistants to solve chess.
My calculations corroborate this.
The answer may come sooner than you think or fear.

Avatar of MARattigan

"Probably can't prove Fermat's last theorem ..." was tongue in cheek (though I know at least one human who can't).

How is the 5 years worked out? Is that for both versions of chess?

Avatar of tygxc

https://arxiv.org/pdf/2112.09386.pdf
See table 3. Human assistants with ChessBase prepare 26-men starting positions 'tabya' to reduce the number of positions.
Every pawn move and every capture drastically reduces the number of relevant positions.
Checkers was solved using the square root of the number of legal positions.
http://library.msri.org/books/Book29/files/schaeffer.pdf 
It is thus plausible that the square root applies to chess as well, maybe more, maybe less.
Cloud engines reach 10^9 nodes / second.
There are 500 ECO codes A00 to E99.
Not all ECO codes are necessary: if 1 e4 e5 draws then it is unnecessary to look at 1 e4 b6 as well.
If black can draw against 1 d4 and 1 e4, then it is trivial that black can draw against 1 Nh3 as well.
Thus 5 years and a few cloud engines suffice to solve it.
That is the standard version of chess, with 50 moves rule and 3-fold repetition rule.

Avatar of MARattigan

Thanks. Hadn't seen the first.

Didn't understand the relevance of the ECO codes, nor how you prove the statements in the following para.

Also the solution will obviously be very different depending on whether the 50 move rule is in force or not. It may not limit the length of games, but it does limit the length of forced mates. It isn't mentioned anywhere.

 

Avatar of tygxc

#92
1.08e37+6.14e36+3.19e36+5.66e35=2.07e37 legal sensible positions starting from 26 men tabiya
in analogy to the checkers proof: square root of this: 4.55e18 relevant positions 
cloud engine 10^9 nodes/s
4.55e9 s = 144 years on 1 cloud engine for the whole of chess i.e. all 500 ECO codes A00 to E99
Hence 0.29 year on 1 cloud engine for 1 ECO code e.g. C67
19 ECO codes suffice to prove a draw against 1 e4: e.g.
C67 C65 C54 C53 C52 C51 C50 C49 C47 C45 C34 C33 C29 C28 C26 C24 C22 C21 C20
That is 5.4 years on 1 cloud engine to prove the draw against 1 e4.
A 2nd cloud engine may likewise prove a draw against 1 d4.
A 3rd cloud engine may work on the relevant moves other than 1 d4 and 1 e4 not transposing.


Avatar of DiogenesDue

Your 5 year clock is already down to 4.5 years wink.png...

Avatar of tygxc

#94
5 years after funding for the cloud engines...

Avatar of MARattigan

OK I see how you plan to use the ECOs - I'll need to think about that.

When the 50 move rule is in effect don't the position counts need to be multiplied by 100?

E.g. with the 50 move rule in effect this White to play position is a win

but this White to play position is a draw

 

Avatar of DiogenesDue
tygxc wrote:

#94
5 years after funding for the cloud engines...

Nope, that's just an excuse to never admit you were wrong.  You'll always be able to claim it wasn't enough, or done right, or what have you.  You're a Vickylan in sheep's clothing... wink.png

As one (of many) of your opponents, I started your clock when you began playing this game.

Avatar of Elroch
tygxc wrote:

#88
Fermat's last theorem was proved by a human.
The Riemann Hypothesis and the Goldbach Conjecture will probably be proved by a human.
The Four Color theorem was solved by a computer guided by humans.
Checkers was solved by a computer guided by humans.
Sveshnikov said 5 years for modern computers and human assistants to solve chess.
My calculations corroborate this.
The answer may come sooner than you think or fear.

When did Sveshnikov say that?

Sadly he died of Covid-19 last August. He was a hero of mine.

Avatar of tygxc

#98
Full quote:
"Chess is an exact mathematical problem. The solution comes from two sides: the opening and the endgame. The middlegame does not exist. The middlegame is a well-studied opening. An opening should result in an endgame.... Give me five years, good assistants and modern computers, and I will trace all variations from the opening towards tablebases and 'close' chess. I feel that power."
That was 2 years before he died. I was surprised by his statement. He was right.

Avatar of tygxc

#96
No, the number of positions 4*10^37 is not affected by the 50/75 moves rule or the 3/5 fold repetition rule. However without the 50/75 moves rule both sides could play around in a 32-men position for trillions of moves jamming the engine. With neither 50/75 moves rule nor 3/5 fold repetition rule, chess is undecisive. A game 1 Nf3 Nf6 2 Ng1 Ng8 etc. can go on forever.

Avatar of MARattigan

@tygxc

"No, the number of positions 4*10^37 is not affected by the 50/75 moves rule or the 3/5 fold repetition rule."

Why not?

If the same board layout and side to move can be reached from two tabya you can't assume the evaluation is the same unless the ply counts match when the 50 move rule is in effect. Including the ply count as part of the position multiplies the number of positions by 100. (For the exercise it can be assumed that a losing player will claim under the 50 move rule if possible, so the 75 move rule can be ignored).