一種對弈游戲的取勝算法

李曉明

談到“對弈游戲”，我們很容易馬上想到的是各種棋藝。說到棋藝，簡單的有對角棋，復(fù)雜的有象棋、圍棋等。編寫會下棋的計算機程序，幾乎是計算機創(chuàng)始之初人們就有的追求。1958年，在中國的哈爾濱工業(yè)大學(xué)，曾經(jīng)就研制出一臺“能說話，會下棋”的模擬計算機（如圖1）。

1997年，IBM的深藍戰(zhàn)勝了國際象棋大師卡斯帕羅夫，引起一陣轟動。2016年，谷歌的AlphaGo戰(zhàn)勝了圍棋世界冠軍李世石，讓人們終于見證了計算機在棋藝領(lǐng)域已經(jīng)可以穩(wěn)定表現(xiàn)出高于人類的智能。這極大地提振了人們對計算機智能應(yīng)用的信心，人工智能迎來了一個新的發(fā)展高潮。

計算機表現(xiàn)出來的任何智能的核心都是算法：有的是若干經(jīng)驗規(guī)則的編碼（如中醫(yī)診斷），有的是基于自然界或社會生活帶來的啟發(fā)式（如陳道蓄教授在本專欄前面介紹過的模擬退火），有的需要先從大量數(shù)據(jù)中學(xué)習(xí)出一些模式（如當下廣泛應(yīng)用的人臉識別），還有的則可能是基于對問題的深刻理解形成的小巧精妙的計算。下面要討論的一種兩個人玩的對弈游戲，就是后面這種情形的一個實例。①

● 游戲介紹

也許讀者玩過下面這個游戲：有兩堆棋子，第一堆3顆，第二堆5顆。兩人輪流拿，每次只能從一堆中拿，至少拿一顆，拿到最后一顆棋子的為勝者。假設(shè)你是先手，希望獲勝。該怎么拿？

如果你一次把第二堆全拿走，對手則可以接著把第一堆全拿走，他勝了。如果你第一次只從第二堆拿走4顆，留下1顆，對手則可以接著從第一堆拿走2顆，留下1顆。你發(fā)現(xiàn)又要輸了。不過稍微想一想，你馬上能意識到這里的制勝法則：總給對方留下棋子數(shù)相同的兩堆。于是，你從第二堆拿走2顆作為開始，剩下（3，3）。后面，對手從某一堆拿走幾顆，你就從另一堆拿走幾顆。兩個回合下來，對手就會認輸了。顯然，如果初始第一堆和第二堆棋子數(shù)分別是n1和n2，只要n1≠n2，你作為先手按照上面的策略就能保證贏。而如果n1=n2，你作為先手就只能隨便拿幾顆，把贏的希望寄托在對手不明白這法則了。

下面，我們前進一步：考慮有三堆棋子（如下頁圖2），數(shù)量記為（3，5，7）。規(guī)則一樣，目標也一樣，你是先手，該怎么拿？

顯然，你不應(yīng)該一開始就拿走一整堆，那樣就讓對方處于在兩堆情形下的先手優(yōu)勢了。好，那你就從第三堆里拿走6顆，給他留1顆，于是變成（3，5，1）。可如果他的應(yīng)對是從第二堆里拿走3顆，留下2顆，成為（3，2，1），你接著該怎么辦呢？稍微想一想，你會發(fā)現(xiàn)該認輸了！

于是你面對兩個問題。第一，在這個對弈游戲中，是否存在一個先手勝的法則？第二，如果存在，它是什么？

● 一般情形下的通解

下面，我們來討論這個問題的最一般的形式，然后看到對這個問題的解可以用一個小小的程序?qū)崿F(xiàn)為“AI”，作為游戲的一方，你可以找一個朋友來和它玩，它不保證一定贏，但只要抓住了對手的“破綻”，它就不客氣了。

問題描述：給定m堆棋子，分別有n1，n2，……，nm顆，ni≥1。兩個玩家輪流從中取棋子，每次只能從一堆拿，至少拿一顆，誰拿最后一顆誰為勝。②是否存在先手勝的條件？如果存在，它是什么？

讓我們先看看m=2的情形。其實前面已經(jīng)有解了，即先手勝的條件是n1≠n2，做法是總讓兩堆棋子相等。讓我們再細細體會一下。

這里，n1和n2是否相等是關(guān)鍵。有兩個層次的含義。如果不相等，先手就可將局面做成相等，后手返回的局面則一定是不相等的，于是可以一直在這種交替性質(zhì)下繼續(xù)。先手做的總是“不相等”→“相等”，后手則總是“相等”→“不相等”。而結(jié)束的局面是兩堆都為0，是相等局面，因此必由先手導(dǎo)致，也就是先手拿了最后一顆棋子。而如果n1=n2，由于每次至少要拿走一顆棋子且只能從一堆拿，先手給出的局面只能是兩堆不相等的，也就是不得不讓后手得到上述有利局面。

