CIT 594 Minimaxing notes for Coin Grabber
Spring 2015, David Matuszek

In case you are having trouble figuring out how to organize the CoinGrabber program, here's the way that I did it. Much of this applies to any minimaxing program.

# States

It's important to keep track of the state of the computation. Since this is a minimaxing program, that means backtracking. Backtracking is a kind of depth-first search, examining many states, so it has to be easy both to determine the "next" state, and also to revert to the current state if we don't like the next state.

For CoinGrabber, what constitutes a state? In my program, a state consists of the board array (what coins are where), the location of each player on the board, and how much money each player has. So that's five things: the board itself (an array of integers), where the human is on the board, where the computer is on the board, how much money the human has, and how much money the computer has. I used a five-tuple to represent a state; tuples are easy to create and work with, but I had to remember what order things were (for example, `state._3` was the computer's location, a 2-tuple of integers).

Other representations are possible. The human and computer locations could be in the array itself, say, 1000 for the human and 2000 for the computer (and two more values for their respective money). Or you could define a `GameElement` class, with subclasses `Coin` and `Player`, in which case your state could be a simple array of GameElements. The important thing is to choose a representation that's easy to work with.

Formally, the state of a game should also include a representation of whose turn it is. In my program that's implicit in the way the methods are called; it isn't part of the state.

# Methods

In minimaxing, it is important to be able to apply an operator to a state and get a new state. It's easiest if states are immutable, so that applying the operator does not change the state, but simply yields a new state. If efficiency is paramount, it may be better if the operator modifies the state, and an inverse operator can be applied to restore the original state. I went with the first of these (immutable states).

`def possibleMoves(player: Char, state: State): List[Char]`
The operators in CoinGrabber are "move up", "move down", "move left", and "move right". In a given state, not all operators may be applicable--the player may be against the edge of the board, or in a corner, or next to the other player.
Given a player,` 'h'` or` 'c'`, and a State, this method returns a list of operators (`'U'`, `'D'`, `'L'`, or `'R'`) that can be applied.

`def nextState(player: Char, direction: Char, state: State): State`
This method returns the `State` that results from moving the `player` in the given `direction`. The original `state` is not changed.

```def chooseMove(depth: Int, state: State): Char```
This method chooses the next move for the computer. It is not recursive--it calls another method (below) to do the recursive minimaxing search. Here's what `chooseMove` does:
• Finds all possible moves (up to 4 of them) for the computer.
• Evaluates each possible move.
• Returns (as a Char) the best move.
`chooseMove` does not itself use the `depth` parameter; it just passes it along to the `evaluateMove` method.

`def evaluateMove(player: Char, direction: Char, depth: Int, state: State): Int`
This method returns the value of the move (larger values are better) for the given `player`.
• If the `depth` is zero, the value returned is the value of the heuristic function.
• If the move is into the center of the board, thus ending the game, the value returned is the value of the heuristic function.
• Otherwise, the move is made. Then, for each of the other player's possible moves, those moves are evaluated (recursively, with `depth - 1`), and the largest value is chosen.
• The value returned is the negative of the value found in the previous step. (This is because we found the value of the best move for our opponent, and what is good for the opponent is bad for us.)

Notice that the heuristic function is only called at the "leaves"--either at the end of the game, or when the depth limit is reached. Values are then propagated upwards via minimaxing.

`def heuristic(player: Char, state: State): Int`
Finds the value of the given `state` for the given `player`. The value should be very high if the player is in the center of the board with at least 100¢ and more money than the other player, and very low if the situation is reversed. If the game hasn't yet ended (no one is in the center of the board), then the value I use is simply the player's money minus the opponent's money.

This is a description of how I implemented the game. It is in no way a requirement that you should do things the same way.

My program searches to a depth of 13 in about 4 or 5 seconds; a depth of 14 is too slow to come in under the required 10 seconds. I have won games in which I played first, but I haven't played enough games to do so consistently.