Chess (and variations) Endgame Complexity
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.