現(xiàn)在我們面對的是m>2個數(shù)，n1，n2，……，nm。相等與否，這種最簡單的計算概念已經(jīng)不好用了。但在這m個數(shù)中能不能建立一種計算，在某種性質(zhì)上呈現(xiàn)滿足與否的狀態(tài)，一旦先手發(fā)現(xiàn)這種性質(zhì)滿足，他總能通過從某一堆中拿掉若干棋子，使得剩下的數(shù)之間不再滿足該性質(zhì)，并且后手做任何動作返回的局面又將滿足該性質(zhì)。而結(jié)束局面是全為0，是不滿足該性質(zhì)的，因而必然為先手導(dǎo)致。

幸運的是③，計算機科學(xué)中有一種重要的邏輯運算——異或，它將給我們帶來所需的性質(zhì)。具體而言，下面來看Python中正整數(shù)按二進制位異或操作（^）的運用。讀者可通過圖3中幾個例子來復(fù)習(xí)一下。

例如④：3^5^7=（011）2^（101）2^（111）2=（001）2=1。簡言之，若干0和1異或操作的結(jié)果由其中1的個數(shù)的奇偶性決定，偶數(shù)為0，奇數(shù)為1。注意，對應(yīng)位進行運算，位和位之間不相干。

設(shè)想?yún)⒄請D3所示例子的樣子，考慮m個非負整數(shù)n1，n2，……，nm的按位異或。結(jié)果總是可以按照是否為0（數(shù)值）做二元區(qū)分。例如，3^5^7=001=1≠0，2^5^9^14=0010^0101^1001^1110=0000=0。特別地，當m=2時，異或為0，當且僅當兩個數(shù)相等。

n1^n2^……^nm結(jié)果為0，意味著所操作的每一個二進制位對應(yīng)的m個0/1中1的個數(shù)都是偶數(shù)。還意味著其中任何單個ni有任何變化，都將導(dǎo)致異或結(jié)果不再為0。⑤讀者此時應(yīng)該可以看到了一些希望。即，如果先手面對的是“結(jié)果不為0”局面，且有辦法通過拿掉若干棋子，給后手一個“結(jié)果為0”的局面，那么無論后手怎么做，他返回的一定是一個“結(jié)果不為0”的局面。

于是，我們就看到了先手做“結(jié)果不為0”→“結(jié)果為0”，后手則不得不做“結(jié)果為0”→“結(jié)果不為0”的重復(fù)模式。注意到結(jié)束局面是全為0，即“結(jié)果為0”，因而必為先手所致，意味著最后一顆棋子是他拿的。這樣，“結(jié)果不為0”，就是先手希望一開始就看到的性質(zhì)。

剩下一個關(guān)鍵問題：當面對一個“結(jié)果不為0”的局面，先手總能通過拿掉若干棋子將它變?yōu)椤敖Y(jié)果為0”局面嗎？對應(yīng)前面m=2的情形，那是要將兩個不相等的變成相等的，比較一目了然。現(xiàn)在則需要一點“計算”了。

設(shè)x=n1^n2^……^nm≠0，我們需要做的是找到一個ni，讓它減少一些，使得在異或的結(jié)果為0。例如，001=011^101^111=3^5^7，如果做7→6，就有3^5^6=011^101^110=0了。

一般地，由于x^x=0，即兩個相等的數(shù)異或總為0，于是也就有n1^n2^……^nm^x=0，注意到異或操作滿足交換律，問題就變成能否找到一個ni，滿足0≤ni^x

這樣的ni總是存在的。凡在x的二進制表示最高位1的位上也是1的ni都符合條件。⑥

這是因為，那樣的ni一旦與x做按位異或操作，ni^x對應(yīng)x最高位1的那一位就是1^1=0了;而由于那個1是x的最高位1，ni^x中更高的位就和ni保持相同，這就保證了ni^x

至此，我們完整研究了這種對弈游戲的玩法。你可以寫一個AI算法了，核心如圖4所示。

當然，為了達成一個實際可與你的客人玩一玩的程序，你還需要做些外圍處理，例如，可以讓客人任意選擇初始的m個數(shù)，n1，n2，……，nm，包括m本身，以及讓他為先手。游戲過程本質(zhì)上就是他和你的程序交替按游戲規(guī)則改變那些數(shù)，直至全部為0。最后一步的執(zhí)行者就是贏家。顯然，如果他也是懂得這其中道理的，那么在某些初值條件下（如她為先手，并且初始m個數(shù)的異或不為0）有可能會贏了你的AI程序。但只要他中間犯一次錯誤，就再也沒有機會了。

