Intro to Chomp
So what’s Chomp about then? Chomp is a POSET (Partially Ordered Set) game. I’ve defined the general “POSET Game” in the following presentation, in case you’re interested in the Math involved with this game:
I made this presentation for the Directed Reading Program (DRP) at UGA, where I was paired up with a Math Grad student. In the DRP, you’re able to explore topics you normally wouldn’t have the opportunity to study. If the presentation was too dense to follow and you’re only concerned with understanding the rules of the game, here’s the basic explanation.
Chomp is a 2 player game, played with a chocolate bar, or a rectangular grid. Each player takes turns “chomping” the board, until the poisoned square is reached. The player to bite the poisoned square is the one to lose (Turns out.. It’s not a great idea to eat poison). Let me explain what a “chomp” consists of and define the position of the poisoned square for you. If we use Cartesian coordinates, (0,0) starts in the bottom left corner. This is our poisoned square. This was one of my first learning moments in coding, as I battled with the conventions of matrix/array formatting. Unlike Cartesian coordinates, matrices have the top left entry labeled as (0,0). Depending on the programming language, representing my Chomp board with a bottom left poisoned square led to some complications, whenever I sought out a general solution to the problem. More on this later.
When a player clicks on a square in the grid, all squares above and to the right are deleted. This entire process is what defines a move in Chomp. You are then left with a new board configuration. I have included a simplistic implementation of a Chomp board below, where you can just practice clicking on the squares and play against yourself, to get an idea of how the game works.
Basic Implementation
Bitstring Chomp
There’s also another implementation of Chomp, which involves permutations of a Bitstring. For the 4x5 Chomp board, the starting configuration is 000001111. The ending configuration is 111100000. The game works by shifting the 1’s ahead of the 0’s. A move (i,j) is legal if the jth 0 appears before the ith 1. The code for the resulting configuration is included in the Python code below. As I mentioned before, the convention for our coordinate systems change to accommodate for the way arrays are defined in most coding languages. The first entry is the 0th entry, the top left entry is (0,0), and other not-so-intuitive conventions that we encounter in CS. Consult the code below and feel free to ask questions. While it involved a lot of tweaking to get the code to work and I believe I have the only coded implementation of this algorithm, I drew heavily from the following paper: Computing Winning Strategies for Poset Games
Implementing The CPU
To construct a CPU for this game, we first note that there is no way to track progress in this game. In Chess, you can come up with a weight for each piece that you lose. In this game, you either click the poisoned square or you don’t. At any time, you could choose to throw the game by picking an N position (losing), which is discussed in the presentation posted on this page. In combinatorial game theory, the Grundy Sprague theorem states that for an impartial game, such as Chomp, we can compute the winning position by computing the nim-sum of every position that we can move to. More on GS Values
So how many positions are we able to move to in Chomp? For an N by M board, we have (N + M) choose N total moves. For the 4 by 7 chomp board, we have 11 C 4 = 330 moves. Barring the poisoned square, that’s 329 viable moves, for which we have to compute the nim-sum. This calculation uses some background of combinatorics such as the binomial coefficient and multiset permutation, which you can read more about here.
Using the Gaussian binomial coefficient, which I briefly mention at the end of my presentation, my supervisor came up with an efficient way of generating all nim-sums of every move possible for the 4x7 board. As mentioned above in the “Calculating Grundy Values”, when writing the nim-values of each position in the same order that they appear, the nim-values may be written more than once. If you were to inspect the stored positions in the Javascript code, you may find these copies. That is, if you were to sort through all 9 arrays of length 7*329. Unfortunately, as we were running out of time in the semester, I didn’t get to see this algorithm and figure out its inner workings. We’ve apparently lost that file and it’s tedious to sort out through the large data stored in the JS code. Another thing to note, would be that a year has passed since we worked on this and it took me some time to familiarize myself with coding to go back through our original files, understand the HTML, JS and work on other projects I had in Python and Java.
If you’re looking for a project, I would consider looking at the bitstring implementation and considering its relation with permutation groups.