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…
- have more experience with recursive backtracking
- have seen how small changes in a solution result in wildly different solutions and runtimes
- see how combinatorial game theory and programming intersect
Definitions from Lecture
- A position is the entire state of a game. The definition of a position varies with the game.
- A legal move is a mapping from one position to another position.
- A terminal position is a position where no legal moves are possible.
- A losing position is one in which the previous player to move will win in optimal play. This is also called a \(P\)-position.
- A winning position is one in which the next player to move will win in optimal play. This is also called an \(N\)-position.
We can compute \(P\) and \(N\) positions using the following co-recursive definition:
- All terminal positions are \(P\)-positions.
- A position is a \(P\)-position iff all legal moves are \(N\)-positions.
- A position is an \(N\)-position iff there exists a legal move to a \(P\)-position.
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…
- A position is a multiset of numbers each indicating the size (number of tokens) in one heap.
- A legal move consists of splitting a single heap into two uneven piles.
- If the position only has heaps of size 0, 1, and 2, it is a terminal position.
Data Structure Invariants
An invariant is a statement that is true before and after all possible operations on a data structure.
GrundyPosition class, we will enforce the following single invariant:
All entries in
heapCountshave 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.
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)
GrundyPosition which has a single heap with height
public List<GrundyPosition> getMoves()
GrundyPositions representing the legal moves from
getMoves method using two nested loops.
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()
true if and only if
this is a terminal position in Grundy’s Game.
public boolean isPPosition()
true if and only if
this is a losing position in Grundy’s Game.
public boolean isNPosition()
true if and only if
this is a winning position in Grundy’s Game.
Task 1. Implement the game solver methods using recursion in two of them.
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
isNPosition and both must be saved.
Task 2. Re-implement the game solver methods by adding a global memo table.
Checking the Results on
Task 3. Check to make sure you are passing all the tests 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. Sometimes, we will ask you to think about questions that you’ll review with the person who checks you off. For this lab, please answer the following questions:
Click the “Submit OpenEndeds” button below.
Then, call over a member of course staff by typing “
!question done” into your
workspace text channel. Someone will get to you as soon as possible.