TalkChess.com

What the OP wants to say is that there might be some "easy" algorithm that predicts the game theoretic value of any position. It might then be possible to verify the correctness of such an algorithm mathematically (it should give the correct value on terminal positions, a predicted lost position should only have predicted won children for the stm, etc...).

So it is possible to solve games without constructing proof trees. An iconic example is nim.

Apparently if we consider NxN chess then is has been proved that such an easy algorithm cannot exist. If we restrict ourselves to 8x8 chess then the concept of "easy" is not well defined (as pointed out by Ronald).

towforce wrote: ↑Mon Sep 07, 2020 11:22 pm
* there is no evidence that it is impossible to build an EF that evaluates most chess positions well without building a game tree. We don't know how big such an EF would have to be

If it evaluates most chess positions well, but not perfectly, does that mean it might lose occasionaly due to errors?

Michel wrote: ↑Tue Sep 08, 2020 10:02 am
Apparently if we consider NxN chess then is has been proved that such an easy algorithm cannot exist. If we restrict ourselves to 8x8 chess then the concept of "easy" is not well defined (as pointed out by Ronald).

It it possible to differentiate where N is less than 12?

Michel wrote: ↑Tue Sep 08, 2020 10:02 amSo it is possible to solve games without constructing proof trees. An iconic example is nim.

The short answer is, "Yes - but we don't know how difficult it will be."

Here's an oversimplified "slightly longer" answer:

There are a large number of positions in which a strong player ("GM" for brevity) can look at the board and accurately say which side is going to win.

At a deep level, the underlying root of this ability is:

1. The GM knows many "atomic" positions known to be won or drawn (e.g. K+R v K)

2. The GM knows that the winning side can reach an atomic position from this position (or that neither side can get out of a position being drawn)

We know that, mostly (granted, not yet universally), what a human can do, a machine can do better: here's an idea for how a machine could extend the range of provably won/drawn positions:

* start with a set of known won/drawn positions (probably don't want to start with the 7 man tablebase for this exercise because it's too big). I'll call these "type A" positions

* work out the rules that determine whether a player can force the game into a type A position. Positions that can transpose into a type A position I call a type B position. It would be necessary to work with rules here - the idea is to NOT to generate all these positions, but to create rules that determine whether a position is type B

* work out the rules that determine whether a player can force the game into a type B position. Positions that can transpose into a type B position I call a type C position

etc.

Finally, if all the above can be done, then I'd expect a computer to be able to have a wider range of "positions known to be won/drawn" than humans could - but we don't know whether it would be practically possible to take this process all the way to the starting position.

I can see flaws in the particular method I have described, but it demonstrates that solid, provable ways to cheat the exponential nature of the game tree do exist in a very large number of positions, and those positions might just include the chess starting position.

Michel wrote: ↑Tue Sep 08, 2020 10:02 amSo it is possible to solve games without constructing proof trees. An iconic example is nim.

One more thing: this is pure speculation, but, as discussed earlier in this thread, it's possible that chess has an emergent pattern, and a mathematician might be able to prove that the emergent pattern applies to all positions. However, it's unlikely that anyone will investigate this seriously as a way to prove that chess is a draw because:

1. it might be that no such pattern exists

2. if it does exist, it's not obvious how you'd prove it applies to all positions

3. If it does exist, we have no idea how large it would have to be

It might be that a branch of maths like chaos theory discovers quick ways to find out whether emergent patterns exist, and quick ways to prove whether it applies universally to a set - but until that happens (if it ever does), I don't think this idea is going to be pursued.

If this can help, here's the thesis who proves the "connect 4" game is solved :
http://www.informatik.uni-trier.de/~fer ... ewinnt.pdf

Vinvin wrote: ↑Tue Sep 08, 2020 12:16 pm If this can help, here's the thesis who proves the "connect 4" game is solved :
http://www.informatik.uni-trier.de/~fer ... ewinnt.pdf

Very interesting!

Shannon's original 1949 paper (link) only has a "type A" and a "type B" strategies: can anyone tell me what his "type C" strategy was, please?

The paper shows that it is possible to resolve Connect 4 by rules alone. It wasn't easy for them, because they had no way to automate the generation of the rules - they crafted the rules by hand.

It doesn't, of course, prove that it's practical to solve chess the same way, and IIRC Connect 4 falls into a different category of game from chess in the "good" paper on game complexity - but it has similarities to what I was saying about generating rules to determine the outcome of a position, and it seems to demonstrate that it's possible to overcome the exponential nature of the game tree in resolving at least some positions.

towforce wrote: ↑Tue Sep 08, 2020 12:57 pm ... can anyone tell me what his "type C" strategy was, please?

"type C" is "goal oriented" :
https://books.google.be/books?id=ZQV4zv ... ed&f=false

Vinvin wrote: ↑Tue Sep 08, 2020 1:25 pm

towforce wrote: ↑Tue Sep 08, 2020 12:57 pm ... can anyone tell me what his "type C" strategy was, please?

"type C" is "goal oriented" :
https://books.google.be/books?id=ZQV4zv ... ed&f=false

Thanks

Michel wrote: ↑Tue Sep 08, 2020 10:02 am Apparently if we consider NxN chess then is has been proved that such an easy algorithm cannot exist. If we restrict ourselves to 8x8 chess then the concept of "easy" is not well defined (as pointed out by Ronald).

But we can still say that a shortcut (such as exists for Nim) is not expected to exist for 8x8 chess. Because it does not exist for NxN chess in general and there is no good reason to believe that 8x8 chess is special.

Of course this expectation could turn out to be wrong. Perhaps 8x8 chess is in fact special. But that would be surprising given our current state of knowledge.

Therefore I very much disagree with towforce's earlier statements that "it would be very surprising" if the initial position of 8x8 chess would not allow for an "easy" resolution (the "evidence" cited for this by towforce being 1) some games like Nim have been solved with a simple trick, 2) Turing has cracked the Enigma code, 3) Wiles has proved FLT).