Fruit fly races on steroids?

[towforce]

Btw - I think that on a larger board, GMs would be just as confused as the rest of us are on an 8x8 board:

* GMs don't get the optimal result in all of their games

* therefore, GMs have encoded a large number of shallow patterns rather than a small number of deep patterns that would enable them to resolve the game correctly (assuming such patterns exist: as I have previously stated, there are good reasons to think that they do)

* in a position on a larger board with more pieces, too many of these shallow patterns would be triggered in the GMs mind

* the large number of these shallow patterns, and interactions between them in the position, would confuse the GM

Over time, GMs might be able to encode new patterns on the larger board, and some of these will be helpful on an 8x8 board. So maybe playing on a larger board could be good training for a competitive GM (and most GMs are competitive!).

[chesskobra]

@towforce - Your argument is logically wrong. The statement "there are infinitely many X (e.g., positions) that satisfy property P (e.g., difficult to solve)" cannot be contradicted by saying that "there is an example of X (e.g., a position) that does not satisfy property P (e.g., that can be easily solved)". But that is what you are doing. You are showing that there are positions that can be easily solved, which is obvious. The paper does not claim that such positions do not exist.

[towforce]

The statement "there are infinitely many X (e.g., positions) that satisfy property P (e.g., difficult to solve)" cannot be contradicted by saying that "there is an example of X (e.g., a position) that does not satisfy property P (e.g., that can be easily solved)".

The above is completely true. It does not contradict my position in even a small way, though.

At it's heart, the paper is saying that the size of the chess game tree rises polynomially with the size of the board, and this makes resolving chess an intractable problem with increasing board size.

The paper actually says nothing about solving chess, so from the above sentence, we must conclude that the paper implies that the only way to resolve chess is to crunch out the entire game tree. I provided a counterexample, in which:

(1) The position cannot be resolved by generating the entire game tree

(2) The position can easily be resolved using well known patterns and heuristics

I thus invalidated the paper's implied idea that a chess position cannot be resolved unless its game tree is generated.

The paper's thesis that the size of the game tree rises polynomially with the board side is very likely to be correct (at least I cannot see a flaw in their reasoning for that), but the statement that this makes chess intractable on a large board is the 1970s equivalent of clickbait. Why is that clickbait included? For the same reason anyone ever creates clickbait: to get more attention than they would do without it (given that, in "The Art Of Computer Programming", Donald Knuth said that games like chess defy computer science analysis, you could be generous and say that the intractability of chess without generating the entire game tree was the prevailing doctrine at the time).

[chesskobra]

At it's heart, the paper is saying that the size of the chess game tree rises polynomially with the size of the board, and this makes resolving chess an intractable problem with increasing board size.

Where does the paper say that "the size of chess game tree rises polynomially with the size of the board"? I ask because an nxn board has n^2 squares and there are 4n pieces in the initial position. That already gives us of the order of binom{n^2}{4n} positions. Does this grow polynomially in n?

Also, does the paper say somewhere that there are no positions whose result can be easily determined?

[towforce]

Where does the paper say that "the size of chess game tree rises polynomially with the size of the board"?

It doesn't. I've said this as my interpretation of what it actually says, in order to enable us to discuss it. Please read what the paper actually says. Here's the link, and the section I'm asking you to read is called "POLYNOMIALITY OF TRANSFORMATION", which is a little over half a page long, and is on page 213.

Also, does the paper say somewhere that there are no positions whose result can be easily determined?

The paper gives ABSOLUTELY NO JUSTIFICATION WHATSOEVER for its own statement that chess intractable on an NxN board. In order to enable us to discuss the issue, I've had to work out and make explicit what the paper's implicit justification is. I've done this as follows: what the paper actually does say is:

1. It describes a game at length

2. It states that this game transforms to chess

3. It gives a reason for saying that this game is polynomial on an NxN board

From this, the implication is the game must be resolved by generating the entire game tree, and that the difficulty of doing this rises polynomially with the size of the board.

The part of this implication that I have attacked is "the game must be resolved by generating the entire game tree". To demonstrate that it's not necessarily true, all I need to do is provide an example position which:

1. Cannot have its game tree generated in a reasonable timescale

2. Can be proven to be a win

I've done this, so the implied part of their justification for saying that chess on an NxN board is intractable falls.

[towforce]

The paper gives ABSOLUTELY NO JUSTIFICATION WHATSOEVER for its own statement that chess intractable on an NxN board.

Oops!

From the lower half of p200 and the first paragraph pf p201 of the paper:

"What we can say, however, is that certain approaches for deciding whether a position in 8 x 8 chess is a winning position for White may not be very promising, namely, those aproaches which work for arbitrary positions and generalize to n X n boards... ...the “game-tree” of chess can be traversed in endorder to determine the win-lose-tie membership of each node (game position)."

Thus is is crystal clear that this paper is talking about (as I had correctly guessed) traversing the entire game tree from the current position. It assumes that chess cannot be resolved any other way, without providing any justification for this implicit assumption.

[chesskobra]

Where does the paper say that "the size of chess game tree rises polynomially with the size of the board"?

It doesn't. I've said this as my interpretation of what it actually says, in order to enable us to discuss it. Please read what the paper actually says.

Also, does the paper say somewhere that there are no positions whose result can be easily determined?

The paper gives ABSOLUTELY NO JUSTIFICATION WHATSOEVER for its own statement that chess intractable on an NxN board. In order to enable us to discuss the issue, I've had to work out and make explicit what the paper's implicit justification is. I've done this as follows: what the paper actually does say is:

