FreeCell 局號怎麼重現同一副牌：相容發牌、Internet FreeCell Project 與 #11982

Microsoft FreeCell 用整數當局號，原版提供 1 到 32,000 號；只要實作遵守相同規則，同一個號碼就能重現同一副牌。這些規則涵蓋 Microsoft C runtime 的 rand()、52 張牌的編號，以及抽牌、補位和發牌方式。局號只是輸入，若中間改了規則，即使數字相同，盤面也可能不同。

本文照 Freecell Solver 的相容實作用 Python 重做一次發牌，印出第 1 局和著名的第 11982 局，兩局都已和 Rosetta Code 的公開牌序逐張核對。後半段整理 Internet FreeCell Project 的紀錄，以及「局號重現」「可解」「防作弊」為什麼要當三種不同的保證來談。這篇接在〈踩地雷無猜測盤面生成〉和〈15-puzzle 均勻可解盤面生成〉後面，前兩篇講怎麼生成和判定，這篇講怎麼讓別人生出同一盤。

相容發牌要固定的四件事

Freecell Solver 的 pi_make_microsoft_freecell_board.c 在檔頭註明，程式碼根據 Jim Horne（原版 Microsoft FreeCell 作者）的程式與 Microsoft C Run-Time Library 改寫；Solitaire Laboratory 的 FAQ 也寫到，這些局是用 Microsoft C 編譯器附的亂數產生器、以整數 seed 產生的。這份實作和 Rosetta Code 列的發牌規則一致，可以拆成四條：

亂數產生器是 LCG，狀態更新為 state = state * 214013 + 2531011，每次輸出 (state >> 16) & 0x7fff，也就是 0 到 32767 之間的 15 bit 整數。初始狀態就是局號。
牌的編號是 rank * 4 + suit，花色順序 C、D、H、S，所以 AC 是 0、AD 是 1、AH 是 2、AS 是 3、2C 是 4，一路到 KS 是 51。
每次抽牌取 rand % 剩餘張數 當索引，把那張牌發出去，然後把牌堆最後一張搬到那個位置，牌堆長度減一。這裡的輸出方式與後面範例的 Fisher-Yates 寫法不同，不能直接互換。
發出的 52 張牌依序放進 8 欄，第 i 張進第 i % 8 欄，所以前四欄 7 張、後四欄 6 張。

照這四條寫成 Python，不到四十行：

import sys

RANKS = "A23456789TJQK"
SUITS = "CDHS"  # card = rank * 4 + suit: AC=0, AD=1, AH=2, AS=3, 2C=4 ...


def ms_rand(state):
    """Microsoft C runtime rand(): LCG; returns new state and a 15-bit output."""
    state = (state * 214013 + 2531011) & 0xFFFFFFFF
    return state, (state >> 16) & 0x7FFF


def deal(game_number):
    deck = list(range(52))
    state = game_number
    dealt = []
    while deck:
        state, r = ms_rand(state)
        j = r % len(deck)
        dealt.append(deck[j])
        deck[j] = deck[-1]  # backfill the hole with the last card, then shrink
        deck.pop()
    return dealt


def card_name(c):
    return RANKS[c >> 2] + SUITS[c & 3]


if __name__ == "__main__":
    n = int(sys.argv[1]) if len(sys.argv) > 1 else 1
    d = deal(n)
    print(f"Game #{n}")
    for row in range(0, 52, 8):  # 8 cards per row; card i goes to column i % 8
        print(" ".join(card_name(c) for c in d[row:row + 8]))

跑第 1 局：

Game #1
JD 2D 9H JC 5D 7H 7C 5H
KD KC 9S 5S AD QC KH 3H
2S KS 9D QD JS AS AH 3C
4C 5C TS QH 4H AC 4D 7S
3S TD 4S TH 8H 2C JH 7D
6D 8S 8D QS 6C 3D 8C TC
6S 9C 2H 6H

每一列是一輪發牌，直式讀下去就是各欄的內容，第一欄從上到下是 JD、KD、2S、4C、3S、6D、6S。這 52 張和 Rosetta Code 所列的第 1 局逐張相同，第 617 局也一致。同一支程式跑 11982：

Game #11982
AH AS 4H AC 2D 6S TS JS
3D 3H QS QC 8S 7H AD KS
KD 6H 5S 4D 9H JH 9S 3C
JC 5D 5C 8C 9D TD KH 7C
6C 2C TH QH 6D TC 4S 7S
JD 7D 8H 9C 2H QD 4C 5H
KC 8D 2S 3S

