1
$\begingroup$

Suppose we simulate the game of chess with a Turing machine $M$ as follows:

The semi-infinite input tape of $M$ contains a sequence of symbols beginning in the first cell of the tape. Each symbol prescribes a possible chess move, i.e., an ordered pair of board positions, e.g., (a3, d5), indicating that the piece in the first position is to be moved to the second position. Thus, there are 64 x 64 such symbols. Note that not all moves would be valid or possible to carry out. Also, there is no explicit indication that there are two players making alternate moves.

Starting with the first cell of the input tape the machine $M$ reads the current symbol and does one of the following:

(1) If the move is possible to carry out, yet not a winning move, $M$ changes its internal state to one designating the new board configuration and any historical information it needs to record about the game (for castling, say) and moves to the next input symbol in the sequence.

(2) If the move is possible to carry out and it is a checkmate, $M$ halts (in "Win" state.)

(3) If the move is possible to carry out and it is a stalemate, $M$ halts (in "Draw" state.)

(4) If the move is invalid or impossible to carry out, $M$ halts (in "Invalid" state.)

Which complexity class does $M$ belong to?

Improve this question
$\endgroup$
3
  • 6
    $\begingroup$ It is not in any complexity class. Complexity classes are for problems, not algorithms. In any case, this Turing machine is trivial from the point of view of complexity. A finite number of states suffices to describe all legal chess situations. Assuming the tape doesn't describe any illegal moves, the number of steps the machine takes is just the length of the chess game. Because of the $75$-move rule, that length is bounded by a constant; if we ignore that rule (and neither player invokes the $50$-move rule), games can be arbitrarily long. $\endgroup$
    – Robert Israel
    Commented Apr 3, 2019 at 2:18
  • $\begingroup$ @Robert Israel: It is common to define the complexity of games like chess by varying the size of the board. For example, in this version Go is exptime complete. I would assume that the proof for Pspace hardness should translate to chess, although the details are a bit more complicated. $\endgroup$
    – Jan-Christoph Schlage-Puchta
    Commented Apr 3, 2019 at 12:03
  • 1
    $\begingroup$ OP is just asking about validating a sequence of chess moves, not about determining who is winning in a given position. $\endgroup$
    – Daniel McLaury
    Commented Apr 3, 2019 at 13:07

1 Answer 1

Reset to default
0
$\begingroup$

First, it's not really necessary to include a bunch of stuff about explicit representation on a Turing machine's tape here. Let me restate the question:

Given a sequence of chess moves which may or may not be valid, determine whether they describe a win for white, a win for black, a tie, or an illegal sequence of moves.

Now chess has a few obscure rules that keep the game from going into an infinite loop. Let's ignore those for now.

Checking whether a given move is legal can always be done in constant time. For most moves the only information involved is the current state of the board. For castling and en passant we need to consult a fixed amount of additional state.

Consequently, the naive algorithm that just goes through the moves one by one and keeps an internal representation of the board is O(n).

Conversely, any algorithm to solve this problem must be O(n) since in the worst case you have to actually read every move in the list to determine the outcome. (Proof: take a valid game of any length and change any of the moves to an invalid one. Any algorthm which doesn't check that move will not be able to determine an invalid move was made.)

Now let's add back in the 50 move rule or whatever. These kind of rules put an upper bound on the length of the game. This makes the problem O(1) because you only have to check the first, say, 10k moves, and then you can stop and declare the game a tie.

Improve this answer
$\endgroup$

Not the answer you're looking for? Browse other questions tagged .