Bitboard Method

Bitboard 本身只是一组 64 个 flag；它不说明这些 flag 的含义。固定到一个游戏以后，通常会给每个语义一张 bitboard。例如在 draughts 里，可以先拆成三张：黑方占位、白方占位、king 标记。

这里沿用本页的映射：a1 是 bit 0，h1 是 bit 7，a8 到 h8 是 bit 56 到 bit 63。开局时还没有 king，所以 king mask 是空的。

{:title "Initial black occupancy"
 :kind :black
 :bits [41 43 45 47
        48 50 52 54
        57 59 61 63]}

{:title "Initial white occupancy"
 :kind :white
 :bits [0 2 4 6
        9 11 13 15
        16 18 20 22]}

{:title "Initial king mask"
 :kind :king
 :bits []}

Occupied and empty

有了黑白占位之后，整局里哪些格子被占用可以用 OR 合出来：

occupied = black | white
empty = ~occupied

这里先把 ~occupied 理解成“只在棋盘这 64 个 bit 里取反”。也就是：黑白都没有占住的格子，就是 empty。

{:title "Initial occupied mask"
 :kind :mask
 :bits [0 2 4 6
        9 11 13 15
        16 18 20 22
        41 43 45 47
        48 50 52 54
        57 59 61 63]}

{:title "Initial empty mask"
 :kind :mask
 :bits [1 3 5 7
        8 10 12 14
        17 19 21 23
        24 25 26 27 28 29 30 31
        32 33 34 35 36 37 38 39
        40 42 44 46
        49 51 53 55
        56 58 60 62]}

File boundary masks

边界 mask 用来避免从 a-file 或 h-file 走出棋盘后 wrap 到另一侧。

{:title "a-file mask"
 :kind :mask
 :bits [:a1 :a2 :a3 :a4 :a5 :a6 :a7 :a8]}

{:title "h-file mask"
 :kind :mask
 :bits [:h1 :h2 :h3 :h4 :h5 :h6 :h7 :h8]}

White pawn simple moves

先只看普通一步，不处理吃子，也不处理 draughts 的强制吃子规则。white-pawn 往棋盘上方移动，在这个 bit mapping 里就是把 source bits 向更高的 bit index shift。

<< 是 bit 左移操作：把二进制里的所有 bit 往左移动 N 格，右边补 0。1 << i 可以理解成“创建一个只有第 i 个位置是 1 的 bitboard”。例如 1 << 3 就是只有 bit 3 为 1。

如果一个棋子在 bit 18，那么它的位置可以写成 1 << 18。整体左移 7 位：

(1 << 18) << 7
= 1 << 25

所以 bitboard << 7 的效果是：把 bitboard 里每一个为 1 的位置都移动到 index + 7。在这里就是把每个 white-pawn 变成它对应方向上的 target bit。

这一步的 target masks 可以先写成：

nw-targets = ((white-pawn & ~a-file) << 7) & empty
ne-targets = ((white-pawn & ~h-file) << 9) & empty

开局时，只有最前排的 white-pawn 可以走到第 4 rank。+7 和 +9 两个 target mask 会在目标格上重叠；所以最终 target bitboard 只有 4 个 bit，但实际 move 数更多。

{:title "Initial white-pawn simple targets"
 :sources {:label "white-pawn"
           :kind :white-pawn
           :bits [0 2 4 6
                  9 11 13 15
                  16 18 20 22]}
 :overlays [{:label "+7 NW targets"
             :kind :nw-target
             :bits [25 27 29]
             :source-shift -7}
            {:label "+9 NE targets"
             :kind :ne-target
             :bits [25 27 29 31]
             :source-shift -9}]
 :result-label "possible target mask"}

黑方同理，只是 black-pawn 往更低的 bit index 移动：

sw-targets = ((black-pawn & ~a-file) >> 9) & empty
se-targets = ((black-pawn & ~h-file) >> 7) & empty

