A-22 The Complexity of King Chase Chess

概要

論文の詳細を見る
Generalized chess is a natural extension of chess to n n board. Praenkel and Lichtenstein proved that generalized chess is EXPTIME complete. In this paper we exhibit another construction of an EXPTIME complete chess problem on the generalized chessboard. Our construction assumes that the player's king is checkmated by the opponent's just one move and there is no way to be saved. Under this assumption for the player to win he (or she) has to continue checking the opponent's king in his every turn until finally invoking checkmate. Along these attacks, moreover, the opponent is always forced to move his king away from the checked squares. In a word, our construction is so-called a king chase chess problem, and we show that even king chase chess with generalization is EXPTIME complete.
2002-09-13