Design Tic-Tac-Toe (N×N, K in a row).

# tictactoe.py, part 1: marks, moves, the board and the win-checker interface
from __future__ import annotations

import threading
from abc import ABC, abstractmethod
from dataclasses import dataclass
from enum import Enum


class Mark(Enum):
    X = "X"
    O = "O"


class Status(Enum):
    IN_PROGRESS = 1
    WON = 2
    DRAW = 3


@dataclass(frozen=True)
class Move:  # a mark placed on a cell: also the entry on the undo stack
    row: int
    col: int
    mark: Mark


class Board:  # only cells: no rules about winning live here
    def __init__(self, n: int) -> None:
        self.n = n
        self.cells: list[list[Mark | None]] = [[None] * n for _ in range(n)]
        self.filled = 0

    def in_bounds(self, r: int, c: int) -> bool:
        return 0 <= r < self.n and 0 <= c < self.n

    def get(self, r: int, c: int) -> Mark | None:
        return self.cells[r][c] if self.in_bounds(r, c) else None

    def place(self, move: Move) -> None:
        if not self.in_bounds(move.row, move.col):
            raise ValueError("off the board")
        if self.cells[move.row][move.col] is not None:
            raise ValueError("cell taken")
        self.cells[move.row][move.col] = move.mark
        self.filled += 1

    def remove(self, move: Move) -> None:
        self.cells[move.row][move.col] = None
        self.filled -= 1

    def is_full(self) -> bool:
        return self.filled == self.n * self.n

    def empty_cells(self) -> list[tuple[int, int]]:
        return [(r, c) for r in range(self.n) for c in range(self.n) if self.cells[r][c] is None]

    def render(self) -> str:
        return "\n".join(" ".join(m.value if m else "." for m in row) for row in self.cells)


class WinChecker(ABC):  # "does this move win?", answered without scanning the board
    @abstractmethod
    def record(self, move: Move) -> bool:
        """Called after the move is on the board. True if it completes K in a row."""

    @abstractmethod
    def forget(self, move: Move) -> None:
        """Called after the move left the board. Reverses record()."""

// TicTacToeDemo.java: an N x N board, K in a row, pluggable players, cheap win checks and undo
import java.util.ArrayList;
import java.util.List;
import java.util.concurrent.locks.ReentrantLock;

enum Mark {
    X, O;

    Mark other() { return this == X ? O : X; }
}

enum Status { IN_PROGRESS, WON, DRAW }

record Move(int row, int col, Mark mark) {} // a mark placed on a cell: also the entry on the undo stack

class Board { // only cells: no rules about winning live here
    final int n;
    private final Mark[][] cells;
    private int filled = 0;

    Board(int n) {
        this.n = n;
        this.cells = new Mark[n][n];
    }

    boolean inBounds(int r, int c) { return r >= 0 && r < n && c >= 0 && c < n; }

    Mark get(int r, int c) { return inBounds(r, c) ? cells[r][c] : null; }

    void place(Move m) {
        if (!inBounds(m.row(), m.col())) throw new IllegalArgumentException("off the board");
        if (cells[m.row()][m.col()] != null) throw new IllegalArgumentException("cell taken");
        cells[m.row()][m.col()] = m.mark();
        filled++;
    }

    void remove(Move m) {
        cells[m.row()][m.col()] = null;
        filled--;
    }

    boolean isFull() { return filled == n * n; }

    List<int[]> emptyCells() {
        List<int[]> out = new ArrayList<>();
        for (int r = 0; r < n; r++)
            for (int c = 0; c < n; c++)
                if (cells[r][c] == null) out.add(new int[] {r, c});
        return out;
    }

    String render() {
        StringBuilder sb = new StringBuilder();
        for (int r = 0; r < n; r++) {
            if (r > 0) sb.append("\n");
            for (int c = 0; c < n; c++) {
                if (c > 0) sb.append(" ");
                sb.append(cells[r][c] == null ? "." : cells[r][c].name());
            }
        }
        return sb.toString();
    }
}

interface WinChecker { // "does this move win?", answered without scanning the board
    boolean record(Move m); // called after the move is on the board; true if it completes K in a row

    void forget(Move m); // called after the move left the board; reverses record()
}

// tictactoe.cpp: an N x N board, K in a row, pluggable players, cheap win checks and undo
#include <algorithm>
#include <array>
#include <cstdlib>
#include <iostream>
#include <memory>
#include <mutex>
#include <stdexcept>
#include <string>
#include <utility>
#include <vector>

enum class Mark { X = 0, O = 1 };

Mark other(Mark m) { return m == Mark::X ? Mark::O : Mark::X; }

char symbol(Mark m) { return m == Mark::X ? 'X' : 'O'; }

enum class Status { InProgress, Won, Draw };

struct Move {  // a mark placed on a cell: also the entry on the undo stack
    int row;
    int col;
    Mark mark;
};

