Chess solved?

[towforce]

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

Interesting: the tool being used here is actually a SAT solver.

If you can formulate the various attributes present in a chess position as a SAT model, you'd be impressed how quick and efficient modern SAT solvers are.

[Dann Corbit]

http://www.cse.unsw.edu.au/~mit/Papers/IJCAI09.pdf
https://drops.dagstuhl.de/opus/volltext ... 019-25.pdf
Oink solves parity games:
https://github.com/trolando/oink
which are not much like other games:
https://en.wikipedia.org/wiki/Parity_game
But it is interesting that graph traversal is involved, and games like chess involve a graph (a tree being a particular instance of a graph)

I think this is the most interesting:
https://www.bc.edu/content/dam/bc1/scho ... ample5.pdf

I don't really see any sort of direct connection to a game like chess in any of this stuff, but it is an interesting subject.

[Dann Corbit]

This thing looks very interesting:
http://www.gambit-project.org/

They give a hint that it may not be so useful for complex games in the documentation, though.

[Dann Corbit]

Speaking of tic-tac-toe:
https://github.com/elben/sat

[syzygy]

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.

Do you mean that you believe chess to be special? Do you have any evidence that it is special? As I said, all the evidence you mentioned before relates to games that are totally unrelated to chess. And none of them have been solved "with polynomials".

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.

Sure, and it is trivial to formalise this using the alpha-beta algorithm. But that does not help you any further.

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

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

Yes, I understand that. By "is not really evidence" I mean that the (empirical) evidence does not hold up under scrutiny.

Your evidence is that several other games have been solved.
As I explained, all of these games either have some special property (usually their rules preserve some invariant) or were sufficiently small that a proof tree could be constructed. We seem to agree that constructing a proof tree for chess is not feasible with current technology.

Since I see no reason to think that chess is special, I see no empirical evidence that supports the belief that chess can be solved with current technology (let alone "with polynomials").

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.

OK, so CAS is as unrelated to the current discussion as the fruitless attempts by hundreda of very brilliant mathematicians to prove or disprove the Riemann conjecture.


As for the polynomials, from what you write you seem to be thinking of fitting a polynomial evaluation function to a number of "solved" positions and hoping that the resulting function will give meaningful values for all positions. And it seems the polynomial evaluation function will have to be constructed by trial and error.

