Chess solved?

[towforce]

https://link.springer.com/content/pdf/1 ... 3-2_23.pdf

Wow! What a read!

That paper would actually make a good YouTube video - it would be much better with animated illustrations - though I cannot promise it would get a million hits. There are actually YouTubers getting large numbers of views by making videos of interesting new papers (this would be a "golden oldie").

This does not rule out that the constant time in which 8x8 chess can be solved is surprisingly low, for example because 8x8 chess has a property that disappears on generalisation to NxN chess.

However, there is absolutely no reason to expect that 8x8 chess has such a property. In particular, the fact that Turing cracked the Enigma code (as has been mentioned about 10 times by towforce, who apparently thinks we didn't know that) is certainly no such reason. This is because Turing having been able to crack the Enigma code says as much about 8x8 chess as it does about 9x9 chess, 10x10 chess, .... 123x123 chess,... etc., and we know that not all of those games have a property that makes them easily solvable.

OK - let's get started. Here's what I think the study is showing us (please correct me if I'm wrong):

1. An academic called Stockmeyer has created a boolean game

2. In this game, it can be shown that it's possible for the number of moves to the end of the game to increase exponentially with the size of the game

3. key mathematical transformations exist between Stockmeyer's boolean game and chess

From what's written in the paper, it's not going to be easy to disprove any of the above 3 points. However, I read the whole paper as carefully as I could, and, unless I missed it, there's actually no proof in there that in complex positions, it's impossible for rules to exist which can tell you quickly whether the game is won or not.

If I have missed something, you can actually copy and paste from that PDF, even though the typeset looks like a typewriter or a daisy wheel printer, so do please quote the part that shows where I am wrong.

Thanks again for bringing it to my attention - reading it was fun!

[jp]

I did not understand the article but I think that you need first to define the game and if the 50 move rule exist or does not exist.
With the 50 move rule even KQ vs K is a draw in most positions when N is big enough and finding if a position is a forced draw by the 50 move rule is not exponential problem and assuming every side has at most N^3 moves you can search 100 plies forward even by minimax in O(N^300) steps.

What is the number of white pieces and the number of black pieces in a general legal position that we need to solve?
Do we have at most 2N white pieces and at most 2N black pieces on the board?

How much memory do we have?(time to solve can be smaller if we have more memory)

My preference is not to have any "50"-move rule. But if we did it'd have to scale up with N too.

[duncan]

Questioning whether an idea will work is completely legitimate, and is actually valuable feedback ( )

As far as I can see we got stuck at: you have no idea to begin with. Your case is built on "it would be surprising if no idea that will work existed".

Questioning an idea with reasons from Computer Science is invaluable feedback. Straw man argument and gratuitous negativity are not.

One of the biggest forces holding people back in today's world is a widespread lack of confidence: people giving inaccurate and unhelpful negative feedback is a contributory factor to this situation. My message to people is: make a decision to change from "demolition" to "builder". The biggest beneficiary of this choice is very likely to be yourself!

I cannot properly understand this discussion but can you solve tic-tac-toe with your method and if so, is this easy to do ?

[towforce]

I cannot properly understand this discussion but can you solve tic-tac-toe with your method and if so, is this easy to do ?

I believe so. Still building...

Here's a (hopefully) simplified version of discussion (which necessarily oversimplifies many aspects):

* a relatively easy way to check whether a set of numbers is truly random is to map them into multi-dimensional space: if they're not random, a pattern will arise (this is how Station X made a major breakthrough against the strong Lorenz cipher in WWII)

* if chess positions and evaluations were mapped into multi-dimensional space, would patterns emerge? The answer to that is almost certainly "yes" IMO

* will these patterns be usable to make quick EFs that can accurately evaluate a wide range of positions?

THAT is the big question here. I am on the "more likely" end of the scale relative to other participants in this thread.

[jp]

From what's written in the paper, it's not going to be easy to disprove any of the above 3 points. However, I read the whole paper as carefully as I could, and, unless I missed it, there's actually no proof in there that in complex positions, it's impossible for rules to exist which can tell you quickly whether the game is won or not.

I'm not sure what exactly you mean by that.

You could hope that some subset of positions is easily solved. After all, we already know that we can set up easily solved positions. (e.g. given N & the piece content, you just set up a mate in 1.)

But if you mean simple rules that apply to every position on the NxN board, that's what the result has disproven.

[towforce]

From what's written in the paper, it's not going to be easy to disprove any of the above 3 points. However, I read the whole paper as carefully as I could, and, unless I missed it, there's actually no proof in there that in complex positions, it's impossible for rules to exist which can tell you quickly whether the game is won or not.

I'm not sure what exactly you mean by that.

You could hope that some subset of positions is easily solved. After all, we already know that we can set up easily solved positions. (e.g. given N & the piece content, you just set up a mate in 1.)

But if you mean simple rules that apply to every position on the NxN board, that's what the result has disproven.

First, second, third and last, I want to emphasise how grateful I am for having been given that paper to read. Once again, a VERY big thank you!

I have read it again (it's a lot easier the second time!), and what I said in this post is actually exactly right (at the risk of immodesty, I'm giving myself a pat on the back for that, because I found the report confusing the first time I read it!).

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

However, the report makes a mistake: the authors assume that the only way to know that a position is won is to play the game out to checkmate. We all know that this is not true for all positions: there are some positions where rules will accurately tell you whether the position is won or not. The issue under dispute here is for what proportion of positions is is possible to determine whether the position is won by applying a rule. I'm afraid the report says nothing whatsoever about that.

It's completely fair to say, "the proportion of positions which can be evaluated accurately without building a game tree is higher than the proportion of positions which today's best evaluation functions (EF) evaluate accurately".

It's even completely fair to say that it would be possible to write an EF that would evaluate all positions accurately: the problem is, how big would that EF have to be?

I have reasons to think that the size of an "accurate EF" need not be as big as you would expect, and that working out what code to put in it is not an insoluble problem with today's technologies and techniques. I accept that other participants in this thread disagree with this opinion.

I apologise if this sounds negative or churlish: I emphasise again my gratitude for having been given access to that report - I am genuinely grateful!

[duncan]

Questioning whether an idea will work is completely legitimate, and is actually valuable feedback ( )

As far as I can see we got stuck at: you have no idea to begin with. Your case is built on "it would be surprising if no idea that will work existed".

Questioning an idea with reasons from Computer Science is invaluable feedback. Straw man argument and gratuitous negativity are not.

One of the biggest forces holding people back in today's world is a widespread lack of confidence: people giving inaccurate and unhelpful negative feedback is a contributory factor to this situation. My message to people is: make a decision to change from "demolition" to "builder". The biggest beneficiary of this choice is very likely to be yourself!

Feedback on what? If you had had an idea, we could talk.

If you want to be a "builder", then go build. You haven't built zilch. You just come in here with silly claims that it would be surprising if you could not solve chess.

1. I am building - I'm working on the key software - fitting information-rich polynomials in multi-dimensional space. It's proving to be more difficult than I expected, but I am making progress.

2. You said that I "just come in here with silly claims...", but if you re-read the thread (just my posts - it doesn't take long - I've done it myself!), you'll see that most of my posts are actually responses to questions that you have asked. So... if you don't wish to read that chess might be solvable, stop asking questions to which that would be the answer. Simple!

There is a difference between saying it is very likely that we will discover some new emergent patterns in the future and saying it is very likely that we will solve chess in the future with these new emergent patterns.

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?

[duncan]

2. You said that I "just come in here with silly claims...", but if you re-read the thread (just my posts - it doesn't take long - I've done it myself!), you'll see that most of my posts are actually responses to questions that you have asked. So... if you don't wish to read that chess might be solvable, stop asking questions to which that would be the answer. Simple!

There is a difference between saying it is very likely that we will discover some new emergent patterns in the future and saying it is very likely that we will solve chess in the future with these new emergent patterns.

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?

[towforce]

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!

[duncan]

Do you mean this "stroke of good luck" to be related to chess in general (i.e. the basic rules of moving, winning and drawing) or do you mean all that plus the specific (opening) position we have? If you mean the former (i.e. the stroke of good luck covers all chess positions), there are theoretical CS reasons why that should not be the case.

Are you planning to answer Paul's question?

"What are these cs (Computer Science?) reasons, please?"