{:title "Initial black-pawn simple targets"
 :sources {:label "black-pawn"
           :kind :black-pawn
           :bits [41 43 45 47
                  48 50 52 54
                  57 59 61 63]}
 :overlays [{:label "-9 SW targets"
             :kind :sw-target
             :bits [32 34 36 38]
             :source-shift 9}
            {:label "-7 SE targets"
             :kind :se-target
             :bits [34 36 38]
             :source-shift 7}]
 :result-label "possible target mask"}

Pawn single capture

普通移动只需要找 adjacent empty target。单次 capture 多一层：先找 adjacent enemy，再找 enemy 后面的 landing empty。

以白方 NE capture 为例：

ne-enemy = ((white-pawn & ~h-file) << 9) & black
ne-landing = ((ne-enemy & ~h-file) << 9) & empty

这里 ne-enemy 不是最终落点，它只是“可以被吃的黑子位置”。真正可以落子的格子是 ne-landing。

{:title "White-pawn NE single capture"
 :label "c3 captures d4 and lands on e5"
 :direction "NE"
 :source {:label "white-pawn source"
          :kind :white-pawn
          :bits [:c3]}
 :enemy {:label "enemy candidate"
         :kind :black-pawn
         :bits [:d4]}
 :landing {:label "landing target"
           :kind :landing
           :bits [:e5]}}

同一个例子用 bit index 看，就是：

c3 = bit 18
d4 = bit 27 = 18 + 9
e5 = bit 36 = 27 + 9

所以 landing mask 只能说明“哪里可以落子”；如果要生成完整 move，还要保留 source、enemy、landing 三者的关系。

Pawn continuous capture

连续 capture 就是：完成一次 single capture 之后，把 landing 当成新的 source，继续检查有没有下一次 single capture。这里先不处理升 king，只看 pawn 的前向连吃。

每跳之后最好及时更新局面：

white' = (white & ~source) | landing
black' = black & ~enemy
empty' = ~(white' | black')

在 forward-only pawn capture 里，刚才的 source 和 enemy 都已经在后方，很多时候不更新也不会影响下一跳判断。但及时清空更接近真实规则，也避免后面引入 backward capture 或 king capture 时概念断裂。

{:title "White-pawn continuous capture"
 :steps [{:label "1. c3 captures d4 and lands on e5"
          :direction "NE"
          :source {:label "source c3"
                   :kind :white-pawn
                   :bits [:c3]}
          :enemy {:label "captured d4"
                  :kind :black-pawn
                  :bits [:d4]}
          :landing {:label "landing e5"
                    :kind :landing
                    :bits [:e5]}}
         {:label "2. e5 captures f6 and lands on g7"
          :direction "NE"
          :source {:label "source e5"
                   :kind :white-pawn
                   :bits [:e5]}
          :enemy {:label "captured f6"
                  :kind :black-pawn
                  :bits [:f6]}
          :landing {:label "landing g7"
                    :kind :landing
                    :bits [:g7]}}]}

图里的中间点 e5 只标成第 1 跳的 landing；它同时也是第 2 跳的 source，不需要再叠一个 source marker。

对应 bit index：

c3 = 18
d4 = 27 = 18 + 9
e5 = 36 = 27 + 9
f6 = 45 = 36 + 9
g7 = 54 = 45 + 9

生成连续 capture 时，程序通常不是只返回一个 landing mask，而是搜索 capture branches：

capture-branches(state, source):
  steps = single-captures-from(state, source)

  if steps is empty:
    return finished path

  for each step:
    state' = apply-capture(state, step)
    continue from step.landing

如果某个 landing 后面有两个方向都能继续吃，就会分出两条 branch。一个完整 move 应该是一条走到底的 branch，而不是中间某个 landing。

White pawn promotion

白方 pawn 的底线是第 8 rank，也就是 a8 到 h8。如果一次 simple move 或 capture 的 landing 落在这条 rank 上，这个 white-pawn 就变成 king。

{:title "White promotion rank"
 :kind :mask
 :bits [:a8 :b8 :c8 :d8 :e8 :f8 :g8 :h8]}

判断是否升 king，本质上就是看 landing mask 和 promotion-rank 有没有交集：

