Michel wrote: ↑
Tue Sep 08, 2020 8:02 am
So 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
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.