Computational Complexity of a Game of NxN Chess
Background: Introduction to Chess
Chess is a game played on a board resembling a checkerboard. Standard real-life games of chess are played on an 8x8-squares board. The objective is for one player to use their pieces to capture the opponent’s “king” gamepiece. The game can also be finished with one of a series of draws or stalemates. Chess rules designate different types of movements for different game pieces, i.e. rooks can move only on the x or the y axis, and knights move in an L-shape, to name a few. There are many more rules of conventional chess, which can be found here, but for the purposes of understanding this topic only the major rules are listed above.
Introduction to Research:
With a complex game like chess, researchers often simplify or generalize the game. The research paper, Computing a Perfect Strategy for nxn Chess Requires Time Exponential in n by Aviezri S. Fraenkel and David Lichtenstein (link), aims to examine the computational complexity of a generalized game of chess. Instead of a traditional game of 8x8 chess, here a game of arbitrary size (NxN) is analyzed for computational complexity. For this analysis, there are no limits on repeated positions or capture-free moves, unlike other generalizations of chess. There are a number of other chess generalizations examining the computational complexity of the game, but this generalization goes into significant depth on the game mechanics necessary to show the game can be played. This chess game is fairly similar in terms of rules to a traditional chess game, but the authors of the paper concede that the actual game mechanics would look significantly different from a regular game of chess.
Similarities: objective is to capture king or end in stalemate; different types of chess pieces retain unique movement abilities
Differences: only one king per player, while other gamepiece counts increase proportionally with size of board; problem approached with random placement of gamepieces on board, instead of from an ordered starting position
Claim: Chess is complete in EXPTIME.
Definitions:
EXPTIME- the set of all decision problems solvable by a deterministic Turing machine in exponential time
PSPACE- the set of all decision problems that can be solved by a Turing machine using a polynomial amount of space.
The Reduction:
Question Q: Given an arbitrary position of a generalized chess game on an NxN chessboard from our class of chess games, can White (Black) win from that position?
To answer the above question, the researchers construct a boolean game G3 already proved complete in EXPTIME by Stockmeyer and Chandra (link). The goal is to show that game G3 answers the question “yes,” that is to say, in game G3 either player can win from that position. We know that the number of possible configurations, given that there are 6 distinct chesspiece types, is 13^n² (which is in EXPTIME). In order to show that G3 answers Q, G3 is simulated on an NxN board.
G3 is created so that a position on the board is constructed where only 1 rook and 2 queens per variable can move, and all the other pieces are deadlocked. This allows for the creation of predefined channels through which a player’s queen may pass, where the placement of the rooks allows for one of two routes to be followed. With this construction, the truth-assignments of each of the variables (the positioning of the pieces) ultimately determine the only routes by which a queen may capture the opponent’s king (and win the game).
The basic structure of this method is the Boolean controller. This is a structure where one of two “pathways” is determined (and changed) by the positioning of rooks and other pieces. Figure 1 illustrates a Boolean controller for the White player, and Figure 2 illustrates the same for a player with the Black pieces (WBC vs BBC). In a normal play of this chess generalization, the player moves his or her rook (WR or BR) in between positions x’ and x (or, as in figure 2, y’ and y) until the game is won by one of the players.
If the opponent does not follow the rules for a normal play, the game can also be won with one of two different methods: Normal-Clock or Rapid-Clock. These are mechanisms where by use of various “switches,” queens are allowed to capture pawns and pass through alternate channels (if a series of preconditions are met, such as the direction the switch is approached), eventually allowing the player’s queen to arrive at the opponent’s king via an alternate path.
Fig. 6 illustrates one such example of a Clock-channel (here intersecting with the Black coup-de-grace (CDG) path, which leads to a Black win.
The Winning Scenario: The research paper explains in significant depth the moves required for the winning scenario of G3 to occur. Step by step, the process is: B (black team) first moves all queens into one of the Boolean controller channels C1i and move them each as far down the channel towards the B-CDG channel. Along the way, a specific number of W pieces are captured, and a number of moves are spent in a W delay line consisting of pawns. Then, two moves are spent traversing the CDG channel, allowing for a checkmate of the White King in a specific number of moves relating to the number of black queens captured along the way. A number of moves to be made by W are also outlined, such as “whenever a BQ in a WBC advances to its first station towards an x or x’ channel while WR is in the x or x’ position, then WR captures BQ.” Two more necessary moves for the W strategy are also detailed, which show that W can checkmate the B King in fewer moves than player B needs, so W is shown to win G3.
As the theoretical game G3 has already been shown by Stockmeyer and Chandra to be complete in EXPTIME, this proof demonstrates the existence of game G3 and thus proves that chess is complete in EXPTIME.
Illegal Moves: A series of moves are then designated “illegal” that, though they follow the regular rules of chess, prohibit game G3 from being completed. Not all of them will be listed here but as an example, one such move would be to move the WQ vertically to the rapid clock or normal clock channel intersection, allowing B to capture the WQ with a BQ or a BP (black pawn). This results in a winning scenario for B, which is not the game G3 as specified.
As an addendum, there is a brief discussion of how the construction and transformation of the setup of the board can be shown to be polynomial. There is also some note made of the possibility that other NxN board games might be proved to be EXPTIME-complete by a similar method to the one used in this paper.
Conclusion and Assessment: The main result of this research paper is that it is shown that there exists game G3 that proves that this specific generalization of NxN chess is EXPTIME-complete. This is ultimately successful and interesting because it proves the scenario put forth by Stockmeyer and Chandra, and shows effectively and clearly the steps taken in this scenario. However, the main shortcoming of this paper is that this highly specific, generalized version of NxN (let alone regular, 8x8) chess is not very applicable outside of this theoretical context. That is to say, no one playing chess will even be able to implement this strategy in real life. However, this is addressed by the authors of the paper, who specify that this result is ultimately only useful for theoretical understandings of chess. It would be interesting to see future papers examining the time complexity of specifically 8x8 games of chess, with detailed possible games such as G3 in this paper.
Unclear areas: Though overall this paper was coherent, clear, and relatively easy to follow, a major shortcoming was the complexity of some of the diagrams. Figure 1 and Figure 2 (both pictured above) show supposedly the same thing (albeit for White and Black, respectively), but not much explanation is given for the different style of rendering. This confused me as a reader, but would be a relatively easy improvement to make.
Contributors: As the sole author of this article, I (Naomi Cebula) am responsible for all parts of this project, including background research, study analysis, and concluding segments.
References:
- Fraenkel, Aviezri S. and David Lichtenstein. “Computing a Perfect Strategy for nxn chess Requires Time Exponential in n.” Journal of Combinatorial Theory, Series A 31 (1981): 199–214.
- Stockmeyer, Larry J. and Ashok K. Chandra. “Provably Difficult Combinatorial Games.” SIAM J. Comput. 8 (1979): 151–174.
- Team, Chess.com. “How to Play Chess: Rules 7 Steps to Begin.” Chess.com, Chess.com, 15 Apr. 2020, www.chess.com/learn-how-to-play-chess.
