tictactoe.py

"""
Tic Tac Toe Player
"""
import math
import random
import copy
import operator

X = "X"
O = "O"
EMPTY = None


def initial_state():
    """
    Returns starting state of the board.
    """
    return [[EMPTY, EMPTY, EMPTY],
            [EMPTY, EMPTY, EMPTY],
            [EMPTY, EMPTY, EMPTY]]


def player(board):
    """
    Returns player who has the next turn on a board.
    """
    if terminal(board):
        return -2
    else:  # we asume that the first player is X
        flat_copy = flatten(board)
        return X if flat_copy.count(X) <= flat_copy.count(O) else O


def actions(board):
    """
    Returns set of all possible actions (i, j) available on the board.
    """
    if terminal(board):
        return -2
    # associate each element to its ordinal value from 0 to 8 tile of grid
    else:
        flat_copy_zip = zip(flatten(board), range(0, 9))
    # transform possible move places to its grid coordinates
    # filter only thoses empty places where player can play ie. None is available
        moves = {map_coordinates(b) for (a, b) in flat_copy_zip if a is None}
    return moves


def result(board, action):
    """
    Returns the board that results from making move (i, j) on the board.
    """
    check(action)
    who_plays = player(board)  # who's turn it is?
    next_board = copy.deepcopy(board)
    (i, j) = action
    # replaces in place the ith tile with X or O players turn
    next_board[i][j] = who_plays
    return next_board


def winner(board):
    """
    Returns the winner of the game, if there is one.
    """
    flat_board = flatten(board)
    line_win = line_winner(board)
    column_win = column_winner(flat_board)
    diagonal_win = diagonal_winner(flat_board)
    return game_winner if line_win or column_win or diagonal_win else None


def terminal(board):
    """
    Returns True if game is over, False otherwise.
    """
    return True if winner(board) or is_full(board) else False


def utility(board):
    """
    Returns 1 if X has won the game, -1 if O has won, 0 otherwise.
    """

    if winner(board):
        if game_winner == O:
            return -1
        elif game_winner == X:
            return 1
    else:
        return 0


def minimax(board):
    """
    Returns the optimal action for the current player on the board.
    """
    if terminal(board):
        return None

    if is_empty(board):  # on the opening move all actions have utility=0
        # any first move is equi-probable of winning?
        return (random.randrange(0, 3), random.randrange(0, 3))

    if player(board) == X:  # AI's plays as X
        move_value_pairs = set()
        for move in actions(board):
            v = min_value(result(board, move))
            if v > 0 : #alpha-beta prunning.
                return move # X has found a winning board no need to search further
            else:
                move_value_pairs.add((move, v))
            # any pair with higest value is ok
        (best_move, _) = max(move_value_pairs, key=operator.itemgetter(1))
        return best_move
    elif player(board) == O:  # AI plays as O
        move_value_pairs = set()
        for move in actions(board):
            v = max_value(result(board, move))
            if v < 0 : # O has found a winning board
                return move
            else:
                move_value_pairs.add((move, v))
        (best_move, _) = min(move_value_pairs, key=operator.itemgetter(1))
        return best_move


"""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""
XXXXXXXXXXXXXXXXXXXX    UTILITY FUNCTIONS     XXXXXXXXXXXXXXXXXXXXXX
"""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""


def max_value(board):
    if terminal(board):
        return utility(board)
    else:
        v = -math.inf
        for action in actions(board):
            v = max(v, min_value(result(board, action)))
        return v


def min_value(board):
    if terminal(board):
        return utility(board)
    else:
        v = math.inf
        for action in actions(board):
            v = min(v, max_value(result(board, action)))
        return v


def check(action):
    (i, j) = action
    if i not in range(0, 3) or j not in range(0, 3):
        raise Exception()


def is_full(board):
    flat_board = flatten(board)
    n = flat_board.count(None)
    return False if n > 0 else True


def is_empty(board):
    flat_board = flatten(board)
    n = flat_board.count(None)
    return True if n == 9 else False


def line_winner(board):
    line_1_win = winning(board[0])
    line_2_win = winning(board[1])
    line_3_win = winning(board[2])
    # if any 3 in a row combination is valid
    return True if line_1_win or line_2_win or line_3_win else False


def column_winner(flat_board):
    column1 = flat_board[0:9:3]
    column2 = flat_board[1:9:3]
    column3 = flat_board[2:9:3]
    column_1_win = winning(column1)
    column_2_win = winning(column2)
    column_3_win = winning(column3)
    return True if column_1_win or column_2_win or column_3_win else False


def diagonal_winner(flat_board):
    diag1 = flat_board[0:9:4]
    diag2 = flat_board[2:8:2]
    diagonal_1_win = winning(diag1)
    diagonal_2_win = winning(diag2)
    return True if diagonal_1_win or diagonal_2_win else False


def winning(series):  # returns the wieiwie
    # counts number of occurrences of first element
    n = [x for x in series if x is not None].count(series[0])
    if n == 3:
        global game_winner  # we have a winner!
        game_winner = series[0]
        return True


def flatten(board):  # flatten the list of list board
    return [item for sublist in board for item in sublist]


def map_coordinates(number):
    if number == 0:
        return (0, 0)
    if number == 1:
        return (0, 1)
    if number == 2:
        return (0, 2)
    if number == 3:
        return (1, 0)
    if number == 4:
        return (1, 1)
    if number == 5:
        return (1, 2)
    if number == 6:
        return (2, 0)
    if number == 7:
        return (2, 1)
    if number == 8:
        return (2, 2)


def map_action(action):
    if action == (0, 0):
        return 0
    if action == (1, 0):
        return 3
    if action == (2, 0):
        return 6
    if action == (0, 1):
        return 1
    if action == (1, 1):
        return 4
    if action == (2, 1):
        return 7
    if action == (0, 2):
        return 2
    if action == (1, 2):
        return 5
    if action == (2, 2):
        return 8