這一局和 Rosetta Code 的 Python 解法印出的牌序逐張相同。另外用 Freecell Solver 作者在 PyPI 上的 pysol_cards 0.24.0 跑 1 到 32,000 局，和上面的 deal() 全部一致。

同一個數字換一種洗法，就是另一局

「用局號當 seed」這句話常被理解成只要 seed 一樣就會得到同一副牌，實際上洗牌方式也在規則裡。下面用同一個 LCG、同一個局號 1，分別跑 Microsoft 的抽牌補位法、教科書的 Fisher-Yates，再加一個 Python 內建的 random.Random(1).shuffle，只看第一列：

import random
from ms_deal import ms_rand, deal, card_name


def fisher_yates_with_ms_rand(game_number):
    """Same LCG, same deal number, but a textbook Fisher-Yates swap."""
    deck = list(range(52))
    state = game_number
    for i in range(51, 0, -1):
        state, r = ms_rand(state)
        j = r % (i + 1)
        deck[i], deck[j] = deck[j], deck[i]
    return deck


def python_shuffle(game_number):
    deck = list(range(52))
    random.Random(game_number).shuffle(deck)
    return deck


for name, d in [("Microsoft", deal(1)),
                ("same LCG, Fisher-Yates", fisher_yates_with_ms_rand(1)),
                ("random.Random(1).shuffle", python_shuffle(1))]:
    print(f"{name:26s} first row: {' '.join(card_name(c) for c in d[:8])}")

Microsoft                  first row: JD 2D 9H JC 5D 7H 7C 5H
same LCG, Fisher-Yates     first row: 6H 2H 9C 6S TC 8C 3D 6C
random.Random(1).shuffle   first row: KD 3D TD 6H AH TH 5S 3S

第二列用同一個 LCG，只是改成和尾端交換、洗完再從頭讀，第一張就從 JD 變成 6H。要相容，seed 以外，抽牌與輸出的順序也得一模一樣。

32,000 和 15 bit 是兩回事

Wikipedia 把原版的局數寫成「由 15 bit 的 pseudorandom-number seed 產生 32,000 局」，局號 1 到 32,000 確實放得進 15 bit，但產生器內部的狀態比 15 bit 寬。從上面的程式碼看，15 bit 出現在輸出那一步的 & 0x7fff，狀態本身是 32 bit 的乘加，32,000 則是 Horne 當年選的局號範圍，三個數字講的是不同東西。

輸出只取狀態的第 16 到 30 位，而乘法和加法的低位不受高位影響，所以單看這條 LCG，狀態用 31 bit、32 bit 還是 64 bit 存，只要局號在 32 bit 以內，這段輸出計算都相同。Rosetta Code 的 Python 解法用 (1 << 31) - 1 遮罩，等於 & 0x7FFFFFFF；Freecell Solver 用 unsigned long long 完全不遮罩，上面的 Python 用 & 0xFFFFFFFF，三種寫法可以直接驗證：

def outputs(game_number, mask):
    state, out = game_number, []
    for _ in range(52):
        state = (state * 214013 + 2531011) & mask
        out.append((state >> 16) & 0x7FFF)
    return out


same = all(
    outputs(n, 0x7FFFFFFF) == outputs(n, 0xFFFFFFFF) == outputs(n, (1 << 64) - 1)
    for n in range(1, 32001)
)
print("1..32000 identical across 31/32/64-bit state:", same)

1..32000 identical across 31/32/64-bit state: True

局號達到 2^31 起，相容規則就不一樣了，Freecell Solver 的 gen_ms_boards__rand.h 對 2^31 以上和 2^32 以上的局號各有一段特別處理（把輸出 | 0x8000、改用 16 bit 輸出加一），這些分支處理擴充局號，FAQ 記載 Ettlinger 後來把 FCPro 的局號範圍擴到 80 億以上，但沒寫各分支何時加入；原版 32,000 局用不到。Windows XP 版把局數擴到 100 萬，局號沿用同一套編號，仍在 2^31 以內。

Internet FreeCell Project 與 #11982

