Chess (and variations) Endgame Complexity

Question

My understanding is that the game of Go with Japanese Ko rules is, like most such games, EXPTIME-Complete, but that ladders are PSPACE-Complete and that Go endgames have been analyzed independently as being PSPACE-Hard.

Has any such research been done into Chess endgames?

Answer 1

There are a very large, but only finite number of possible chess games. This is a consequence of the 50 move rule, which limits the maximum theoretical number of moves to about 5000 (although in real life, chess games over 100 moves are extremely rare). To see this, we know that 50 moves without a pawn move is a draw. There are 16 pawns, and each pawn can move 6 times.

So we have 50 * (16 * 6 + 1) + 1 = 4851 moves.

This means that the complexity of chess is actually O(1), because in theory with a big enough lookup table, you could find the answer to any chess position immediately. This gives rise to the amusing idea, first described by Shannon, of a game between two perfect players:

A game between two such mental giants, Mr. A and Mr. B, would proceed as follows. They sit down at the chessboard, draw the colours, and then survey the pieces for a moment. Then either: -

(1)Mr. A says, "I resign" or

(2)Mr. B says, "I resign" or

(3)Mr. A says, "I offer a draw," and Mr. B replies, "I accept."

Of course, the size of that lookup table is completely impractical (larger than the number of atoms in the observable universe), but your question asked about computational complexity, not practicality!

It thus follows that all chess endgames are also O(1). Chess positions with up to 6 pieces have been perfectly solved, and lookup tables constructed in this way. However the size grows rapidly; the implemented 6-piece database is around 7GB, and the 7-piece database is estimated at 1.2TB.

If the constraints on threefold repetition are ignored, then chess becomes PSPACE-hard. If you're also willing to throw away the 50 move rule, then chess becomes EXPTIME-hard.