**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
an X or an O.**either** - 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.

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

Prior to the deadline, use the homework submission system

https://www.cs.uni.edu/~schafer/submit/which_course.cgi

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.