Reversi move simulation with captures in 8 directions

A move in Reversi is legal when the new piece brackets at least one straight
run of opponent pieces: walking from (row, col) in one of the 8 compass
directions you see one or more opponent pieces and then a piece of your own,
with no empty cell or board edge in between. Every bracketed run in every
direction flips, not only the first one found.

Brute force. For every direction, copy the board, walk and flip
speculatively, and throw the copy away if the walk ends badly. It is correct
but copies the board up to 8 times per move, which is O(8·n²) for one move.

Optimal. Scan first, flip second:

1. If the cell is out of bounds or not empty, the move is illegal.
2. For each of the 8 directions (dr, dc), step from the neighbour and
   collect coordinates while the cell holds the opponent's colour.
3. The run counts only if it is non-empty and the walk stops on a
   player piece that is still on the board. Hitting . or the edge
   discards the run.
4. If no run counts, the move is illegal and the board is returned
   unchanged. Otherwise place the piece and flip every collected cell.

Invariants that keep it correct:

• Directions are independent. The 8 rays from one cell share no cells, so a
  run in one direction never depends on another. Scanning the original board
  before any write makes that obvious and lets one function serve both
  "is this legal?" and "apply this move".
• Only opponent pieces strictly between the new piece and the closing piece
  change. The closing piece and everything past it stay.
• An illegal move has no side effects. We return a copy so the caller's
  board is never mutated; say this out loud and ask whether in-place is
  preferred.

from typing import List, Tuple

Board = List[List[str]]

DIRECTIONS: Tuple[Tuple[int, int], ...] = (
    (-1, -1), (-1, 0), (-1, 1),
    (0, -1),           (0, 1),
    (1, -1),  (1, 0),  (1, 1),
)


def opponent(player: str) -> str:
    if player not in ("B", "W"):
        raise ValueError(f"player must be 'B' or 'W', got {player!r}")
    return "W" if player == "B" else "B"


def captures(board: Board, row: int, col: int, player: str) -> List[Tuple[int, int]]:
    """Cells that would flip if `player` moved at (row, col). Empty list = illegal."""
    n = len(board)
    if not (0 <= row < n and 0 <= col < len(board[row])) or board[row][col] != ".":
        return []
    other = opponent(player)
    flipped: List[Tuple[int, int]] = []
    for dr, dc in DIRECTIONS:
        r, c = row + dr, col + dc
        run: List[Tuple[int, int]] = []
        while 0 <= r < n and 0 <= c < len(board[r]) and board[r][c] == other:
            run.append((r, c))
            r, c = r + dr, c + dc
        closed = 0 <= r < n and 0 <= c < len(board[r]) and board[r][c] == player
        if run and closed:
            flipped.extend(run)
    return flipped


def make_move(board: Board, row: int, col: int, player: str) -> Board:
    """Return the board after `player` tries to move at (row, col).

    An illegal move (occupied cell, off the board, or nothing captured)
    returns an unchanged copy. The input board is never mutated.
    """
    result = [list(line) for line in board]
    to_flip = captures(board, row, col, player)
    if not to_flip:
        return result
    result[row][col] = player
    for r, c in to_flip:
        result[r][c] = player
    return result


def legal_moves(board: Board, player: str) -> List[Tuple[int, int]]:
    """Follow-up helper: every cell where `player` may legally move."""
    return [
        (r, c)
        for r in range(len(board))
        for c in range(len(board[r]))
        if captures(board, r, c, player)
    ]


