# Chess (and variations) Endgame Complexity

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?

• Voting to close - this belongs on cstheory.stackexchange.com Commented Dec 23, 2011 at 23:33
• This would probably be closed on cstheory, since there isn't much of a research-level problem here (see my answer). I do think it's generically interesting enough to ask here though. Commented Dec 24, 2011 at 16:32

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.

• Note that the 'lookup table' approach only works for a board of fixed size, whereas computational complexity - and in particular the results on the complexity of chess - is concerned with the behavior for boards of arbitrary size (where the lookup-table approach is irrelevant). Commented Dec 24, 2011 at 18:16
• does arbitrary size of a chess game is relevant ? Commented Jan 2, 2012 at 17:00