Chess solved?

[towforce]

Name a claim.

The flawed, and highly obfuscated, chess-specific paper states:

We will show that a natural generalization of chess to nxn boards is complete in exponential time, the first such result for a "real" game. This implies that for any k ~ l , there are infinitely many positions ~ such that any algorithm for deciding whether White (Black) can win from that position requires at least cI~l k time-steps to compute, where c > 1 is a constant, and l~I is the size of ~ Generalized chess is thus provably intractable...

...but that paper is 100% dependent on another paper (which I had to find for myself, despite asking over and over - but no matter!), and that paper, a very clearly higher quality paper, states:

The main purpose of this paper is to prove that the decision problems for certain simple combinatorial games are complete in exponential time with respect to efficient reducibility.

See the difference?

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

Following the discussion, I now agree that 30 is too high - but I didn't make the claim strongly (link).

[towforce]

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?

There was a time when knowledge was the preserve of the high priests. That time has gone. Reduction is explained perfectly well here.

This is the 21st century and repeatedly telling someone that they're not a sufficiently high status person to be allowed to have knowledge doesn't cut it (you could argue that it amounts to gaslighting). When somebody asks you to explain something, I would advise you to respond by either saying "I'm too busy", or by giving them at least a hint of where they should look for the answer.

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

I was hoping to be able to get some help with what, and how, the paper was proving. That's why I asked over and over. And over. And over. And I asked politely.

[Uri Blass]

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

A possible reason to believe some chess position is special is if we see some program that practically does not lose with white or black.
We can suspect that some engine practically solved the position in the meaning that it is unbeatable even with no mathematical proof that the game is a draw.

I do not know if some program with no book is already unbeatable at some time control that we can practically play but it may be interesting to make a match between the program and itself from the opening position at long time control when you give 10 minutes per move to one side and 1 minute per move to the second side and you give the side with less time no book to see how many draws we are going to get.

[syzygy]

Name a claim.

The flawed, and highly obfuscated, chess-specific paper states:

We will show that a natural generalization of chess to nxn boards is complete in exponential time, the first such result for a "real" game. This implies that for any k ~ l , there are infinitely many positions ~ such that any algorithm for deciding whether White (Black) can win from that position requires at least cI~l k time-steps to compute, where c > 1 is a constant, and l~I is the size of ~ Generalized chess is thus provably intractable...

...but that paper is 100% dependent on another paper (which I had to find for myself, despite asking over and over - but no matter!), and that paper, a very clearly higher quality paper, states:

The main purpose of this paper is to prove that the decision problems for certain simple combinatorial games are complete in exponential time with respect to efficient reducibility.

See the difference?

What is the problem? A math/theoretical cs paper that invokes a theorem proved in another math/theoretical cs paper?

The second paper proves that G3 is EXPTIME complete. The first paper uses this result to prove that NxN chess is EXPTIME complete. This is a rather common way of proceeding.

Is it the word "intractable" that bothers you? Being EXPTIME complete implies intractable for all practical purposes. Not to be confused with uncomputable.
https://en.wikipedia.org/wiki/Computati ... actability
Note that the first paper first states precisely what is going to be proved: that NxN chess is EXPTIME complete. The intractability is then just mentioned as the practical consequence.

So what is the flaw precisely? Can you express it in words? Rather than "Don't you see it!"

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

Following the discussion, I now agree that 30 is too high - but I didn't make the claim strongly (link).

But you never have the guts to just be clear and admit you were wrong.

There is no shame in admitting one was wrong about something.

[syzygy]

A possible reason to believe some chess position is special is if we see some program that practically does not lose with white or black.
We can suspect that some engine practically solved the position in the meaning that it is unbeatable even with no mathematical proof that the game is a draw.

That may be a reason to suspect that the position is drawn but not a reason to suspect that it can be proved to be a draw in a reasonable amount of time (which is what we are talking about it here, or at least I was - solving the position in the mathematical sense).

[syzygy]

This is the 21st century and repeatedly telling someone that they're not a sufficiently high status person to be allowed to have knowledge doesn't cut it (you could argue that it amounts to gaslighting).

Nobody said you're not allowed to have the knowledge. You are being criticised for making grand claims about things you obviously have no expertise in and then flat out rejecting the long-standing theoretical results you are presented with.

