Chess solved?

Discussion of anything and everything relating to chess playing software and machines.

Moderators: hgm, Rebel, chrisw

User avatar
towforce
Posts: 11572
Joined: Thu Mar 09, 2006 12:57 am
Location: Birmingham UK

Re: Chess solved?

Post by towforce »

duncan wrote: Thu Sep 03, 2020 1:20 pmI have not been following this discussion properly but have you posted about why you believe we will very likely solve chess in the future with these new emergent patterns, if that is your claim?

I cannot give you a straight answer, so I'll answer in parts and try to keep those parts understandable:

* some chess positions (and in particular, my intuition tells me, relationships between pieces) and their evaluations will be mapped into multidimensional space

* I will use an algorithm I am building to fit a polynomial that is good in the machine learning sense (accuracy de-emphasised (hence ranges for evaluation scores rather than exact numbers), simplicity emphasised - lowest degree and smallest number of terms possible)

* hopefully, some of the positions will then be able to be discarded without lowering the standard of the resulting EF

* hopefully, the resulting EF will evaluate some positions well

* where it evaluates a position badly, new position/evaluation data will be added to strengthen it there

* repeat

IMO, there are two reasons to be hopeful:

1. my intuition tells me that the size of the polynomial will grow less quickly than the number of data rows (if the polynomial grows exponentially with extra data rows, that will be very disappointing)

2. my experience with CBR tells me that the number of data rows needed is likely to be lower than most people are expecting. In CBR, the number of cases needed to make a good system is almost always a lot lower than people expect, and my intuition tells me that there are similarities with what I am doing here

The ultimate achievement would be, to put it simply, to look at the polynomial, spot where it is converging to, and hence write an EF that evaluates all chess positions correctly. A way to go to get to that point! :lol:
Writing is the antidote to confusion.
It's not "how smart you are", it's "how are you smart".
Your brain doesn't work the way you want, so train it!
duncan
Posts: 12038
Joined: Mon Jul 07, 2008 10:50 pm

Re: Chess solved?

Post by duncan »

jp wrote: Sun Aug 30, 2020 1:23 amDo you mean this "stroke of good luck" to be related to chess in general (i.e. the basic rules of moving, winning and drawing) or do you mean all that plus the specific (opening) position we have? If you mean the former (i.e. the stroke of good luck covers all chess positions), there are theoretical CS reasons why that should not be the case.
Are you planning to answer Paul's question?

"What are these cs (Computer Science?) reasons, please?"
jp
Posts: 1470
Joined: Mon Apr 23, 2018 7:54 am

Re: Chess solved?

Post by jp »

duncan wrote: Thu Sep 03, 2020 2:39 pm Are you planning to answer Paul's question?

"What are these cs (Computer Science?) reasons, please?"

Already answered a couple of days ago --
jp wrote: Tue Sep 01, 2020 2:11 am TCS = theoretical computer science.

Consider this from the TCS angle. As syzygy has stated a couple of times (in different words), if we just mean solving the standard chess game, then that is of fixed size, so then it's just debating lots of different very large constants, whether some are larger than others, and whether you can make some slightly less large. But we're not really talking about that (as the quoted text makes clear). We're really talking about solving it in some sort of quick, clever way.

So the TCS way is to look at the complexity of NxN chess. The problem is to solve an arbitrary position in NxN chess by a method that is not exponential in N. But it was shown decades ago that this cannot be done.

To which was added --
syzygy wrote: Tue Sep 01, 2020 2:32 am https://link.springer.com/content/pdf/1 ... 3-2_23.pdf

This does not rule out that the constant time in which 8x8 chess can be solved is surprisingly low, for example because 8x8 chess has a property that disappears on generalisation to NxN chess.

