miserable_tictactoe.py

import random
from fractions import Fraction

# each game is two integers, "my marks" and "other's marks"
# player 1 plays randomly, player 2 tries to minimize their own score


SCORE_CACHE = {}

def score(game):
    if game not in SCORE_CACHE:
        SCORE_CACHE[game] = calc_score(game)
    return SCORE_CACHE[game]

WIN_PRIO = 3
SMALL = -3

def calc_score(game, verbose=False):
    if game_is_won(game):
        return -1, -1, 0
    num_positions = 0
    random_avg = 0
    misere_move = 0
    max_prio = SMALL
    max_opponent_score = SMALL
    for m, c in continuations(game):
        c_min, c_avg, c_move = score(c)
        if verbose:
            moveid = m.bit_length()
            print(f"Move {moveid}: expected value {c_avg:.2f}", end="")
        num_positions += 1
        random_avg += c_min
        if game_is_won(c):
            prio = WIN_PRIO
            if verbose:
                print(" and I win!")
        elif c_min == 1 and can_win_immediately(c):
            # Opponent can win next turn, we shouldn't go here if there's an alternative!
            prio = SMALL
            if verbose:
                print(" and you can win...")
        else:
            # Opponent to improve position when moving at random...
            prio = c_avg
            if verbose:
                print()
        if prio > max_prio or (prio == max_prio and c_avg > max_opponent_score):
            max_prio = prio
            max_opponent_score = c_avg
            misere_move = m
        elif prio == max_prio:
            misere_move |= m
    if num_positions == 0:
        return 0, 0, 0
    if verbose:
        print(f"Best move(s) found: {bin(misere_move)}, score {max_opponent_score:.2f}")
    return -max_opponent_score, Fraction(-random_avg, num_positions), misere_move


FINISHED_STATES = [
        0b111_000_000,
        0b000_111_000,
        0b000_000_111,
        0b100_100_100,
        0b010_010_010,
        0b001_001_001,
        0b100_010_001,
        0b001_010_100,
]


def game_is_draw(game):
    a, b = game
    return (a | b) == (1 << 10) - 1

def game_is_won(game):
    a, b = game
    return any((b & state) == state for state in FINISHED_STATES)


def can_win_immediately(game):
    # inefficient but w/e
    return any(game_is_won(c) for _, c in continuations(game))

VALID_MOVES = [1<<i for i in range(9)]

def continuations(game):
    for move in VALID_MOVES:
        if (n := make_move(move, game)) is not None:
            yield move, n

def make_move(move, game):
    a, b = game
    filled = a | b
    if move & filled:
        return None
    return b, a | move


def print_game(game, flip):
    if flip:
        b, a = game
    else:
        a, b = game
    fields = []
    for i in range(9):
        if a & (1<<i):
            fields.append('X')
        elif b & (1<<i):
            fields.append('O')
        else:
            fields.append(str(i + 1))
    return """\
+-+-+
|{}|{}|{}|
+-+-+
|{}|{}|{}|
+-+-+
|{}|{}|{}|
+-+-+""".format(*fields)


def get_user_next_move(game):
    while True:
        x = input("Play where? (? to show options) ").strip()
        if x == '?':
            print("Expected scores:")
            for m, c in continuations(game):
                min_score, _, _ = score(c)
                moveidx = m.bit_length()
                print(f"Move {moveidx}: {-min_score:.2f}")
            _, avg, _ = score(game)
            print(f"Expected: {avg:.2f}")
            continue
        if not x.isdigit():
            continue
        m = int(x) - 1
        if not 0 <= m < 9:
            continue
        n = make_move(1 << (int(x) - 1), game)
        if n is not None:
            break
    return n

def main():
    game = 0, 0
    flip = False
    if input('Do you want to start? [y] ') == 'n':
        flip = True
    else:
        game = get_user_next_move(game)
    while True:
        print(print_game(game, not flip))
        if game_is_draw(game):
            print("DRAW!")
            break
        if game_is_won(game):
            print("Yes! You win!")
            break
        print("My turn...")
        _, _, moves = calc_score(game, verbose=True)
        valid_moves = []
        for i in range(9):
            move = 1 << i
            if move & moves:
                valid_moves.append(move)
        move = random.choice(valid_moves)

        game = make_move(move, game)
        if game_is_draw(game):
            print("DRAW!")
            break
        if game_is_won(game):
            print("I win this time!")
            break
        print(print_game(game, flip))
        game = get_user_next_move(game)
    print("Thanks for playing! Launch me with python3 -i to explore the decision tree")


if __name__ == '__main__':
    main()