在我小時候以前做題的時候，遇到博弈題往往都是漫無目的地打表找規律，或者找一些特殊情況但是沒有很好的分析方法，
其實博弈題是有比較套路的解題方法的，那就是利用SG函式，第一節不會講到SG函式的具體用法，我們先來博弈入個門，學習一下最基本的博弈型別：Nim游戲，
?? 作者：Eriktse
?? 簡介：19歲，211計算機在讀，現役ACM銀牌選手??力爭以通俗易懂的方式講解演算法！??歡迎關注我，一起交流C++/Python演算法，（優質好文持續更新中……）??
?? 閱讀原文獲得更好閱讀體驗：https://www.eriktse.com/algorithm/1110.html
巴什博奕
在進入Nim游戲之前，我們先看一個簡單的博弈：巴什博奕，
看這道例題：http://acm.hdu.edu.cn/showproblem.php?pid=1846
由于HDUOJ經常打不開，我這里復制一下題意：
1、 本游戲是一個二人游戲;
2、 有一堆石子一共有n個；
3、 兩人輪流進行;
4、 每走一步可以取走1…m個石子；
5、 最先取光石子的一方為勝；
如果游戲的雙方使用的都是最優策略，請輸出哪個人能贏，
假設此時的n = 10, m = 3，我們來分析一下這個局面，
我們設一個布爾函式f(x)，表示當n = x時的輸贏，
- f(0) = 0，因為無法繼續操作了，顯然是0，也就是說這是一個必敗態，
- f(1) = 1，可以取走一個石子，使對手陷入必敗態，所以這是一個必勝態，
- f(2) = 1，可以取走兩個，
- f(3) = 1，可以取走三個，
- f(4) = 0，無論取走一個、兩個或三個都必然使得對手進入必勝態，所以這是一個必敗態，
- f(5) = 1
- f(6) = 1
- f(7) = 1
- f(8) = 0，無論取走一個、兩個或三個都必然使得對手進入必勝態，所以這是一個必敗態，
- f(9) = 1
- f(10) = 1
至此，我們得到了答案，f(n) = f(10) = 1所以先手必勝，不難發現上面這個函式f(x)的規律，僅當x % 4 == 0時為0，其余情況都為1，
于是我們只需要判斷n % (m + 1)是否為0就能判斷先手是否獲勝，
這就是巴什博奕模型，是不是很簡單，我們簡單打個表就找到了規律，
Nim游戲
依然看這道例題：https://www.luogu.com.cn/problem/P2197
我們這么分析：
敗局一定是全為0的情況，此時所有數字的異或和為0（不知道怎么寫異或和的latex，大家湊合著看）：
\[\oplus_{i=1}^{n}a_i = 0 \]那么想一下那些狀態可以到這個敗局呢？我們反向的思考，往任意一個位置加上一個數字，就可以作為前一個狀態，也就是一個必勝態（因為那個狀態必然可以到達敗局的狀態），
往任意一個位置加上一個數字之后就必然有：
\[\oplus_{i=1}^{n}a_i \ne 0 \]再想一下，從一個異或和不為0的狀態，是否一定有辦法轉移到一個異或和為0的狀態，
不難發現是一定可以的，
舉個栗子：
我們有4堆石子，數量分別為：1 7 2 6，這是我隨便寫的一個資料，
它們的異或和為：1 ^ 7 ^ 2 ^ 6 = (0 1 0)，那么我可以通過調整2 -> 0使得異或和為0，現在有1 ^ 7 ^ 0 ^ 6 = 0，當然我還可以通過6 -> 4，異或和結果也是0，
不難發現，只需要從陣列中找一個最高非零位大于等于異或的結果的最高非零位的數字，然后減少一部分就可以，這樣的數是一定存在的，
那么也就是說任意一個異或和非零的狀態都可以通過一步轉移到異或和為0的狀態，任意一個異或和為0的狀態不管怎么走一步，都必然轉移到異或和非0的狀態，
而石子的個數是一直減小的，最終一定會走到全0，異或和為0的狀態且一定是敗局，
也就是說：
必勝態W(win)：異或和非0;
必敗態L(lose)：異或和為0;
以上就是Nim游戲模型，當然你也可以叫他Nim博弈，
這一節先了解這些，下一節將會講解SG函式的轉移和子游戲的合并，
?? 本文由eriktse原創，創作不易，如果對您有幫助，歡迎小伙伴們點贊??、收藏?、留言??
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/549662.html
標籤：其他