class Board {  // only cells: no rules about winning live here
public:
    const int n;

    explicit Board(int size) : n(size), cells(size, std::string(size, '.')) {}

    bool inBounds(int r, int c) const { return r >= 0 && r < n && c >= 0 && c < n; }

    char get(int r, int c) const { return inBounds(r, c) ? cells[r][c] : '.'; }

    void place(const Move& m) {
        if (!inBounds(m.row, m.col)) throw std::invalid_argument("off the board");
        if (cells[m.row][m.col] != '.') throw std::invalid_argument("cell taken");
        cells[m.row][m.col] = symbol(m.mark);
        filled++;
    }

    void remove(const Move& m) {
        cells[m.row][m.col] = '.';
        filled--;
    }

    bool isFull() const { return filled == n * n; }

    std::vector<std::pair<int, int>> emptyCells() const {
        std::vector<std::pair<int, int>> out;
        for (int r = 0; r < n; r++)
            for (int c = 0; c < n; c++)
                if (cells[r][c] == '.') out.push_back({r, c});
        return out;
    }

    std::string render() const {
        std::string out;
        for (int r = 0; r < n; r++) {
            if (r > 0) out += "\n";
            for (int c = 0; c < n; c++) {
                if (c > 0) out += " ";
                out += cells[r][c];
            }
        }
        return out;
    }

private:
    std::vector<std::string> cells;
    int filled = 0;
};

class WinChecker {  // "does this move win?", answered without scanning the board
public:
    virtual ~WinChecker() = default;
    virtual bool record(const Move& m) = 0;  // called after the move is on the board; true if it completes K in a row
    virtual void forget(const Move& m) = 0;  // called after the move left the board; reverses record()
};

// tictactoe.js: an N x N board, K in a row, pluggable players, cheap win checks and undo
const Mark = Object.freeze({ X: "X", O: "O" });
const otherMark = (m) => (m === Mark.X ? Mark.O : Mark.X);
const Status = Object.freeze({ IN_PROGRESS: "IN_PROGRESS", WON: "WON", DRAW: "DRAW" });

// a mark placed on a cell: also the entry on the undo stack
const move = (row, col, mark) => Object.freeze({ row, col, mark });

class Board {
  // only cells: no rules about winning live here
  constructor(n) {
    this.n = n;
    this.cells = Array.from({ length: n }, () => Array(n).fill(null));
    this.filled = 0;
  }

  inBounds(r, c) {
    return r >= 0 && r < this.n && c >= 0 && c < this.n;
  }

  get(r, c) {
    return this.inBounds(r, c) ? this.cells[r][c] : null;
  }

  place(m) {
    if (!this.inBounds(m.row, m.col)) throw new RangeError("off the board");
    if (this.cells[m.row][m.col] !== null) throw new RangeError("cell taken");
    this.cells[m.row][m.col] = m.mark;
    this.filled++;
  }

  remove(m) {
    this.cells[m.row][m.col] = null;
    this.filled--;
  }

  isFull() {
    return this.filled === this.n * this.n;
  }

  emptyCells() {
    const out = [];
    for (let r = 0; r < this.n; r++) for (let c = 0; c < this.n; c++) if (this.cells[r][c] === null) out.push([r, c]);
    return out;
  }

  render() {
    return this.cells.map((row) => row.map((m) => m ?? ".").join(" ")).join("\n");
  }
}

// WinChecker: record(move) -> true if it completes K in a row (called after the move is on the board);
// forget(move) reverses record() (called after the move left the board). No scan of the board in either.

# part 2: two ways to answer "did this move win?"
class CounterChecker(WinChecker):  # K == N: one counter per line and mark, so a move is O(1)
    def __init__(self, n: int) -> None:
        self.n = n
        self.rows = {m: [0] * n for m in Mark}
        self.cols = {m: [0] * n for m in Mark}
        self.diag = {m: 0 for m in Mark}  # cells where row == col
        self.anti = {m: 0 for m in Mark}  # cells where row + col == n - 1

    def _bump(self, move: Move, d: int) -> None:
        r, c, m = move.row, move.col, move.mark
        self.rows[m][r] += d
        self.cols[m][c] += d
        if r == c:
            self.diag[m] += d
        if r + c == self.n - 1:
            self.anti[m] += d

    def record(self, move: Move) -> bool:
        self._bump(move, 1)
        r, c, m = move.row, move.col, move.mark
        return (
            self.rows[m][r] == self.n
            or self.cols[m][c] == self.n
            or (r == c and self.diag[m] == self.n)
            or (r + c == self.n - 1 and self.anti[m] == self.n)
        )

    def forget(self, move: Move) -> None:
        self._bump(move, -1)


