Complexity of Large Variants

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

• 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)