迷宮生成的取樣偏差：隨機 Kruskal 與 Wilson 的生成樹分布

完美迷宮就是格線圖的一棵生成樹，但隨機生成一棵樹，沒有保證每棵樹等機率出現。把 Kruskal 的邊順序隨機打亂，在 2×3 格線上列舉全部 5,040 種順序，會得到 15 棵樹，其中 9 棵各出現 360 次，另外 6 棵各出現 300 次。Wilson 的 loop-erased random walk 則能均勻抽出生成樹。

在 20×20 格線的比較裡，backtracker 的死路較少、直徑較長，適合先拿來試需要長路徑的關卡；要求每棵生成樹等機率出現，就用 Wilson。

完美迷宮就是生成樹

把每個格子當成頂點，相鄰格子之間的牆當成候選邊，拆掉一面牆，就在圖上留下一條通道。完美迷宮要求任兩格之間恰好有一條路，所有格子都連得起來，也沒有迴圈，正好是一棵生成樹。

有 n 格就會留下 n−1 條通道。20×20 格線有 400 格，760 條候選邊最後留下 399 條；縮到 2×3 時只有 6 格、7 條候選邊，共有 15 棵生成樹。

三個生成器

Recursive backtracker 用深度優先搜尋（DFS），從一格出發，隨機走向還沒去過的相鄰格，沒有地方可走就沿原路退回，繼續找未訪格。這種走法傾向留下長而彎的走廊，分叉較少（迷宮生成文件）。

隨機 Kruskal 把所有候選邊打亂，再依序檢查每條邊。union-find 記住哪些格子已經連在一起，邊的兩端還沒連通就拆牆，已經連通就略過，避免形成迴圈。

Wilson 先選一格放進樹，再從樹外任一格出發做隨機漫步，每一步都從相鄰格等機率選一格。走回這次路徑已經經過的格子，就刪掉剛形成的迴圈，這就是 loop-erased random walk；碰到既有的樹時，把剩下的整條路接上去，再選一個樹外的格子繼續，直到所有格子都進入樹裡。初始格固定在左上角也能均勻取樣，均勻性有 Wilson 1996 年的證明保證。

2×3 全列舉：Kruskal 不均勻

7 條邊只有 7! = 5040 種排列，可以每種都跑過，不必靠抽樣估計 Kruskal 的分布。kruskal_enum.py 把結果存成邊的集合，計算每棵樹出現幾次，再用 Wilson 在同一張圖抽 504,000 次作比較：

# Does "random spanning tree" mean "every spanning tree equally likely"?
# On a 2x3 grid (6 cells, 7 edges) we can feed Kruskal every one of the 7! = 5040 edge
# orderings and count how often each tree appears. Wilson's algorithm on the same grid is
# sampled 504,000 times for comparison; it is known to sample spanning trees uniformly.
from itertools import permutations
from collections import Counter
import random

random.seed(42)
W, H = 3, 2
cells = [(x, y) for y in range(H) for x in range(W)]
edges = [((x, y), (x + 1, y)) for y in range(H) for x in range(W - 1)] + \
        [((x, y), (x, y + 1)) for y in range(H - 1) for x in range(W)]
nb = {c: [b if a == c else a for a, b in edges if c in (a, b)] for c in cells}

def kruskal(order):
    parent = {c: c for c in cells}
    def find(c):
        while parent[c] != c:
            c = parent[c]
        return c
    tree = []
    for a, b in order:
        ra, rb = find(a), find(b)
        if ra != rb:
            parent[ra] = rb
            tree.append((a, b))
    return frozenset(tree)

def wilson():
    in_tree = {cells[0]}
    tree = []
    while len(in_tree) < len(cells):
        c = random.choice([x for x in cells if x not in in_tree])
        path = [c]
        while c not in in_tree:            # loop-erased random walk
            c = random.choice(nb[c])
            if c in path:
                path = path[:path.index(c) + 1]
            else:
                path.append(c)
        for a, b in zip(path, path[1:]):
            tree.append(tuple(sorted((a, b))))
            in_tree.add(a)
    return frozenset(tree)

