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