Chess is EXPTIME, not NP.
Unless you want to consider that it's only played on a fixed-size board, in which case it's actually a constant-time algorithm.
Unless you want to consider that it's only played on a fixed-size board, in which case it's actually a constant-time algorithm.
A move, though possibly part of an infinite series of moves, is still only one of a finite number of states for the board. And each state can theoretically be evaluated to results in a win/lose/draw for either white/black assuming both player play a perfect game.
Now I'm going to go way outside my comfort zone with the hope of correction or confirmation: Since the nature of chess on a board of of N dimensions is EXPTIME-hard, would chess on an infinite board be NEXPTIME-hard? (And if not, what level of the time hierarchy would that fall under?)
Also, if chess was "solved" and board states determined "winnable" after significantly more moves, the rules might very well change to extend that limit.
Something along those lines has happened before: When a combination of pieces have been shown to be "winnable" but might exceed the 50 move rule, exceptions have been made to the rule to allow more time to develop the win. At some point though, the rules went back to 50, but still with conditions about pawn moves, pieces taken, etc.
The history is interesting: 50 was originally chosen (or maybe just compromised on) because players felt than all winnable games could be won in 50 moves or under.
However on an info it's chess board there would always be a unique board state possible. That doesn't by any means refute your point, only add a twist to things.
However, there is no reason to expect that a timelike worldline rooted at "here and now" (converting a chosen comoving coordinate into the origin of spherical coordinates for a Eulerian observer) cannot be extended into the infinite future, and at +infinite time the horizon will be at an infinite spatial distance in this system of coordinates. We don't even need to say anything about the matter content of the Hubble volume at any time, anything about -infinite time, or anything about how various measures of entropy fit in; all of these can generate infinities that defy easy (and possibly any) removal in a universe similar to the concordance model.
A taste of this can be found at https://en.wikipedia.org/wiki/Cosmological_horizon#Future_ho...
More deeply and technically, Baez's "Struggles with the Continuum" is great A smooth manifold tends to generate infinities and infinitesimals, and all our fundamental physical descriptions of the universe we inhabit are (at least at present) defined on a Lorentzian spacetime, which is a smooth manifold. He discusses practical reasons to [a] worry about infinities and [b] to work with them anywhere because they might not be removable. https://arxiv.org/abs/1609.01421 (§5 starting on p. 27 is directly relevant, and the concluding §6 is pithy).
I.e. we can talk about Turing machines with infinite tapes without actually making one with an infinite tape.
So we can construct approximations of it in the sense that we can create computers with varying, finite amounts of RAM. This might seem like a pedantic/obvious point to make, but it is actually also possible to design abstract computational machines that operate on truly infinite quantities, like a machine that has random access to an infinite, uncomputable sequence.
From a simplicity perspective, it also makes more sense to consider machines with an arbitrarily large amount of RAM (you can always hotplug more RAM), compared to setting some arbitrary limit because that is the most RAM we happen to be able to achieve in this universe.
I.e. a (cryptographic) random number generator?