A program that solves tic tac toe using the Minimax algorithm. Can defeat or draw always.

tic_tac_toe_solved.py

import time
import sys

print "Maximizer is X and Minimizer O"

class Position:
    def __init__(self, parent_):
        self.parent = parent_
        self.children = []
        self.best_eval = []
        self.pos_matrix = []
        self.last_move = []

    def set_pos_matrix(self, pos_matrix_):
        self.pos_matrix = list(list(l) for l in pos_matrix_)

    def set_last_move(self, last_move_):
        self.last_move = list(last_move_)

    # this below is an exploration function
    def evaluate(self, chance):
        if not self.children:
            return self.get_static_evaluation()
        if chance==1:
            mex = ([42, 720], -9001) # Move, evaluation
            for child in self.children:
                temp_eval = child.evaluate(-chance)
                if temp_eval[1]>mex[1]:
                    mex = temp_eval
        elif chance==-1:
            mex = ([42, 720], 9001)
            for child in self.children:
                temp_eval = child.evaluate(-chance)
                if temp_eval[1]<mex[1]:
                    mex = temp_eval
        self.best_eval = mex
        return (self.last_move, mex[1])

    # this below is not an exploration function
    # instead, a static evaluation of leaf positions is given
    # by this guy
    def get_static_evaluation(self):
        # Eval is 9000 if X is winning, -9000 if O is winning,
        # 0 if draw.
        # -1 if game still going on
        m = self.pos_matrix

        # dem rows
        for i in xrange(3):
            if set(m[i])==set([1]):
                self.evaluation = 9000
                return (self.last_move, self.evaluation)
            if set(m[i])==set([-1]):
                self.evaluation = -9000
                return (self.last_move, self.evaluation)
        # dem columns
        for i in xrange(3):
            temp = set([m[j][i] for j in xrange(3)])
            if temp==set([1]):
                self.evaluation = 9000
                return (self.last_move, self.evaluation)
            if temp==set([-1]):
                self.evaluation = -9000
                return (self.last_move, self.evaluation)
        
        temp = set([m[i][i] for i in xrange(3)])
        if temp==set([1]):
            self.evaluation = 9000
            return (self.last_move, self.evaluation)
        if temp==set([-1]):
            self.evaluation = -9000
            return (self.last_move, self.evaluation)

        temp = set([m[i][2-i] for i in xrange(3)])
        if temp==set([1]):
            self.evaluation = 9000
            return (self.last_move, self.evaluation)
        if temp==set([-1]):
            self.evaluation = -9000
            return (self.last_move, self.evaluation)

        if not self.get_possible_moves():
            return (self.last_move, 0) # Game drawn

        return ([-155, -155], -1) # Game still going on

    def play_move(self, move, kiska_chance):
        m2 = list(list(l) for l in self.pos_matrix)
        x, y = move
        m2[x][y] = kiska_chance

        return m2

    def generate_children(self, kiska_chance):
        stetic_evel = self.get_static_evaluation()
        if stetic_evel[1]==9000 or stetic_evel[1]==-9000 or stetic_evel[1]==0:
            self.children = []
            return []

        children_ = []
        for move in self.get_possible_moves():
            # Passing a Position object into the possible moves with
            # parent as self.
            pos_temp = Position(self)
            pos_temp.set_pos_matrix(self.play_move(move, kiska_chance))
            pos_temp.set_last_move(move)

            children_.append(pos_temp)
        self.children = children_

        return children_

    def get_possible_moves(self):
        dem_moves = []
        for i in xrange(3):
            for j in xrange(3):
                if self.pos_matrix[i][j]==0:
                    dem_moves.append([i, j])
        return dem_moves

    def find_child(self, grid):
        for child in self.children:
            if child.pos_matrix==grid:
                return child


pos_daddy = Position(None)
pos_daddy.set_pos_matrix([[0, 0, 0],
                          [0, 0, 0],
                          [0, 0, 0]])

# BFS to enumerate possibility tree
time_start = time.time()
next_ = []
frontier = [pos_daddy]
chance = 1 # X's chance
depth = 1
while frontier:
    print "Current depth: {0}".format(depth)
    print "    Frontier length: {0}".format(len(frontier))
    time.sleep(0.5)
    next_ = []
    i = 0
    for node in frontier:
        next_.extend(node.generate_children(chance))
        if i%100==0: print ".",
        i+=1
    print


    frontier = next_
    depth += 1
    chance = -chance

print "Time taken for populating tree: {0}".format(
    time.time()-time_start)

#   Top Down approach:
#     Just call evaluate for daddy object and it calls children's
#     evaluate with appropriate min/max intentions and in turn 
#     the whole tree gets explored.
#     dun dun dun

time_start = time.time()
print pos_daddy.evaluate(1)
print "Time taken for running Minimax: {0}".format(
    time.time()-time_start)


def pretty_print_dat_grid(grid):
    for i in xrange(3):
        for j in xrange(3):
            if grid[i][j]==-1:
                print "O",
            elif grid[i][j]==1:
                print "X",
            else:
                print "-",
        print


print "Time to play."
print "You take X and I take O"
print "Also, I follow zero indexing. Remember that."
print "Counting starts at zero."


current_grid = [[0, 0, 0],
                [0, 0, 0],
                [0, 0, 0]]
current_node = pos_daddy
while True:
    print "Enter row coord to make X in:"
    x = int(raw_input())
    print "Enter column coord to make X in:"
    y = int(raw_input())
    current_grid[x][y] = 1
    
    current_node = current_node.find_child(current_grid)
    pretty_print_dat_grid(current_grid)

    last_move, cureval = current_node.get_static_evaluation()
    print "static eval:", last_move, cureval
    print "Best move from this position:", current_node.best_eval
    if cureval!=-1:
        if cureval==-9000:
            print "I win sucker."
        elif cureval==9000:
            print "You win this time."
        else:
            print "Draw huh. I feel embarassed."
            print current_node.get_static_evaluation()
        break

    best_m8_rekt = current_node.best_eval
    move = best_m8_rekt[0]
    print "My move is: {0} {1}".format(*move)
    current_grid[move[0]][move[1]] = -1

    current_node = current_node.find_child(current_grid)
    pretty_print_dat_grid(current_grid)

    last_move, cureval = current_node.get_static_evaluation()
    print "Last move and cureval:", last_move, cureval
    print "Best move from this position:", current_node.best_eval
    if cureval!=-1:
        if cureval==-9000:
            print "I win!"
        elif cureval==9000:
            print "You win this time."
        else:
            print "Draw. I feel embarassed."
            print current_node.get_static_evaluation()
        break