class RunChecker(WinChecker):  # any K: walk out from the move along four axes, O(K) and independent of N
    AXES = ((0, 1), (1, 0), (1, 1), (1, -1))

    def __init__(self, board: Board, k: int) -> None:
        self.board, self.k = board, k

    def _count(self, move: Move, dr: int, dc: int) -> int:
        n, r, c = 0, move.row + dr, move.col + dc
        while n < self.k - 1 and self.board.get(r, c) == move.mark:
            n, r, c = n + 1, r + dr, c + dc
        return n

    def record(self, move: Move) -> bool:
        return any(1 + self._count(move, dr, dc) + self._count(move, -dr, -dc) >= self.k for dr, dc in self.AXES)

    def forget(self, move: Move) -> None:
        pass  # stateless: it reads the board, so undoing the move is enough


def default_checker(board: Board, k: int) -> WinChecker:
    return CounterChecker(board.n) if k == board.n else RunChecker(board, k)

// part 2: two ways to answer "did this move win?"
class CounterChecker implements WinChecker { // K == N: one counter per line and mark, so a move is O(1)
    private final int n;
    private final int[][] rows, cols; // [mark ordinal][index]
    private final int[] diag = new int[2], anti = new int[2]; // diag: row == col; anti: row + col == n - 1

    CounterChecker(int n) {
        this.n = n;
        this.rows = new int[2][n];
        this.cols = new int[2][n];
    }

    private void bump(Move m, int d) {
        int k = m.mark().ordinal();
        rows[k][m.row()] += d;
        cols[k][m.col()] += d;
        if (m.row() == m.col()) diag[k] += d;
        if (m.row() + m.col() == n - 1) anti[k] += d;
    }

    public boolean record(Move m) {
        bump(m, 1);
        int k = m.mark().ordinal();
        return rows[k][m.row()] == n
                || cols[k][m.col()] == n
                || (m.row() == m.col() && diag[k] == n)
                || (m.row() + m.col() == n - 1 && anti[k] == n);
    }

    public void forget(Move m) { bump(m, -1); }
}

class RunChecker implements WinChecker { // any K: walk out from the move along four axes, O(K) and independent of N
    private static final int[][] AXES = {{0, 1}, {1, 0}, {1, 1}, {1, -1}};
    private final Board board;
    private final int k;

    RunChecker(Board board, int k) {
        this.board = board;
        this.k = k;
    }

    private int count(Move m, int dr, int dc) {
        int n = 0, r = m.row() + dr, c = m.col() + dc;
        while (n < k - 1 && board.get(r, c) == m.mark()) {
            n++;
            r += dr;
            c += dc;
        }
        return n;
    }

    public boolean record(Move m) {
        for (int[] a : AXES)
            if (1 + count(m, a[0], a[1]) + count(m, -a[0], -a[1]) >= k) return true;
        return false;
    }

    public void forget(Move m) {} // stateless: it reads the board, so undoing the move is enough
}

class Checkers {
    static WinChecker defaultChecker(Board board, int k) {
        return k == board.n ? new CounterChecker(board.n) : new RunChecker(board, k);
    }
}

// part 2: two ways to answer "did this move win?"
class CounterChecker : public WinChecker {  // K == N: one counter per line and mark, so a move is O(1)
public:
    explicit CounterChecker(int size) : n(size) {
        for (int k = 0; k < 2; k++) {
            rows[k].assign(size, 0);
            cols[k].assign(size, 0);
        }
    }

    bool record(const Move& m) override {
        bump(m, 1);
        int k = static_cast<int>(m.mark);
        return rows[k][m.row] == n || cols[k][m.col] == n || (m.row == m.col && diag[k] == n) ||
               (m.row + m.col == n - 1 && anti[k] == n);
    }

    void forget(const Move& m) override { bump(m, -1); }

private:
    int n;
    std::array<std::vector<int>, 2> rows, cols;  // [mark][index]
    std::array<int, 2> diag{}, anti{};           // diag: row == col; anti: row + col == n - 1

    void bump(const Move& m, int d) {
        int k = static_cast<int>(m.mark);
        rows[k][m.row] += d;
        cols[k][m.col] += d;
        if (m.row == m.col) diag[k] += d;
        if (m.row + m.col == n - 1) anti[k] += d;
    }
};

class RunChecker : public WinChecker {  // any K: walk out from the move along four axes, O(K) and independent of N
public:
    RunChecker(const Board& b, int kk) : board(b), k(kk) {}

    bool record(const Move& m) override {
        static const int axes[4][2] = {{0, 1}, {1, 0}, {1, 1}, {1, -1}};
        for (const auto& a : axes)
            if (1 + count(m, a[0], a[1]) + count(m, -a[0], -a[1]) >= k) return true;
        return false;
    }

    void forget(const Move&) override {}  // stateless: it reads the board, so undoing the move is enough

private:
    const Board& board;
    int k;

