HDU 2177 取石子遊戲：威佐夫博弈（Wythoff Game）數學解法全解析

HDU 2177 取石子遊戲：威佐夫博弈（Wythoff Game）數學解法全解析

題目來源：ECJTU 2008 Summer Contest
核心標籤：博弈論、威佐夫博弈、黃金分割、數學推導

遊戲規則與勝負判定

兩堆石子 (a, b)，a ≤ b ≤ 1,000,000。雙方輪流操作，可選：

1. 從任意一堆取走任意數量石子
2. 從兩堆同時取走相同數量石子

取走最後石子者勝。給定初始狀態，先手是否必勝？若必勝，列出所有第一步獲勝移動（優先輸出「同步取走」類型）。

威佐夫博弈核心理論：奇異局勢（P-position）

定義一系列有序對 (a_k, b_k)（k = 0, 1, 2...）：

• a_0 = b_0 = 0
• a_k 為未在前面出現過的最小自然數
• b_k = a_k + k

前幾項：(0,0), (1,2), (3,5), (4,7), (6,10)...

三大性質（證明略）

1. 任意自然數僅屬於唯一一個奇異局勢
2. 從奇異局勢出發，任意合法操作必變為非奇異局勢
3. 從非奇異局勢出發，存在至少一種操作可轉移到奇異局勢

結論：面對奇異局勢 = 必敗（P-position）；否則 = 必勝（N-position）。

黃金分割公式：O(1) 判定奇異局勢

令 φ = (1+√5)/2 ≈ 1.618（黃金比例），則：

a_k = ⌊k × φ⌋
b_k = a_k + k

給定 (a, b)，設 k = b - a，計算 a_k = ⌊k × φ⌋：

• 若 a_k == a → 奇異局勢 → 輸出 0
• 否則 → 必勝，需構造獲勝移動

構造所有第一步獲勝移動

必勝時需找出所有能轉移到某奇異局勢 (a_k, b_k) 的移動。四種可能來源：

1. 同步取走：a - a_k == b - b_k 且 a > a_k
2. 只取 b 堆（視 a 為奇異局勢的 a_k）：反推 k = ⌊2a/(1+√5)⌋ + 1
3. 只取 b 堆（視 a 為奇異局勢的 b_k）：反推 k = ⌊2a/(3+√5)⌋ + 1
4. 只取 a 堆（視 b 為奇異局勢的 b_k）：反推 k = ⌊2b/(3+√5)⌋ + 1

每種情況驗證反推出的 (a_k, b_k) 是否合法且滿足取石子約束，合法則輸出。

完整代碼關鍵片段

const double phi = (1.0 + sqrt(5.0)) / 2.0;
while (scanf("%d%d", &a, &b), a || b) {
    if (a > b) swap(a, b);
    if (a == 0) { printf("1\n0 0\n"); continue; } // 直接取光 b 堆
    
    int k = b - a;
    int ak = (int)(k * phi);
    if (ak == a) { printf("0\n"); continue; } // 奇異局勢
    
    printf("1\n");
    int bk = ak + k;
    // 1. 同步取走
    if (a - ak == b - bk && a > ak) printf("%d %d\n", ak, bk);
    // 2. 只取 b，a 為 a_k
    k = (int)(2.0 * a / (1 + phi)) + 1;
    bk = a + k; ak = (int)(k * phi);
    if (ak == a && b > bk) printf("%d %d\n", a, bk);
    // 3. 只取 b，a 為 b_k
    k = (int)(2.0 * a / (3 + phi)) + 1;
    bk = a; ak = (int)(k * phi);
    if (bk - k == ak) printf("%d %d\n", ak, a);
    // 4. 只取 a，b 為 b_k
    k = (int)(2.0 * b / (3 + phi)) + 1;
    bk = b; ak = (int)(k * phi);
    if (bk - k == ak && ak <= a && a != b) printf("%d %d\n", ak, b);
}

複雜度與精度注意

• 時間：O(1) 每測資，極快
• 精度：double 足夠支撐 1e6 範圍，若擴大至 1e9 需用 long double 或整數模擬
• 輸出順序：題目要求「同步取走優先」，代碼順序即滿足

威佐夫博弈是博弈論中極具美感的經典模型，掌握其黃金分割特性，可瞬間解決大量變體題目。