white-promotion-rank = rank-8
promoted = landing & white-promotion-rank
promotes? = promoted != 0

例如 g7 -> h8：

{:title "White-pawn reaches promotion rank"
 :sources {:label "white-pawn"
           :kind :white-pawn
           :bits [:g7]}
 :overlays [{:label "+9 NE landing"
             :kind :ne-target
             :bits [:h8]
             :source-shift -9}]
 :result-label "landing mask"}

应用这个 move 时，白方占位还是把 pawn 放到 landing：

white' = (white & ~source) | landing

区别是 king bitboard 也要把这个 landing 打开：

king' = king | promoted

所以升 king 之后，h8 同时在 white occupancy 里，也在 king mask 里。判断某个白子是不是 king，就是：

white-king = white & king

{:title "King mask after white promotion"
 :kind :king
 :bits [:h8]}

在当前 draughts 规则里，pawn 一旦升 king，这一 turn 就结束；后面再单独介绍 king 的移动和 capture。

King simple moves

Pawn 的普通移动是固定 shift 一次；king 的普通移动不是。King 可以沿四个对角线方向一直滑动，直到遇到棋盘边界或任意棋子。

这里先只讲普通移动，不讲 king capture。King 的四个方向仍然可以用同样的 bit index delta 表示：

NW: +7
NE: +9
SW: -9
SE: -7

从某个格子出发，沿一个方向一直延伸出去的那条线，叫做 ray。例如 king 在 d4，NE ray 是：

e5, f6, g7, h8

{:title "NE ray from d4"
 :kind :mask
 :bits [:e5 :f6 :g7 :h8]}

Ray 本身还没有考虑 blocker。它只是几何上的“这条方向线上有哪些格子”。

Method 1: loop shift

最容易理解的实现是循环 shift。用 NE 方向举例：

targets = 0
pos = source

loop:
  pos = (pos & ~h-file) << 9

  if pos == 0:
    stop

  if (pos & occupied) != 0:
    stop

  targets = targets | pos

这里 pos 是一个只有一个 bit 的 bitboard，不是 index。每次 shift 一格；如果这一格是 empty，就加入 targets；如果这一格被占住，就停止这个方向。

例如 d4 的 NE ray 上，f6 有棋子：

{:title "Blocker on NE ray"
 :kind :black
 :bits [:f6]}

循环会先看到 e5 是 empty，所以加入 targets；下一步看到 f6 occupied，于是停止。g7 和 h8 虽然也在 ray 上，但不能越过 blocker。

{:title "NE legal targets before blocker"
 :kind :target
 :bits [:e5]}

Method 2: ray table and truncation

另一种实现是预计算 ray table：

ray-table[source][direction] = ray-bitboard

比如：

ray = ray-table[:d4][:NE]
;; e5 | f6 | g7 | h8

运行时先找这条 ray 上有哪些 blocker：

blockers = ray & occupied

如果 blockers 是 0，说明整条 ray 没有棋子挡住：

targets = ray & empty

如果有 blocker，就要把 blocker 后面的 ray 截掉。NE 和 NW 是 bit index 递增方向，所以离 source 最近的 blocker 是 blockers 里的最低位 set bit：

first-blocker = lsb(blockers)

拿到 first blocker 之后，递增方向的截断可以这样写：

targets = ray & (first-blocker - 1) & empty

原因是如果：

first-blocker = 1 << 45

那么：

first-blocker - 1

会让 bit 0 到 bit 44 都变成 1。再和 ray 做 AND，就只留下 blocker 前面的 ray bits。

在 d4 -> NE 的例子里：

ray = e5 | f6 | g7 | h8
first-blocker = f6
ray & (first-blocker - 1) = e5

对于 SW 和 SE 这种 bit index 递减方向，离 source 最近的 blocker 是最高位 set bit：

first-blocker = msb(blockers)

这时要保留 blocker 以上的 bits：

targets = ray & ~(first-blocker | (first-blocker - 1)) & empty

