Chess solved?

[towforce]

I accept that there's no hard proof that solving chess like algebra is possible, but I think that the balance of evidence is that it can be: people have written theorem proving software, so why wouldn't chess theorem proving software be possible?

Do you believe chess to be special, or do you believe that any two-player zero-sum game with full information can be solved "like algebra"? After all, all the evidence you have is based on games that are totally unrelated to chess.

(As discussed earlier, it is trivially true that chess has a solution and that an algorithm exists to find it. Apparently "like algebra" means that constructing, storing and verifying the proof can be done with limited computational resources, let's say one year of a TOP 10 super computer.)

Thank you for demonstrating an interest in my posts with thoughtful, challenging follow up questions!

Yes - I believe that any two player game with full information can be solved like algebra (assuming the game itself doesn't contain any non-algebraic attributes, which I don't think chess does). As a simple example, you could make an equation with a huge number of parts, and you'll find that a CAS would be able to solve it quickly. A CAS has a large number of ways to simplify or solve expressions, and there's no reason why a chess solver couldn't as well. A CAS can do a large number of simplification or resolving steps in a second, and there's no reason why a chess solver wouldn't be able to. For this reason, I don't think you'd need a supercomputer: I've done a large amount of work with CAS software, but never once used anything other than a standard PC. My thinking is that a PC should be able to solve almost any legal chess position in well under a second.

I might be wrong: it might be that, in a complex position (like the start position), the extremely large number of ways to get to checkmate makes it prohibitively difficult. That doesn't mean that other ways of solving chess don't exist. Very often, in solving a maths puzzle, it's very helpful to "get the solution dirty", and from the solution, work out how the solution can be properly "worked out". This naturally prompts me to think in terms of fitting polynomials to the multi-dimensional space of chess, and, if reasonably "clean" polynomials arise, then using these polynomials to tell me what the relationship between the position properties is in win/draw/lose positions. If all goes well, this will enable me to construct the rules for won or drawn positions. It might be that to solve a position 100 moves ahead, you have to construct a polynomial of degree 100. If so, that would very obviously by P, and not NP!

For simple turn-based games, it's not difficult to discern win/draw rules. It seems to me that in more complex turn-based games, people haven't tried very much to solve it like a puzzle.

[jp]

According to my calculations, once you have an advantage of 444 centipanwns or more, you are almost certainly going to win.
It might be hard to prove it, but I guess new technology will make it easier in about 5 years

What calculations are these? It sounds like you've just made a statistical observation, which just forms a rule of thumb.

[jp]

I have wasted a fair amount of cpu time trying to prove that giving queen odds is a forced loss.

So what can you prove is a forced loss, Queen + rook, Queen + 2 rooks ?

If you trust engines' mate announcements, then this board has shown forced losses for odds of:

8 pawns, 2 rooks, 2 bishops, 2 knights;
8 pawns, queen, 2 bishops, 2 knights;
Queen, 1 rook, 2 bishops, 2 knights;
and some larger odds.

( http://talkchess.com/forum3/viewtopic.php?t=73030 )

Those are quite large odds to give. (But someone did say that he won a game against a child at odds of Queen, 2 rooks, 2 bishops, 2 knights.)

There was also debate about whether you can trust mate-in-N engine announcements, especially if N is large.

[syzygy]

I accept that there's no hard proof that solving chess like algebra is possible, but I think that the balance of evidence is that it can be: people have written theorem proving software, so why wouldn't chess theorem proving software be possible?

Do you believe chess to be special, or do you believe that any two-player zero-sum game with full information can be solved "like algebra"? After all, all the evidence you have is based on games that are totally unrelated to chess.

(As discussed earlier, it is trivially true that chess has a solution and that an algorithm exists to find it. Apparently "like algebra" means that constructing, storing and verifying the proof can be done with limited computational resources, let's say one year of a TOP 10 super computer.)

Thank you for demonstrating an interest in my posts with thoughtful, challenging follow up questions!

Yes - I believe that any two player game with full information can be solved like algebra (assuming the game itself doesn't contain any non-algebraic attributes, which I don't think chess does).

But where is your evidence? All games that have been solved either have a very particular invariant-preserving structure like NIM or were sufficiently simple that a proof tree could be constructed. There is no evidence that arbitrary two-player games with perfect information can be tackled with an invariant-based trick. (And I know of no game that has been solved by a CAS.)

There are results like this one that strongly suggest that no efficient algorithm exists:
https://www.sciencedirect.com/science/a ... 0078900454

Of course the problem with looking at a single finite game like chess is that alpha-beta solves it in O(1), the constant being really big but uninteresting from an algorithmic-complexity point of view.

As a simple example, you could make an equation with a huge number of parts, and you'll find that a CAS would be able to solve it quickly. A CAS has a large number of ways to simplify or solve expressions, and there's no reason why a chess solver couldn't as well. A CAS can do a large number of simplification or resolving steps in a second, and there's no reason why a chess solver wouldn't be able to. For this reason, I don't think you'd need a supercomputer: I've done a large amount of work with CAS software, but never once used anything other than a standard PC. My thinking is that a PC should be able to solve almost any legal chess position in well under a second.

A CAS may be wonderful but can't work miracles. If no solution exists, it will not find any. And if a solution exists but the search space is just too big, there can be no guarantee that the solution is found within a reasonable time.

Did anyone else ever make a connection between solving two-player games and a CAS? If you are the first, can you explain the connection without hand waving?

I might be wrong: it might be that, in a complex position (like the start position), the extremely large number of ways to get to checkmate makes it prohibitively difficult. That doesn't mean that other ways of solving chess don't exist. Very often, in solving a maths puzzle, it's very helpful to "get the solution dirty", and from the solution, work out how the solution can be properly "worked out". This naturally prompts me to think in terms of fitting polynomials to the multi-dimensional space of chess, and, if reasonably "clean" polynomials arise, then using these polynomials to tell me what the relationship between the position properties is in win/draw/lose positions. If all goes well, this will enable me to construct the rules for won or drawn positions. It might be that to solve a position 100 moves ahead, you have to construct a polynomial of degree 100. If so, that would very obviously by P, and not NP!

This is what I would call hand waving. "Fitting polynomials to the multi-dimensional space of chess".

For simple turn-based games, it's not difficult to discern win/draw rules. It seems to me that in more complex turn-based games, people haven't tried very much to solve it like a puzzle.

Perhaps you can present us with a CAS-based solution to tic-tac-toe.

[towforce]

All games that have been solved either have a very particular invariant-preserving structure like NIM or were sufficiently simple that a proof tree could be constructed. There is no evidence that arbitrary two-player games with perfect information can be tackled with an invariant-based trick.

In WWII, German experts assumed that ciphers like Enigma and Lorenz could not be solved in a useful amount of time. However, there were enough people with enough ability and enough motivation to crack them - and so they got cracked. They were good ciphers - but they weren't perfect, and usable emergent patterns arose in them.

Chess was not designed to avoid being cracked at all: it would be very surprising if there weren't a large number if useful emergent patterns in it.

GMs play good chess at more-or-less ply 1. It would be very surprising if they represent the limit of what's possible at ply one. Humans playing chess tend to be guided by visual aspects of the game. It's very likely that there are many very good non-visual patterns in the game which are actually very good tells to the strength of a position. It is also likely that different types of patterns combined in a way that's too difficult for a human also give very good tells.

Also, consider Fermat's Last Theorem (link). We now know it to be true - but the method used to prove it used some mathematics that wasn't available to Fermat.

There are results like this one that strongly suggest that no efficient algorithm exists:
https://www.sciencedirect.com/science/a ... 0078900454

I've just read that paper carefully, and I see some work done on some games which I cannot find in YouTube (a shame, because the graph theory based games look interesting), but not any evidence that no efficient algorithms are possible for solving them. If I've missed something, please quote that section of the paper.

As a simple example, you could make an equation with a huge number of parts, and you'll find that a CAS would be able to solve it quickly. A CAS has a large number of ways to simplify or solve expressions, and there's no reason why a chess solver couldn't as well. A CAS can do a large number of simplification or resolving steps in a second, and there's no reason why a chess solver wouldn't be able to. For this reason, I don't think you'd need a supercomputer: I've done a large amount of work with CAS software, but never once used anything other than a standard PC. My thinking is that a PC should be able to solve almost any legal chess position in well under a second.

A CAS may be wonderful but can't work miracles. If no solution exists, it will not find any. And if a solution exists but the search space is just too big, there can be no guarantee that the solution is found within a reasonable time.

That's a straw-man argument: I didn't say a CAS could solve two-player games (though it might be possible): I was giving an analogy of a different type of puzzle that software can resolve efficiently.

Here is a more straightforward version of the analogy:

Chess:

* in simple positions, it's easy to prove the outcome of the game

* a large number of ways to construct such resolutions exist

* it is possible to combine such techniques to resolve more complex positions

Computer Algebra System

* for simple expressions, it's easy to resolve them

* a large number of ways to construct such resolutions exists

* a CAS can combine many such methods to resolve complex expressions

This is what I would call hand waving. "Fitting polynomials to the multi-dimensional space of chess".

We might have to agree to differ on this: fitting polynomials to the multi-dimensional space of chess looks like a completely obvious thing to do to me. Why wouldn't you do it?

Top tip: there are many ways to tell whether a set of numbers is random or not, but one way is to map the numbers into multi-dimensional space: there, non-random numbers tend to form obvious patterns.

Likewise, if, as I suspect, the patterns needed to resolve chess are actually a lot simpler than most people are expecting, it would be possible to make good polynomial fits to the multiple dimensions of chess with simpler polynomials than most people would expect.

Perhaps you can present us with a CAS-based solution to tic-tac-toe.

I am confident that one could write out a set of rules for best play for that game that would avoid the need for a player to build a game tree to the end of a game.

[syzygy]

All games that have been solved either have a very particular invariant-preserving structure like NIM or were sufficiently simple that a proof tree could be constructed. There is no evidence that arbitrary two-player games with perfect information can be tackled with an invariant-based trick.

In WWII, German experts assumed that ciphers like Enigma and Lorenz could not be solved in a useful amount of time. However, there were enough people with enough ability and enough motivation to crack them - and so they got cracked. They were good ciphers - but they weren't perfect, and usable emergent patterns arose in them.

Chess was not designed to avoid being cracked at all: it would be very surprising if there weren't a large number if useful emergent patterns in it.

I'd say it is more like chess is a random real number and you are hoping it to be a rational number.

But it seems we are close to agreeing that your original evidence is not really evidence.

As a simple example, you could make an equation with a huge number of parts, and you'll find that a CAS would be able to solve it quickly. A CAS has a large number of ways to simplify or solve expressions, and there's no reason why a chess solver couldn't as well. A CAS can do a large number of simplification or resolving steps in a second, and there's no reason why a chess solver wouldn't be able to. For this reason, I don't think you'd need a supercomputer: I've done a large amount of work with CAS software, but never once used anything other than a standard PC. My thinking is that a PC should be able to solve almost any legal chess position in well under a second.

A CAS may be wonderful but can't work miracles. If no solution exists, it will not find any. And if a solution exists but the search space is just too big, there can be no guarantee that the solution is found within a reasonable time.

That's a straw-man argument: I didn't say a CAS could solve two-player games (though it might be possible): I was giving an analogy of a different type of puzzle that software can resolve efficiently.

Huh? Are you no longer planning to solve chess with a CAS?

This is what I would call hand waving. "Fitting polynomials to the multi-dimensional space of chess".

We might have to agree to differ on this: fitting polynomials to the multi-dimensional space of chess looks like a completely obvious thing to do to me. Why wouldn't you do it?

Why wouldn't you do it?

I'm not going to do it because I have no idea what "the multi-dimensional space of chess" could mean. (Just to be clear, I do understand you weren't referring to "me" specifically.)

Perhaps you can present us with a CAS-based solution to tic-tac-toe.

I am confident that one could write out a set of rules for best play for that game that would avoid the need for a player to build a game tree to the end of a game.

Show us how you convert the basic rules of tic tac toe in a set of polynomial equations such that a solution to those equations is equivalent to a solution of/optimal strategy for tic tac toe.

[towforce]

I'd say it is more like chess is a random real number and you are hoping it to be a rational number.

I personally would be VERY surprised if the game of chess didn't contain enough emergent properties to enable a quick algorithm to be created to solve it for almost all reachable positions at ply 1.

I am almost certain that it would be easy to prove that the best move (or moves) in a set of positions had important differences from random selections.

But it seems we are close to agreeing that your original evidence is not really evidence.

It's not "proof", but it is "evidence".

Huh? Are you no longer planning to solve chess with a CAS?

I apologise if I gave the impression that I thought I'd be using a CAS to solve chess. What I wanted to convey is that there is analogy between how a CAS solves complex expressions and how it might be possible to solve complex chess positions.

We might have to agree to differ on this: fitting polynomials to the multi-dimensional space of chess looks like a completely obvious thing to do to me. Why wouldn't you do it?

Why wouldn't you do it?

Just to be clear, this is a completely different idea to the one about solving chess like a CAS solves a complex mathematical expression. This is the one that I would choose, because I believe in it more strongly. The first step is for me to write software that would fit polynomials to multi-dimensional problems. There are an infinite number of polynomials that could be fitted, but, IMO, for making polynomials that are useful for AI, the polynomial you want to fit is the simplest possible fit. For me, this would have some key benefits over NNs:

1. the polynomial fit could actually be optimised for AI purposes - from start to finish

2. the resulting expression would be simpler than the expression an NN would produce (e.g. it would run against new positions an order of magnitude more quickly)

3. it would be easier to look at the resulting expression and disentangle what it was telling us about the relationships between the attributes of the position

The polynomial fitting tool I'm thinking of building would have widespread usage - not just for chess.

I'm not going to do it because I have no idea what "the multi-dimensional space of chess" could mean. (Just to be clear, I do understand you weren't referring to "me" specifically.)

My initial estimate of the number of dimensions would be "several hundred" - but if the polynomial fitting told me that some of those dimensions aren't needed, they could be discarded. Very quickly (I haven't thought out the detail here), I think that I'd want a dimension for each possible piece (8 pawns, 2 rooks, 2 knights, 2 bishops, one queen, one king, each in two colours), and one dimension for each relationship between each piece and each other piece (I reserve the right to change my mind about what the dimensions should be). Constructing a polynomial of several degrees will enable a fitting process to capture emergent relationships. Then, of course, you would need a large number of positions, each with a reliable (but, importantly, NOT exact: to get the simplest possible fit, the evaluations would need to be in the form of a wide range) evaluation. The challenge would then be to construct the simplest polynomial possible that generates scores within the acceptable range for each sample position provided.

[Dann Corbit]

I have no idea if a formal proving system can prove even a simple game like tic-tac-toe.

This is an automated proving system called Otter:
https://www.cs.unm.edu/~mccune/otter/

Vastly simpler, of course, but here is an example of using Otter to solve the 8 queens problem:
https://www.mcs.anl.gov/research/projec ... /queens.in

This is the successor to Otter:
https://www.cs.unm.edu/~mccune/prover9/

[Dann Corbit]

Another thing:
https://www.tautvidas.com/blog/2019/02/ ... em-prover/

I do not imagine that using a prover to solve a complex game is simpler than other methods.
So, if you can solve complex games with a prover, my supposition is that it is computationally expensive

[towforce]

I have no idea if a formal proving system can prove even a simple game like tic-tac-toe.

Maybe - but it might be better to build an application specifically for the domain.

* think about how you could determine whether a tic-tac-toe position is won/drawn/list without building a tree

* think about things that are known in chess (e.g. king + rook beats king)

* think about how you might resolve the outcome if two such rules are both present