"""Agent Arena game engines (Strategy Games league). Deterministic, standard library only. No stakes, no money: a rating only.
Tic-tac-toe: cells 1-9 (row-major). Connect Four: 6 rows x 7 columns, columns 1-7, pieces drop to the lowest empty row.
Used by leagues/rounds.py (sealed puzzle key) and scripts/games_ladder.py (house-bot Elo ladder)."""
from functools import lru_cache
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 ttt_winner(b):
    for a, c, d in LINES:
        if b[a] != "." and b[a] == b[c] == b[d]: return b[a]
    return "D" if "." not in b else None
def ttt_turn(b): return "X" if b.count("X") == b.count("O") else "O"
@lru_cache(None)
def ttt_value(b):
    """Value for the side to move under perfect play: 0 draw, +(1+empty cells left) win, negative loss."""
    w = ttt_winner(b)
    if w == "D": return 0
    if w: return -(1 + b.count("."))   # previous mover won; quicker wins score higher
    p = ttt_turn(b); best = -99
    for i in range(9):
        if b[i] == ".": best = max(best, -ttt_value(b[:i] + p + b[i+1:]))
    return best
def ttt_best_moves(b):
    p = ttt_turn(b); sc = {i+1: -ttt_value(b[:i] + p + b[i+1:]) for i in range(9) if b[i] == "."}
    m = max(sc.values()); return sorted(k for k, v in sc.items() if v == m), m
R, C = 6, 7
def c4_empty(): return tuple(tuple("." for _ in range(C)) for _ in range(R))
def c4_drop(b, col, p):
    for r in range(R-1, -1, -1):
        if b[r][col] == ".":
            rows = [list(x) for x in b]; rows[r][col] = p; return tuple(tuple(x) for x in rows)
    return None
def c4_legal(b): return [c for c in range(C) if b[0][c] == "."]
def c4_winner(b):
    for r in range(R):
        for c in range(C):
            p = b[r][c]
            if p == ".": continue
            for dr, dc in ((0,1),(1,0),(1,1),(1,-1)):
                if all(0 <= r+k*dr < R and 0 <= c+k*dc < C and b[r+k*dr][c+k*dc] == p for k in range(4)): return p
    return "D" if not c4_legal(b) else None
def c4_text(b): return "\n".join("".join(r) for r in b)
def c4_wins_now(b, p): return [c for c in c4_legal(b) if c4_winner(c4_drop(b, c, p)) == p]
def c4_eval(b, p):
    o = "O" if p == "X" else "X"; s = 0
    for r in range(R):
        for c in range(C):
            for dr, dc in ((0,1),(1,0),(1,1),(1,-1)):
                cells = [(r+k*dr, c+k*dc) for k in range(4)]
                if not all(0 <= x < R and 0 <= y < C for x, y in cells): continue
                v = [b[x][y] for x, y in cells]
                if o not in v: s += (0, 1, 4, 16, 0)[v.count(p)]
                if p not in v: s -= (0, 1, 4, 16, 0)[v.count(o)]
    return s + sum(3 for r in range(R) if b[r][3] == p) - sum(3 for r in range(R) if b[r][3] == o)
def c4_negamax(b, p, depth, a=-10**9, beta=10**9):
    w = c4_winner(b); o = "O" if p == "X" else "X"
    if w == "D": return 0
    if w: return -100000 - depth   # previous mover won
    if depth == 0: return c4_eval(b, p)
    best = -10**9
    for c in sorted(c4_legal(b), key=lambda c: abs(c-3)):
        v = -c4_negamax(c4_drop(b, c, p), o, depth-1, -beta, -a); best = max(best, v); a = max(a, v)
        if a >= beta: break
    return best