这里仍然把 ~ 理解成只在棋盘 64 bits 内取反。first-blocker | (first-blocker - 1) 会覆盖从 bit 0 到 blocker 的所有 bits，取反后就只剩 blocker 以上的 bits。再和 ray 相交，就得到 source 和 blocker 之间的格子。

所以 king 普通移动可以总结成：

ray = ray-table[source][direction]
blockers = ray & occupied

if blockers == 0:
  targets = ray & empty
else if direction is increasing:
  first = lsb(blockers)
  targets = ray & (first - 1) & empty
else:
  first = msb(blockers)
  targets = ray & ~(first | (first - 1)) & empty

Loop shift 更容易写对；ray table 加 truncation 更接近引擎优化。两者算出来的普通 king targets 应该一样。

King capture

King capture 也沿 diagonal ray 计算，但和 pawn capture 有两个差别：

1. Enemy 不一定相邻；它是 ray 上遇到的第一个 blocker。

2. 越过 enemy 后，king 可以落在 enemy 后面任意 empty square，直到下一个 blocker 之前。

还是用 d4 -> NE 举例：

d4 king
NE ray: e5, f6, g7, h8

如果 f6 是 enemy，g7 和 h8 都是 empty，那么 king 可以选择：

d4 x g7
d4 x h8

{:title "King capture NE ray"
 :kind :mask
 :bits [:e5 :f6 :g7 :h8]}

{:title "King capture enemy"
 :kind :black
 :bits [:f6]}

{:title "King capture landing choices"
 :kind :target
 :bits [:g7 :h8]}

用 ray table 算时，第一步仍然是：

ray = ray-table[source][NE]
blockers = ray & occupied

如果 blockers 是 0，就没有 capture。否则找到最近 blocker：

first = lsb(blockers)

NE/NW 是 bit index 递增方向，所以最近 blocker 是最低位 set bit。然后必须检查这个 blocker 是不是 enemy：

if (first & enemy) == 0:
  no capture

如果最近 blocker 是自己的子，它会挡住 ray，后面就算有 enemy 也不能吃。

如果 first 是 enemy，就要取 enemy 后面的 ray：

after-first = ray & ~(first | (first - 1))

然后再看 enemy 后面有没有第二个 blocker：

next-blockers = after-first & occupied

如果没有第二个 blocker，所有 after-first 里的 empty squares 都是 landing：

landings = after-first & empty

如果有第二个 blocker，要在第二个 blocker 前截断。NE 是递增方向：

second = lsb(next-blockers)
landings = after-first & (second - 1) & empty

例如 h8 又有一个 blocker：

d4 king
f6 enemy
g7 empty
h8 occupied

那么 landing 只有 g7：

{:title "King capture landing before second blocker"
 :kind :target
 :bits [:g7]}

SW/SE 方向同理，只是 bit index 递减。最近 blocker 用 msb：

first = msb(blockers)

enemy 后面的 ray 是 first 以下的 ray bits：

after-first = ray & (first - 1)

如果 enemy 后面还有 blocker，第二个 blocker 也是 msb(next-blockers)，landing 要保留第二个 blocker 之前、也就是 index 更大的那段：

second = msb(next-blockers)
landings = after-first & ~(second | (second - 1)) & empty

所以 king capture 的 NE/NW 递增方向可以总结成：

ray = ray-table[source][direction]
blockers = ray & occupied

if blockers == 0:
  no capture
else:
  first = lsb(blockers)

  if (first & enemy) == 0:
    no capture
  else:
    after-first = ray & ~(first | (first - 1))
    next-blockers = after-first & occupied

    if next-blockers == 0:
      landings = after-first & empty
    else:
      second = lsb(next-blockers)
      landings = after-first & (second - 1) & empty

King capture 生成 move 时，不能只返回一个 landing mask。因为同一个 enemy 后面可能有多个 landing，每个 landing 都可能导致不同的后续连吃 branch：

{:source :d4
 :enemy :f6
 :landings [:g7 :h8]}

之后要对每个 landing 分别应用 capture、更新局面，再继续搜索下一跳。