However, there is absolutely no reason to expect that 8x8 chess has such a property. In particular, the fact that Turing cracked the Enigma code (as has been mentioned about 10 times by towforce, who apparently thinks we didn't know that) is certainly no such reason. This is because Turing having been able to crack the Enigma code says as much about 8x8 chess as it does about 9x9 chess, 10x10 chess, .... 123x123 chess,... etc., and we know that not all of those games have a property that makes them easily solvable.

And that old paper is not the only one on the topic...
Last edited by jp on Fri Sep 04, 2020 12:48 am, edited 1 time in total.
duncan
Posts: 12038
Joined: Mon Jul 07, 2008 10:50 pm

Re: Chess solved?

Post by duncan »

jp wrote: Fri Sep 04, 2020 12:41 am
duncan wrote: Thu Sep 03, 2020 2:39 pm Are you planning to answer Paul's question?

"What are these cs (Computer Science?) reasons, please?"

Already answered a couple of days ago --
jp wrote: Tue Sep 01, 2020 2:11 am TCS = theoretical computer science.

Consider this from the TCS angle. As syzygy has stated a couple of times (in different words), if we just mean solving the standard chess game, then that is of fixed size, so then it's just debating lots of different very large constants, whether some are larger than others, and whether you can make some slightly less large. But we're not really talking about that (as the quoted text makes clear). We're really talking about solving it in some sort of quick, clever way.

So the TCS way is to look at the complexity of NxN chess. The problem is to solve an arbitrary position in NxN chess by a method that is not exponential in N. But it was shown decades ago that this cannot be done.

To which was added --
syzygy wrote: Tue Sep 01, 2020 2:32 am https://link.springer.com/content/pdf/1 ... 3-2_23.pdf

This does not rule out that the constant time in which 8x8 chess can be solved is surprisingly low, for example because 8x8 chess has a property that disappears on generalisation to NxN chess.

However, there is absolutely no reason to expect that 8x8 chess has such a property. In particular, the fact that Turing cracked the Enigma code (as has been mentioned about 10 times by towforce, who apparently thinks we didn't know that) is certainly no such reason. This is because Turing having been able to crack the Enigma code says as much about 8x8 chess as it does about 9x9 chess, 10x10 chess, .... 123x123 chess,... etc., and we know that not all of those games have a property that makes them easily solvable.

And that that old paper is not the only one on the topic...
Paul denied that it said that. Would you be able to give the page number and which paragraph?
jp
Posts: 1470
Joined: Mon Apr 23, 2018 7:54 am

Re: Chess solved?

Post by jp »

That is unquestionably the whole point of the paper. Just read the abstract!

The only possibility (which is what towforce apparently thinks now) is that the paper has a fatal mistake in it. Of course, any human proof has a non-zero probability of having an error, but no sensible punter would bet money on this one having a fatal error IMO.
duncan
Posts: 12038
Joined: Mon Jul 07, 2008 10:50 pm

Re: Chess solved?

Post by duncan »

jp wrote: Fri Sep 04, 2020 12:55 am That is unquestionably the whole point of the paper. Just read the abstract!

The only possibility (which is what towforce apparently thinks now) is that the paper has a fatal mistake in it. Of course, any human proof has a non-zero probability of having an error, but no sensible punter would bet money on this one having a fatal error IMO.
It is not just Paul asserting the fatal flaw. He has brought evidence for the fatal flaw "there's actually no proof in there that in complex positions, it's impossible for rules to exist which can tell you quickly whether the game is won or not."


It should be easy to disprove his evidence with the relevant page number quote. Do you have the relevant page number? ( I should point out that the paper is beyond me)
syzygy
Posts: 5563
Joined: Tue Feb 28, 2012 11:56 pm

Re: Chess solved?

Post by syzygy »

duncan wrote: Fri Sep 04, 2020 1:38 am
jp wrote: Fri Sep 04, 2020 12:55 am That is unquestionably the whole point of the paper. Just read the abstract!

The only possibility (which is what towforce apparently thinks now) is that the paper has a fatal mistake in it. Of course, any human proof has a non-zero probability of having an error, but no sensible punter would bet money on this one having a fatal error IMO.
It is not just Paul asserting the fatal flaw. He has brought evidence for the fatal flaw "there's actually no proof in there that in complex positions, it's impossible for rules to exist which can tell you quickly whether the game is won or not."


It should be easy to disprove his evidence with the relevant page number quote. Do you have the relevant page number? ( I should point out that the paper is beyond me)
Evidence? :shock: :roll:
jp
Posts: 1470
Joined: Mon Apr 23, 2018 7:54 am

Re: Chess solved?

Post by jp »

duncan wrote: Fri Sep 04, 2020 1:38 am It is not just Paul asserting the fatal flaw. He has brought evidence for the fatal flaw "there's actually no proof in there that in complex positions, it's impossible for rules to exist which can tell you quickly whether the game is won or not."
That is not evidence. That is simply an assertion that contradicts the whole result of the paper. Just stating something contradictory to the abstract is not bringing evidence. (I hope this is clear to you. If it isn't, please tell us what's not clear.)
User avatar
towforce
Posts: 11572
Joined: Thu Mar 09, 2006 12:57 am
Location: Birmingham UK

Re: Chess solved?

Post by towforce »

jp wrote: Fri Sep 04, 2020 8:11 amThat is not evidence. That is simply an assertion that contradicts the whole result of the paper. Just stating something contradictory to the abstract is not bringing evidence. (I hope this is clear to you. If it isn't, please tell us what's not clear.)

The paper "proves" (I'm not convinced, but for the purpose of this discussion I'll grant it) that on an n*n chess board, in the worst positions, the number of moves to the end of the game (with best play) will increase exponentially with n.

However, there is NOT ONE SINGLE SENTENCE anywhere in the report that addresses the issue that it's possible to write rules (in at least some positions) which can correctly determine whether a position is won or not without having to play out every possible line in the game.

So yes: the report is wrong, and whomever peer reviewed it wasn't thorough.

The report contains other clumsy errors as well (e.g. incorrect use of the word "infinitely" on the first page).

But again, I'm thankful for having been shown the report! :)
Writing is the antidote to confusion.
It's not "how smart you are", it's "how are you smart".
Your brain doesn't work the way you want, so train it!
duncan
Posts: 12038
Joined: Mon Jul 07, 2008 10:50 pm

Re: Chess solved?

Post by duncan »

jp wrote: Fri Sep 04, 2020 8:11 am
duncan wrote: Fri Sep 04, 2020 1:38 am It is not just Paul asserting the fatal flaw. He has brought evidence for the fatal flaw "there's actually no proof in there that in complex positions, it's impossible for rules to exist which can tell you quickly whether the game is won or not."
That is not evidence. That is simply an assertion that contradicts the whole result of the paper. Just stating something contradictory to the abstract is not bringing evidence. (I hope this is clear to you. If it isn't, please tell us what's not clear.)
Thank you for your offer for explaining to me what I do not have clear.

When I say evidence, I do not mean evidence he is right, rather evidence the paper is wrong in that to prove its thesis, it would need to show that it is impossible for rules to exist which can tell you quickly whether the game is won or not.

Do you accept or not that in order for the paper to prove its thesis it would have to show that it is impossible for rules to exist which can tell you quickly whether the game is won or not?

(The low probability or not of such rules existing should not be relevant here.)
Last edited by duncan on Fri Sep 04, 2020 11:51 am, edited 1 time in total.