Solitaire Laboratory 的 FreeCell FAQ 作者 Michael Keller 是當年參與者，他的紀錄是：1994 年 8 月 Dave Ring 在 rec.puzzles、sci.math 等地方徵求志工，最後超過 100 人參加，每人分到 100 個連號的局；計畫在 1995 年 4 月結束，32,000 局裡只有 11982 沒有人回報解出。中間有人回報解出過 11982，後來發現對方手動玩的是 Baker’s Game，規則不同，這筆回報作廢。Wikipedia 的 Microsoft FreeCell 條目引用 1999 年的《Windows 98 in a Nutshell》，記的也是同一個結果。

人力搜尋沒有找到解，還不足以證明無解；32,000 局中有一局未解，只能先記為當時未找到解。後來還有電腦搜尋的紀錄：FAQ 記載 Adrian Ettlinger 用 Don Woods 的求解器加上自己的擴充，主要透過他和 Wilson Callan 寫的 FCPro 程式分析了 2,000 萬局，其中特別寫到「我們驗證了 Ring 計畫的結果：32,000 個標準局裡除了一局（11982）之外全部可解」。Keller 另外說 11982 已經讓他知道的至少八個獨立求解程式都解不出來，他有把握稱它無解；也寫到這一局用五個 freecell 就能解，四個不行。FAQ 另外提到這些程式多數是做窮舉搜尋，只是沒有附搜尋紀錄；本文引用這個結果，沒有重跑搜尋。

XP 版擴到 100 萬局之後，FAQ 說其中 8 局無解，並列出前 1,000 萬局裡 130 個無解局號，開頭八個是 11982、146692、186216、455889、495505、512118、517776、781948，全部落在 100 萬以內，數量也剛好是 8。

重現、可解、防作弊是三種保證

局號讓別人重現同一副牌，沒有保證這副牌可解，也沒有保證玩家能在時限內解出。Keller 估計有幾千人試過 11982 沒解出來，但要判定無解，得靠求解器照正確規則做完窮舉搜尋。〈踩地雷無猜測盤面生成〉討論先生成候選盤，再用 solver 篩選，失敗時可能得重來；〈15-puzzle 均勻可解盤面生成〉則用奇偶判定檢查可解性。規格要寫清楚採用哪種方法，不能只靠局號承諾可解。

要讓 solver 替盤面背書，結果至少要分三類：找到解、完整搜尋後確定無解、搜尋逾時尚未確定。第二類和第三類在工程上差很多，前者要在搜尋完整且規則正確的前提下，才足以支持無解結論，後者只代表這次沒找到。一般化的 FreeCell 是 NP-complete（Wikipedia 引用 Helmert 2003），這不代表某個固定盤面一定會逾時，但工程上仍得處理搜尋未完成的情況，設計產品時得決定逾時的盤面是丟掉、標成「未分類」，還是照樣發給玩家。

排行榜還得另外考慮作弊。即使伺服器驗證每一步是否合法，並自行計時，公開局號仍讓玩家有機會事先算好盤面，背下解法或交給 solver。單靠合法步驟序列，未必能辨認這些準備。防作弊規格應說清楚要擋哪種行為，以及哪些行為不在保證範圍內。每日挑戰若提前公開盤面，也有同樣限制；是否用日期當 seed，不影響玩家能事先準備這件事。

需要結果事先猜不到的玩法，則得避免提前公開足以重現結果的資訊，〈遊戲 RNG：正式環境要猜不到、測試要能重播〉談的是這種需求。FreeCell 的局號用來分享同一盤，公開 seed 與發牌規則符合這個目的，採用前要先確認遊戲需要哪一種保證。

補充筆記

Microsoft FreeCell 的局號要重現同一副牌，得固定四件事：LCG（214013、2531011、輸出取 15 bit）、牌的編號（rank * 4 + suit，花色 CDHS）、抽牌後用最後一張補位、依序發進 8 欄。
同一個 LCG、同一個局號，抽牌補位法換成 Fisher-Yates，第 1 局第一張就對不上（JD 對 6H）；相容性仍取決於完整的發牌規則。
15 bit 是每次輸出的寬度，32,000 是局號範圍；狀態用 31、32、64 bit 存，32,000 局的輸出都相同。
Internet FreeCell Project 1994 年 8 月到 1995 年 4 月，31,999 局回報解出，11982 沒人解出；之後 Ettlinger 等人用 FCPro 的分析驗證了這個結果，Keller 另記有至少八個獨立求解程式解不出它。
局號重現、可解、防作弊是三種保證，solver 的結果要分找到解、完整搜尋無解、逾時未定，公開盤面擋不了事先準備。