Complexity of Large Variants
Some comments about the complexity of large chess/checkers variants for a non-computer science person.
The games of Chess/checkers are interesting because of their complexity. There aren't any simple rules for winning strategy, as in the NIM game. In computer science such intractible problems known as NP-complete. In Complexity theory exists a hierarchy of such intractible problems:
- Harder PSPACE-complete (i.e. Othello/Reversi )
- Yet harder EXPTIME-complete
It was proved that generilized chess/checkers on boards NxN are EXPTIME-compete. (roughly: EXPITIME problems have time-complexity bounded above 2 power P(N), where P(N) is polynomial of input size N). The exponential growth is well known from legend about the chess inventor in India with 2 power 64 grains.
Here are references to these articles:
- A.Fraenkel, D.Lichtenstein
Computing a perfect strategy for NxN chess requires time exponential in N.
Journal of Combinatorial Theory, Series A31, 1981, pp. 199-214
What is interesting, is that the proof used only king, queen, rook, pawn and bishop pieces!!! No knights, cardinals, etc...
As I understand it, they construct a position, where only one rook and 2 queens can move (all other pieces are deadlocked) and used it in their proof.
On generilized NxN board number of pieces increased as a fractional power N.
N by N checkers is EXPTIME complete
SIAM Journal of computing, Vol.13, No.2, 1984, pp. 252-267
Robson proved that GO game is EXPTIME-complete too.
- H.Adachi, H.Kamekawa, S.Iwata
Shogi on NxN board is complete in exponential time
(this article published in 1987, and written in japanese)
Written by Eli Bachmutsky. HTML conversion by David Howe.
WWW page created: January 30, 1999.