Project: an unbeatable game opponent

Minimax

Give every finished game a score from X's point of view: +1 if X won, -1 if O won, 0 for a draw. Now work backward. On X's turn, X picks the move with the highest score; on O's turn, O picks the lowest. Each player assumes the other plays perfectly, so the score of a position is the result of perfect play from there. That rule is minimax.

Try it first on a game small enough to follow by hand. In Trail markers, a pile holds some markers, and the two players take turns removing 1, 2 or 3 of them. Whoever takes the last marker wins.

from functools import cache

@cache
def best(markers):
    """(score, move) for the player about to move: +1 means they can force a win."""
    if markers == 0:
        return (-1, None)  # the other player just took the last marker
    options = []
    for take in (1, 2, 3):
        if take <= markers:
            their_score, _ = best(markers - take)
            options.append((-their_score, take))  # good for them is bad for me
    return max(options)

for n in range(1, 13):
    score, take = best(n)
    print(f"{n:2} markers: {'win by taking ' + str(take) if score == 1 else 'lose against perfect play'}")

This version uses a common shortcut called negamax: instead of one player maximizing and the other minimizing, each player maximizes their own score, and a score passes to the other player with its sign flipped. The pattern in the output is the game's secret: a pile that's a multiple of 4 is lost for the player to move, and from any other pile you win by leaving a multiple of 4. The search found that without being told.

Now play it. You move first from 15 markers, and the program plays perfectly, so you win only by leaving it a multiple of 4 every time:

from functools import cache

@cache
def best(markers):
    if markers == 0:
        return (-1, None)
    return max((-best(markers - take)[0], take) for take in (1, 2, 3) if take <= markers)

markers = 15
while markers > 0:
    answer = input(f"{markers} markers left. Take 1, 2 or 3: ")
    if answer not in ("1", "2", "3") or int(answer) > markers:
        print("Take 1, 2 or 3, and no more than are left.")
        continue
    markers -= int(answer)
    if markers == 0:
        print("You took the last marker. You win!")
        break
    score, take = best(markers)
    markers -= take
    print(f"I take {take}." + (" I can't lose from here." if score == 1 else ""))
    if markers == 0:
        print("I took the last marker. I win!")

Win fast, lose slowly

Plain minimax treats every win alike, so an opponent that could win right now might wander and win three moves later, which looks foolish. Scoring with depth fixes it: a win is worth more the sooner it comes, and a loss costs less the later it comes. With nine cells, 10 - depth for an X win and depth - 10 for an O win works, where depth counts the moves already on the board.

Breaking ties matters too. When several moves score the same, pick deterministically, such as the lowest cell number, so the program behaves the same in every run and its tests are repeatable.

Proving it never loses

How do you test "this opponent never loses"? For tic-tac-toe you can check every game: let the program play one side, and at each of the other side's turns try every possible reply. If no branch ends in a loss, the claim is proved, not just likely. That's an exhaustive test, possible whenever the space of inputs is small enough to enumerate; for larger problems, tests sample it instead.

Beyond tic-tac-toe

Chess has more possible positions than there are atoms in the observable universe, so a chess program can't search to the end. It searches a few moves ahead, scores the positions it reaches with an evaluation function (material, mobility, king safety), and uses alpha-beta pruning to skip branches that can't change the decision. Programs for Go went further with Monte Carlo tree search and neural networks that learn the evaluation. The skeleton you're building is the same in all of them.

def turn(board):
    pass


def full(board):
    pass


print(turn((" ",) * 9), turn(("X",) + (" ",) * 8), full(("X", "O") * 4 + ("X",)))

LINES = [(0, 1, 2), (3, 4, 5), (6, 7, 8), (0, 3, 6), (1, 4, 7), (2, 5, 8), (0, 4, 8), (2, 4, 6)]

def winner(b):
    for a, c, d in LINES:
        if b[a] != " " and b[a] == b[c] == b[d]:
            return b[a]
    return None

def score_of(b):
    w = winner(b)
    return 1 if w == "X" else -1 if w == "O" else 0 if " " not in b else None

visits = {"minimax": 0, "alphabeta": 0}

def minimax(b, p):
    visits["minimax"] += 1
    s = score_of(b)
    if s is not None:
        return s
    nxt = "O" if p == "X" else "X"
    scores = [minimax(b[:i] + (p,) + b[i + 1:], nxt) for i, c in enumerate(b) if c == " "]
    return max(scores) if p == "X" else min(scores)

def alphabeta(b, p, alpha=-2, beta=2):
    visits["alphabeta"] += 1
    s = score_of(b)
    if s is not None:
        return s
    nxt = "O" if p == "X" else "X"
    best = -2 if p == "X" else 2
    for i, c in enumerate(b):
        if c != " ":
            continue
        v = alphabeta(b[:i] + (p,) + b[i + 1:], nxt, alpha, beta)
        if p == "X":
            best, alpha = max(best, v), max(alpha, v)
        else:
            best, beta = min(best, v), min(beta, v)
        if alpha >= beta:
            break  # the other player would never allow this line, so stop looking
    return best

center = (" ",) * 4 + ("X",) + (" ",) * 4  # X took the center; O to move
print("minimax:", minimax(center, "O"), "after", f"{visits['minimax']:,}", "positions")
print("alpha-beta:", alphabeta(center, "O"), "after", f"{visits['alphabeta']:,}", "positions")

import random

WIDTH = {"rock": 1, "branch": 3, "gap": 4}
LENGTH = 1000
JUMP_STEPS, DUCK_STEPS = 6, 5


def make_course(seed):
    """Obstacles along the ridge: (position, kind), at least 20 apart."""
    rng = random.Random(seed)
    obstacles, x = [], 30
    while True:
        x += rng.randint(20, 42)
        if x >= LENGTH - 10:
            return obstacles
        kind = rng.choice(list(WIDTH))
        obstacles.append((x, kind))
        x += WIDTH[kind]


def run_course(policy, seed):
    """How far the runner gets on one course: LENGTH if it reaches the end."""
    obstacles = make_course(seed)
    pos, air, duck = 0.0, 0, 0
    while pos < LENGTH:
        speed = 1 + 1.5 * pos / LENGTH
        # Landing in a gap or on a rock, or standing up under a branch, ends the run.
        for at, kind in obstacles:
            if at <= pos <= at + WIDTH[kind] and ((kind != "branch" and air == 0) or (kind == "branch" and duck == 0)):
                return round(at)
        ahead = [o for o in obstacles if o[0] > pos]
        nxt = ahead[0] if ahead else None
        seen = {"distance": round(nxt[0] - pos, 2) if nxt else None, "kind": nxt[1] if nxt else None,
                "width": WIDTH[nxt[1]] if nxt else None, "speed": round(speed, 3)}
        if air == 0 and duck == 0:
            action = policy(seen)
            if action == "jump":
                air = JUMP_STEPS
            elif action == "duck":
                duck = DUCK_STEPS
        new_pos = pos + speed
        for at, kind in obstacles:
            if pos < at + WIDTH[kind] and new_pos >= at:
                safe = air > 0 if kind != "branch" else (duck > 0 and air == 0)
                if not safe:
                    return round(max(at, pos))
        pos = new_pos
        air, duck = max(0, air - 1), max(0, duck - 1)
    return LENGTH


def score(policy, seeds=range(1, 21)):
    """The average distance over many courses: 1000 means it finished every one."""
    return sum(run_course(policy, s) for s in seeds) / len(seeds)


def policy(seen):
    return "run"  # your code: look at seen and decide


print("courses 1-20:", score(policy))
print("courses 21-40:", score(policy, range(21, 41)))