So your interpretation that the number of positions grows polynomially with n is wrong - it is neither the fact nor do the authors say so. Let us discuss what the paper actually says.

Also, you didn't answer my question "does the paper say somewhere that there are no positions whose result can be easily determined?". I would like to know what you understand by 'intractable'.

I will gradually read the paper at my pace. But since it is a fairly technical paper in a top combinatorial theory journal, and you are willing to give a 2 line synopsis of what is at the heart of their argument, and are willing to call their conclusions click-bait, and that you have an easy counter example to their claim, I will be going into technical details of what the paper actually says, and how you and I interpret it.

[towforce]

So your interpretation that the number of positions grows polynomially with n is wrong - it is neither the fact nor do the authors say so. Let us discuss what the paper actually says.

What the paper has to say about the growth of the scale of chess on an NxN board as N increases is entirely in the section "POLYNOMIALITY OF TRANSFORMATION". It takes a little over half a page, and it's on page 213 of the paper.

It does not explicitly say that the size of the game tree increases polynomially with the size of the board - but this is my best interpretation of what it does say. Game tree size is mentioned earlier in the paper, and is a sensible interpretation of what the section says IMO.

Also, you didn't answer my question "does the paper say somewhere that there are no positions whose result can be easily determined?". I would like to know what you understand by 'intractable'.

It doesn't say that. The whole point of the paper is that the game tree becomes too large to be computable on an NxN board, so it is implied that positions in which the game tree is small can easily be resolved. What I showed you was a position with a large game tree that can easily be resolved, which contradicts the central message of the paper.

I will gradually read the paper at my pace.

Excellent! You have my full support in doing this!

But since it is a fairly technical paper in a top combinatorial theory journal, and you are willing to give a 2 line synopsis of what is at the heart of their argument, and are willing to call their conclusions click-bait, and that you have an easy counter example to their claim, I will be going into technical details of what the paper actually says, and how you and I interpret it.

Yes - I stand by my summary of the paper, which is as follows:

1. Chess transforms to a game described in the paper (the description of this game is the bulk of the paper)

2. The complexity of this game increases polynomially with the size of the board


Once again, for everyone's convenience, here's a link to the paper - link.

In the section about computational complexity (P201), the following is stated:

"A nondeterministic algorithm is an “algorithm” which can “guess” an existential solution, such as a path in a tree and then verify its validity by means of a deterministic algorithm."

A very strange definition! Firstly, this algorithm would use a heuristic to choose a candidate solution, then use another algorithm to prove that solution. In the simple position I provided (king and rook v king), you could prove the win by exhaustive search of the game tree (the only type of proof I can find in the paper), or you can prove it as follows:

1. Prove that the black king can be forced to the edge of the board

2. Prove that the black king can be mated at the edge of the board

There is nothing in the paper about using such techniques to prove the outcome of the position.

[towforce]

Once again, for everyone's convenience, here's a link to the paper - link.

In the section about computational complexity (P201), the following is stated:

"A nondeterministic algorithm is an “algorithm” which can “guess” an existential solution, such as a path in a tree and then verify its validity by means of a deterministic algorithm."

A very strange definition! Firstly, this algorithm would use a heuristic to choose a candidate solution, then use another algorithm to prove that solution.

This needs clarification: in this context, "nondeterministic algorithm" basically means using heuristics to select which forks in the game tree to choose, and then checking that the outcome is a win. Here's the relevant section from the wiki article about nondeterministic algorithms - link (the paragraph starting with "In computational complexity theory...").

In the simple position I provided (king and rook v king), you could prove the win by exhaustive search of the game tree (the only type of proof I can find in the paper), or you can prove it as follows:

1. Prove that the black king can be forced to the edge of the board

2. Prove that the black king can be mated at the edge of the board

Thus heuristics can be at the level of mathematical proof.

[petero2]

Let us discuss what the paper actually says.

A high-level description of their proof that generalized chess cannot be solved in polynomial time is as follows:

1. It is known from prior work that the game G3 is EXPTIME-complete.

2. It is known from prior work that P != EXPTIME, which means that any algorithm that can solve all problems in G3 requires more than polynomial time for some problem instances.

3. An algorithm can be created that transforms any problem in G3 to a corresponding problem in generalized chess, and the time required to execute this algorithm is polynomial in the size of the G3 problem instance, and the size of the resulting generalized chess position is polynomial in the size of the G3 problem instance. This is the main achievement of the paper.

4. The rest of the proof is by contradiction. Assume there is an algorithm that can solve any generalized chess problem in polynomial time. This algorithm could then be combined with the reduction algorithm from 3 to create an algorithm for solving any problem in G3 in polynomial time. But this is known to be impossible from 2, which means that the assumption is wrong, and generalized chess therefore cannot be solved in polynomial time.

The above proof technique is very similar to how problems are proven to be NP-complete (see polynomial-time reduction) or undecidable (see Turing reduction).

The difficult part of the proof is step 3, and unfortunately the drawings in the paper have low quality, so it is not easy to follow their description of the reduction.

The paper also claims that there are an infinite number of positions that require more than polynomial time to solve, even though the worst case execution time would be more than polynomial even if only one problem instance required more than polynomial time. However, it is easy to prove that there must be an infinite number problem instances that require more than polynomial time to solve. If it was possible to construct a polynomial time algorithm that only fails on a finite number of positions, it would be trivial to extend this algorithm to a perfect algorithm by adding a lookup table for the finite number of positions the algorithm cannot solve. But it has already been proven that such a perfect algorithm does not exist. Therefore a polynomial time algorithm that only gets a finite number of positions wrong does not exist either.