【學習筆記】博弈論

• 2022 年 8 月 2 日
• 筆記
• 學習筆記

博弈論基(寄)礎

幾個基本的知識

有限博弈

• 先手必勝當且僅當先手將當前狀態變為先手必敗態
• 先手必敗當且僅當先手不能將當前狀態變為先手必敗態

有向無環圖博弈

• 給定一個 \(\text{DAG}\)，初始 \(1\) 號點有一個棋子，小 \(A\) 和小 \(B\) 可以將棋子沿出邊移動一次，最後無法移動的為輸者。

SG 函數

• 基本描述：

  • 對於有向無環圖博弈，\(SG(i) = \text{mex}(SG(j)|edge(i,j) \in E)\)，\(\text{mex}\) 即未出現過的最小非負整數。則先手必勝則意味著 \(SG(1) \not= 0\)，也就是 \(SG(1) = 0\) 意味著先手必敗態。

  • 證明： 我們將分以下三個部分證明，\(SG(1) \not= 0\) 時先手必勝：

    • 最終態是必敗態：
      • 顯然最終態就是無法移動，也就是 \(SG = 0\)，也就是必敗態。
    • 必勝態可以走向必敗態：
      • 若 \(SG(1) \not= 0\)，意味著我們可以走向 \(SG = 0\) 的點，也就是可以走向必敗態
    • 必敗態只能走向必勝態：
      • 當 \(SG(1) = 0\) 時，顯然不能走到 \(SG = 0\) 的點，所以只能走向必勝態

子遊戲

• 問題描述：

  • 給定 \(m\) 個 \(\text{DAG}\)，小 \(A\) 和小 \(B\) 每次可以選擇一個 \(\text{DAG}\)，並將其上的棋子沿出邊移動一次，移動不了為輸。

  • SG定理： 先手必勝當且僅當每個 \(\text{DAG}\) 的起點的 \(SG\) 的異或值不等於 \(0\)

  • 證明： 依舊分以下三個部分證明：

    • 最終態是必敗態：
      • 最終態就是無法移動，所有的 \(SG\) 都等於 \(0\)，顯然是必敗態
    • 必勝態可以走向必敗態：
      • 若 \(\oplus_{i=1}^m SG(i) = a \not= 0\)，顯然我們可以通過某個 \(\text{DAG}\) 上走一步，使得 \(\oplus_{i=1}^m SG(i) = 0\)，也就是可以走向必勝態。因為我們最終的答案裡面的每一個 \(1\)，肯定都可以通過在某一個 \(\text{DAG}\) 上走一步，使得答案除去當前起點的值導致最高位消掉，我們再走到含有剩下的 \(1\) 的點，這樣加入貢獻之後這些 \(1\) 也消掉了。
    • 必敗態只能走向必勝態：
      • 顯然無法移動一步，使得移動後的 \(SG\) 的異或和等於現在的異或和，也就是一定走向必勝態。

Nim 遊戲

Nim 遊戲

• 題目描述：

  • 有 \(n\) 堆石子，第 \(i\) 堆石子有 \(a_i\) 個，\(A\) 和 \(B\) 每次可以從任意一堆中取出至少一個，不能取的人為輸，請問誰有必勝策略。

• 題目分析：

  • 顯然每一堆石子都是一個子遊戲，我們可以以石子數為\(\text{DAG}\)上的點，那麼對於起點 \(i\) 它的 \(SG\) 顯然等於 \(a_i\)，因為我們可以將圖理解為如下樣子：

  • 

  • 顯然從底向上 \(SG\) 值依次為：\(0,1,2,3\)。注意最底端的節點代表 \(0\) 個石子。

例題

• 題目描述：

  • 給定 \(n\) 行，第 \(i\) 行的長度為 \(a_i\)，每行最左邊有一顆白子，最右邊有一顆黑子， \(A\) 可以移動白子，\(B\) 可以移動黑子，不能跨過對方的棋子，不能移動為輸。

• 題目分析：

  • 我們棋子向邊上走肯定不優，因為根據模仿的思想，假設白子向左移 \(x\)，那麼黑子也可以向左移 \(x\)，這樣顯然使得白子的局勢不會更優。那麼我們就考慮向中間走 \(1\)，就理解為拿一顆石子，那麼對於第 \(i\) 行就是相當於有 \(a_i – 2\) 個石子，也就是成為了我們的 Nim 遊戲。