鼓勵有興趣的讀者自己實現(xiàn)這個AI程序。如果感覺有較大困難，也歡迎和我們聯(lián)系。下頁圖5是我的程序的運行界面，供參考。

● 進一步討論

不難認識到，異或運算的性質(zhì)在求解這個問題中起到了關(guān)鍵作用。事實上，異或運算定義簡單，但功能奇妙。例如，假設(shè)要在程序中交換兩個整數(shù)變量a和b的值。通常的做法是用一個中間變量tmp，做tmp←a; a←b; b←tmp。如果利用按位異或操作，也可以是：

a=a ^ b # 得到初始a和b的異或值

b=a ^ b # 現(xiàn)在b中就是初始a的值了，因為（a^b）^b=a

a=a ^ b # 現(xiàn)在a中就是初始b的值了，因為（a^b）^a=b

這樣一種“節(jié)省一個存儲單元”的做法，在過去存儲很珍貴的年代是有實際意義的。異或運算在信息加密、數(shù)據(jù)結(jié)構(gòu)等方面也都有出色的應(yīng)用。不僅如此，異或概念在現(xiàn)實生活中也有用。例如，有些場合一盞燈是由兩個開關(guān)控制的，即所謂雙控開關(guān)。進門按一個開關(guān)B1，燈亮了，進屋后按另一個開關(guān)B2，燈滅了;再按B2，燈又亮了，出門時再按B1，燈就滅了。這就是異或邏輯在背后起作用。

在前面討論通解時，我們體驗了一種邏輯運算和算術(shù)運算“混合作用”的場景。即一方面將數(shù)據(jù)對象分別看成是0/1字符串，執(zhí)行按對應(yīng)位置的邏輯運算，另一方面又將那樣的0/1字符串看成是“數(shù)”，從而可以比較大小。初次接觸這種情境的讀者可能會有些困惑，但這個例子恰恰很好地展示了計算機進行“計算”的要義，即表示、變換和解釋。具有某種含義的信息通過編碼表示為數(shù)據(jù)，對該數(shù)據(jù)進行操作變換得到中間數(shù)據(jù)和結(jié)果數(shù)據(jù)，結(jié)果數(shù)據(jù)再通過適當解釋得到符合需要的含義。在這個過程中，同一個數(shù)據(jù)可以有不同的解釋，有些解釋可能更加便于達到計算的最終目的。

最后，我們說按照上述通解編出的程序，在和人對弈的過程中，顯然會表現(xiàn)出“智能”——它能“隨機應(yīng)變”，因此，也可以稱為是一個“人工智能程序”。它的智能基于知識（如異或運算的性質(zhì)）和對問題本身的理解，而不是基于數(shù)據(jù)的，也就是不同于現(xiàn)在流行的通過機器學(xué)習(xí)得到的智能。在此強調(diào)這一點，是想告訴讀者，人工智能是一個廣闊的領(lǐng)域，不限于大數(shù)據(jù)基礎(chǔ)上的機器學(xué)習(xí)，盡管后者十分重要且當下正是大力發(fā)展的機遇窗口期。

釋：

①此例受參考文獻[1]中第226個問題的啟發(fā)。該問題的具體呈現(xiàn)形式為棋子的移動，本文等效呈現(xiàn)為棋子的拿取。同時，本文在朋友間傳閱過程中，湖州師范大學(xué)的邵斌老師指出2006年全國青少年信息學(xué)奧賽中有一個類似的題目。

②在本文待發(fā)表期間，也考慮了一個相反的問題，即“拿最后一顆者為輸”，是否也存在先手勝的條件。在課堂上和學(xué)生提起，李夏鯤同學(xué)當晚就給出了一個條件和證明。讀者讀過本文后，也能想出那個反問題該怎么解決嗎？

③下面討論的通解方法，不是本文作者的發(fā)明。我依稀記得很久前在某個材料上看過（但忘了出處），寫這篇文章時只是做了回顧整理的工作。

④這個例子中，我們特別用下標2表示是二進制數(shù)。在不至于混淆的情況下，后面的例子將省略這種表示，以求簡潔明了。

⑤這一個認識可以這樣體會：ni改變，它的二進制表示中總會有某些0變成1或者某些1變成0，于是就會破壞前面所說異或為0，必有每個二進制位上1的個數(shù)為偶數(shù)的條件。

⑥即，若記x=x1x2…xk…xt為x的二進制表示，如果xk=1，所有xi=0，i<k，這個k就是這里關(guān)注的位。

參考文獻：

[1]（蘇）柯爾詹姆斯基.趣味數(shù)學(xué)[M].張繼武，程韜，譯.北京：少年兒童出版社，1961，5.

[2]Maaz.XOR–The magic bitwise operator[DB/OL].http：//kackernoon.com.

注：作者系北京大學(xué)計算機系原系主任。