CS 2 (Winter 2023) Lab 05: Grundy's Game

This lab focuses on solving a combinatorial game using recursive functions. It is also an example of a situation where memoization is extremely important.

Setup

Register for the lab using grinch: https://grinch.caltech.edu/register and clone the repository as explained in the setup instructions.

Goals and Outcomes

By the end of this lab, you will…

Definitions from Lecture

We can compute \(P\) and \(N\) positions using the following co-recursive definition:

Grundy’s Game

Grundy’s Game is an impartial combinatorial game. It’s very similar to Nim (as discussed in class) in that it’s made up of several “heaps” of identical “tokens”.

In Grundy’s Game…

Data Structure Invariants

An invariant is a statement that is true before and after all possible operations on a data structure.

For the GrundyPosition class, we will enforce the following single invariant:

All entries in heapCounts have at least three tokens.

That is, all heaps represented in the position must be active. In a situation where we actually have five heaps, each with one token, and one heap with ten tokens, our representation would omit the five heaps of one token entirely. We’ll see why this is useful later.

Implementing The GrundyPosition Class

The GrundyPosition class represents a position in Grundy’s Game. The heapCounts field should be a map from height of pile to number of piles of that height in the position. Implement the following methods to simulate a game:

public GrundyPosition(int heapHeight)

Initializes a GrundyPosition which has a single heap with height heapHeight.

public List<GrundyPosition> getMoves()

Returns a List of GrundyPositions representing the legal moves from this position.

Implementing The Game Solver

Now, use the recursive definition of P and N positions to write a solver for Grundy’s Game.

public boolean isTerminalPosition()

Returns true if and only if this is a terminal position in Grundy’s Game.

public boolean isPPosition()

Returns true if and only if this is a losing position in Grundy’s Game.

public boolean isNPosition()

Returns true if and only if this is a winning position in Grundy’s Game.

Speeding Up The Computation using Memoization

Add a memoization table (e.g., a HashMap) to memoize recursive calls to isPPosition. Note that there are calls to this method in both isPPostion and isNPosition and both must be saved.

Checking the Results on gitlab

Getting Checked Off

At the end of every lab, you will need to call over a member of course staff to review your work. For you to receive credit for the lab, a staff member must check you off!