博弈論Nim取子問題，困擾千年的問題一行代碼解決

雲栖号資訊：【 點選檢視更多行業資訊

】

在這裡您可以找到不同行業的第一手的上雲資訊，還在等什麼，快來！

這個博弈問題非常古老，延續長度千年之久，一直到20世紀初才被哈佛大學的一個數學家找到解法，可見其思維的難度。但是這個問題本身卻很有意思，推導的過程更是有趣，哪怕你沒有多少資料基礎也一定可以看明白。

Nim取子問題

這個問題的題面是這樣的，我們有3堆石子，有A和B兩個人輪流從其中的一堆取石子。規定每個人每次最少取1顆，最多可以取完目前堆，無法繼續拿取石子的人落敗。請問如果你是先手，你有必勝政策嗎？

根據我們之前分析威佐夫博弈問題的套路，我們需要先來分析一下問題，找到一些典型的局面。比如說(0, 0, 0)對于先手來說一定是必敗的，同理，對于一個(0, n, n)的局面，也一樣是必敗的。因為不論先手怎麼取石子，後手隻需要在另外一堆石子當中如法炮制，那麼留給先手的依然是一個(0, n, n)的局面。在博弈論問題當中，我們通常會将先手必敗的局面稱為奇異局勢。

那麼這些奇異局勢之間有沒有什麼關聯呢？我們能不能找到這些局面之間的聯系或者是公式呢？

我們光是靠腦子想或者是用紙筆去羅列我們所能想到的奇異局面是很難想出來的，不然也不會困擾人們長達一千多年了。但是這個問題的謎底卻又如此簡單，簡單到讓人不可思議。

首先，我們先來思考一個問題，這個問題之是以複雜，根本原因在于石子有3堆，而不是兩堆。如果石子有兩堆，那麼就很容易了，先手除非面臨兩堆石子相等的情況，否則必勝。因為它可以通過拿取石子留下兩堆一樣的給後手，這樣不論後手如何拿取，先手隻需要在另一堆當中采取同樣的操作，就必然可以給後手留下奇異局勢。這和我們剛才分析的(0, n, n)的局面是一樣的。

但是題目明确說了是3堆而不是兩堆，我們不禁就開始設想起了一個問題，我們能不能想到一種政策，使得可以将三堆石子”轉化“或者是看成是兩堆石子呢？這樣我們就可以非常容易地判斷石子的輸赢情況了。

解法分析

明明是3堆石子，怎麼看成是兩堆呢？怎麼看都是自說自話，但如果你對二進制熟悉的話，你會發現這個問題可能并不是不可能的。

是的，二進制就是天生的二維“生物”，在二進制的世界當中，一切都隻有兩種，0和1。是以從直覺上我們會覺得，也許可以将石子的數量和二進制取得關聯。也許這樣的關聯會有助于我們找到解法。剩下的問題就成了，這個關聯究竟是什麼？

我們來思考另外一個問題，對于一堆石子來說，我們取走一個數量，石子的數量會減少，這是顯而易見的。展現在石子的總數上，就是表示這堆石子數量的數字，減去了另外一個數字。這個是減法的操作，國小生都知道。但是國小生不知道的是，減法在二進制當中是怎麼進行的，或者是它有什麼規律呢？

我們先不急着回答，先來仔細分析一波。首先，減數和被減數都可以化作是二進制，也就是若幹個1和0組成的數字。我們假設減數每一個為1的二進制位對應的被減數的值也是1，那麼這個減法會進行得非常順利。對應的就是從被減數當中移除掉若幹個1的過程。

舉個例子，被減數是9，減數是1。我們都知道9寫成二進制是1001，而1的二進制是1。是以被減數減去減數的值為8，也就是1000，可以看成是1001移除了末尾的1。

如果減數存在二進制位被減數為0，比如10 - 3的情況，10的二進制是1010，3是11。很明顯3的第0位是1，而10是0，這種情況下怎麼辦？首先，我們先把3和10當中都是1的二進制位去除。剩下的就是1000 減去 1，那麼我們可以先把1000 減1 變成111，這樣就回到了上面說的第一種情況，完成減法之後再加回來，是以得到的結果就是111，這其實就是一個向高位借位的過程。縱觀整個減法的計算過程，其實就是被減數當中二進制位變化的過程，減去某一個數，等價于将被減數當中若幹個0變成1，1變成0。

結合二進制，我們可以想到一種政策。就是統計這3個數所有的二進制位，由于我們有3個數，是以每一個二進制位最多有3個1，最少有0個1。如果每一位的1的數量和都是偶數，也就是不是0就是2的話，那麼這一定是一個奇異局面。

舉個例子，比如[10, 8, 2]是一個奇異局面，我們把它們寫成二進制。10的二進制是1010，8的二進制是1000，2的二進制是10。是以我們可以發現這三個數的二進制位加起來，第1、2、3位都出現了兩個1。這個時候先手不論如何操作，後手隻需要保證剩下的三個數的二進制位維持這個特性即可。這樣做可以保證最後一次拿取結束之後，給先手留下[0, 0, 0]的局面。本質上來說，它的原理和兩堆石子的時候是一樣的，隻不過轉化了一種形式。