if __name__ == "__main__":
    def parse(rows: List[str]) -> Board:
        return [list(r) for r in rows]

    start = parse([
        "........",
        "........",
        "........",
        "...WB...",
        "...BW...",
        "........",
        "........",
        "........",
    ])
    after = make_move(start, 2, 3, "B")
    assert after[2][3] == "B" and after[3][3] == "B"
    assert start[2][3] == "."  # input untouched
    assert sorted(legal_moves(start, "B")) == [(2, 3), (3, 2), (4, 5), (5, 4)]
    assert make_move(start, 0, 0, "B") == start  # nothing captured
    assert make_move(start, 3, 3, "B") == start  # occupied

    multi = parse([
        ".WWB",
        "WW..",
        "B.B.",
        "....",
    ])
    # Right, down and the diagonal all close on B; all three runs flip.
    assert make_move(multi, 0, 0, "B") == parse(["BBBB", "BB..", "B.B.", "...."])

    open_end = parse([".WW", "...", "..."])
    assert make_move(open_end, 0, 0, "B") == open_end  # run hits the edge
    assert make_move(parse(["BWWWWW."]), 0, 6, "B") == parse(["BBBBBBB"])
    assert make_move(parse(["."]), 0, 0, "W") == parse(["."])
    print("ok")

• captures / make_move: O(n) time per direction in the worst case, so
  O(8n) = O(n) to scan, plus O(n²) to copy the board for the returned value.
  If the caller allows in-place mutation the move itself is O(n) time.
• Space: O(n²) for the returned copy, O(n) for the list of cells to flip.
• legal_moves: O(n²) cells × O(n) scan = O(n³) time, O(n) extra space.

• Standard opening, B at (2, 3): places B at (2, 3), flips (3, 3)
  from W to B; nothing else changes.
• Standard opening, legal moves for B: (2, 3), (3, 2), (4, 5),
  (5, 4).
• Move on an occupied cell: board returned unchanged.
• Move that touches opponent pieces but is not closed (run ends at . or
  the board edge): unchanged.
• Move adjacent only to the player's own pieces: unchanged (a run of length
  zero does not count).
• Board .WWB / WW.. / B.B. / ...., B at (0, 0): the run to the right
  closes on (0, 3), the run down closes on (2, 0), the diagonal closes on
  (2, 2). Result BBBB / BB.. / B.B. / .....
• Board .W. / ... / ..., B at (0, 0): the run hits ., so the board
  is unchanged.
• Long run: row B W W W W W ., B at the last cell flips all five W.
• 1 x 1 board .: any move is illegal.
• Invalid player (for example 'X'): raise ValueError.

1. List every legal move / does the player have to pass? Call captures
   on each empty cell (shown as legal_moves). A player with no legal move
   passes; the game ends when both must pass. Optimise by only checking
   empty cells adjacent to an opponent piece.
2. Play a full game from a move list. Keep a Game class with the board,
   the side to move and piece counts. Apply each move, update counts by
   1 + len(flipped) for the mover and -len(flipped) for the opponent,
   handle passes, and report the winner when neither side can move.
3. Greedy AI: pick the move that flips the most pieces. Score each legal
   move by len(captures(...)), break ties by position (corners first).
   A stronger answer mentions minimax with alpha-beta and a positional weight
   table, since greedy flipping is a weak strategy.
4. Undo. Return the flipped list from each move and push
   (row, col, flipped) on a stack. Undo clears the placed cell and flips the
   list back to the opponent. O(flips) per undo, no board copies.
5. Very large or sparse boards. Store pieces in a dict keyed by
   (r, c); the scan is unchanged because it only walks until it leaves a
   run. Bitboards (one 64-bit mask per colour with shift-and-mask per
   direction) make 8x8 move generation a few dozen bit operations.

Mid-level (L4)

• Gets the 8-direction scan right, including the rule that the run must be
  non-empty and closed by the player's own piece.
• Handles occupied cells, edges and the "no capture" case without crashing.
• Writes a few hand-traced tests and states O(n) per move.

Senior (L5)

• Separates "find captures" from "apply move", so legality checks, listing
  moves and undo all reuse one function.
• Asks whether to mutate in place and what to return for an illegal move,
  and explains why scanning before writing keeps directions independent.
• Extends cleanly to legal-move listing, passing and full-game simulation.

Staff (L6+)

• Designs the game state (board, turn, counts, history) so undo and AI
  search are cheap, and discusses copy versus in-place trade-offs for search.
• Mentions bitboards or incremental frontier tracking for speed, and minimax
  with alpha-beta for the AI follow-up.
• Drives the conversation on edge rules (passes, game end, invalid input)
  and on how they would test the engine (property tests: piece count
  conservation, no flips on illegal moves).