Chess solved?

[towforce]

It is possible that the proof tree is not a worst case size. Suppose, for instance, from the root position there is a checkmate in 42 that nobody has ever found that is forced from the root position. Once the mate was verified, chess would be weakly solved.

Unfortunately, it is likely that the opposite is true - that it's not possible for either side to be able to force any material gain in the first 30 moves. Or any number of moves.

[towforce]

I'm sorry but "emergent' is just a meaningless term in this ill-defined context.

It means that in what look like highly complex setups, surprisingly simple patterns often arise.

It is quite clear that your "polynomial evaluation function" is not going to be of any help here. Just like an NN-based evaluation function or a handcrafted evaluation function is not going to do the job.

Actually, you cannot eliminate the possibility that either a handcrafted EF or an NN might be able to do the job. I think the multi-dimensional polynomial fit has a better chance: it would be able to uncover relationships that humans might miss, and if it works well, it would be relatively easier to "reverse compile" it and get some meaning from it. Once the humans can understand what relationships it has uncovered, they might be able to work from that to create an EF that works well in almost all positions.

[jp]

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

But it's only quick if we get lucky with the particular instance of the SAT problem, right? Typically, solving an instance of the SAT problem is exponentially slow.

So why would we expect the initial chess position to map to a lucky easy instance of SAT? We might guess that those instances map to e.g. positions where the 32 chess pieces are two kings and 30 White queens.

[towforce]

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

But it's only quick if we get lucky with the particular instance of the SAT problem, right? Typically, solving an instance of the SAT problem is exponentially slow.

So why would we expect the initial chess position to map to a lucky easy instance of SAT? We might guess that those instances map to e.g. positions where the 32 chess pieces are two kings and 30 White queens.

The only way to know would be to build it out and try it. I suspect that the bigger problem would be generating correct sets of CNF expressions when both black and white have multiple mating threats. It would be worth trying out simple endgame positions to ensure we've mastered that part of it, and then plotting SAT resolution time against position complexity.

My gut feeling is that this method of solving chess is going to be very difficult, and, as you point out, given that all permutations of checkmate are possible at the start of the game, the CNF expression list at the start of the game might be impractically large.

[Dann Corbit]

The main problem, as I see it, is that the fundamental nature of chess is exponential.
So I think that a solution will have to deal with that level of complexity.
Any simpler sort of solution would be some kind of stroke of good fortune (like a forced solution nearby).

If there were no tempo advantage, it would seem an incredibly even game. The only thing besides the initial tempo is that the position of black and white are not duplicates but mirrors because of the queen sitting on her own color. So that at the start of the game the king is closer to your right hand if you are playing as white and to your left if you are playing as black.

But if we think of it like a battle, the armies are exactly equal in size and strength. If there is perfect play, a draw outcome seems very logical.

[syzygy]

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

But it's only quick if we get lucky with the particular instance of the SAT problem, right? Typically, solving an instance of the SAT problem is exponentially slow.

Yes, unless P=NP. (But even if P=NP and we could prove that P=NP, we might never discover the polynomial-time algorithm.)

Of course chess is solved in O(1) either way because it is just one finite calculation.

So why would we expect the initial chess position to map to a lucky easy instance of SAT? We might guess that those instances map to e.g. positions where the 32 chess pieces are two kings and 30 White queens.

The argument is that "it would be strange" if we would not be lucky.

[Ozymandias]

I have several smaller systems that pull a few hundred watts and I don't turn them off. But the 64 amd 128 core commercial systems take a nap starting in July and come back on line in October.

The commercial systems are also very loud. You have to buy sound proof boxes for them to use them in a house (unless you were to build your own dedicated server room, which I am considering -- I would also want to wire the room for 220V and add special dedicated air conditioning).

Pretty much what I figured. Your smaller systems draw more power than all of mine combined and you leave them on continuously.

Your solution to the sound problem, will probably grant you a visit from the DEA though, as it will only increase the watt intake of your household.

If there were no tempo advantage, it would seem an incredibly even game. The only thing besides the initial tempo is that the position of black and white are not duplicates but mirrors because of the queen sitting on her own color. So that at the start of the game the king is closer to your right hand if you are playing as white and to your left if you are playing as black.

But if we think of it like a battle, the armies are exactly equal in size and strength. If there is perfect play, a draw outcome seems very logical.

The tempo is falling short, and the mirror quality of the arrangement only makes it more even. Probably the reason why it evolved that way.

Not being a scientist, I'm not particularly concerned about when it could be solved. As a centaur player, however, I'm very concerned with the fact that the only one who ever sponsored Freestyle events, obviously finds them boring and hasn't financed a new tournament in years.

For me, it would be far more important to prove that guy that it's not practically solved, but no one has found a way for white to attack promisingly, so he remains understandably bored. Even the much faster paced "Engine Masters Tournaments" are on a halt, while they implement measures to bring down the draw ratio.

[jefk]

yep chess is a draw

in the past i posted some arguments from Zermelo,
that it there's no winning strategy (for such games as chess)
then it's a draw.
And we now know there's no fundamental opening advantage
possible for White. ofcourse, in sharp lines, it's sometimes
difficult to defend for Black, especially in human games.
But in ICCF correspondence chess, it seems we are
approaching the limit (Elo 4000 or so ?) .
With neural nets you get better quality opening lines,
yet in the end Black again fundamentally has enough
resources (degrees of freedom) to draw.
Not suprising coz there's a certain drawing margin in chess.
|
OIfcourse there are puzzles where comps still cant find
the answer, but usually you don't get such positions in a real game.
In other words, Black can fundamentally avoid such positions.
Is that a proof ? No.
Is that the truth;
yes.
BLM

[Vinvin]

yep chess is a draw

You're wrong.
You "think that chess is draw", that's very different from "chess is proof as draw".

[towforce]

The main problem, as I see it, is that the fundamental nature of chess is exponential.
So I think that a solution will have to deal with that level of complexity.
Any simpler sort of solution would be some kind of stroke of good fortune (like a forced solution nearby).

The "stroke of good luck" that is very likely to exist in chess would be an unexpected emergent pattern. They do tend to arise in complex systems - even when you try to design them out (and nobody has done that in chess).

Look at the luck involved in cracking the WWII Lorenz cipher, allowing Station X to read Germany's top level mail:

* Polish mathematicians found a way to attack the Enigma cipher

* on the eve of WWII, they handed that knowledge over to Britain

* on this basis, Britain set up a large station dedicated to deciphering

* breaking the rules, a German Lorenz operator sent the same message twice

* this enabled the mathematicians at the station to discover an emergent pattern in the cipher

* some machines were built to help crack parts of the cipher

* a Post Office engineer saw these machines, and realised that he could build the same process purely in electronics

* this lead to Colossus - the first purely electronic computer

This "lucky" sequence of events meant that it became possible for Station X to regularly read Lorenz encrypted messages in a useful timescale - something which, if you didn't know that it had actually happened, would have been very easy to dismiss as impossible.

If somebody wants to look for emergent patterns in chess using NNs, the following might work.

* choose a number n (my intuition would suggest 50,000 as a starting number: obviously experimenting would be needed)

* train an NN with n positions

* find positions that can be removed from the set without reducing performance (would need to retrain the NN with the reduced set and see whether it's still as good)

* replace these removed positions with new positions (choose positions where the NN's evaluation is poor to strengthen it's knowledge)

* repeat the above until the NN plays very strongly in most positions with the smallest set of positions you can

* reverse compile the NN to discover what it is telling you about the relationships between positional attributes in good chess

All of the above would be easier with polynomial fitting than with NNs IMO.