    int count(const Move& m, int dr, int dc) const {
        int n = 0, r = m.row + dr, c = m.col + dc;
        while (n < k - 1 && board.get(r, c) == symbol(m.mark)) {
            n++;
            r += dr;
            c += dc;
        }
        return n;
    }
};

std::unique_ptr<WinChecker> defaultChecker(const Board& board, int k) {
    if (k == board.n) return std::make_unique<CounterChecker>(board.n);
    return std::make_unique<RunChecker>(board, k);
}

// part 2: two ways to answer "did this move win?"
class CounterChecker {
  // K === N: one counter per line and mark, so a move is O(1)
  constructor(n) {
    this.n = n;
    const per = () => ({ [Mark.X]: Array(n).fill(0), [Mark.O]: Array(n).fill(0) });
    this.rows = per();
    this.cols = per();
    this.diag = { [Mark.X]: 0, [Mark.O]: 0 }; // cells where row === col
    this.anti = { [Mark.X]: 0, [Mark.O]: 0 }; // cells where row + col === n - 1
  }

  bump(m, d) {
    this.rows[m.mark][m.row] += d;
    this.cols[m.mark][m.col] += d;
    if (m.row === m.col) this.diag[m.mark] += d;
    if (m.row + m.col === this.n - 1) this.anti[m.mark] += d;
  }

  record(m) {
    this.bump(m, 1);
    const n = this.n;
    return (
      this.rows[m.mark][m.row] === n ||
      this.cols[m.mark][m.col] === n ||
      (m.row === m.col && this.diag[m.mark] === n) ||
      (m.row + m.col === n - 1 && this.anti[m.mark] === n)
    );
  }

  forget(m) {
    this.bump(m, -1);
  }
}

class RunChecker {
  // any K: walk out from the move along four axes, O(K) and independent of N
  static AXES = [[0, 1], [1, 0], [1, 1], [1, -1]];

  constructor(board, k) {
    this.board = board;
    this.k = k;
  }

  count(m, dr, dc) {
    let n = 0, r = m.row + dr, c = m.col + dc;
    while (n < this.k - 1 && this.board.get(r, c) === m.mark) {
      n++;
      r += dr;
      c += dc;
    }
    return n;
  }

  record(m) {
    return RunChecker.AXES.some(([dr, dc]) => 1 + this.count(m, dr, dc) + this.count(m, -dr, -dc) >= this.k);
  }

  forget() {} // stateless: it reads the board, so undoing the move is enough
}

const defaultChecker = (board, k) => (k === board.n ? new CounterChecker(board.n) : new RunChecker(board, k));

# part 3: players are strategies; the greedy one uses place/undo to look one move ahead
class Player(ABC):
    def __init__(self, name: str, mark: Mark) -> None:
        self.name, self.mark = name, mark

    @abstractmethod
    def choose(self, game: "Game") -> tuple[int, int]:
        """The cell this player wants next."""


class ScriptedPlayer(Player):  # replays a fixed list of cells: for tests and demos
    def __init__(self, name: str, mark: Mark, cells: list[tuple[int, int]]) -> None:
        super().__init__(name, mark)
        self._cells = iter(cells)

    def choose(self, game: "Game") -> tuple[int, int]:
        return next(self._cells)


class GreedyPlayer(Player):  # win if you can, block if you must, else the free cell nearest the centre
    def choose(self, game: "Game") -> tuple[int, int]:
        n = game.board.n
        cells = game.board.empty_cells()
        for mark in (self.mark, game.other(self.mark)):
            for r, c in cells:
                if game.would_win(r, c, mark):
                    return r, c
        return min(cells, key=lambda rc: (abs(2 * rc[0] - (n - 1)) + abs(2 * rc[1] - (n - 1)), rc[0], rc[1]))

// part 3: players are strategies; the greedy one uses place/undo to look one move ahead
interface Player {
    String name();

    Mark mark();

    int[] choose(Game game); // the cell this player wants next: {row, col}
}

class ScriptedPlayer implements Player { // replays a fixed list of cells: for tests and demos
    private final String name;
    private final Mark mark;
    private final List<int[]> cells;
    private int next = 0;

    ScriptedPlayer(String name, Mark mark, List<int[]> cells) {
        this.name = name;
        this.mark = mark;
        this.cells = cells;
    }

    public String name() { return name; }

    public Mark mark() { return mark; }

    public int[] choose(Game game) { return cells.get(next++); }
}

class GreedyPlayer implements Player { // win if you can, block if you must, else the free cell nearest the centre
    private final String name;
    private final Mark mark;

    GreedyPlayer(String name, Mark mark) {
        this.name = name;
        this.mark = mark;
    }

    public String name() { return name; }

    public Mark mark() { return mark; }

