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.
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
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.
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]
'c', and a State, this method returns a list of operators (
'R') that can be applied.
def nextState(player: Char, direction: Char, state: State): State
Statethat results from moving the
playerin the given
direction. The original
stateis not changed.
def chooseMove(depth: Int, state: State): Char
chooseMovedoes not itself use the
depthparameter; it just passes it along to the
def evaluateMove(player: Char, direction: Char, depth: Int, state: State): Int
depthis zero, the value returned is the value of the heuristic function.
depth - 1), and the largest value is chosen.
def heuristic(player: Char, state: State): Int
statefor 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.