舉個例子，比如我們從10當中拿走3顆石子，得到(7, 8, 2)，我們觀察二進制位分别是111, 1000, 10。會發現每一位1的數量從低到高分别是[1, 2, 1, 1]。是以我們可以從1000拿取3個石子，保證留下的數量是101，也就是5。這樣剩下的1的個數就是[2, 2, 2]，依然是偶數。是以先手不論如何拿，後手都可以保證一定可以讓留下的數字在二進制上保持偶數，先手一定必敗。在不滿足這個條件的局面當中先手一定必勝，因為先手可以在第一次通過拿取掉多餘的1，保證留下一個必敗的局面給後手。

這也是這題的解法，即通過二進制位來判斷是否先手必勝。我們要判斷每個二進制位當中出現的1的次數和是否是偶數，可以通過位運算的亦或來完成。在亦或操作當中，對每一個二進制位進行計算，奇數為1，偶數為0。是以我們隻需要計算一下這三堆石子亦或之後的結果是否為0，就可以知道是否每一個二進制位的1的數量是否都是偶數了。

我們寫成代碼非常簡單，我們通常用^這個符号表示亦或運算，那麼代碼隻需要一行：

def win_or_lose(a, b, c):
    return (a ^ b ^ c) == 0           

推廣以及證明

這裡還沒有結束，我們同樣可以将3堆石子的局面推廣到n堆，不管遊戲當中玩家面臨的是多少堆石子，這個結論依然都是成立的。這個成立的原因我們很容易想明白，為了嚴謹起見，我們可以用博弈問題常用的證明套路來證明一下。

在一個博弈問題當中，如果存在奇異局面，也就是必敗局面，那麼一定滿足三個條件。第一個條件是無法進行任何操作的局面是奇異局面。第二個條件是可以移動到奇異局面的局面是非奇異局面。第三個條件是在奇異局面當中所作的任何操作得到的都是非奇異局面。

隻要能夠證明這三點，就可以證明我們的思路是正确的。

對于第一點毋庸置疑，所有石堆都沒有石子的時候無法移動，這是必敗狀态。

我們來看第二個條件，我們假設這n堆石子的數量是a1, a2, ... an。如果目前局面是非奇異局面，根據我們的理論，那麼a1 ^ a2 ^ a3 ^... ^an > 0。也就是說存在某個二進制位1的數量是奇數。

我們假設a1 ^ a2 ^ a3 ^... ^an = k，那麼必然可以找到一個ai, 使得它的二進制表示在k的最高位上是1，因為k的所有二進制的1都是從這n個數當中來的，是以這樣的ai一定存在。那麼我們可以繼續推導得到：ai ^ k < ai。因為最高位的1經過亦或之後變成了0，是以亦或操作之後一定是減小的。我們令p = ai ^ k，我們在a1^a2^a3^...^an = k 的等式兩邊同時亦或ai，可以得到a1 ^ a2 ^ ...^ai-1^ai+1^...^an = k ^ai，是以a1 ^ a2 ^ ...^ p ^...an = 0。

第三個條件也很好證明，因為如果目前是必敗局面，也就是說a1 ^ a2 ^ ... ^ an=0。我們假設我們将an轉變成了p之後依然有a1 ^ a2 ^ ... ^p=0, p < an。我們在等式兩邊同時亦或上p和an，可以得到：an ^ p = 0，也就是說p = an。這與p < an沖突，是以不存在這樣的轉化使得奇異局面操作之後仍然是奇異局面。

這樣我們就從數學上證明了這個推理的正确性，實際上已經有人對Nim取子問題有過深入的研究，這也是一個已經得到過證明的定理，叫做Bouton定理。定理的内容是先手可以在非平衡的Nim博弈中取勝，而後手可以在平衡的Nim博弈中取勝。這裡的平衡就是指的是所有二進制位1的數量是偶數。

那麼我們寫出代碼也非常簡單：

def win_or_lose(nums):
    ret = 0
    for i in nums:
        ret ^= i
    return ret == 0           

總結

到這裡，關于Nim博弈的問題就講完了。通過亦或操作去判斷的解法真的是非常簡單，但是這其中的推導過程想明白卻不容易。我看過很多部落格，都是直接給出的亦或這個結論，很少能夠看到詳細的推導過程。直接記住結論是簡單的，但也很容易忘記，隻有親自推導一遍，才會明白亦或這個神奇的操作是怎麼來的，為什麼它可以解決Nim博弈的問題。

在整個思考推理和證明的過程當中，我們大量使用了亦或這個位運算操作，如果對它不熟悉的同學可能會看起來有些困擾。建議可以先了解學習一下二進制當中亦或的性質之後再來閱讀本文，效果會更好。

目前為止，我們已經介紹完了巴什博奕、威佐夫博弈和Nim博弈這三種相對比較簡單的博弈模型。在後續的文章當中，我們将會繼續深入博弈論這個問題，一起去研究更加困難的博弈論問題，看看在複雜的場景當中，我們怎麼樣尋找奇異狀态。

【雲栖号線上課堂】每天都有産品技術專家分享！

課程位址：

https://yqh.aliyun.com/live

立即加入社群，與專家面對面，及時了解課程最新動态！

【雲栖号線上課堂 社群】

https://c.tb.cn/F3.Z8gvnK

原文釋出時間：2020-06-30

本文作者：承志

本文來自：“

掘金

”，了解相關資訊可以關注“掘金”