[towforce]

Let's see if we can get to a conclusion we can agree on:

* proving the starting position of a large n*n board is a draw is not possible with today's maths and technology

* proving the starting position on a standard 8*8 board is drawn is close to impossible with today's maths and technology, but with intense work from applied mathematicians over an extended period, and dramatic improvement in SAT and other theorem proving technology, there could be the tiniest possibility that it might be reachable in the foreseeable future

* in the foreseeable future, a chess computer might be created that no other chess computer will be able to beat for a long period of time. Per a previous post in this thread, my name for this would be a "practical proof" that chess is a draw (some people might object to the inclusion of the word "proof" in that name)

* despite massive advances in both hardware and software, there is no evidence that it is possible to force the win of material from the chess starting position. My opinion is that it is not possible for either side to force the win of material at all. My opinion is that this information is important, but I understand and accept the views of those who disagree

* there is no evidence that it is impossible to build an EF that evaluates most chess positions well without building a game tree. We don't know how big such an EF would have to be

* I have given what I consider to be good reasons why, IMO, such an EF could probably be smaller and faster than others think would be necessary, but I understand and accept that I haven't proven this to be the case

[syzygy]

Let's see if we can get to a conclusion we can agree on:

* proving the starting position of a large n*n board is a draw is not possible with today's maths and technology

Agreed.

* proving the starting position on a standard 8*8 board is drawn is close to impossible with today's maths and technology, but with intense work from applied mathematicians over an extended period, and dramatic improvement in SAT and other theorem proving technology, there could be the tiniest possibility that it might be reachable in the foreseeable future

Nope, the branching factor of chess and the total number of possible positions prevent this. Even if one could build an oracle chess engine that could reasonably quickly produce an optimal move in (almost) all positions, it would take too long to produce and verify the whole proof tree. Developments in theorem provers are not going to help because the optimal theorem prover for chess is known (it is called alpha-beta).

* there is no evidence that it is impossible to build an EF that evaluates most chess positions well without building a game tree. We don't know how big such an EF would have to be

I don't know and don't care too much what EF is but "evaluation functions" already exist that do a very good job at evaluating "most" chess positions. Just pick a top engine and let it search to a reasonable depth. (I see no good reason to disallow building a limited search tree.) They don't bring us any closer to actually solving the starting position for the reason already mentioned. Even if they could be perfected and take zero time to produce the optimal move, it would take too long to construct and verify the proof that the initial position is drawn (or winning for white or winning for black, pick a choice). (Not so in checkers or suicide chess and most other games that have been solved.)

[jp]

This is the 21st century and repeatedly telling someone that they're not a sufficiently high status person to be allowed to have knowledge doesn't cut it (you could argue that it amounts to gaslighting.

Nobody said you're not allowed to have the knowledge. You are being criticised for making grand claims about things you obviously have no expertise in and then flat out rejecting the long-standing theoretical results you are presented with.

Yes, there's an obvious huge difference between status bestowed by birth (e.g. kings and queens in the dark ages) and people acquiring basic knowledge and demonstrating that knowledge (or at least not demonstrating that they lack that knowledge).

There is nothing stopping towforce from trying to gain knowledge, but he seems reluctant to do that. It seemed to me that one of his problems is that he does not understand what a reduction is, but now I'm concerned that he does not understand even the concept of mathematical proof. I am still interested in understanding the psychology driving his beliefs.

[jp]

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?

There was a time when knowledge was the preserve of the high priests. That time has gone.

This is the 21st century and repeatedly telling someone that they're not a sufficiently high status person to be allowed to have knowledge doesn't cut it (you could argue that it amounts to gaslighting).

Well, thanks for starting to give insight into your psychology.

But would you be happy to take an airflight on a plane whose pilot and crew had no training in flying planes? I definitely would not be. It doesn't matter how talented the pilot thinks he is or really is. He needs to have the necessary training. (That is where the 21st century is different: it allows more people access to information and education.)

Don't you agree with that?

So how is this different? Or do you believe that mathematics, computer science, science, etc. don't actually require training?

Your attitude to the paper is like going to the cockpit and telling the crew that they are flying incorrectly, just because you've realized you don't like the city they are flying to.