Game Playing using MiniMax
Due: Friday, October 12, 10:00 AM
Consider the following variation to tic-tac-toe
- Players alternate taking turns placing a piece on a standard tic-tac-toe
- When it is their turn, players may place either an X or an O.
- First player to cause the board to get three of any single pieces in a
Thus, in theory, the shortest game is 3 moves since both players could place
Xs (although that would mean that player two played very foolishly).
For this homework you should write a program that meets the following requirements:
- You may write your code in either Python or Java (other languages available with pre-approval)
- Your search code should be in a file called either HW2.py or HW2.java
- Your primary search should be in a function calleed search() which takes in a single parameter. This parameter should be the "starting state"
of the game as a SINGLE, string of consisting
of x, o, or - (empty)
- Thus, starting with an empty board is the input string "---------"
- Starting with an x in the upper right corner and an o in the lower left
corner is "--x---o--"
- You must devise a program which uses minimax to search for the "optimal"
next move for the current player.
- The definition of optimal here CAN take many forms. For a variety of
reasons I am going ask that you use the following utility function:
- A draw has a score of zero.
- A "win" by either player is scored as
- (N+1) * playerMultipier
- Where N is the number of empty cells left
- playerMultiplier is 1 for MAX (player 1) and -1 for MIN (player 2)
- Notice that this means that when MAX wins the utility of that board will
be 7, 5, 3, or 1 while if MIN wins the utility of that board will be -6, -4,
- Since you should consider the optimal move then a guaranteed win NOW is a
better move than a guaranteed win in two moves.
- When the optimal move is discovered your code needs to print out the specific
move to take ("X in cell 6") and an indication of whether this move will
eventually lead to a win, a lose, or a draw.
Submitting Your Work
Prior to the deadline, use the homework submission system
to upload any files you have produced.
In addition to online copies, please submit hard copies of this lab at the start of class on the day
this lab is due.