petero2 wrote: ↑Sun Apr 07, 2024 10:32 pmThe article does not have to consider whether the algorithm is doing "search" or not (and how to define what "search" means), since it proves results that are valid for any algorithm that can be executed on a Turing machine. In particular it shows that if an algorithm is able to determine the game-theoretical value of any position, there exist positions for which the algorithm has a runtime larger than polynomial in the board size. (This assumes the 50-move draw rule does not apply though to the generalized chess variant.)
A direct quote from the article:
This implies that there exists d > 0 and infinitely many positions p such that an algorithm for deciding whether White (Black) can win from that position requires at least c^(|p|^d) time-steps to compute, where c > 1 is a constant and |p| is the size of p. Generalized chess is thus provably intractable, which is a stronger result than the complexity results for board games such as Checkers, Go, Gobang and Hex which were shown to be Pspace-hard.
To help anyone who's interested, here's a direct link to the paper PDF -
link.
Assuming that the paper is, in general, correct, then the part of the paper that
REALLY MATTERS is the section called "POLYNOMIALITY OF TRANSFORMATION", which is a little over half a page long, and is on page 213 of the paper.
This proves that in the given position, the number of moves (more accurately, the complexity of the game tree) it would take to get from that position to the win rises exponentially with the size of the board. I have no argument whatsoever with this proof - it looks entirely correct to me.
However, their proof assumes that there is no other way to prove the win other than to play out all the possible ways the game could go.
It is utterly trivial to show that this is wrong. Take another look at this position:
[d]8/8/8/8/3k4/8/8/4KR2 w - - 0 1
This position is won for white, with 29 moves to mate (see my previous post about this position for the EGTB link). I am going to prove it's won another way, without reference to the EGTB, as follows:
IT'S CONSPICUOUSLY OBVIOUS THAT WHITE IS WON IN THIS POSITION
What I mean by that is:
1. The position has a pattern which is known to be won
2. All chess players who are not beginners know this pattern
Now imagine a similar position on a 100x100 chess board. The kind of proof discussed in that paper would now be intractably large (as would a game tree of all possible games from that position - assuming that the 50-move rule becomes the "5000 move rule"). Using the mechanism described in the paper, you could reasonably say that it couldn't be proven to be a win in a reasonable amount of time on a cheap computer.
However, using my proof above ("it's obvious"), you can say it's won. It will take hundreds of moves to win rather than the 29 moves it takes on an 8x8 board, but its still a provable win.
Continuing the theme of "obvious statements", there are going to be many positions on a 100x100 board (and even on an 8x8 board) where there are not known patterns to quickly tell you whether white can win. But the point is that I have disproven the assertion that the paper proves that
"This implies that there exists d > 0 and infinitely many positions p such that an algorithm for deciding whether White (Black) can win from that position requires at least c^(|p|^d) time-steps to compute...". The paper only proves that, in similar positions*, the distance to the win can rise exponentially with the board size. It has nothing whatsoever to say about patterns and heuristics.
*a simplification for clarity
The simple reveals itself after the complex has been exhausted.
