# Minimax in tic-tac-toe

The goal of this assignment is to make an optimal tic-tac-toe player using minimax.

Here are the minimax functions:

```max-value(state)
if state is a completed game, return its utility
otherwise return the opponent's max(min-value(child)) over all children of state
```

```min-value(state)
if state is a completed game, return its utility
otherwise return the opponent's min(max-value(child)) over all children of state
```

To apply this algorithm to tic-tac-toe, think of a state as a partially completed game. The "children" of a state are the ones that can be reached by marking an empty spot on the grid.

A Game class and an Agent class have been started for you below. Once you complete the indicated methods, you will be able to watch a perfect game being played. Adjust the height of your console window to match the grid height, so that each display appears in the same place.

```import copy
import time

class Game(object):
"""A tic-tac-toe game."""

def __init__(self, grid):
"""Instances differ by their grid marks."""
self.grid = copy.deepcopy(grid) # No aliasing!

def display(self):
"""Print the game board."""
for row in self.grid:
for mark in row:
print mark,
print
print

def moves(self):
"""Return a list of possible moves given the current marks."""
# YOU FILL THIS IN

def neighbor(self, move, mark):
"""Return a Game instance like this one but with one move made."""
# YOU FILL THIS IN

def utility(self):
"""Return the minimax utility value of this game:
1 = X win, -1 = O win, 0 = tie, None = not over yet."""
# YOU FILL THIS IN

class Agent(object):
"""Knows how to play tic-tac-toe."""

def __init__(self, mark):
"""Agents use either X or O."""
self.mark = mark

def maxvalue(self, game, opponent):
"""Compute the highest utility this game can have."""
# YOU FILL THIS IN

def minvalue(self, game, opponent):
"""Compute the lowest utility this game can have."""
# YOU FILL THIS IN

def main():
"""Create a game and have two agents play it."""

game = Game([['-','-','-'], ['-','-','-'], ['-','-','-']])
game.display()

maxplayer = Agent('X')
minplayer = Agent('O')

while True:

(value, move) = maxplayer.maxvalue(game, minplayer)
game = game.neighbor(move, maxplayer.mark)
time.sleep(1)
game.display()

if game.utility() is not None:
break

(value, move) = minplayer.minvalue(game, maxplayer)
game = game.neighbor(move, minplayer.mark)
time.sleep(1)
game.display()

if game.utility() is not None:
break

if __name__ == '__main__':
main()
```