Chess solved?

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

Moderators: hgm, Dann Corbit, Harvey Williamson

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
syzygy
Posts: 4951
Joined: Tue Feb 28, 2012 10:56 pm

Re: Chess solved?

Post by syzygy » Sun Sep 06, 2020 11:26 pm

towforce wrote:
Sun Sep 06, 2020 9:29 pm
syzygy wrote:
Sun Sep 06, 2020 12:58 pm
towforce wrote:
Sun Sep 06, 2020 11:23 am
[Page 2: it is clearly stated that the purpose of the report is to show that the games discussed are complete in exponential time with respect to EFFICIENT REDUCIBILTY. Using roughly the method the paper uses, off the top of my head, I would guess that Fermat's Last Theorem (FLT) has complexity of at least O(y * z^2) to prove to power integer y for by testing pairs of integers to z, and therefore cannot be solved to infinity. However, FLT HAS been proved - just not by reduction.
So you have no clue what this all is about. What a surprise!

Algorithmically, FLT is a single statement in an appropriately chosen axiomatic system. Proving that statement, if a proof exists (which we know to be the case), can obviously be done in constant time, since it is just a single instance.

I absolutely do not want to dwell on this any longer, but I just want to clarify my FLT point. Let's go back 26 years, to a time when FLT hadn't been solved for all cases. Then the complexity of solving it to power y for pairs of integers 1..z would be approximately O(y*z^2).
No it would not. I'm afraid you're just getting lost in a forest here...

But basically all you are doing is hoping that 8x8 chess or the initial position is "special", even if you do not actually understand that, and there is still absolutely no good reason to believe that 8x8 chess or the initial position is special.

chrisw
Posts: 3861
Joined: Tue Apr 03, 2012 2:28 pm

Re: Chess solved?

Post by chrisw » Mon Sep 07, 2020 7:02 am

syzygy wrote:
Sun Sep 06, 2020 11:26 pm
towforce wrote:
Sun Sep 06, 2020 9:29 pm
syzygy wrote:
Sun Sep 06, 2020 12:58 pm
towforce wrote:
Sun Sep 06, 2020 11:23 am
[Page 2: it is clearly stated that the purpose of the report is to show that the games discussed are complete in exponential time with respect to EFFICIENT REDUCIBILTY. Using roughly the method the paper uses, off the top of my head, I would guess that Fermat's Last Theorem (FLT) has complexity of at least O(y * z^2) to prove to power integer y for by testing pairs of integers to z, and therefore cannot be solved to infinity. However, FLT HAS been proved - just not by reduction.
So you have no clue what this all is about. What a surprise!

Algorithmically, FLT is a single statement in an appropriately chosen axiomatic system. Proving that statement, if a proof exists (which we know to be the case), can obviously be done in constant time, since it is just a single instance.

I absolutely do not want to dwell on this any longer, but I just want to clarify my FLT point. Let's go back 26 years, to a time when FLT hadn't been solved for all cases. Then the complexity of solving it to power y for pairs of integers 1..z would be approximately O(y*z^2).
No it would not. I'm afraid you're just getting lost in a forest here...

But basically all you are doing is hoping that 8x8 chess or the initial position is "special", even if you do not actually understand that, and there is still absolutely no good reason to believe that 8x8 chess or the initial position is special.
Quick question to which you (syzygy) may know the answer (I don’t, my serious math was way too long ago). We know the worst case storage size for chess (address space of a 32 man table base), which I guess is a 0s and 1s bit stream stretching off past Alpha Centauri somewhere, N bits long. I also seem to remember that a wave form (the bit stream being a square wave form) can be represented (is it Fourier transform or something?) by addition of sine waves of various frequency, phase shift and amplitude (might be being random here). In a sense those parameters could be also those of an additive polynomial, so I guess if one knows how many additive sine waves are needed to represent a bit stream N long, then we have a worst case number for a polynomial parameter count for 8x8 chess. Does that make sense, or is there another way to estimate parameter count of such a thing?

Actually, thinking about it, upper bound parameter count for a chess solving polynomial, is actually N, the length of the bit stream. Less if you can compress the stream, and less if there’s a cyclic repetition within the stream. But we’re still in alpha centauri territory, and there’s the problem.

User avatar
towforce
Posts: 10759
Joined: Wed Mar 08, 2006 11:57 pm
Location: Birmingham UK

Re: Chess solved?

Post by towforce » Mon Sep 07, 2020 8:35 am

syzygy wrote:
Sun Sep 06, 2020 11:26 pm
But basically all you are doing is hoping that 8x8 chess or the initial position is "special", even if you do not actually understand that, and there is still absolutely no good reason to believe that 8x8 chess or the initial position is special.

There is also the possibility that the 8*8 starting position is "within reach" of some method, whereas 50*50 might not be.

I think that we can write off formally proving 8*8 for the time being. However, evaluating a large proportion of positions well without building a game tree is probably reachable. NNs can already do that, but not yet as well as human players.

What makes good human / machine EF possible without 32 man tablebases is the fact that knowledge of one positional Knowledge of one type of pattern seems to confer benefits in positions other than the one it was learned in. Without this being true, GMs would not be able to play "good" chess with a mere 50,000 chess patterns - the estimated number it takes to become a GM.
Last edited by towforce on Mon Sep 07, 2020 8:42 am, edited 1 time in total.
Writing is the antidote to confusion

jp
Posts: 1442
Joined: Mon Apr 23, 2018 5:54 am

Re: Chess solved?

Post by jp » Mon Sep 07, 2020 8:42 am

jp wrote:
Sat Sep 05, 2020 11:02 am
towforce wrote:
Sat Sep 05, 2020 10:54 am
At the moment, I'm afraid it's not 100% clear to me that there any proofs ..., but I'm humble enough to admit that I might be wrong about this.
It's not clear to you because you don't understand the paper. You do not appear to be familiar with computational complexity either.
It's long overdue that you at least prove one of your statements correct by admitting that you were completely wrong.
Last edited by jp on Mon Sep 07, 2020 8:44 am, edited 1 time in total.

User avatar
towforce
Posts: 10759
Joined: Wed Mar 08, 2006 11:57 pm
Location: Birmingham UK

Re: Chess solved?

Post by towforce » Mon Sep 07, 2020 8:43 am

jp wrote:
Mon Sep 07, 2020 8:42 am
It's long overdue that you at least prove one of your statements correct by admitting that you were completely wrong.

What am I completely wrong about?
Writing is the antidote to confusion

jp
Posts: 1442
Joined: Mon Apr 23, 2018 5:54 am

Re: Chess solved?

Post by jp » Mon Sep 07, 2020 8:44 am

towforce wrote:
Mon Sep 07, 2020 8:43 am
What am I completely wrong about?
Your claims about the paper that was linked (e.g. that it is wrong and you can point out where).

Sheesh, you're not still going to claim you were right about that, are you?

User avatar
towforce
Posts: 10759
Joined: Wed Mar 08, 2006 11:57 pm
Location: Birmingham UK

Re: Chess solved?

Post by towforce » Mon Sep 07, 2020 9:09 am

jp wrote:
Mon Sep 07, 2020 8:44 am
towforce wrote:
Mon Sep 07, 2020 8:43 am
What am I completely wrong about?
Your claims about the paper that was linked (e.g. that it is wrong and you can point out where).

Sheesh, you're not still going to claim you were right about that, are you?

Yes. The paper makes bigger claims than the paper it references and depends upon. Therefore, the paper is wrong. QED.
Writing is the antidote to confusion

syzygy
Posts: 4951
Joined: Tue Feb 28, 2012 10:56 pm

Re: Chess solved?

Post by syzygy » Mon Sep 07, 2020 9:30 am

towforce wrote:
Mon Sep 07, 2020 9:09 am
jp wrote:
Mon Sep 07, 2020 8:44 am
towforce wrote:
Mon Sep 07, 2020 8:43 am
What am I completely wrong about?
Your claims about the paper that was linked (e.g. that it is wrong and you can point out where).

Sheesh, you're not still going to claim you were right about that, are you?

Yes. The paper makes bigger claims than the paper it references and depends upon. Therefore, the paper is wrong. QED.
Name a claim.

Oh, and are you willing to admit that you were actually wrong about something? For example, your claim that "we know that there is no forced win of material in the first 30 moves". (I know you will now be trying to be "smart" and once again ask for an example of a forced material win, but that just shows you are either trolling or have no facility for logical reasoning.)

jp
Posts: 1442
Joined: Mon Apr 23, 2018 5:54 am

Re: Chess solved?

Post by jp » Mon Sep 07, 2020 9:35 am

towforce wrote:
Mon Sep 07, 2020 9:09 am
Therefore, the paper is wrong. QED.
Do you mind trying to explain the psychology behind your views? i.e. what convinces you that you even understand papers in an area you have no training in, let alone can find fatal mistakes in them?

Does it not bother you that you've changed your story at least three times about what is "wrong" in the paper?

chrisw
Posts: 3861
Joined: Tue Apr 03, 2012 2:28 pm

Re: Chess solved?

Post by chrisw » Mon Sep 07, 2020 9:54 am

towforce wrote:
Mon Sep 07, 2020 8:43 am
jp wrote:
Mon Sep 07, 2020 8:42 am
It's long overdue that you at least prove one of your statements correct by admitting that you were completely wrong.

What am I completely wrong about?
Everything. Everything you know is wrong.

Post Reply