tictactoe_tree.py

# Solves the exact evaluation of any tic tac toe position

import copy

# Square definitions
X_SQUARE = 'X'
O_SQUARE = 'O'
BLANK = '_'

# Evaluation definitions
X_WINS = 'X wins!'
O_WINS = 'O wins!'
DRAW = 'Draw!'


# Returns true if X's turn to move, false otherwise
def is_X_turn(pos):
    x_count = 0
    for row in pos:
        x_count += row.count(X_SQUARE)
        x_count -= row.count(O_SQUARE)
    return x_count == 0


# Returns true if every space is taken, false otherwise
def is_full(pos):
    for row in pos:
        if BLANK in row:
            return False
    return True


# Takes a position, and returns a list of every position that can result from a move
def get_branches(pos, X_turn):
    symbol = X_SQUARE if X_turn else O_SQUARE
    branches = []
    for row in range(3):
        for square in range(3):
            if pos[row][square] == BLANK:
                branches.append(copy.deepcopy(pos))
                branches[-1][row][square] = symbol
    return branches


# Checks for three in a row in the current position, returns evaluation
def get_static_eval(pos):
    potential_wins = []

    # Three in a row
    for row in pos:
        potential_wins.append(set(row))

    # Three in a column
    for i in range(3):
        potential_wins.append(set([pos[k][i] for k in range(3)]))

    # Two in a diagonal
    potential_wins.append(set([pos[i][i] for i in range(3)]))
    potential_wins.append(set([pos[i][2 - i] for i in range(3)]))

    # Checking if any three are the same
    for trio in potential_wins:
        if trio == set([X_SQUARE]):
            return X_WINS
        elif trio == set([O_SQUARE]):
            return O_WINS
    return DRAW


# Returns the dynamic evaluation of any valid position
def main_solve(pos):
    solution = solve(pos)
    return solution


def solve(pos, count=None):
    # Immediately return the static evaluation if it is decisive
    if count is None:
        count = {"X wins!": 0, "O wins!": 0, "Draw!": 0}

    # Check for full board
    game_eval = get_static_eval(pos)
    full = is_full(pos)
    if full:
        count[game_eval] += 1
        return count
    if not full and game_eval != DRAW:
        count[game_eval] += 1
        return count

    # Checking and evaluating every path
    X_turn = is_X_turn(pos)
    branches = get_branches(pos, X_turn)
    branch_evals = [solve(branch, count) for branch in branches]

    return count




states = [
    [
        ['X', 'O', '_'],
        ['_', '_', '_'],
        ['_', '_', '_']
    ],
    [
        ['X', '_', '_'],
        ['_', '_', 'O'],
        ['_', '_', '_']
    ],
    [
        ['X', '_', '_'],
        ['_', 'O', '_'],
        ['_', '_', '_']
    ],
    [
        ['X', '_', '_'],
        ['_', '_', '_'],
        ['_', '_', 'O']
    ],
    [
        ['X', '_', 'O'],
        ['_', '_', '_'],
        ['_', '_', '_']
    ],
    [
        ['_', 'O', '_'],
        ['_', 'X', '_'],
        ['_', '_', '_']
    ],
    [
        ['_', '_', 'O'],
        ['_', 'X', '_'],
        ['_', '_', '_']
    ],
    [
        ['O', 'X', '_'],
        ['_', '_', '_'],
        ['_', '_', '_']
    ],
    [
        ['_', 'X', '_'],
        ['_', 'O', '_'],
        ['_', '_', '_']
    ],
    [
        ['_', 'X', '_'],
        ['O', '_', '_'],
        ['_', '_', '_']
    ],
    [
        ['_', 'X', '_'],
        ['_', '_', '_'],
        ['O', '_', '_']
    ],
    [
        ['_', 'X', '_'],
        ['_', '_', '_'],
        ['_', 'O', '_']
    ],
]

solutions = [main_solve(state) for state in states]
totals = [
    sum(solution.values())
    for solution in solutions
]
values = [
    solution[X_WINS] - solution[O_WINS]
    for solution in solutions
]
print()