tic-tac-toe-minimax

"""
tic-tac-toe using minimax
Uros Ogrizovic
"""

from time import sleep

empty_space_sign = 'E'
spaces = [[empty_space_sign, empty_space_sign, empty_space_sign],
          [empty_space_sign, empty_space_sign, empty_space_sign],
          [empty_space_sign, empty_space_sign, empty_space_sign]]


def check_vertical_termination():
    """
    checks for column-wise termination

    :return: 0 (no termination), 1 (computer wins), -1 (player wins)
    """
    pairs = [(0, 0), (0, 1), (0, 2)]
    for i, j in pairs:
        if spaces[i][j] == spaces[(i+1) % 3][j] == spaces[(i+2) % 3][j] != empty_space_sign:
            player = -1 if spaces[i][j] == 'X' else 1
            return player
    return 0


def check_diagonal_termination():
    """
    checks for diagonal-wise termination

    :return: 0 (no termination), 1 (computer wins), -1 (player wins)
    """
    if spaces[0][0] == spaces[1][1] == spaces[2][2] != empty_space_sign:
        player = -1 if spaces[1][1] == 'X' else 1
        return player
    elif spaces[0][2] == spaces[1][1] == spaces[2][0] != empty_space_sign:
        player = -1 if spaces[1][1] == 'X' else 1
        return player
    return 0


def check_horizontal_termination():
    """
    checks for row-wise termination
    
    :return: 0 (no termination), 1 (computer wins), -1 (player wins)  
    """
    pairs = [(0, 0), (1, 0), (2, 0)]
    for i, j in pairs:
        if spaces[i][j] == spaces[i][(j+1) % 3] == spaces[i][(j+2) % 3] != empty_space_sign:
            player = -1 if spaces[i][j] == 'X' else 1
            return player
    return 0


def check_termination():
    """
    checks for three types of termination: column-wise, diagonal-wise and row-wise
    
    :return: 0 (not over), 1 (computer wins) or -1 (human wins)
    """
    val = check_diagonal_termination()
    if val != 0:
        return val
    val = check_vertical_termination()
    if val != 0:
        return val
    val = check_horizontal_termination()
    if val != 0:
        return val
    return 0


def place_sign(sign, row, col):
    """
    places 'X' or 'O' at [row][col] space on board.
    Checks if space is already taken.

    :param sign: 'X' or 'O'
    :param row: row index
    :param col: column index
    :return: -1 if space is already taken
    """
    if spaces[row][col] == empty_space_sign:
        spaces[row][col] = sign
    else:
        print("Space already taken. Try again.")
        return -1   # used if player tries to play on square that is taken


def get_possible_moves():
    """
    checks which spaces are empty, and
    returns a list of those spaces/moves

    :return: list of possible moves
    """
    possible_moves = []
    for i in range(len(spaces)):
        for j in range(len(spaces)):
            if spaces[i][j] == empty_space_sign:
                possible_moves.append((i, j))
    return possible_moves


def minimax(player):
    """
    minimax algorithm. The computer is the maximizer,
    whereas the human is the minimizer.

    :param player: 1 (computer), -1 (human)
    :return:
    """
    winner = check_termination()
    if winner != 0:     # if the game is over
        return winner, -1, -1

    possible_moves = get_possible_moves()
    if len(possible_moves) == 0:    # no possible moves, i.e. no empty spaces
        return 0, -1, -1    # draw

    # human minimizes, computer maximizes
    sign, best_score = ('X', 10) if player == -1 else ('O', -10)

    score, best_row, best_col = 0, 0, 0
    for move in possible_moves:
        place_sign(sign, move[0], move[1])
        score, _, _ = minimax(player * -1)    # change player when calling minimax
        spaces[move[0]][move[1]] = 'E'  # undo move

        if player == 1 and score > best_score:  # update best score and best move
            best_score, best_row, best_col = score, move[0], move[1]
        if player == -1 and score < best_score:     # update best score and best move
            best_score, best_row, best_col = score, move[0], move[1]

    return best_score, best_row, best_col


def display_board():
    """
    displays board in console

    :return:
    """
    for i in range(len(spaces)):
        for j in range(len(spaces)):
            print(spaces[i][j], end=' ')
        print('')


if __name__ == "__main__":
    print("NOTE: Upper-left corner has coordinates (1, 1), bottom-right corner has coordinates (3, 3)")
    while True:
        display_board()

        while True:
            row = int(input('Which row do you want to place X on? ')) - 1
            col = int(input('Which column do you want to place X on? ')) - 1
            if place_sign('X', row, col) != -1:
                break
        if check_termination() == -1:
            display_board()
            print("Human wins.")
            break

        display_board()
        print('Computer\'s turn. Please wait...')
        score, row, col = minimax(1)
        sleep(1)    # better UX, couldn't resist :)
        if score == 0 and len(get_possible_moves()) == 0:
            display_board()
            print("The game is a draw.")
            break
        print('Computer chooses:', row + 1, col + 1)
        place_sign('O', row, col)
        if check_termination() == 1:
            display_board()
            print("Computer wins.")
            break