|
Home
| |
Game Trees and the MiniMax Procedure
Related Reading: Chapter 6 in
the Omnibus.
Due: By class time Wednesday April 16,
2008
[This problem
is originally due to Cormac Flanagan.]
[ Note: Some hints and additions
were made Sunday morning -- they are in red. ]
In this assignment you will implement a strategy to play a simple game. The
game is called Mancala,
and in particular a version called
Kalah, but you don't
need to worry about the specific rules, since we have implemented that part for
you. Your job is to build a tree of possible move sequences and choose the move
that appears best.
Download the support code,
(here is a
newer version) which provides the
following set of data types and functions:
 | Player: values of this type represent the players of the game
(A or B). |
| PState: contains
a player's current score and the contents of her pits. |
| State: values of this type represent game configurations. |
| initialState :: Player -> State represents the initial
configuration of the game board (the given player goes first). |
| getPlayer: State -> Player: given a configuration, returns
the player who makes the next move. |
| nextStates :: State -> [State] gives the possible
configurations after the next move. If the returned list is empty, then the
game is over. |
| simulateGame :: IO () runs a 2 player interactive game.
|
| playComputer :: (Player->State->Int) -> IO () allows you to
play the computer by providing a rating function (see below). |
| computerWar :: (Player->State->Int)
-> (Player->State->Int) -> IO ()
allows the computer to play itself by providing
two rating functions, one for
player A, and the other for player B. |
Note: the newer version does a
better job with I/O from the user -- if you make a mistake in what you type, or
type an invalid move, it will tell you and then ask for you to try again.
If you want to stop the game prematurely, type the move "0".
Extend this file with the following additional definitions:
- Define a data type
GameTree to represent the game
tree starting at some configuration.
Each node should have its current configuration and a
list of subtrees, where each subtree corresponds to
the game tree after a specific single move.
- Define the tree of all legal board configurations (those obtainable by
repeated application of
nextStates to the initialState).
- Define
prune :: Int -> GameTree -> GameTree, which prunes a
tree to a given height.
- Define
minimax :: Player -> GameTree -> Int, which consumes a
(pruned) tree and evaluates the configuration by looking ahead and applying
the minimax algorithm. If a node has no children, it receives its own
immediate score. If it corresponds to Player's turn, it receives
the maximum of the recursively-computed child scores, otherwise it receives
the minimum.
- Define
rating :: Player -> State -> Int, which provides a
rating about how good each state is for the given player. This function should
create a pruned game tree and run the minimax algorithm on that tree.
- Define
bestMove :: (Player->State->Int) -> State -> Int,
such that bestMove r s will determine the best move from state s given rating
function r. (Note: This is not a new requirement, but it was not spelled
out here on the assignment webpage.)
In ghci, run playComputer rating. The playComputer
function then uses your rating function to evaluate each of its possible moves,
and choose the best one. You should only need to add to
Macala.lhs, not change any
other functions.
Hints:
| Remember that if a player's
last stone is placed in her pit, then she gets to move again. This means
that the game tree will not strictly alternate between "min" nodes and "max"
nodes. But the basic idea still works -- you just need to treat each
node on its own, rather than by level. |
| It may seem that the overall
structure of the program is inefficient, in that the game tree is recomputed
at every node. And you are right! But this structure makes it a
little easier to separate the code that you are writing from the rest of the
code. The concepts are all still the same. |
Solution.
|
