The Chess Variant Pages

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:

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:

Written by Eli Bachmutsky. HTML conversion by David Howe.
WWW page created: January 30, 1999.