LLD 案例：国际象棋

国际象棋是规则最多的 LLD 题之一。面试官不指望你把每条规则都写完，而是看你怎么组织规则：每种棋子各自怎么走，“走完不能让自己的王被将”这类全局规则放在哪，悔棋需要记住什么。

需求澄清

功能需求

1. 两名玩家轮流走棋，白方先走。
2. 校验每一步是否合法，包括六种棋子的基本走法。
3. 判断将军、将死、逼和（无子可动但没被将军）。
4. 支持三种特殊走法：王车易位、吃过路兵、兵升变。
5. 支持悔棋、认输。

明确不做：AI 对手、棋钟、联网对战（放到扩展讨论）。

和面试官约定：先把基本走法和将死判断写完整，特殊走法讲清楚需要哪些状态，代码只写骨架。

核心类

classDiagram
  accTitle: 国际象棋类图：对局、棋盘、棋子与走法
  class Game {
    -Board board
    -Color turn
    -List history
    -CastlingRights rights
    -Square enPassant
    +legalMoves(Square from) List
    +play(Square from, Square to)
    +undo()
    +status() Status
  }
  class Board {
    -Piece[][] grid
    +at(Square sq) Piece
  }
  class Piece {
    -Color color
    -Kind kind
  }
  class Move {
    -Square from
    -Square to
    -Piece captured
    -Kind promotion
  }
  class Player {
    -String name
    -Color color
  }
  Game *-- Board
  Game "1" o-- "2" Player
  Game "1" *-- "many" Move : history
  Board o-- Piece

Piece 不需要“已经移动过”这类可变字段，这些信息属于对局状态，放在 Game 里（见下文的易位权）。

用到的设计模式

• 按棋子分派走法：车、象、后是“沿直线滑动直到被挡住”，马和王是“跳到固定的几个相对位置”，兵单独处理。不必为每种棋子写一个子类，一张方向表加一个是否滑动的标志就能覆盖五种棋子。如果面试官希望看到多态，也可以写成 MoveRule 策略接口，每种棋子一个实现。
• 命令模式：Move 是命令对象，apply 执行，undo 撤销。撤销需要的信息（被吃的子、走之前的易位权和过路兵目标格）都记在命令里。

核心代码

走法分两层：先按棋子自己的规则生成“伪合法”走法，再逐个试走，过滤掉会让自己的王被攻击的那些：

from dataclasses import dataclass

WHITE, BLACK = "w", "b"
Square = tuple[int, int]  # (row, col), each 0..7


@dataclass(frozen=True)
class Piece:
    color: str
    kind: str  # K Q R B N P


@dataclass
class Move:
    src: Square
    dst: Square
    captured: Piece | None = None  # filled in by apply, so undo can put it back


LINES = {"R": [(1, 0), (-1, 0), (0, 1), (0, -1)], "B": [(1, 1), (1, -1), (-1, 1), (-1, -1)]}
LINES["Q"] = LINES["R"] + LINES["B"]
STEPS = {"N": [(1, 2), (2, 1), (-1, 2), (-2, 1), (1, -2), (2, -1), (-1, -2), (-2, -1)],
         "K": LINES["Q"]}


def inside(r: int, c: int) -> bool:
    return 0 <= r < 8 and 0 <= c < 8


def pseudo_moves(grid, sq: Square):
    """Moves by the piece's own rule, ignoring whether they expose the king."""
    (r, c), piece = sq, grid[sq[0]][sq[1]]
    if piece.kind == "P":
        yield from pawn_moves(grid, sq)  # pushes, diagonal captures, promotion
        return
    slide = piece.kind in LINES
    for dr, dc in LINES.get(piece.kind) or STEPS[piece.kind]:
        nr, nc = r + dr, c + dc
        while inside(nr, nc):
            target = grid[nr][nc]
            if target is None or target.color != piece.color:
                yield Move(sq, (nr, nc))
            if target is not None or not slide:
                break
            nr, nc = nr + dr, nc + dc


class Game:
    def __init__(self, grid):
        self.grid, self.turn, self.history = grid, WHITE, []

    def squares(self):
        return [(r, c) for r in range(8) for c in range(8) if self.grid[r][c]]

    def legal_moves(self, sq: Square) -> list[Move]:
        piece = self.grid[sq[0]][sq[1]]
        if piece is None or piece.color != self.turn:
            return []
        legal = []
        for move in pseudo_moves(self.grid, sq):
            self.apply(move)
            if not self.in_check(piece.color):  # never leave your own king attacked
                legal.append(move)
            self.undo()
        return legal

    def play(self, src: Square, dst: Square) -> None:
        move = next((m for m in self.legal_moves(src) if m.dst == dst), None)
        if move is None:
            raise ValueError("illegal move")
        self.apply(move)
        self.turn = BLACK if self.turn == WHITE else WHITE

    def apply(self, move: Move) -> None:
        (r0, c0), (r1, c1) = move.src, move.dst
        move.captured = self.grid[r1][c1]
        self.grid[r1][c1], self.grid[r0][c0] = self.grid[r0][c0], None
        self.history.append(move)

    def undo(self) -> None:
        move = self.history.pop()
        (r0, c0), (r1, c1) = move.src, move.dst
        self.grid[r0][c0], self.grid[r1][c1] = self.grid[r1][c1], move.captured

    def in_check(self, color: str) -> bool:
        king = next(sq for sq in self.squares() if self.grid[sq[0]][sq[1]] == Piece(color, "K"))
        return any(move.dst == king
                   for sq in self.squares() if self.grid[sq[0]][sq[1]].color != color
                   for move in pseudo_moves(self.grid, sq))

    def status(self) -> str:
        can_move = any(self.legal_moves(sq) for sq in self.squares())
        if can_move:
            return "check" if self.in_check(self.turn) else "playing"
        return "checkmate" if self.in_check(self.turn) else "stalemate"

“试走一步再撤回”这个做法看起来笨，却一次覆盖了三种情况：被牵制的子不能离开那条线；王不能走进被攻击的格子；被将军时，只有能解将的走法才合法。每种棋子的走法规则不需要知道王的存在。

status 依赖同一个函数：当前方没有任何合法走法时，被将军就是将死，没被将军就是逼和。

特殊走法需要的状态

这三种走法有个共同点：只看当前棋盘，判断不了它们是否合法，所以要在 Game 里多存一点状态。

• 王车易位：要求王和这边的车从开局起都没动过，两者之间没有其他棋子，王当前没被将军，经过和到达的格子都不被攻击。“没动过”看不出来，所以 Game 维护四个易位权（白方长短易位、黑方长短易位），王或车一动就清掉对应的权利。
• 吃过路兵：只在对方兵刚走了两格之后的下一步有效。Game 记下“被跳过的那一格”，下一步之后清空。
• 兵升变：兵走到底线时，Move 带上 promotion 字段（默认升后）。

因为这些状态会被 apply 修改，Move 要保存修改前的值，undo 时恢复，否则悔棋后易位权就丢了。另外，王车易位不能放进 pseudo_moves：in_check 也调用它，易位又要检查是否被将军，会互相递归。

扩展讨论

• 和棋规则：三次重复局面需要给局面算哈希（常用 Zobrist 哈希，增量更新），存进计数表；五十步规则加一个计数器。
• 棋钟：Clock 记录双方剩余时间，走棋时切换计时方；超时判负。
• 联网对战：服务器是唯一裁判，客户端只发“起点、终点、升变”，服务器校验后广播给双方和观战者（观察者模式）。
• 性能：试走再撤回的做法每步要扫一遍对方所有棋子，人人对弈完全够用；要做引擎时才需要位棋盘（bitboard）。