LeetCode 292. Nim 遊戲：博弈論與位運算解法

LeetCode 292. Nim 遊戲

遊戲規則

• 一堆石子，共 n 顆。
• 雙方輪流取石子，每次可取 1~3 顆。
• 取走最後一顆石子者獲勝。
• 你先手，雙方均採取最優策略。

核心洞察：模 4 律

分析小數值發現規律：

結論：n % 4 == 0 時先手必敗，否則先手必勝。

代碼實現

bool canWinNim(int n) {
    return n % 4 != 0;
    // 等價位運算寫法
    // return n & 0x03;
}

博弈論視角

• 「必勝態」：存在至少一種移動轉移到「必敗態」。
• 「必敗態」：所有移動均轉移到「必勝態」。
• 終態 n=0 為必敗態（輪到你時無石子可取）。
• 遞推可證：n % 4 == 0 為必敗態，其餘為必勝態。

擴展：任意取 1~k 顆

若每次可取 1~k 顆，則 n % (k+1) == 0 為先手必敗態。本題 k=3，故模 4。

總結

Nim 遊戲是組合博弈論入門經典，掌握「模 (k+1) 律」與位運算技巧（n & k 當 k+1 為 2 的冪次時），可 O(1) 解決此類取石子遊戲問題。