Take the 2-minute tour ×
Board & Card Games Stack Exchange is a question and answer site for people who like playing board games, designing board games or modifying the rules of existing board games. It's 100% free, no registration required.

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?

share|improve this question
    
Voting to close - this belongs on cstheory.stackexchange.com –  BlueRaja - Danny Pflughoeft Dec 23 '11 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. –  ire_and_curses Dec 24 '11 at 16:32

1 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.

share|improve this answer
2  
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). –  Steven Stadnicki Dec 24 '11 at 18:16
    
does arbitrary size of a chess game is relevant ? –  Xavier Combelle Jan 2 '12 at 17:00
    
+1 nice analysis –  tdc Jan 13 '12 at 15:07

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.