K-Nim 遊戲

• 題目描述：

  • 有 \(n\) 堆石子，第 \(i\) 堆石子有 \(a_i\) 個，\(A\) 和 \(B\) 輪流進行操作，每次操作最多可以選擇 \(K\) 堆石子每堆石子拿至少一個，不能取的人為輸，問誰有必勝策略。

  • 定理： 將 \(a_i\) 按二進位拆分，若每個二進位位上為 \(1\) 的個數對 \(K + 1\) 取模等於 \(0\)，則先手必敗

  • 證明：

    • 最終態是必敗態：顯然最終態為必敗態，因為已經全部取完了
    • 必勝態可以走向必敗態：
      • 假設我們已經改變了 \(m\) 堆，使得第 \(i\) 位之前的位都是 \(K+1\) 倍數，那麼就要找到一種方式使得第 \(i\) 位也是 \(K + 1\) 的整數倍。顯然對於考慮完的 \(m\) 堆，我們可以任意的選擇其第 \(i\) 位是 \(0\) 或 \(1\)，那麼我們記不考慮這 \(m\) 堆，剩下的堆里第 \(i\) 位 \(1\) 的個數為 \(sum\)。
        • 若 \(sum \le K – m\)，顯然可以將這 \(sum\) 個 \(1\) 都變成 \(0\)，然後將 \(m\) 堆的 \(1\) 也都變成 \(0\)。這樣就相當於第 \(i\) 位的總數為 \(0\)，符合條件。
        • 若 \(sum > K – m\)，我們在這 \(m\) 堆里，選出 \(K + 1 – sum\) 堆變成 \(1\)，這樣兩者一加就是 \(K+1\) 個 \(1\)，符合條件。化簡一下就能得到 \(K + 1 – sum \le m\)
    • 必敗態只能走向必勝態：
      • 我們每次最多將某一個二進位位上的 \(1\) 改變 \(K\) 個，最少將某一個二進位位上的 \(1\) 改變 \(1\)，因為我們最少改變一堆最多改變 \(K\) 堆。因為我們原來的每一個二進位位都是 \(K+1\) 的倍數，所以我們更改之後一定不都是，即一定是必勝態。

例題

• 題目來源：

  • [SDOI2011]黑白棋

• 題目分析：

  • 這個題其實最麻煩的是證明 K-Nim 遊戲，不過我證了
    我們考慮如果初始狀態給定，那麼這就是一個 K-Nim 遊戲，我們依舊將距離視為石子也就能發現了。然後根據 K-Nim 遊戲的過程，我們可以想出一個顯然巨難的狀態：\(dp[i][j]\) 表示前 \(i-1\) 位取模後全部是 \(0\)，當前放了 \(j\) 個棋子的方案數，也就是先手必輸的方案數。
  • 那麼轉移就是我們枚舉第 \(i\) 位是 \(d + 1\) 的多少倍，然後也就是從這 \(\dfrac{k}{2}\) 個堆里，選 \(x(d + 1)\) 個，也就是乘一個組合數 \(\binom{\frac{k}{2}}{x(d + 1)}\)，然後我們最後還要搞一下這些堆在哪裡，也就是乘 \(\binom{n – i – \frac{k}{2}}{\frac{k}{2}}\)

反 Nim 遊戲

• 題目描述：
  • 有 \(n\) 堆石子，第 \(i\) 堆石子的個數為 \(a_i\)，\(A\) 和 \(B\) 輪流從一堆中選擇至少一個石子，取到最後一個的人為輸，問誰有必勝策略。