orders = list(permutations(edges))
kc = Counter(kruskal(o) for o in orders)
print(f"2x3 grid: {len(edges)} edges, {len(orders)} edge orderings, {len(kc)} distinct spanning trees, uniform would be {len(orders) // len(kc)} each")
print("Kruskal: trees per multiplicity ->", dict(sorted(Counter(kc.values()).items())))
samples = 504_000
wc = Counter(wilson() for _ in range(samples))
print(f"Wilson ({samples} samples): {len(wc)} trees, counts from {min(wc.values())} to {max(wc.values())}, uniform would be {samples // len(wc)}")

2x3 grid: 7 edges, 5040 edge orderings, 15 distinct spanning trees, uniform would be 336 each
Kruskal: trees per multiplicity -> {300: 6, 360: 9}
Wilson (504000 samples): 15 trees, counts from 33360 to 34007, uniform would be 33600

如果每棵樹等機率，每棵應該各分到 5,040 種順序裡的 336 種。實際結果分成兩群，9 棵各有 360 種順序，另外 6 棵各有 300 種。

兩群可以用格線中間那條直邊區分。這條邊同時屬於左右兩個長度為 4 的迴圈，含它的 9 棵樹各出現 360 次，不含它的 6 棵各出現 300 次。Kruskal 產出的樹包含中間邊的機率是 3240/5040，約 64.3%；均勻取樣時應該是 9/15，也就是 60%。

Wilson 這次抽到的 15 棵樹，各出現 33,360 到 34,007 次，均勻分布下每棵的期望次數是 33,600。以每棵樹命中機率 1/15 的二項分布計算，次數的標準差約 177，最大偏差約 2.3σ，在同時觀察 15 棵樹時，這樣的波動不奇怪。

只抽少量 Kruskal 迷宮，360 與 300 的差距可能混在波動裡，這張小格線的全列舉直接算出了差距。

20×20 的紋理指標

死路是只有一條通道的格子，死路比例就是這種格子占全部格子的比例。直徑則是任兩格之間最短路徑的最大值，單位用邊數。樹的直徑可以做兩次 BFS：先從任一格找最遠格，再從那一格找最遠格，第二次得到的距離就是直徑。入口與出口已經固定時，要另外算這兩格之間的距離；把直徑兩端當成入口與出口，通關路徑才會等於直徑。

把程式存成 maze_metrics.py 執行，會在 20×20 格線上每種生成器各跑 200 張，開頭只設一次 seed 42，後面的生成器接續使用同一個亂數狀態，要重現結果就得保留執行順序：

# Texture of 20x20 mazes from three generators: share of dead ends, diameter (longest shortest
# path, counted in edges) and wall-clock time. Numbers describe this grid size and sample
# size only; they are not fixed properties of the algorithms.
import random, time

random.seed(42)
W = H = 20
CELLS = [(x, y) for x in range(W) for y in range(H)]

def nbrs(c):
    x, y = c
    return [(x + dx, y + dy) for dx, dy in ((1, 0), (-1, 0), (0, 1), (0, -1)) if 0 <= x + dx < W and 0 <= y + dy < H]

def link(adj, a, b):
    adj[a].add(b); adj[b].add(a)

def backtracker():
    adj = {c: set() for c in CELLS}
    stack, seen = [(0, 0)], {(0, 0)}
    while stack:
        c = stack[-1]
        options = [n for n in nbrs(c) if n not in seen]
        if not options:
            stack.pop(); continue
        n = random.choice(options)
        link(adj, c, n); seen.add(n); stack.append(n)
    return adj

def kruskal():
    adj = {c: set() for c in CELLS}
    parent = {c: c for c in CELLS}
    def find(c):
        while parent[c] != c:
            parent[c] = parent[parent[c]]; c = parent[c]
        return c
    edges = [(a, b) for a in CELLS for b in nbrs(a) if a < b]
    random.shuffle(edges)
    for a, b in edges:
        ra, rb = find(a), find(b)
        if ra != rb:
            parent[ra] = rb; link(adj, a, b)
    return adj

