tukaunuandClaude Opus 5.5
c52f30dc59
Online play over WebSockets with any-string game codes, seats and spectators, and a 1-second heartbeat. Practice mode against Columbina, backed by a full solver, with an accuracy slider, spoilers, undo and piece freshness. Co-Authored-By: Claude Opus 5.5 <[email protected]>
111 lines
4.2 KiB
Python
111 lines
4.2 KiB
Python
"""Perfect play for vanishing tic-tac-toe.
|
|
|
|
Every position reachable from the empty board (~17k) is solved by retrograde analysis:
|
|
positions where the player to move can win immediately are wins, a position is a loss
|
|
once every move leads to an opponent win, and whatever is never resolved is a draw
|
|
(the players can keep cycling forever). Positions are (mine, theirs): the cells of the
|
|
player to move and of their opponent, each oldest first.
|
|
"""
|
|
|
|
import random
|
|
from collections import deque
|
|
|
|
from game import LINES, MAX_PIECES
|
|
|
|
WIN, LOSS, DRAW = "win", "loss", "draw"
|
|
|
|
|
|
def _wins(cells):
|
|
return any(all(i in cells for i in line) for line in LINES)
|
|
|
|
|
|
def _moves(mine, theirs):
|
|
"""(cell, next position) for each legal move; next position is None if the move wins.
|
|
The opponent's oldest piece goes as their turn starts if they have a full set."""
|
|
occupied = set(mine) | set(theirs)
|
|
remaining = theirs[1:] if len(theirs) == MAX_PIECES else theirs
|
|
for cell in range(9):
|
|
if cell in occupied:
|
|
continue
|
|
placed = mine + (cell,)
|
|
yield cell, (None if _wins(placed) else (remaining, placed))
|
|
|
|
|
|
class Solver:
|
|
def __init__(self):
|
|
self.value = {}
|
|
self.distance = {} # plies until the game ends with best play from both sides
|
|
self._solve()
|
|
|
|
def _solve(self):
|
|
start = ((), ())
|
|
succ, preds = {}, {}
|
|
queue = deque([start])
|
|
succ[start] = None
|
|
while queue:
|
|
pos = queue.popleft()
|
|
succ[pos] = list(_moves(*pos))
|
|
for _, nxt in succ[pos]:
|
|
if nxt is None:
|
|
continue
|
|
preds.setdefault(nxt, []).append(pos)
|
|
if nxt not in succ:
|
|
succ[nxt] = None
|
|
queue.append(nxt)
|
|
|
|
unresolved = {pos: sum(n is not None for _, n in moves) for pos, moves in succ.items()}
|
|
queue = deque()
|
|
for pos, moves in succ.items():
|
|
if any(n is None for _, n in moves):
|
|
self.value[pos], self.distance[pos] = WIN, 1
|
|
queue.append(pos)
|
|
while queue:
|
|
pos = queue.popleft()
|
|
for prev in preds.get(pos, ()):
|
|
if prev in self.value:
|
|
continue
|
|
if self.value[pos] == LOSS:
|
|
self.value[prev], self.distance[prev] = WIN, self.distance[pos] + 1
|
|
queue.append(prev)
|
|
else:
|
|
unresolved[prev] -= 1
|
|
if unresolved[prev] == 0:
|
|
self.value[prev] = LOSS
|
|
self.distance[prev] = 1 + max(self.distance[n] for _, n in succ[prev])
|
|
queue.append(prev)
|
|
for pos in succ:
|
|
self.value.setdefault(pos, DRAW)
|
|
|
|
def best_moves(self, mine, theirs):
|
|
"""All optimal cells: win fastest, else draw, else lose as slowly as possible.
|
|
Returns None for positions not reachable from the empty board."""
|
|
if (mine, theirs) not in self.value:
|
|
return None
|
|
scored = []
|
|
for cell, nxt in _moves(mine, theirs):
|
|
if nxt is None:
|
|
score = (3, 0)
|
|
elif self.value[nxt] == LOSS:
|
|
score = (2, -self.distance[nxt])
|
|
elif self.value[nxt] == DRAW:
|
|
score = (1, 0)
|
|
else:
|
|
score = (0, self.distance[nxt])
|
|
scored.append((score, cell))
|
|
best = max(score for score, _ in scored)
|
|
return [cell for score, cell in scored if score == best]
|
|
|
|
def choose(self, game, accuracy, rng=random):
|
|
"""Pick a move for the player to move: optimal with probability `accuracy`, else random.
|
|
|
|
Returns (cell, how): how is "perfect" if the roll chose an optimal move, "lucky" if
|
|
a random move happened to be optimal anyway, and "random" otherwise.
|
|
"""
|
|
mine = tuple(game.history[game.turn])
|
|
theirs = tuple(game.history[1 - game.turn])
|
|
best = self.best_moves(mine, theirs) or []
|
|
if best and rng.random() < accuracy:
|
|
return rng.choice(best), "perfect"
|
|
cell = rng.choice([c for c in range(9) if game.board[c] is None])
|
|
return cell, "lucky" if cell in best else "random"
|