象棋和圍棋存在不敗策略？.docxVIP

1、象棋和圍棋存在不敗策略?象棋和圍棋都是中華文明的瑰寶，更是訓練和測試思維能力的方式之一，那些在這兩種棋類上取得成就的人們，其智商普遍得到公眾認可。但是,我們是否想過，在這兩種棋類上是否存在必勝或者平局的策略？答案是存在的,這是策梅洛關于雙人完全信息博弈的一個定理的結(jié)論。本文將詳細介紹這個定理的證明，并將其用于諸如五子棋的分析中。如無特殊說明，后文所提及的游戲都是雙人游戲。什么是最優(yōu)策略為了讓大家對最優(yōu)策略有一個直觀的理解，這里舉一個小游戲作為例子。這個小游戲叫Chop，在游戲的最開始有一個mxn的網(wǎng)格（下圖是一個4x6網(wǎng)格示例）,游戲由兩位玩家輪流操作，每位玩家每輪可以沿著一整根豎網(wǎng)格線或者一

2、整根橫網(wǎng)格線將網(wǎng)格割掉一塊，割到只剩下一個小方格的玩家為勝者。注意,不能沿著剩余網(wǎng)格的邊界線做切割，例如不能沿著下圖的AB線切割，但是沿著CD線或者EF線切割都是可以的。每次切割完之后網(wǎng)格會被分成兩塊，由操作切割的玩家決定留下哪一塊。對于這類雙人游戲,一般會有最先進行操作的玩家，我們將其稱為先手,另一位被稱為后手。如果T始的時候m和n其中一個數(shù)為1,比如n=l,先手玩家可以直接切割掉(m-l)個格子即可獲得勝利，這個策略就是先手玩家的最優(yōu)策略。如果對于一般的m和n,先手或者后手怎樣才能保證獲勝呢？讀者可以稍作思考，再接著往下看。其實很簡單，如果m和n不相等，那么先手的最優(yōu)策略會導致必勝的結(jié)果：

3、這時候先手玩家只要割掉其中一塊使得剩下的網(wǎng)格是個長和寬相等的網(wǎng)格即可。這樣，無論后手切割哪條線，都是在長和寬相等的基礎上進行切割，最后必然得到一個長寬不相等的網(wǎng)格，也就不可能是單獨一個網(wǎng)格。先手玩家只要每一步實行這個策略,無論后手玩家怎么操作,先手玩家都會獲勝。這時候讀者肯定明白了，當m=n的時候，無論先手玩家怎么操作，后手玩家都可以借助前述一樣的策略獲勝。完全信息博弈和策梅洛定理現(xiàn)在回到一般游戲的討論上。策梅洛定理適用于被稱為完全信息博弈的一類游戲。所謂完全信息博弈,指的是游戲的所有信息都是公開的，游戲雙方都能清楚了解到目前游戲所處的狀態(tài)信息，并且游戲的每一步都不涉及概率因素。這個條件把撲克

4、、飛行棋、暗棋和翻棋玩法下的軍棋都排除掉了。然后，我們還需要這個游戲能在有限步內(nèi)結(jié)束,并且，游戲的結(jié)局要么是平局要么有一方是勝者。很明顯，圍棋是屬于完全信息博弈的。至于象棋，有可能會進入循環(huán)狀態(tài)從而整個游戲沒完沒了。為了避免這一點，我們可以加入一些新規(guī)則使得象棋不會出現(xiàn)循環(huán)，比如，設定一個很大的數(shù)N,只要連續(xù)N步雙方都沒有被吃掉棋子就判為和棋，或者不允許超過N次進入同一種棋子狀態(tài)，否則判為和棋。加入這些規(guī)則或者類似的規(guī)則之后，象棋就滿足要求了。下面給出策梅洛定理的嚴格表述：在雙人完全信息博弈下，只有三種情況：要么先手具有必勝策略，要么后手具有必勝策略，要么雙方的最優(yōu)策略會導致平局。比如前面所說

5、的Chop游戲，當mn時，先手玩家具有必勝策略;如果m二n,后手玩家具有必勝策略。Chop游戲沒有平局。策梅洛定理是一個結(jié)論很強的定理，下面我們會發(fā)現(xiàn)，它的證明非常簡單，不需要用到很高深的知識。策梅洛定理的證明為了證明策梅洛定理，我們需要引入一個小小的概念：游戲樹。在游戲的每一步，玩家有很多種走法，每一個走法都會產(chǎn)生新的分支，把兩位玩家的所有可能走法考慮進來，就會得到一個樹狀結(jié)構(gòu)。這個樹狀結(jié)構(gòu)窮盡了游戲過程的所有可能性。下圖是Chop游戲在1x4情況下的游戲樹。在本文，我們用（L0）表示先手獲勝，（0,1）表示后手獲勝，。0）表示平局。(1,0)在游戲樹上，節(jié)點會標注上游戲狀態(tài)，比如上圖中的方

6、格。有時候為了信息完全，還會標注上在此節(jié)點輪到哪位玩家操作了。因為我們把游戲循環(huán)往復的可能性排除了，游戲狀態(tài)轉(zhuǎn)移圖不會出現(xiàn)圈圖，所以必然是樹圖。（對于象棋，如果用A表示棋子狀態(tài)，加上了前文所述的其中一個規(guī)則后，整個游戲狀態(tài)將由（A,i)表示，其中i表示已經(jīng)連續(xù)i步雙方都沒有被吃掉棋子或者已經(jīng)i次進入棋子狀態(tài)A了。在這樣的表示下，當i不等于j時，(A,i)和(A,j)哪怕棋子狀態(tài)都是A，但是依然代表不同的游戲狀態(tài)。于是，象棋的游戲轉(zhuǎn)移也不會出現(xiàn)圈圖。)接下來我們假設每一位玩家都是理智的，當玩家處于游戲樹的某個節(jié)點時,她/他必然會選擇對其最有利的走法。假如現(xiàn)在游戲狀態(tài)來到了倒數(shù)第二步，再走一步游戲

