演算法中的一些數學問題分享，ICG游戲

1，石子游戲

題目出處
https://leetcode-cn.com/problems/stone-game/
亞歷克斯和李用幾堆石子在做游戲，偶數堆石子排成一行，每堆都有正整數顆石子 piles[i] ，

游戲以誰手中的石子最多來決出勝負，石子的總數是奇數，所以沒有平局，

亞歷克斯和李輪流進行，亞歷克斯先開始， 每回合，玩家從行的開始或結束處取走整堆石頭， 這種情況一直持續到沒有更多的石子堆為止，此時手中石子最多的玩家獲勝，

假設亞歷克斯和李都發揮出最佳水平，當亞歷克斯贏得比賽時回傳 true ，當李贏得比賽時回傳 false ，
思路：常見的為動態規劃演算法，輪流去很容易想到遞回，然后用動態規劃優化，定義二維陣列 dp，其行數和列數都等于石子的堆數，元素表示當石子堆的元素剩從i到j時，狀態轉移方程如下
dp[i][j]=max(piles[i]?dp[i+1][j],piles[j]?dp[i][j?1])

class Solution {
    public boolean stoneGame(int[] piles) {
        int length = piles.length;
        int[][] dp = new int[length][length];
        for (int i = 0; i < length; i++) {
            dp[i][i] = piles[i];
        }
        for (int i = length - 2; i >= 0; i--) {
            for (int j = i + 1; j < length; j++) {
                dp[i][j] = Math.max(piles[i] - dp[i + 1][j], piles[j] - dp[i][j - 1]);
            }
        }
        return dp[0][length - 1] > 0;
    }
}

另一種方法為數學思路
假設有 nnn 堆石子，nnn 是偶數，則每堆石子的下標從 000 到 n?1n-1n?1，根據下標將 nnn 堆石子分成兩組，每組有 n2\frac{n}{2}2n? 堆石子，下標為偶數的石子堆屬于第一組，下標為奇數的石子堆屬于第二組，
在此種狀態下，作為先手的人可以選擇自己拿奇陣列還是偶陣列（拿第一個還是最后一個），后手只能根據先手的選擇來進行選擇，無論后手怎么選擇，他拿到的都是奇陣列或者偶陣列，即先手可以選擇自己拿奇陣列或者偶陣列中較大的一組，則先手必贏

class Solution {
    public boolean stoneGame(int[] piles) {
        return true;
    }
}

