NIM IS EASY, CHESS IS HARD — BUT WHY??¹

Article type: Research Article

Authors: Fraenkel, Aviezri S.²

Affiliations: Rehovot, Israel

Note: [1] This is an expanded version of a note that appeared in the “Reader’s Corner” of Plus Mag., Issue 40 September 2006 http://plus.maths.Org/issue40/editorial/index.html#chess

Note: [2] Department of Computer Science and Applied Mathematics, Weizmann Institute of Science, Rehovot 76100, Israel. Email: [email protected] http://www.wisdom.weizmann.ac.il/~fraenkel

Abstract: The game of chess appears to be hard. According to authoritative sources, this is due to the extremely large number of possible chess moves. We refute this argumentation by showing that simple games of moderate size — as an example we consider nim — have a larger number of moves than chess, yet possess a very easy winning strategy. So perhaps chess has also an easy strategy which remains elusive? We argue that this is rather unlikely, in view of several high-complexity aspects of chess, notably the proven Exptime-completeness of n × n chess.

DOI: 10.3233/ICG-2006-29405

Journal: ICGA Journal, vol. 29, no. 4, pp. 203-206, 2006