Chomp

This is a web application to play the game Chomp. In Chomp, two players take turns in removing objects of an $m \times n$ rectangular array, each turn removing all objects above and to the right of the chosen object, including the chosen object itself. The player that removes the last object (bottom-left, per definition) loses.
This situation can be visualized as a chocolate bar, where the bottom-left piece is poisoned.

To follow the definition of normal play (first player that cannot move loses), this project takes the liberty of excluding the possibility of picking the bottom-left piece and losing the game on purpose. Thus, the “first player that cannot move” will only have the poisoned piece left to pick, meaning that they would lose the game this turn as per the original definition.

This project was developed by Daniel L. Tobi as a bachelor thesis for computer science, supervised by Oswin Aichholzer, at Graz University of Technology. It is based on a project by Marvin Gutgesell.

The server is written in Python, using Flask. The client is written in HTML and JavaScript, using jQuery. Compatibility was tested in Chromium and Mozilla Firefox running on Linux, Android and Windows. Nevertheless the application should be compatible with any browser like Microsoft Edge.

Features

Choose the number of rows and columns for the playing field
Either player (A and B) can be controlled by a human or the computer (AI)
Choose the level of the AI: “Perfect” will always make an optimal move (which might not be unique), “Just Win” will randomly choose a winning move (if available, and not necessary optimal), “Random” will randomly pick a move
Move info: Optionally display the number of half-moves till the end of the game for the possible moves
Recommend move: Shows a perfect move for the current player
Undo/Redo: Revert or redo the last move made by either player
Save/Load: Saves the game (in local storage, provided by HTML5) to resume the game later on

Basics

The AI of this game is based on an exhaustive evaluation of all possible game positions stored in a large database. For each possible position its status (current player win, opponent player win) is known, as well as as the maximum number of half-moves needed to force a win from this position. A green even number shows in how many further half-moves the game can be won by taking this move (assuming optimal play of the opponent, otherwise you can win faster). A red odd number shows the maximum number of half-moves you can delay the victory of the opponent (again assuming optimal play of the opponent). So an even number shows a winning move, which guarantees a win for the current player (when continuing to play optimally) in at most this number of half-moves. An optimal winning move is a move which guarantees the shortest available sequence of half-moves till the player wins.

Control Info

Use the dropdown menus below to choose the dimensions of the position. Dimensions cannot be changed after the game has started.

Hover over a piece of chocolate to preview the corresponding move.

Move coordinates start at (1, 1) in the bottom-left corner and should be read as (row ↑, column →).