    public int[] choose(Game game) {
        int n = game.board.n;
        List<int[]> cells = game.board.emptyCells();
        for (Mark m : new Mark[] {mark, mark.other()})
            for (int[] rc : cells)
                if (game.wouldWin(rc[0], rc[1], m)) return rc;
        int[] best = null;
        int bestDist = Integer.MAX_VALUE;
        for (int[] rc : cells) { // cells come in row-major order, so the first of equals wins
            int dist = Math.abs(2 * rc[0] - (n - 1)) + Math.abs(2 * rc[1] - (n - 1));
            if (dist < bestDist) {
                bestDist = dist;
                best = rc;
            }
        }
        return best;
    }
}

// part 3: players are strategies; the greedy one uses place/undo to look one move ahead
class Game;

class Player {
public:
    Player(std::string n, Mark m) : name(std::move(n)), mark(m) {}
    virtual ~Player() = default;
    virtual std::pair<int, int> choose(Game& game) = 0;  // the cell this player wants next
    std::string name;
    Mark mark;
};

class ScriptedPlayer : public Player {  // replays a fixed list of cells: for tests and demos
public:
    ScriptedPlayer(std::string n, Mark m, std::vector<std::pair<int, int>> c) : Player(std::move(n), m), cells(std::move(c)) {}

    std::pair<int, int> choose(Game&) override { return cells.at(next++); }

private:
    std::vector<std::pair<int, int>> cells;
    size_t next = 0;
};

class GreedyPlayer : public Player {  // win if you can, block if you must, else the free cell nearest the centre
public:
    GreedyPlayer(std::string n, Mark m) : Player(std::move(n), m) {}

    std::pair<int, int> choose(Game& game) override;  // defined after Game
};

// part 3: players are strategies; the greedy one uses place/undo to look one move ahead
class ScriptedPlayer {
  // replays a fixed list of cells: for tests and demos
  constructor(name, mark, cells) {
    this.name = name;
    this.mark = mark;
    this.cells = cells;
    this.next = 0;
  }

  choose() {
    return this.cells[this.next++];
  }
}

class GreedyPlayer {
  // win if you can, block if you must, else the free cell nearest the centre
  constructor(name, mark) {
    this.name = name;
    this.mark = mark;
  }

  choose(game) {
    const n = game.board.n;
    const cells = game.board.emptyCells();
    for (const mark of [this.mark, otherMark(this.mark)])
      for (const [r, c] of cells) if (game.wouldWin(r, c, mark)) return [r, c];
    const dist = ([r, c]) => Math.abs(2 * r - (n - 1)) + Math.abs(2 * c - (n - 1));
    return cells.reduce((best, rc) => (dist(rc) < dist(best) ? rc : best)); // first of equals wins
  }
}

# part 4: the game: turns, history, status, undo
class Game:
    def __init__(self, n: int, k: int, players: list[Player], checker: WinChecker | None = None) -> None:
        if not 1 < k <= n:
            raise ValueError("K must be between 2 and N")
        if len(players) != 2 or players[0].mark == players[1].mark:
            raise ValueError("two players with different marks")
        self.board = Board(n)
        self.k = k
        self.checker = checker or default_checker(self.board, k)
        self.players = players
        self.turn = 0
        self.history: list[Move] = []
        self.status = Status.IN_PROGRESS
        self.winner: Player | None = None
        self._lock = threading.RLock()  # reentrant: a bot's choose() runs inside step() and calls would_win()

    @staticmethod
    def other(mark: Mark) -> Mark:
        return Mark.O if mark is Mark.X else Mark.X

    @property
    def current(self) -> Player:
        return self.players[self.turn]

    def play(self, row: int, col: int) -> Status:
        with self._lock:
            if self.status is not Status.IN_PROGRESS:
                raise RuntimeError("game over")
            move = Move(row, col, self.current.mark)
            self.board.place(move)  # raises on an off-board or taken cell, before anything changes
            self.history.append(move)
            if self.checker.record(move):
                self.status, self.winner = Status.WON, self.current
            elif self.board.is_full():
                self.status = Status.DRAW
            else:
                self.turn = 1 - self.turn
            return self.status

    def undo(self) -> None:
        with self._lock:
            if not self.history:
                raise RuntimeError("nothing to undo")
            move = self.history.pop()
            self.board.remove(move)
            self.checker.forget(move)
            self.status, self.winner = Status.IN_PROGRESS, None
            self.turn = 0 if self.players[0].mark is move.mark else 1

    def would_win(self, row: int, col: int, mark: Mark) -> bool:  # place, ask, take back: no board copy
        with self._lock:
            move = Move(row, col, mark)
            self.board.place(move)
            won = self.checker.record(move)
            self.board.remove(move)
            self.checker.forget(move)
            return won

    def step(self) -> Status:  # ask the current player for a cell and play it
        with self._lock:
            row, col = self.current.choose(self)
            return self.play(row, col)