2，黑板異或游戲
https://leetcode-cn.com/problems/chalkboard-xor-game/
黑板上寫著一個非負整數陣列 nums[i] ，Alice 和 Bob 輪流從黑板上擦掉一個數字，Alice 先手，如果擦除一個數字后，剩余的所有數字按位異或運算得出的結果等于 0 的話，當前玩家游戲失敗， (另外，如果只剩一個數字，按位異或運算得到它本身；如果無數字剩余，按位異或運算結果為 0，）

并且，輪到某個玩家時，如果當前黑板上所有數字按位異或運算結果等于 0，這個玩家獲勝，

假設兩個玩家每步都使用最優解，當且僅當 Alice 獲勝時回傳 true，

思路
對于本題，給定的是判斷「勝利」的規則（在給定序列的情況下，如果所有數值異或和為 000 可立即判斷勝利，其他情況無法立即判斷勝負），那么我們應該優先判斷何為「先手必勝態」，如果不好分析，才考慮分析后手的「必敗態」，

接下來是分情況討論：

1. 如果給定的序列異或和為 000，游戲開始時，先手直接獲勝：

由此推匯出性質一：給定序列 nums 的異或和為 000，先手處于「必勝態」，回傳 True，
2. 如果給定序列異或和不為 000，我們需要分析，先手獲勝的話，序列會滿足何種性質：

顯然如果要先手獲勝，則需要滿足「先手去掉一個數，剩余數值異或和必然不為 0；同時后手去掉一個數后，剩余數值異或和必然為 000」，

換句話說，我們需要分析什么情況下「經過一次后手操作」后，序列會以上述情況 1 的狀態，回到先手的局面，

也就是反過來分析想要出現「后手必敗態」，序列會有何種性質，

假設后手操作前的異或和為 Sum（Sum/0），「后手必敗態」意味著去掉任意數字后異或和為 000，

同時根據「相同數值異或結果為 000」的特性，我們知道去掉某個數值，等價于在原有異或和的基礎上異或上這個值，
則有：Sum′=Sum⊕nums[i]=0

由于是「后手必敗態」，因此 iii 取任意一位，都滿足上述式子，

則有：

Sum⊕nums[0]=…=Sum⊕nums[k]=…=Sum⊕nums[n?1]=0Sum ⊕ nums[0] = … = Sum ⊕ nums[k] = … = Sum ⊕ nums[n - 1] = 0 Sum⊕nums[0]=…=Sum⊕nums[k]=…=Sum⊕nums[n?1]=0

同時根據「任意數值與 0 異或數值不變」的特性，我們將每一項進行異或：

(Sum⊕nums[0])⊕…⊕(Sum⊕nums[k])⊕…⊕(Sum⊕nums[n?1])=0(Sum ⊕ nums[0]) ⊕ … ⊕ (Sum ⊕ nums[k]) ⊕ … ⊕ (Sum ⊕ nums[n - 1]) = 0 (Sum⊕nums[0])⊕…⊕(Sum⊕nums[k])⊕…⊕(Sum⊕nums[n?1])=0

根據交換律進行變換：

(Sum⊕Sum⊕…⊕Sum)⊕(nums[0]⊕…⊕nums[k]⊕…⊕nums[n?1])=0(Sum ⊕ Sum ⊕ … ⊕ Sum) ⊕ (nums[0] ⊕ … ⊕ nums[k] ⊕ … ⊕ nums[n - 1]) = 0 (Sum⊕Sum⊕…⊕Sum)⊕(nums[0]⊕…⊕nums[k]⊕…⊕nums[n?1])=0

再結合 SumSumSum 為原序列的異或和可得：

(Sum⊕Sum⊕…⊕Sum)⊕Sum=0,Sum≠0(Sum ⊕ Sum ⊕ … ⊕ Sum) ⊕ Sum = 0 , Sum \neq 0 (Sum⊕Sum⊕…⊕Sum)⊕Sum=0,Sum?=0

至此，我們分析出當處于「后手必敗態」時，去掉任意一個數值會滿足上述式子，

根據「相同數值偶數次異或結果為 0」的特性，可推匯出「后手必敗態」會導致交回到先手的序列個數為偶數，由此推導后手操作前序列個數為奇數，后手操作前一個回合先手為偶數，

到這一步，我們推匯出想要出現「后手必敗態」，先手操作前的序列個數應當為偶數，

那么根據先手操作前序列個數為偶數（且異或和不為 0），是否能夠推匯出必然出現「后手必敗態」呢？

顯然是可以的，因為如果不出現「后手必敗態」，會與我們前面分析程序矛盾，

假設先手操作前異或和為 XorXorXor（序列數量為偶數，同時 Xor≠0Xor \neq 0Xor?=0），如果最終不出現「后手必敗態」的話，也就是先手會輸掉的話，那么意味著有 Xor⊕nums[i]=0Xor ⊕ nums[i] = 0Xor⊕nums[i]=0，其中 iii 為序列的任意位置，利用此性質，像上述分析那樣，將每一項進行展開異或，會得到奇數個 XorXorXor 異或結果為 0，這與開始的 Xor!=0 矛盾，

由此推匯出性質二：只需要保證先手操作前序列個數為偶數時就會出現「后手必敗態」，從而確保先手必勝，

綜上，如果序列 nums 本身異或和為 0，天然符合「先手必勝態」的條件，答案回傳 True ；如果序列 nums 異或和不為 0，但序列長度為偶數，那么最侄訓出現「后手必敗態」，推匯出先手必勝，答案回傳 True，
對于這兩種題型的共同點為很容易想到dp，但是仔細想想會發現有點類似于井字棋，都存在先手必勝或必敗的情況，具體描述參考如下，

百度搜索ICG博弈, ICG博弈是這類博弈的總括性理論. 這類博弈的核心特征在于, 只根據初始狀態就可以判斷雙方的輸贏情況
看對一些同學有幫助, 順便把我自己的總結放在這里.
經典的Bash, Wythoff 以及Nim博弈問題, 都屬于所謂的公平組合博弈(Impartial Combinatorial Games, ICG), ICG具有的的特征/性質如下(用局勢(position)描述游戲中的一個狀態):
兩人參與, 輪流進行, 有限步內結束.
position空間只能劃分為兩個部分: 奇異局勢(P-position)空間和非奇異局勢(N-position)空間.
面對同一position, 兩人具有相同的合法操作集合; 即選手的操作只與position有關而與選手無關.
對于任一P-position, 任意的合法操作都會使其變成N-position; 對于任一N-position至少存在一種合法操作使其變為P-position. (position空間的劃分要滿足此性質)
結束局勢(E-position)定義為N-position空間中的一些, 面對它的選手贏; 或者定義為P-position空間中的一些, 面對它的選手輸. (面對是指上一位選手操作完畢, 輪到當前選手, 而當前選手還未操作)
如果一個游戲滿足上述性質, 即為ICG游戲. 那么由于P-position/N-position之間的這種轉換關系(性質4), 我們就能, 只根據初始局勢就可以判斷雙方的輸贏情況. 通常判斷先手是否贏, 先手贏的條件是初始局勢為N-position.
啟示: 面對一個博弈論(Game theory)問題, 我們可以大膽猜測它是一個ICG問題. 然后通過輸贏關系找出一些N-position和P-position, 并嘗試劃分出各自的空間. 最后, 證明第4個性質. 當然在比賽中, 如果比較難證明, 我們可以直接通過提交代碼來測驗.