https://cs50.harvard.edu/ai/2020/projects/0/tictactoe/

runner.py

"""
Tic Tac Toe Player
"""

import math
import random
import copy

X = "X"
O = "O"
EMPTY = None
turn = 0

WINNING_STATES = [
    # HORIZONTAL
    {(0, 0),
     (0, 1),
     (0, 2)},

    {(1, 0),
     (1, 1),
     (1, 2)},

    {(2, 0),
     (2, 1),
     (2, 2)},

    # VERTICAL
    {(0, 0),
     (1, 0),
     (2, 0)},

    {(0, 1),
     (1, 1),
     (2, 1)},

    {(0, 2),
     (1, 2),
     (2, 2)},

    # DIAGONAL
    {(0, 0),
     (1, 1),
     (2, 2)},

    {(0, 2),
     (1, 1),
     (2, 0)}
]


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.
    """
    x_count = 0
    o_count = 0

    for row_number, row in enumerate(board):
        for cell_number, cell in enumerate(row):
            if cell == X:
                x_count += 1

            if cell == O:
                o_count += 1

    # if X starts, then O goes after and will always have to catch up...
    if o_count == x_count:
        return X

    # if there are more O's then it's X's turn
    if x_count > o_count:
        return O
    else:
        return X


def actions(board):
    """
    Returns set of all possible actions (i, j) available on the board.
    """

    actions = []

    for row_number, row in enumerate(board):
        for cell_number, cell in enumerate(row):
            if cell == EMPTY:
                actions.append((row_number, cell_number))

    return actions


def result(board, action):
    """
    Returns the board that results from making move (i, j) on the board.
    """
    board_copy = copy.deepcopy(board)

    if not action in actions(board_copy):
        raise BaseException('The action you provided does not exist')

    ROW = action[0]
    CELL = action[1]
    board_copy[ROW][CELL] = player(board_copy)

    return board_copy


def winner(board):
    """
    Returns the winner of the game, if there is one.
    """
    x_cells = set()
    o_cells = set()

    for row_number, row in enumerate(board):
        for cell_number, cell in enumerate(row):
            if cell == X:
                x_cells.add((row_number, cell_number))
            if cell == O:
                o_cells.add((row_number, cell_number))

    for winning_state in WINNING_STATES:
        if all(elements in x_cells for elements in winning_state):
            return X

        if all(elements in o_cells for elements in winning_state):
            return O


def terminal(board):
    """
    Returns True if game is over, False otherwise.
    """
    if winner(board) == X or winner(board) == O or len(actions(board)) == 0:
        return True

    return False


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

    if winner(board) == O:
        return -1

    return 0


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

    current_player = player(board)
    acts = actions(board)
    result_action = {}
    key = None

    min_player = X
    max_player = O

    for index, action in enumerate(acts):
        r = result(board, action)

        result_action[index] = min_value(
            r) if current_player == max_player else max_value(r)

    if current_player == min_player:
        key = min(result_action, key=result_action.get)

    if current_player == max_player:
        key = max(result_action, key=result_action.get)

    return acts[key]


def max_value(board):
    """
    Returns highest value for the state provided
    """
    if terminal(board):
        return utility(board)

    value = -1000
    for action in actions(board):
        r = result(board, action)
        value = max(value, min_value(r))

    return value


def min_value(board):
    """
    Returns lowest value for the state provided
    """
    if terminal(board):
        return utility(board)

    value = 1000
    for action in actions(board):
        r = result(board, action)
        value = min(value, max_value(r))

    return value