// part 4: the game: turns, history, status, undo
class Game {
    final Board board;
    final WinChecker checker;
    final List<Player> players;
    final List<Move> history = new ArrayList<>();
    Status status = Status.IN_PROGRESS;
    Player winner = null;
    private int turn = 0;
    private final ReentrantLock lock = new ReentrantLock(); // reentrant: a bot's choose() runs inside step() and calls wouldWin()

    Game(int n, int k, List<Player> players, WinChecker checker) {
        if (k < 2 || k > n) throw new IllegalArgumentException("K must be between 2 and N");
        if (players.size() != 2 || players.get(0).mark() == players.get(1).mark())
            throw new IllegalArgumentException("two players with different marks");
        this.board = new Board(n);
        this.checker = checker != null ? checker : Checkers.defaultChecker(board, k);
        this.players = players;
    }

    Player current() { return players.get(turn); }

    Status play(int row, int col) {
        lock.lock();
        try {
            if (status != Status.IN_PROGRESS) throw new IllegalStateException("game over");
            Move move = new Move(row, col, current().mark());
            board.place(move); // throws on an off-board or taken cell, before anything changes
            history.add(move);
            if (checker.record(move)) {
                status = Status.WON;
                winner = current();
            } else if (board.isFull()) {
                status = Status.DRAW;
            } else {
                turn = 1 - turn;
            }
            return status;
        } finally {
            lock.unlock();
        }
    }

    void undo() {
        lock.lock();
        try {
            if (history.isEmpty()) throw new IllegalStateException("nothing to undo");
            Move move = history.remove(history.size() - 1);
            board.remove(move);
            checker.forget(move);
            status = Status.IN_PROGRESS;
            winner = null;
            turn = players.get(0).mark() == move.mark() ? 0 : 1;
        } finally {
            lock.unlock();
        }
    }

    boolean wouldWin(int row, int col, Mark mark) { // place, ask, take back: no board copy
        lock.lock();
        try {
            Move move = new Move(row, col, mark);
            board.place(move);
            boolean won = checker.record(move);
            board.remove(move);
            checker.forget(move);
            return won;
        } finally {
            lock.unlock();
        }
    }

    Status step() { // ask the current player for a cell and play it
        lock.lock();
        try {
            int[] cell = current().choose(this);
            return play(cell[0], cell[1]);
        } finally {
            lock.unlock();
        }
    }
}

// part 4: the game: turns, history, status, undo
class Game {
public:
    Board board;
    Status status = Status::InProgress;
    Player* winner = nullptr;

    Game(int n, int k, std::vector<std::shared_ptr<Player>> ps, std::unique_ptr<WinChecker> c = nullptr)
        : board(n), checker(c ? std::move(c) : defaultChecker(board, k)), players(std::move(ps)) {
        if (k < 2 || k > n) throw std::invalid_argument("K must be between 2 and N");
        if (players.size() != 2 || players[0]->mark == players[1]->mark)
            throw std::invalid_argument("two players with different marks");
    }

    Player& current() { return *players[turn]; }

    Status play(int row, int col) {
        std::lock_guard<std::recursive_mutex> g(lock);
        if (status != Status::InProgress) throw std::logic_error("game over");
        Move move{row, col, current().mark};
        board.place(move);  // throws on an off-board or taken cell, before anything changes
        history.push_back(move);
        if (checker->record(move)) {
            status = Status::Won;
            winner = &current();
        } else if (board.isFull()) {
            status = Status::Draw;
        } else {
            turn = 1 - turn;
        }
        return status;
    }

    void undo() {
        std::lock_guard<std::recursive_mutex> g(lock);
        if (history.empty()) throw std::logic_error("nothing to undo");
        Move move = history.back();
        history.pop_back();
        board.remove(move);
        checker->forget(move);
        status = Status::InProgress;
        winner = nullptr;
        turn = players[0]->mark == move.mark ? 0 : 1;
    }

    bool wouldWin(int row, int col, Mark mark) {  // place, ask, take back: no board copy
        std::lock_guard<std::recursive_mutex> g(lock);
        Move move{row, col, mark};
        board.place(move);
        bool won = checker->record(move);
        board.remove(move);
        checker->forget(move);
        return won;
    }

    Status step() {  // ask the current player for a cell and play it
        std::lock_guard<std::recursive_mutex> g(lock);
        auto [row, col] = current().choose(*this);
        return play(row, col);
    }

private:
    std::unique_ptr<WinChecker> checker;
    std::vector<std::shared_ptr<Player>> players;
    std::vector<Move> history;
    int turn = 0;
    std::recursive_mutex lock;  // reentrant: a bot's choose() runs inside step() and calls wouldWin()
};