• 題目分析：

  • Anti-SG定理： 假設當所有子遊戲的 \(SG\) 均為 \(0\) 時遊戲結束，那麼滿足如下條件之一先手必勝：

    • 所有子遊戲的 \(SG\) 的異或和不為 \(0\)，且某個遊戲的 \(SG\) 值大於 \(1\)
    • 所有子遊戲的 \(SG\) 的異或和為 \(0\)，且所有遊戲的 \(SG\) 值都小於等於 1

  • 證明：

    • 我們定義如下的四個狀態：
      • \(A\)：\(SG\) 的異或和等於 \(0\)，且存在某個遊戲的 \(SG\) 大於 \(1\)（先手必敗）
      • \(B\)：\(SG\) 的異或和等於 \(0\)，且任意遊戲的 \(SG\) 小於等於 \(1\)（先手必勝）
      • \(C\)：\(SG\) 的異或和不等於 \(0\)，且存在某個遊戲的 \(SG\) 大於 \(1\)（先手必勝）
      • \(D\)：\(SG\) 的異或和不等於 \(0\)，且任意遊戲的 \(SG\) 小於等於 \(1\)（先手必敗）
    • 最終態是必勝態：
      • 因為最終態就是所有的子遊戲 \(SG\) 值都為 \(0\)，顯然此時先手必勝
    • 必勝態可以走向必敗態：
      • 若滿足狀態 \(C\)
        • 若只有一個遊戲的 \(SG\) 大於 \(1\)，那麼顯然可以將這個遊戲的 \(SG\) 值變成 \(0\) 或 \(1\)，而我們 \(SG\) 的異或和不為 \(0\)，所以就走到了狀態 \(D\)，必敗態。
        • 若有多個遊戲的 \(SG\) 大於 \(1\)，則可以使用類似 \(SG\) 定理的推導過程，將 \(SG\) 的異或和變為 \(0\)，且存在某個遊戲的 \(SG\) 大於 \(1\)，即走到了狀態 \(A\)，必敗態
      • 若滿足狀態 \(B\)
        • 若到達終止條件，即全是 \(0\)，則直接勝利並終止遊戲
        • 若某個遊戲的 \(SG\) 值為 \(1\)，則將這個值變為 \(0\)，那麼就到達了狀態 \(D\)，必敗態
    • 必敗態必須走向必勝態
      • 若滿足狀態 \(A\)
        • 若多個遊戲的 \(SG\) 值大於 \(1\)，顯然只能轉化為狀態 \(C\)，必勝態。因為此時 \(SG\) 的異或值不可能為 \(0\)，而且也存在某個遊戲的 \(SG\) 值大於 \(1\)
        • 若只有一個遊戲的 \(SG\) 值大於 \(1\)，顯然這種條件下不可能導致 \(SG\) 的異或值不等於 \(0\)
      • 若滿足狀態 \(D\)
        • 若將某一個 \(SG\) 值為 \(1\) 的遊戲的 \(SG\) 值改為 \(0\)，顯然對於 \(SG\) 的異或和是取反的，因為原來異或的值只有 \(1\) 或 \(0\)，異或之後依舊是 \(1\) 或 \(0\)，這樣就會到達狀態 \(B\)，必勝態。
        • 若將一個 \(SG\) 值為 \(0\) 的遊戲的 \(SG\) 值改為 \(1\)，顯然也是取反，會到達狀態 \(B\)，必勝態.
        • 若將一個 \(SG\) 值為 \(0\) 的遊戲的 \(SG\) 值改為大於 \(1\) 的值，顯然會到達狀態 \(C\)，必勝態。因為此時顯然 \(SG\) 異或和不會等於 \(0\)，而有的遊戲的 \(SG\) 值大於 \(1\)。

階梯博弈

• 題目描述：
  • 有 \(n\) 個階梯呈編號升序排列，每個階梯上有若干個石子，可行的操作是將一個階梯上的石子移至少一個到前一個台階。當沒有可行操作時，即所有石子都被移動到了地面（第 \(0\) 號台階）輸。
• 題目分析：

  • 定理： 階梯博弈相當於奇數號台階的 Nim 遊戲，即當奇數號台階上的石子數的異或和不為 \(0\) 時，先手必勝。

  • 證明：

    • 最終態是必敗態：
      • 顯然最終態是所有的石子數為 \(0\)，僅考慮奇數也是必敗態
    • 必勝態可以走到必敗態：
      • 我們一定可以把某一些石子放到偶數堆上，也就是能使得奇數堆的異或和為 \(0\)，即走到必敗態
    • 必敗態必定走到必勝態：
      • 顯然我們無法通過調整石子數使得異或和保持 \(0\) 不變，所以必敗態必定會走到必勝態。

例題

• 題目描述
  • 給定 \(n\) 堆石子，第 \(i\) 堆石子的個數為 \(a_i\) 個，保證初始石子數單調不降，\(A\) 和 \(B\) 輪流操作，每次可以從某一堆石子中移走至少一個，需要滿足在任意時刻石子數均單調不降，不能取的人輸。
• 題目分析
  • 對石子數差分，然後倒序編號，也就相當於階梯博弈的模型。