Tic-tac-toe
It looks easy. That's the trap.

record Move(int playerIndex, int row, int col) {}
enum GameStatus { IN_PROGRESS, WON, DRAW }

class Board {
    private final int size; private final char[][] cells; private int filled;
    static final char EMPTY = '.';

    Board(int size) {
        this.size = size; cells = new char[size][size];
        for (char[] row : cells) Arrays.fill(row, EMPTY);
    }
    void place(int r, int c, char symbol) {
        if (r < 0 || c < 0 || r >= size || c >= size) throw new IllegalArgumentException("Out of bounds");
        if (cells[r][c] != EMPTY) throw new IllegalArgumentException("Cell occupied");
        cells[r][c] = symbol; filled++;
    }
    void clear(int r, int c) { cells[r][c] = EMPTY; filled--; }
    boolean isFull() { return filled == size * size; }
    int size() { return size; }
    char at(int r, int c) { return cells[r][c]; }
}

/** O(1) win detection: per player, count the marks in each row, column and both diagonals. */
class CounterWinningStrategy {
    private final int n;
    private final int[][] rows, cols;      // [player][index]
    private final int[] diag, anti;        // [player]

    CounterWinningStrategy(int n, int players) {
        this.n = n; rows = new int[players][n]; cols = new int[players][n];
        diag = new int[players]; anti = new int[players];
    }
    boolean recordAndCheck(Move m) { return update(m, +1); }
    void undo(Move m) { update(m, -1); }

    private boolean update(Move m, int delta) {
        int p = m.playerIndex(), r = m.row(), c = m.col();
        rows[p][r] += delta; cols[p][c] += delta;
        if (r == c) diag[p] += delta;
        if (r + c == n - 1) anti[p] += delta;
        return rows[p][r] == n || cols[p][c] == n || diag[p] == n || anti[p] == n;
    }
}

interface Player { String name(); char symbol(); int[] nextMove(Board board); }

record HumanPlayer(String name, char symbol, Scanner in) implements Player {
    public int[] nextMove(Board b) { return new int[]{in.nextInt(), in.nextInt()}; }
}

/** The bot is pluggable via a strategy: random, rule-based, or minimax for a 3x3 board. */
record BotPlayer(String name, char symbol, BotStrategy strategy) implements Player {
    public int[] nextMove(Board b) { return strategy.choose(b); }
}
interface BotStrategy { int[] choose(Board b); }

class Game {
    private final Board board; private final List<Player> players;
    private final CounterWinningStrategy winCheck;
    private final Deque<Move> history = new ArrayDeque<>();
    private int turn = 0; private GameStatus status = GameStatus.IN_PROGRESS; private Player winner;

    Game(int size, List<Player> players) {
        if (players.size() < 2) throw new IllegalArgumentException("Need at least 2 players");
        this.board = new Board(size); this.players = List.copyOf(players);
        this.winCheck = new CounterWinningStrategy(size, players.size());
    }

    /** Applies a move for the current player. */
    public GameStatus play(int row, int col) {
        if (status != GameStatus.IN_PROGRESS) throw new IllegalStateException("Game over: " + status);
        Player p = players.get(turn);
        board.place(row, col, p.symbol());                     // validates
        Move m = new Move(turn, row, col);
        history.push(m);
        if (winCheck.recordAndCheck(m)) { status = GameStatus.WON; winner = p; }
        else if (board.isFull()) status = GameStatus.DRAW;
        else turn = (turn + 1) % players.size();
        return status;
    }

    public void undo() {
        if (history.isEmpty()) throw new IllegalStateException("Nothing to undo");
        Move m = history.pop();
        board.clear(m.row(), m.col());
        winCheck.undo(m);
        status = GameStatus.IN_PROGRESS; winner = null;
        turn = m.playerIndex();
    }

    public void run() {                                        // a game loop for a CLI
        while (status == GameStatus.IN_PROGRESS) {
            Player p = players.get(turn);
            int[] mv = p.nextMove(board);
            try { play(mv[0], mv[1]); } catch (IllegalArgumentException e) { System.out.println(e.getMessage()); }
        }
        System.out.println(status == GameStatus.WON ? winner.name() + " wins" : "Draw");
    }
}