std::pair<int, int> GreedyPlayer::choose(Game& game) {
    int n = game.board.n;
    auto cells = game.board.emptyCells();
    for (Mark m : {mark, other(mark)})
        for (auto [r, c] : cells)
            if (game.wouldWin(r, c, m)) return {r, c};
    std::pair<int, int> best = cells[0];
    int bestDist = 1 << 30;
    for (auto [r, c] : cells) {  // cells come in row-major order, so the first of equals wins
        int dist = std::abs(2 * r - (n - 1)) + std::abs(2 * c - (n - 1));
        if (dist < bestDist) {
            bestDist = dist;
            best = {r, c};
        }
    }
    return best;
}

// part 4: the game: turns, history, status, undo
class Game {
  // single-threaded in JavaScript, so no lock: play/undo/wouldWin never yield, and that is what the lock buys elsewhere
  constructor(n, k, players, checker = null) {
    if (!(k > 1 && k <= n)) throw new RangeError("K must be between 2 and N");
    if (players.length !== 2 || players[0].mark === players[1].mark) throw new RangeError("two players with different marks");
    this.board = new Board(n);
    this.k = k;
    this.checker = checker ?? defaultChecker(this.board, k);
    this.players = players;
    this.turn = 0;
    this.history = [];
    this.status = Status.IN_PROGRESS;
    this.winner = null;
  }

  get current() {
    return this.players[this.turn];
  }

  play(row, col) {
    if (this.status !== Status.IN_PROGRESS) throw new Error("game over");
    const m = move(row, col, this.current.mark);
    this.board.place(m); // throws on an off-board or taken cell, before anything changes
    this.history.push(m);
    if (this.checker.record(m)) {
      this.status = Status.WON;
      this.winner = this.current;
    } else if (this.board.isFull()) {
      this.status = Status.DRAW;
    } else {
      this.turn = 1 - this.turn;
    }
    return this.status;
  }

  undo() {
    if (this.history.length === 0) throw new Error("nothing to undo");
    const m = this.history.pop();
    this.board.remove(m);
    this.checker.forget(m);
    this.status = Status.IN_PROGRESS;
    this.winner = null;
    this.turn = this.players[0].mark === m.mark ? 0 : 1;
  }

  wouldWin(row, col, mark) {
    // place, ask, take back: no board copy
    const m = move(row, col, mark);
    this.board.place(m);
    const won = this.checker.record(m);
    this.board.remove(m);
    this.checker.forget(m);
    return won;
  }

  step() {
    // ask the current player for a cell and play it
    const [row, col] = this.current.choose(this);
    return this.play(row, col);
  }
}

# part 5: a scripted 3x3, an undo after a win, and a 5x5 (K = 4) between two bots
def report(game: Game) -> str:
    return f"{game.status.name}" + (f" ({game.winner.name})" if game.winner else "")


if __name__ == "__main__":
    ann = ScriptedPlayer("Ann", Mark.X, [(0, 0), (1, 1), (2, 2), (2, 2)])
    bob = ScriptedPlayer("Bob", Mark.O, [(0, 1), (0, 2)])
    g = Game(3, 3, [ann, bob])
    for _ in range(5):
        g.step()
    print("3x3:", report(g))
    print(g.board.render())
    g.undo()  # take back Ann's winning move
    print("after undo:", report(g), "| next:", g.current.name, "| (2,2) free:", g.board.get(2, 2) is None)
    g.step()  # Ann plays (2, 2) again and wins again
    print("replayed:", report(g))
    try:
        g.play(1, 0)
    except RuntimeError as e:
        print("rejected:", e)

    bots = Game(5, 4, [GreedyPlayer("Zed", Mark.X), GreedyPlayer("Yan", Mark.O)])
    while bots.status is Status.IN_PROGRESS:
        bots.step()
    print(f"5x5 K=4: {report(bots)} after {len(bots.history)} moves")
    print(bots.board.render())
    try:
        Game(3, 3, [GreedyPlayer("a", Mark.X), GreedyPlayer("b", Mark.O)]).play(3, 3)
    except ValueError as e:
        print("rejected:", e)

public class TicTacToeDemo {
    // a scripted 3x3, an undo after a win, and a 5x5 (K = 4) between two bots
    static String report(Game g) {
        return g.status.name() + (g.winner != null ? " (" + g.winner.name() + ")" : "");
    }

