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:
Computing a perfect strategy for NxN chess requires time exponential
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.
Shogi on NxN board is complete in exponential time
(this article published in 1987, and written in japanese)