Game of Chomp: Extended Analysis

The combinatorial game of Chomp will be analyzed, which has both a geometric and arithmetic form. Geometrically, 2-dimensional Chomp is a two-player game where players take turns in choosing a square box from an m x n board. That box and those to its right and below it disappear. The player who chooses the topmost-leftmost box loses. Frederik Schuh expressed this game numerically by having each player choose a proper divisor of a given natural number N, except 1 and a multiple of a previously chosen divisor. The number of prime factors the natural number contains determines the dimensions of Chomp (i.e., 2-D or 3-D), and the exponents of the primes in its prime factorization determine the dimensions of the board. It is well known that the strategy stealing argument proves that the first player has the winning strategy; however, the winning strategy is still yet to be determined. The goal of this project is to deduce the first player’s winning strategy by creating an adapting learning program as a tool and then recording the moves made when two computers play each other. After playing thousands of games for a set of fixed boards, the opening moves made by the first computer at every game will be observed and the winning strategy for a particular board will hopefully be deduced. These findings will allow predictions to be made about potential opening moves for the 3-dimensional version of Chomp.

F. Schuh, “Spel van delers”, Nieuw Tijdschrift voor Wiskunde 39 (1952), 299-304.