## Homework 2

### Due: Friday, October 12, 10:00 AM

Introduction

Consider the following variation to tic-tac-toe

• Players alternate taking turns placing a piece on a standard tic-tac-toe board
• 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 row, wins.

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).

Instructions

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, or -2
• 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.