7、將結(jié)束了，那么我們就會看到游戲樹的末端，大概是如下圖這樣的，其中省略號表示未畫出的末端節(jié)點在上圖的游戲樹中，如果在A處輪到先手玩家操作了，那么她/他必然會選擇走向B。走向C和D對先手玩家來說都不是最優(yōu)走法。于是,A雖然不是末端節(jié)點，但是它依然可以帶有勝負信息(1,0)，這個勝負信息表示先手方在A處只要按最優(yōu)策略走就會獲勝。當然，上圖只是一個例子，有可能末端節(jié)點都不是(L0)狀態(tài)的，這時候?qū)ο仁滞婕襾碚f最優(yōu)策略就是走到平局狀態(tài)(如果有平局末端的話)，這樣A節(jié)點將會帶有(0,0)的勝負信息。如果是最壞情況，節(jié)點A下的所有末端節(jié)點都對應(0,1)的勝負，那么在A處無論先手玩家怎么走都必輸，于是節(jié)點A

8、帶有的勝負信息是(0,1)。假如我們給勝負弓I入大小關系:(1,0)>(0,0)>(0,1)，那么前述得到A的勝負信息的分析可以總結(jié)為:輪到先手方操作,A節(jié)點的勝負=A的下一級節(jié)點的勝負最大值。另一方面,如果在A處輪到后手玩家操作了，我們也可以通過類似的分析得到A處的勝負信息,只不過最大值要換成最小值：輪到后手方操作,A節(jié)點的勝負二A的下一級節(jié)點的勝負最小值。得到了A處的勝負信息之后，我們就可以忽略A下面的所有節(jié)點了,這時候A就成了一個末端節(jié)點,它帶有相應的勝負信息,這個勝負信息表示從該節(jié)點出發(fā)，兩位玩家都使用最優(yōu)策略后會導致的勝負結(jié)局。這個操作可以繼續(xù)進行下去，不斷得到上一級節(jié)點

9、的勝負信息,然后忽略掉舊的末端節(jié)點。如此往復,因為樹是有限高的，最終我們會得到游戲一開始那個節(jié)點(術語叫根節(jié)點)的勝負信息。如果根節(jié)點的勝負信息是Q0)，那么意味著先手玩家只要按最優(yōu)策略走下去就會必勝，如果根節(jié)點的勝負信息是(0,1)，那么意味著后手玩家具有必勝策略；如果根節(jié)點的勝負信息是(0,0),那么意味著雙方的最優(yōu)策略會導致平局。至此，策梅洛定理證明完畢。IlliIO，。)（0,1）(1,0)(i,o)（°）（o,i）(1,0)從下往上的勝負信息推導如何確定誰才具有必勝策略：策略竊取想必讀者已經(jīng)躍躍欲試了，如果知道了象棋或者圍棋的最優(yōu)策略，豈不是在棋壇上橫著走？可惜的是，雖然策

10、梅洛定理的證明是構(gòu)造性的,但是構(gòu)造過程需要我們先得到整個游戲樹，而像圍棋這類棋，游戲的路徑（指從根節(jié)點到末端節(jié)點的一條路徑）比宇宙的原子數(shù)目還要多,要想通過整個游戲樹來得到最優(yōu)策略是不可能的了。如此說來，策梅洛定理僅僅給必勝或者平局策略提供了存在性。不過，借助策梅洛定理所提供的存在性，我們可以利用被稱為策略竊取的方法證明在某些游戲上后手不存在必勝策略，換言之，先手有不敗策略。本文將以著名的五子棋為例介紹策略竊取是怎么一回事。很明顯，五子棋滿足策梅洛定理的條件，于是有且僅有三種可能性：先手具有必勝策略、后手具有必勝策略、雙方的最優(yōu)策略會導致平局。接下來我們使用反證法。假如后手具有必勝策略，我們把

11、這個策略稱為S。這時候無論先手玩家怎么走，后手玩家只要使用策略S,先手玩家必輸。策略竊取的要點就是把對方的策略"竊取"過來。先手玩家先在棋盤上隨便放一個棋子，位置記為P1,然后假裝這個棋子不存在。這時候輪到后手玩家放子了，由于假裝P1上的棋子不存在，后手玩家成了"先手“，而先手玩家成了"后手"，于是先手玩家可以使用必勝策略S。根據(jù)這個策略的必勝性質(zhì),無論對方怎么走，”后手"玩家（也就是先手玩家）都將獲勝。不過,事情似乎沒那么簡單。我們只是假裝P1上的棋子不存在而已,實際上這個棋子是存在的。P1位置上的棋子會怎么影響到策略s的使用呢？假如走到了某一步，策略S要求"后手"玩家將棋子放在P1位置,這時候P1已經(jīng)存在"后手"玩家的棋子了，但是游戲要求玩家每一步都不能不下棋子，此時"后手玩家可以在這一步把棋子下在其他的任意位置,記為P20這樣的話P1和P2都占據(jù)了"后手"玩家的棋子,這就等價于游戲一開始“后手"玩家將棋子下在了P2,并且在目前這一輪“后手"玩家根據(jù)策略S的要求把棋子下在了P1位置。如果接下來策略要求棋子下在P2,那么"后手"玩家可以任意把棋子下在P3位置.如此類推，先手玩家可以完美使