def wilson():
    adj = {c: set() for c in CELLS}
    in_tree = {(0, 0)}
    while len(in_tree) < len(CELLS):
        c = random.choice([x for x in CELLS if x not in in_tree])
        path = [c]
        while c not in in_tree:
            c = random.choice(nbrs(c))
            if c in path:
                path = path[:path.index(c) + 1]
            else:
                path.append(c)
        for a, b in zip(path, path[1:]):
            link(adj, a, b); in_tree.add(a)
    return adj

def farthest(adj, start):
    dist = {start: 0}
    queue = [start]
    for c in queue:
        for n in adj[c]:
            if n not in dist:
                dist[n] = dist[c] + 1; queue.append(n)
    far = max(dist, key=dist.get)
    return far, dist[far]

RUNS = 200
print(f"20x20, {RUNS} mazes each")
for name, gen in (("recursive backtracker", backtracker), ("Kruskal", kruskal), ("Wilson", wilson)):
    dead = diameter = 0.0
    t0 = time.perf_counter()
    mazes = [gen() for _ in range(RUNS)]
    elapsed = (time.perf_counter() - t0) / RUNS * 1000
    for adj in mazes:
        dead += sum(len(v) == 1 for v in adj.values()) / len(CELLS)
        a, _ = farthest(adj, (0, 0))
        diameter += farthest(adj, a)[1]
    print(f"{name:22s} dead ends={dead / RUNS * 100:5.1f}%  mean diameter={diameter / RUNS:6.1f} edges  ({elapsed:5.1f} ms per maze)")

20x20, 200 mazes each
recursive backtracker  dead ends= 10.6%  mean diameter= 228.6 edges  (  0.6 ms per maze)
Kruskal                dead ends= 30.3%  mean diameter=  81.8 edges  (  0.7 ms per maze)
Wilson                 dead ends= 29.3%  mean diameter=  91.5 edges  (  5.1 ms per maze)

Backtracker 的平均死路比例是 10.6%，平均直徑 228.6 邊，死路較少，最長路徑也比另外兩種長。Kruskal 與 Wilson 的死路比例接近，分別是 30.3% 與 29.3%，平均直徑則是 81.8 與 91.5 邊。

生成耗時不含指標計算，backtracker 每張約 0.6 ms，Kruskal 約 0.7 ms，Wilson 約 5.1 ms，這是 Mac 上 Python 單執行緒的單次量測，只適合比較這組實作。關卡若換了格線尺寸，就重新量測耗時與死路比例，別直接沿用這裡的 10.6%。

均勻對玩家有什麼意義

Wilson 讓格線圖的每棵生成樹等機率出現，但同一個死路比例可能對應很多棵樹，對應的樹越多，玩家遇到這個比例的機會就越高，路徑長度也一樣。

每日關卡要能重現，先保存各關的 seed，連同生成器與 Python 版本一起記錄，讓每關使用獨立的亂數狀態，就不用重跑前面關卡消耗過的亂數。這個做法也適用於 Kruskal 與 backtracker。

需要所有生成樹等機率時，用 Wilson，生成後就不再按紋理淘汰結果。能接受取樣偏差、想要接近 Wilson 的死路比例，又希望減少生成耗時，可以先試 Kruskal；需求偏向死路少、最長路徑長，就先試 backtracker。要控制關卡的死路與路程，可以把量測程式接成篩選步驟：生成器回傳的 adj 列出每格可通行的鄰格，逐張計算死路比例與入口到出口的距離，符合需求才依連線拆牆，不合的就丟棄重抽。

補充筆記

驗收完美迷宮時，先確認所有格子連通且沒有迴圈，再檢查取樣分布。
能列舉的小圖就直接數完：2×3 格線的 7! 種邊順序讓 Kruskal 的 9 棵樹各出現 360 次、6 棵各出現 300 次，偏差可以精確算出來。
核對 Wilson 實作時，用小圖比較各棵樹的出現次數；504,000 次抽樣接近均勻期望，可作為對照。
20×20、每種 200 張的比較可當選型起點：要死路少、路徑長，可先試 backtracker（死路約 10.6%、直徑約 229 邊）；Kruskal 與 Wilson 的死路約 30%、直徑約 82 到 92 邊。
關卡篩選要量每張迷宮的死路比例與入口到出口的距離，整批平均值不能代替逐張檢查。