    public static void main(String[] args) {
        Player ann = new ScriptedPlayer("Ann", Mark.X, List.of(new int[] {0, 0}, new int[] {1, 1}, new int[] {2, 2}, new int[] {2, 2}));
        Player bob = new ScriptedPlayer("Bob", Mark.O, List.of(new int[] {0, 1}, new int[] {0, 2}));
        Game g = new Game(3, 3, List.of(ann, bob), null);
        for (int i = 0; i < 5; i++) g.step();
        System.out.println("3x3: " + report(g));
        System.out.println(g.board.render());
        g.undo(); // take back Ann's winning move
        System.out.println("after undo: " + report(g) + " | next: " + g.current().name() + " | (2,2) free: " + (g.board.get(2, 2) == null ? "True" : "False"));
        g.step(); // Ann plays (2, 2) again and wins again
        System.out.println("replayed: " + report(g));
        try {
            g.play(1, 0);
        } catch (IllegalStateException e) {
            System.out.println("rejected: " + e.getMessage());
        }

        Game bots = new Game(5, 4, List.of(new GreedyPlayer("Zed", Mark.X), new GreedyPlayer("Yan", Mark.O)), null);
        while (bots.status == Status.IN_PROGRESS) bots.step();
        System.out.println("5x5 K=4: " + report(bots) + " after " + bots.history.size() + " moves");
        System.out.println(bots.board.render());
        try {
            new Game(3, 3, List.of(new GreedyPlayer("a", Mark.X), new GreedyPlayer("b", Mark.O)), null).play(3, 3);
        } catch (IllegalArgumentException e) {
            System.out.println("rejected: " + e.getMessage());
        }
    }
}

// a scripted 3x3, an undo after a win, and a 5x5 (K = 4) between two bots
std::string report(Game& g) {
    std::string s = g.status == Status::InProgress ? "IN_PROGRESS" : g.status == Status::Won ? "WON" : "DRAW";
    return g.winner ? s + " (" + g.winner->name + ")" : s;
}

int main() {
    auto ann = std::make_shared<ScriptedPlayer>("Ann", Mark::X, std::vector<std::pair<int, int>>{{0, 0}, {1, 1}, {2, 2}, {2, 2}});
    auto bob = std::make_shared<ScriptedPlayer>("Bob", Mark::O, std::vector<std::pair<int, int>>{{0, 1}, {0, 2}});
    Game g(3, 3, {ann, bob});
    for (int i = 0; i < 5; i++) g.step();
    std::cout << "3x3: " << report(g) << "\n" << g.board.render() << "\n";
    g.undo();  // take back Ann's winning move
    std::cout << "after undo: " << report(g) << " | next: " << g.current().name
              << " | (2,2) free: " << (g.board.get(2, 2) == '.' ? "True" : "False") << "\n";
    g.step();  // Ann plays (2, 2) again and wins again
    std::cout << "replayed: " << report(g) << "\n";
    try {
        g.play(1, 0);
    } catch (const std::logic_error& e) {
        std::cout << "rejected: " << e.what() << "\n";
    }

    Game bots(5, 4, {std::make_shared<GreedyPlayer>("Zed", Mark::X), std::make_shared<GreedyPlayer>("Yan", Mark::O)});
    int moves = 0;
    while (bots.status == Status::InProgress) {
        bots.step();
        moves++;
    }
    std::cout << "5x5 K=4: " << report(bots) << " after " << moves << " moves\n" << bots.board.render() << "\n";
    try {
        Game bad(3, 3, {std::make_shared<GreedyPlayer>("a", Mark::X), std::make_shared<GreedyPlayer>("b", Mark::O)});
        bad.play(3, 3);
    } catch (const std::invalid_argument& e) {
        std::cout << "rejected: " << e.what() << "\n";
    }
}

// a scripted 3x3, an undo after a win, and a 5x5 (K = 4) between two bots
const report = (g) => g.status + (g.winner ? ` (${g.winner.name})` : "");

const ann = new ScriptedPlayer("Ann", Mark.X, [[0, 0], [1, 1], [2, 2], [2, 2]]);
const bob = new ScriptedPlayer("Bob", Mark.O, [[0, 1], [0, 2]]);
const g = new Game(3, 3, [ann, bob]);
for (let i = 0; i < 5; i++) g.step();
console.log("3x3:", report(g));
console.log(g.board.render());
g.undo(); // take back Ann's winning move
console.log("after undo:", report(g), "| next:", g.current.name, "| (2,2) free:", g.board.get(2, 2) === null ? "True" : "False");
g.step(); // Ann plays (2, 2) again and wins again
console.log("replayed:", report(g));
try {
  g.play(1, 0);
} catch (e) {
  console.log("rejected:", e.message);
}

const bots = new Game(5, 4, [new GreedyPlayer("Zed", Mark.X), new GreedyPlayer("Yan", Mark.O)]);
while (bots.status === Status.IN_PROGRESS) bots.step();
console.log(`5x5 K=4: ${report(bots)} after ${bots.history.length} moves`);
console.log(bots.board.render());
try {
  new Game(3, 3, [new GreedyPlayer("a", Mark.X), new GreedyPlayer("b", Mark.O)]).play(3, 3);
} catch (e) {
  if (!(e instanceof RangeError)) throw e;
  console.log("rejected:", e.message);
}

3x3: WON (Ann)
X O O
. X .
. . X
after undo: IN_PROGRESS | next: Ann | (2,2) free: True
replayed: WON (Ann)
rejected: game over
5x5 K=4: WON (Zed) after 13 moves
. O O . .
. X O O .
X X X O O
. X X . .
. X . . .
rejected: off the board