Chess solved?

[duncan]

If would be surprising if towforce were not able to square the circle. I encourage him to take a couple of years to try.

Is it possible in the future that queen vs rook end game can be solved with an algorithm of 10 lines of code?

[duncan]

I 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!

Thanks for your explanation.
Are you planning to respond to Chris's Linear evaluations with tic-tac-toe, thread?

Are you planning to respond to Chris's Linear evaluations with tic-tac-toe, thread?

[syzygy]

What the paper ACTUALLY proves is that, in worst case scenarios, the shortest path (minimum number of moves) from the current position to the end of the game, given an opponent who is trying their hardest to stop you, can grow exponentially in n on an n*n chessboard (I am not convinced that their case is watertight, but given that disproving it would take a lot of time, I'll grant that assertion as "maybe correct" for the purpose of this discussion).

What part of the paper are you basing this on?

The paper proves that if you have an algorithm to decide the problem Q = "Given an arbitrary position of a generalized chess game on an n×n chessboard from our class of chess games, can White (Black) win from that position?", then you also have an algorithm to decide the problem G_3 (up to a transformation that takes polynomial time in n). Since G_3 is known to take exponential time in n, there is no hope for an efficient algorithm to solve Q.

It does not matter how you are going to try to tackle Q, unless you believe that mathematics is inconsistent (or can point out an actual problem in the construction that the paper develops to reduce G_3 to Q).

[jp]

What the paper proves is that any algorithm that solves NxN chess requires a number of computational steps that is asymptotically exponential in N. The paper proves this by showing that another game that is known to be EXPTIME-complete can be reduced to NxN chess. This means that NxN chess is EXPTIME-complete as well. A problem is EXPTIME-complete if any problem solvable in exponential time (or less) can be reduced to it with at most polynomial overhead.

One of towforce's problems with understanding the proof is that he obviously has no idea what a reduction is. Hence, he keeps repeating questions that make zero sense like where in the paper it shows there are no quick chess rules, etc.

So perhaps it would help him if he read some textbook material online on computational complexity.

[towforce]

Btw, your "shortest path problem" is computationally really easy to solve.

I know: I told you that the complexity is O(edges + vertices). I deliberately chose a simple problem so that we could discuss the issue, rather than the problem itself.

[towforce]

The proof in the original paper is that chess has key mathematical transformations to boolean game G3, and that boolean game G3 has already been proven to be exponentially more difficult to resolve as its size increases. The original paper says nothing whatsoever about proving that G3 is EXPTIME complete, so actually the paper we need to be looking at is the one that claims to prove that G3 is EXPTIME complete. That would be this paper - link.

I will look at that paper and then come back with comments (I'm not promising how long I will take to respond).

[towforce]

The proof in the original paper is that chess has key mathematical transformations to boolean game G3, and that boolean game G3 has already been proven to be exponentially more difficult to resolve as its size increases. The original paper says nothing whatsoever about proving that G3 is EXPTIME complete, so actually the paper we need to be looking at is the one that claims to prove that G3 is EXPTIME complete. That would be this paper - link.

I will look at that paper and then come back with comments (I'm not promising how long I will take to respond).

This is a MASSIVELY better paper than the chess paper: it's an order of magnitude clearer, and in terms of quality, I am seeing many positive indicators and very few negative ones.

I haven't finished reading it yet, so apologies if this is premature, but a couple of observations:

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.

Page 3: the paper mentions that SAT has been proven to be NP-Complete (which is correct). However, many large SAT problems (thousands of variables, millions of statements) can be resolved quickly.

We know that many 8*8 chess positions can be resolved by heuristics: a strong player can often look at a board and quickly declare, correctly, that one side will win. It's also safe to say that the set of positions that could be resolved by heuristics is greater than the set of positions are able to be resolved that way by human players. We don't yet know the upper limit of positions that could be, or whether the rate of growth of the size of a single heuristic would necessarily have to grow at the same rate as the number of positions it could resolve accurately.

The original question in this thread was (paraphrased) at what level of elo will all chess games be drawn: my opinion is that computer chess will get to that level without having to either completely reduce the game to atomic component positions or resolve the entire game tree. If I am right about that (and I would guess that most people who have thought about it, and who agree that chess is almost certainly drawn, would agree), then that alone is proof that chess can be solved (though not proven to be solved) at less than the full complexity of the game.

[syzygy]

The proof in the original paper is that chess has key mathematical transformations to boolean game G3, and that boolean game G3 has already been proven to be exponentially more difficult to resolve as its size increases.

I don't know why you would call them "key" (perhaps it sounds more interesting), and the transformation is from the boolean game G3 to Q = NxN chess, not the other way around. (From the fact that Q is in EXPTIME and G3 is EXPTIME-complete, it follows that a polynomial transformation from Q to G3 also exists, but the paper does not and need not describe one.)

The paper shows that any instance of G3 can be transformed into/encoded as an instance of Q with polynomial overhead. This implies trivially that an algorithm to decide Q can be used to decide G3 with at most polynomial overhead.

Basically, the paper shows that NxN chess is sufficiently expressive to express G3. The same technique has been used to show that there exist no algorithm at all to decide if an instance of the Game of Life will die out or if a system of diophantine equations has a solution (both problems are sufficiently expressive to encode any algorithm/Turing machine).

The original paper says nothing whatsoever about proving that G3 is EXPTIME complete, so actually the paper we need to be looking at is the one that claims to prove that G3 is EXPTIME complete.

Only if you have no trust whatsoever in long-standing results in theoretical computer science.

If you trust yourself more than a couple of generations of theoretical computer scientists in an area in which you obviously have no expertise, then Dunning-Kruger effect is the proper term.

[syzygy]

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

We know that many 8*8 chess positions can be resolved by heuristics: a strong player can often look at a board and quickly declare, correctly, that one side will win.

There are lots of mate-in-1 positions that even I can solve quickly.

The fact that simple-to-solve positions exist does not mean that the initial position can be solved quickly. There is certainly no general technique to solve any NxN chess position in a short time (because the non-existence of such a technique has been proven).

So, perhaps there is a miracle trick that can be used to give a quick proof that the initial position is a draw (or a white win or a black win) but there is no evidence for the existence of such a trick at all. Such a trick can exist only if the initial position is "special" in the sense that it has a particular mathematical structure that does not exist in all of NxN chess. There is no reason to believe that the initial position is special.

But I see that you are now bowing out of your original position and are retreating to "it's enough for me that engines play really strong chess".

[towforce]

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

Now move forward a year to 1995: suddenly, it's proven for all X,Y,Z positive integers greater than 1. That was done by using some new mathematics which was able to sidestep the complexity issue. It's not possible to say that there will never be any more new maths that will enable some types of EXPTIME problems to be 100% solved in less than EXPTIME.

But I see that you are now bowing out of your original position and are retreating to "it's enough for me that engines play really strong chess".

Perhaps we need a new term: how about... "practically solved". What I mean by this is what I think the OP meant: a machine that's so strong that no other machine ever beats it. It would be nice if this could be achieved with a quick EF that doesn't build a game tree. I think this would be possible if humans already have a reasonable proportion of the knowledge needed (say 10% - on the grounds that top GMs would probably not be far from unbeatable if they knew 10x more about chess than they actually do).

I might be wrong about this, but I think that if a GM plays for a draw against another GM, they've actually got a good chance of getting it.