Program 4, CS 463
Due at the beginning of class on Friday, October 23rd.
This assignment uses Minimax and Expectimax for the 5x5 tic-tac-toe game. You will program three strategies: One completely random, one using Minimax, against which you will play, and then expectimax, against which the random player will play.
The heuristic you will use is the following.
For every line (row, column, or one of the two diagonals), if there are exactly
k X's and no )'s, then add k. If there are exactly k O's,
then subtract k.
Unless, of course, the game has already been won, in which casethe value is +100 for X winning, and -100 for O winning.
Your minimax and expectimax will search two deep, and then use the heuristic to
evaluate the board.
Your random strategy is to choose one of the open squares (all with equal likelihood).
To do:
-
Come up with an interface to display a game in progress and take input. It can be straight ASCII display if you'd like.
-
Implement the random strategy. Play against it, 10 games or more. Collect the following data: Who won each game, and in how many moves.
-
Implement the minimax strategy. Play against it, trying a few different openings and responses, 10 games or more. Collect the same data.
-
Implement the expectimax strategy, and have it play against the random strategy. Collect the same data.
To hand in:
- A description of how you implemented the interface and the strategies;
- the data you collected (summarized, or in a table or graph);
- the expectimax and minimax code (commented, of course);
- a brief statement of what you observed, and what you learned.