How do you want to formally verify that a particular polynomial evluation function that you have constructed indeed does give the correct value for all positions? Perhaps by testing it on a million positions (comparing their polynomial evaluation with SF's evaluation?) and then arguing that the evidence suggests that you have found the solution to chess?

[Ozymandias]

I don't know how to tell them, "My house is a place where we turn electricity into chess."
I am not sure they would understand, even if I explained it very carefully

Alternatively, you could place your computers all over your house, so that they substitute regular heating. Electricity based heating is inefficient, so the graph would be quite normal then. Granted, you lose a few months in summer, but at least you got them off your back.

[supersharp77]

How many more elo until chesd considered solved?

ELO around 7799 or so.....That means all openings played perfectly (including gambits) perfect middlegame play and absolutely perfect endgame play with no.. 0% mistakes...based on what I am seeing...that may take a little time..

[chrisw]

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.

Do you mean that you believe chess to be special? Do you have any evidence that it is special? As I said, all the evidence you mentioned before relates to games that are totally unrelated to chess. And none of them have been solved "with polynomials".

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.

Sure, and it is trivial to formalise this using the alpha-beta algorithm. But that does not help you any further.

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

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

Yes, I understand that. By "is not really evidence" I mean that the (empirical) evidence does not hold up under scrutiny.

Your evidence is that several other games have been solved.
As I explained, all of these games either have some special property (usually their rules preserve some invariant) or were sufficiently small that a proof tree could be constructed. We seem to agree that constructing a proof tree for chess is not feasible with current technology.

Since I see no reason to think that chess is special, I see no empirical evidence that supports the belief that chess can be solved with current technology (let alone "with polynomials").

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.

OK, so CAS is as unrelated to the current discussion as the fruitless attempts by hundreda of very brilliant mathematicians to prove or disprove the Riemann conjecture.


As for the polynomials, from what you write you seem to be thinking of fitting a polynomial evaluation function to a number of "solved" positions and hoping that the resulting function will give meaningful values for all positions. And it seems the polynomial evaluation function will have to be constructed by trial and error.

How do you want to formally verify that a particular polynomial evluation function that you have constructed indeed does give the correct value for all positions? Perhaps by testing it on a million positions (comparing their polynomial evaluation with SF's evaluation?) and then arguing that the evidence suggests that you have found the solution to chess?

Well, how to 'solve' chess via an evaluation function?

We tried the computation method of splitting the chess position into features, applying weights and adding them up. Works up to a point but nowhere near solving (without AB and a lot of time).

We tried a lookup function, but didn't yet get beyond 7 or 8 pieces, because the address space is impossibly large.

We tried a mix of a lookup and a computation, neural network, which can be seen as stacked layers of spreadsheets, or stacked polynomials, and we were quite surprised when this gave ply one 'lookup' results which can arguably be seen as approaching GM strength, or arguably may approach GM strength given a few years.

If we're prepared to overlook the inexact nature of NN output, it looks already that we managed to short-circuit the impossibly large address space and/or impossibly large search time by using/training stacked polynomials (at the cost of inexactitude). For some reason, towforce wants to reduce the stack to one layer and apply some sort of pre-processing of terms (psq) that finds the necessary non-linearities beforehand. he doesn't call it that, preferring a wide range of mixed word salads, 'Fitting polynomials to the multi-dimensional space of chess", or theorem proving, or finding emergent properties or whatever. Essentially, he's arguing to take the non-linearity finder of the hidden layers of an NN, work out how to apply those non-linearites to pre-process the inputs, et voila, add them all up in a weighted polynomial. Since 'Fitting polynomials to the multi-dimensional space of chess" is currently the function of the hidden layers of NN, with his 'polynomial' being the final layer, our best technology is already doing it, with, as we know, inexactitude being the price paid for shrinking the address space from impossibly large to tractable. His 'Fitting polynomials to the multi-dimensional space of chess" means essentially unravelling the hidden layers of the NN and still doesn't constitute a solve or "proof" of chess (inexact output result).

[towforce]

Since I see no reason to think that chess is special, I see no empirical evidence that supports the belief that chess can be solved with current technology (let alone "with polynomials").

I think you have "special" the wrong way around - "special" systems are the ones that don't have emergent patterns:

* most systems have emergent patterns

* most mathematical conjectures can be proved or disproved

The first point is obvious: if the world didn't behave in predictable ways, then there would be no "survival of the fittest" value in the evolution of intelligence. More subtly, it's harder than you think to design a system without emergent patterns: the WWII Enigma and Lorenz ciphers' emergent patterns were unwanted - they would have been more "fit for purpose" if they hadn't had them! The game of chess was absolutely not designed to avoid yielding emergent patterns to powerful types of search.

As for the polynomials, from what you write you seem to be thinking of fitting a polynomial evaluation function to a number of "solved" positions and hoping that the resulting function will give meaningful values for all positions.

Roughly speaking, yes - and I intend to construct those polynomials in a way that will yield maximum useful information.

And it seems the polynomial evaluation function will have to be constructed by trial and error.

No. The secret sauce is my idea for generating the polynomial that would yield the maximum amount of useful information with the minimum number of terms (and polynomial degree).

How do you want to formally verify that a particular polynomial evaluation function that you have constructed indeed does give the correct value for all positions? Perhaps by testing it on a million positions (comparing their polynomial evaluation with SF's evaluation?) and then arguing that the evidence suggests that you have found the solution to chess?

Having got to this stage, the next task would then be to find ways to tease out the relationships between chess position attributes that the polynomial has uncovered. It would be surprising if some important relationships that are currently unknown weren't found, and there may be something there that can be parlayed into a complete solution: a rule that's quick to compute and which could be applied to any reachable position.

[towforce]

I think this is the most interesting:
https://www.bc.edu/content/dam/bc1/scho ... ample5.pdf

I don't really see any sort of direct connection to a game like chess in any of this stuff, but it is an interesting subject.

It is interesting, and it could be applied to chess - but it would be difficult. Here, stated in a greatly oversimplified way ( ), is what you have to do:

* come up with a list of tells as to whether a position is won or drawn, and ways to relate them to each other

* for the given chess position, write out the above information which applies to the position in CNF.

* have a SAT solver find a solution to the CNF (if it can, the conjecture constructed above is true: if it cannot, then the conjecture is false).

Solving SAT problems is often quick, but can be computationally expensive. I strongly suspect that it would be MASSIVELY quicker than building a complete game tree to the end of the game, though. Another way of putting it: I would be ABSOLUTELY AMAZED if it wasn't.