# 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…

- 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

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.

For the `GrundyPosition`

class, we will enforce the following single invariant:

All entries in

`heapCounts`

have at leastthreetokens.

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 `GrundyPosition`

s representing the legal moves from `this`

position.

** Task 0.**
Implement the `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()`

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.

** 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* `isPPostion`

and `isNPosition`

and both must be saved.

** Task 2.**
Re-implement the game solver methods by *adding a global memo table.*

## Checking the Results on `gitlab`

** 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:

** Task 4.**
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.