Chomp Game AI

Introduction

Chomp is a two-player strategy game played on a rectangular chocolate bar made up of smaller square blocks (cells). The players take it in turns to choose one block and “eat it” (remove from the board), together with those that are below it and to its right. The top left block is “poisoned” and the player who eats this loses.

The following image shows the basic rule of “eating” in Chomp.

Chomp is actually a classical discrete mathematics problem. The player goes first was proved that it always have winning strategy, although the winning strategy might not be easily explicitly specified.

The purpose of the project is to develop a potent AI that can give explicit winning strategy during the game.

Run the Game

The Chomp was developed using Python and PyGame. The player needs to install Python 2.7, Numpy and PyGame in order to run the game. The Python source code of the game and the AI can be downloaded from my GitHub.

To install PyGame, it is extremely easy if you are using pip, simply run “pip install pygame” in the terminal.

To run the Chomp game, run the command in terminal:

python chomp_gui.py x m n

x designates who goes first in the game. It can be either Human or AI. m and n are the width and height of the rectangle. m and n are the positive integers no larger than AI_limit. In this version, the AI_limit is 12.

Here is a demo of playing Chomp with the AI.

About the AI

The data for winning strategy was actually pre-calculated and saved in file. The AI will use the data to design winning strategy during the game.

The AI is extremely potent that it is guaranteed to win if it goes first. It also has extremely high winning rate (nearly 100%) against human players (mostly my friends) if human players goes first, because human players will likely make mistake during the game. Once the human player makes a mistake even if the human player goes first, the AI guarantees to win.

The AI has its limit. Because it relies on the pre-calculated data, and the data was calculated for the board size no larger than AI_limit $\times$ AI_limit.

Future Plan

It might be good idea to add an interface layer asking the user to input game parameters in the GUI.

The python game should also be compiled for the universal usage in different systems without installing Python environment and libraries.

Acknowledgment

I would like to thank my old colleague Guotu Li at Duke University for his smart function to calculate the total number of game states during AI development.