*Eli Bachmutsky*

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:

- NP-complete
- Harder PSPACE-complete (i.e. Othello/Reversi )
- Yet harder EXPTIME-complete
- etc.

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-214What 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.

**J.B.Robson**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.