Minimax Search and Alpha-Beta Pruning
The aim of this lab is to implement minimax search with
alpha-beta pruning. These are well-known search
techniques often applied in AI game-playing programs and other
situations where decisions are made on the basis of
utility or estimated utility (an evaluation function).
Your Tasks
Your tasks for this lab are as follows:
- Implement the standard minimax algorithm. This
will require that you:
- Write the algorithm, Minimax,
itself. It is recommended that you write this as
a recursive algorithm. A template for
this algorithm has been supplied for you to
complete in the
file Minimax.skeleton in the
search package.
- Write an implementation of the interface
NodeInfo to supply terminal conditions and
utilities for the algorithm. As this is a utility-based
algorithm the goal method need not be used and may
simply return false. The isTerminal method
should return true if the game is over (for example, when
one player has no king in the game CheX) and cut off unproductive
searches where possible (such as the case of two null
moves in a row). The utility function need only provide
values for terminal nodes at this stage.
Note that the NodeInfo interface is in the
search package since it is generic to a range of
searches. However your implementation(s) should be in
your player package, since they are specific to
individual players' strategies.
- Write an implementation of Player that
uses the minimax algorithm.
- Test the algorithm using a very small game just to make
sure it works.
- Add a depth-limit to your algorithm. This will
also require that you upgrade your utility function
to provide utilities for non-terminal states (if it
doesn't already). You might start with the utility function you developed in the "Simple Agents" lab.
You should now be able to test your algorithm on
larger games by setting the cut-off depth
appropriately (probably quite small).
- Once you have the basic Minimax algorithm working,
implement Alpha-Beta search (Minimax with alpha-beta
pruning). This can be achieved by copying and modifying your
minimax code. You will need to pass two new
arguments, alpha and beta, in each recursive call.
This should allow you to search to the same depth using less time and fewer expanded nodes. Print out the number of nodes expanded by Minimax and Alpha-Beta on the same problems to check whether this is true. What kind of performance difference do you observe?
Similarly, you should be able to increase the depth of your search while still
achieving reasonable response time.
You should now be able to implement an agent that shows reasonably competent performance, and consistently beats at least some of the sample agents.
|