Don't you be insulting me on my planet!

Moderator: Ras
Does your explanation fail for generalized chess? If it does not fail, we can conclude that your explanation is wrong or incomplete, since it is already known that generalized chess is EXPTIME-complete and therefore there cannot exist "simple" patterns that can decide the game-theoretic value of all positions in generalized chess.towforce wrote: ↑Tue Apr 16, 2024 5:07 pm The trend is that relatively simple underlying patterns are being found in all sorts of places where you wouldn't expect them, and as a person who has looked into this, it seems "obvious" to me that the chess set is going to have them. See previous threads on this subject for more explanation on why I think that.
petero2 wrote: ↑Tue Apr 16, 2024 10:35 pmDoes your explanation fail for generalized chess? If it does not fail, we can conclude that your explanation is wrong or incomplete, since it is already known that generalized chess is EXPTIME-complete and therefore there cannot exist "simple" patterns that can decide the game-theoretic value of all positions in generalized chess.
Yes, but you later admitted that your answer was wrong.towforce wrote: ↑Tue Apr 16, 2024 11:46 pmAsked and answered (link).petero2 wrote: ↑Tue Apr 16, 2024 10:35 pmDoes your explanation fail for generalized chess? If it does not fail, we can conclude that your explanation is wrong or incomplete, since it is already known that generalized chess is EXPTIME-complete and therefore there cannot exist "simple" patterns that can decide the game-theoretic value of all positions in generalized chess.
So the main problem is still the following:towforce wrote: ↑Mon Apr 08, 2024 3:21 pmAgreed.chesskobra wrote: ↑Mon Apr 08, 2024 11:15 amI have not read the paper, but petero2 quoted "there exist infinitely positions for which deciding ... requires ... steps to compute". This does not mean there are no simple positions where the win can be proved easily. There could also be infinitely many simple positions as in your example.
petero2 wrote: ↑Sun Apr 07, 2024 10:32 pm 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.
petero2 wrote: ↑Wed Apr 17, 2024 6:45 amYes, but you later admitted that your answer was wrong.towforce wrote: ↑Tue Apr 16, 2024 11:46 pmAsked and answered (link).petero2 wrote: ↑Tue Apr 16, 2024 10:35 pmDoes your explanation fail for generalized chess? If it does not fail, we can conclude that your explanation is wrong or incomplete, since it is already known that generalized chess is EXPTIME-complete and therefore there cannot exist "simple" patterns that can decide the game-theoretic value of all positions in generalized chess.
towforce wrote: ↑Mon Apr 08, 2024 3:21 pmAgreed.chesskobra wrote: ↑Mon Apr 08, 2024 11:15 amI have not read the paper, but petero2 quoted "there exist infinitely positions for which deciding ... requires ... steps to compute". This does not mean there are no simple positions where the win can be proved easily. There could also be infinitely many simple positions as in your example.
towforce wrote: ↑Sun Apr 07, 2024 11:50 pmTo 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