雙人回合制智力競技遊戲是否都存在先手優勢？

11-25

今天玩五子棋的時候得知其先手優勢很明顯，才發現很多棋類遊戲比如象棋、圍棋、國際象棋等都可能存在先手優勢，也就是先下的人可能更佔優勢。
這類遊戲滿足以下特徵：
1、除了先後手區別以外，規則對參與者相同。
2、採取回合制比賽。
3、依靠雙方的博弈最終只有一人取勝或打成平手。

從科學角度看，是否所有這種智力競賽都存在先手優勢的現象？
再深入思考下，假如雙方的實力完全相當，極端點，比賽中任何一方都知道對手的下一步棋的目的是什麼，因此可能對其採取最優的防守措施，那麼各種遊戲的結局會是怎麼樣呢？

@morpheus說的動態博弈我並沒有專門學過，而@龍洋所說的，應該是Finite Impartial Two-player Strategy Game of Perfect Information，對此我有過一些了解，我來大致說一下。首先，先來解釋一下這個這麼長的詞是什麼意思：

Finite：這是指，遊戲是在有限步數之內可以分出勝負的，比如Nim遊戲。Nim遊戲我稍後會介紹。

Impartial：這個意思是，對於同一個遊戲局面，下一步無論誰走，可做出的移動是一樣的。這是什麼意思呢？比如@龍洋所說的遊戲，現在如果已經數到了3，無論接下來輪到紅方還是藍方，他們都可以選擇查4或4,5。那什麼遊戲是不是Impartial的呢？比如象棋。在同一個局面下，考查下一步。一方只能動紅子，一方只能動黑子。也就是說，一方能做出的移動另一方做不了，所以象棋不是Impartial的。

Two-player：這個很容易理解，就是兩個人之間玩的遊戲。

Strategy Game：這也就是題主所說的『智力競技遊戲』的意思，而不是靠運氣。

of：唔，這是個介詞。

Perfect Information：譯為完全信息。這是指每個參與者都可以了解到其他參與者的一切信息，還用@龍洋的例子，對於每一個局面，玩家都可以知道對方接下來所有可能的移動，所以這個遊戲是完全信息的。而很多撲克牌遊戲並不是完全信息，因為每個玩家不知道其他玩家手上有什麼牌。

好的，接下來介紹一個典型的Finite Impartial Two-player Strategy Game of Perfect Information，那就是Nim遊戲。Nim遊戲很類似與@龍洋的例子，不過我這裡介紹原版：

有若干堆有限數量的石子，兩人輪流取，每次必須且只能從其中一堆石子里取走若干（至少取一個，最多可以把整堆全部拿走），拿走最後一個石子的人獲勝。

這是不是很有小學奧數的即視感！

先上結論：

如果兩個知道Nim遊戲策略的人要一起玩這個遊戲，那麼他們只需要看一下桌上石子擺放的狀態，就可以知道誰會贏誰會輸了。

接下來介紹幾個名詞：

Position：Position是指遊戲目前的局面（State），並通過最精簡的語言敘述出來。

P position：走上一步的玩家可以確保勝利的局面。（P指Previous）

N position：走下一步的玩家可以確保勝利的局面。（N指Next）

所以，玩家都希望把遊戲變為P position，這樣自己對於P position來說，就是走了上一步的玩家。

注意，在Finite Impartial Two-player Strategy Game of Perfect Information中，每一個position要麼是P position，要麼是N position。

P position和N position有這麼幾個性質：

1. The winning position (or final position) is a P position.
2. Every P position can not be transferred from another P position within one move.
3. Every N position can be transferred into a P position within one move.

本想偷懶，直接把課上的內容搬上來……還是來翻譯一下吧。

1.遊戲最後的局面是一個P position，因為上一個玩家把最後一個石子拿走了，上一個玩家贏了。

2.每一個P position在一步之內無法轉換為另一個P position。這個也很好理解，如果我拿完石子之後是個P position，那麼我應該可以保證遊戲的勝利，如果你走完下一步，又變成了P position，那麼你也可以保證勝利。不可能兩方同時取勝，矛盾，哼唧。

3.每個N position都可以在一步之內變為P position。這也不難理解，因為如果現在是N position，就意味著走下一步的玩家可以保證獲勝，怎麼保證獲勝呢？就是把遊戲變為P position。所以只要是N position，那麼它都可以在一步之內變為P position。

這麼說有些抽象，我們來看一個具體的Nim遊戲的例子。比如一開始桌上有兩堆石子，一堆14個，一堆57個，記為（14,57），玩家是你和我。其中，我對Nim遊戲有了解，而你沒有，所以，嘿嘿。【各位先看，遊戲結束之後再分析為什麼。】

我一看（14,57），呀，這是個N position，我得先走，把它變成一個P position。於是我提出要先走，你很大度地點了點頭。

我從57個石子的那一堆中拿走了43個石子，還剩下14個石子。於是現在的position是（14,14），P position。

你完全不知道該怎麼辦，嗯，反正都是14個，我隨便選一堆拿走一半好了。於是變為（7,14）。

我一看，嗯，果不其然是N position，好，我從另一堆里也拿7個。（7,7），P position。

你打算矜持一點，拿走了一個，變為（6,7）。

我從另一堆里拿了一個，變為（6,6）。

你拿走三個，（3,6）。

我拿走三個，（3,3）。

你大喊：「你幹嘛學我！」一氣之下把一堆全拿光了，（0,3）。

我大喊：「我就學你！」一氣之下把另一堆也拿光了，（0,0）。【這不是顏文字啊！這是數學啊數學！！】

我贏了，yay~！

各位應該已經發現了，我一開始把兩堆石子變成一樣多，然後只需要學你就行了，這樣就可以一直保證我拿完之後兩堆一樣多，直到（0,0）。

所以，在這個遊戲中，（n,n）是P position，其餘都是N position。

那如果一開始有三堆棋子怎麼辦呢？n堆呢？美國數學家Charles L. Bouton發明了Nim遊戲的通解。

1.把每一堆石子的數量都換成二進位。

2.把這些二進位數字不進位地豎式相加（其實是異或，這裡為了通俗易懂一點），比如1+1=0，1+1+1=1，得到一個新的數m。如果這個數是0，那麼目前的遊戲處於P Position。若不是0，繼續。

3.把m從左數第一位不是0的數位（是1）圈出來，然後在豎式中的這一列數字中找一個1。一定有1，否則最後加起來是0，而不是1。

4.找到1之後，把1改為0，然後把包含這個改動的數記為s。

5.接下來，只要m的其中一個數位上是1，就把s對應數位的數字改掉，即0改為1或者1改為0。

6.把二進位換回十進位，按照結果取石子。

好的，我知道這個很抽象，我們來舉例子。

比如一開始的position是（27,25,12），那麼我接下來要做這樣的事情。

11011 （27）
11001 （25）
+1100 （12）
----------（不進位的豎式加法）
01110 （m）

m從左數第一位不是0的數是1。噗，廢話。是從左數第二位上的那個1啦。
好的，我們在那個1所在的一列（第二列）中找一個1。哎？都是1。那就隨便找一個，比如第一行第二列的1。並且把第一個數記為s。

11011 （s）
11001 （25）
+1100 （12）
----------（不進位的豎式加法）
01110 （m）

把第一行第二列的1改為0，並且把s的每一個m是1的數位都改掉。這個例子中，m的第2、3、4位是1，所以把s的2、3、4位改掉。

10101 （s）
11001 （25）
+1100 （12）
----------
01110 （m）

把s換回十進位，得21。所以，我下一步要把（27,25,12）變為（21,25,12）。

接下來無論你怎麼走，我都用這個方法，就可以確保勝利了。

回過頭看兩堆石子的情況，其實也是如此。因為兩個一樣的數換為二進位後，進行不進位的加法，0+0=0,1+1=0，得到的就是0。所以（n,n）對應了每一個P position。

好的，現在大家都是Nim遊戲小王子了！

那對於其他類似的遊戲，我們怎麼來找P position和N position呢？方法如下：

1.找已知最小的P position。（正如之前所說，勝利的position一定是P position）

2.把每一個能一步走到這個P position的position都列出來，這些都是N position。

3.沒有列出來的最小的position就是一個P position。

4.返回1。

其實這就是利用了之前所說的P position和N position的性質。

空說無憑，我們再來看看@龍洋所使用的例子。方便起見，我換一個規則：

兩人輪流報數，從28開始依次遞減，每人每次最少報1個數，最多報4個數，報到0的人獲勝。

最小的P position是0，因為報到了0的那個人獲勝。

所有能報到0的局面是1,2,3,4。沒有列出來的最小的數是5，所以5是下一個P position。

所有能報到5的局面是6,7,8,9。沒有列出來的最小的數是10，所以10是下一個P position。

…………

可以看出，所有5的倍數都是P position。所以在遊戲中，我只需要不斷把數報到5的倍數，就可以確保勝利了。

現在增加一點難度，其他規則不變，但每次每個人只能報1個、2個或4個數呢？方法一樣。

最小的P position是0，因為報到了0的那個人獲勝。

所有能報到0的局面是1,2,4。沒有列出來的最小的數是3，所以3是下一個P position。

所有能報到3的局面是4,5,7。沒有列出來的最小的數是6，所以6是下一個P position。

所有能報到6的局面是7,8,10。沒有列出來的最小的數是9，所以9是下一個P position。

…………

這回，P position是3n。

當然，P position不會每次都如此工整，但都是有規律可循的。

好的，我們再增加一點難度，其他規則不變，即，兩人輪流報數，每人每次最少報1個數，最多報4個數。但我們有兩個數，16和28，每次只能選擇一個數，報完之後兩個數都為0的人獲勝。

等一下，是不是有種似曾相識的感覺？對了！Nim遊戲！但是又不完全一樣，因為Nim遊戲從一堆里拿石子的個數是沒有限制的。也就是說，這個遊戲里的（16,28）與Nim遊戲里的（16,28）是不一樣的。

那有沒有什麼辦法讓它們變得等價呢？有！這就牽涉到一個新的概念，Nimber。嗯，我沒拼錯，Nimber。這是個合成詞，Nim+Number，是不是很萌！

這個遊戲中，每一個5的倍數的Nimber都是0，以此類推：（5n+1）的Nimber是1，（5n+2）的Nimber是2，（5n+3）的Nimber是3，（5n+4）的Nimber是4。

於是，（16,28）的Nimber就是（1,3）。

此時，這個遊戲里的（16,28）與Nim遊戲里的（1,3）是等價的！

別激動，聽我說。當Nim遊戲的position是（1,3）的時候，我應該把其變為（1,1），對吧？那（1,1）在這個遊戲中對應的是啥呢？是（5n+1,5n+1）。其中能從（16,28）一步轉化的position是（16,26）。所以，我應該選擇28，然後報到26。

注意，當這個遊戲的Nimber是（0,0）的時候，並不意味著已經獲勝。比如（15,25）。此時，對手隨便走一步，都會使得遊戲的Nimber變為（0,n）或者（n,0），此時依然按照我們的Nim策略，再把position變回（0,0）就可以了。

其實這就相當於一個可以往回放石子的Nim。就是說，有若干堆有限數量的石子，每次必須且只能從其中一堆石子里取走若干石子，或者放入若干自己之前取走的石子。拿走最後一個石子的人獲勝。

這個遊戲叫Poker Nim，策略與Nim完全一樣。當然了，如果引入負數，那麼這兩個遊戲實際上就是同一個遊戲了。

接下來我來介紹一個非常牛逼的定理：

每一個Finite Impartial Two-player Strategy Game of Perfect Information都等價於Nim或者Poker Nim。

這就是Sprague-Grundy Theorem，是由R. P. Sprague和P. M. Carmelo Grundy兩位數學家分別獨立發現的。

這個定理，也許能夠部分回答題主的問題。

當然了，為了保證答案的可讀性，我的表述不是很嚴謹。有興趣的可以看Sprague-Grundy Theorem。

關於計算Nimber的方法，有一個Minimum-Excluded Rule，簡稱MEx Rule，可以看Nimber和MEx (mathematics)。

嗯，早就想寫關於Nim的文章了，一直拖啊拖，這回直接寫知乎里了。希望對題主有所幫助。

nim遊戲就有先手必敗。。

不一定，請搜動態博弈。
個人認為象棋、圍棋、國際象棋的先手優勢來源於博弈樹複雜度大不可完全預知。

都有，但可減弱，比如

六子棋

公平是很難定義的

從0開始兩人輪流加數可加1或者2 誰加完之後數字變成60 誰就獲勝

看起來很公平吧符合要求吧

後手必勝如果想不出為啥那把規則改成加完之後數字變成3

有的遊戲先手必勝，有的遊戲後手必勝。不一定都是先手有優勢。
最簡單的棋類遊戲可能是這個：
兩個人從1開始交替查數，輪到一方時，他可以查一個數或兩個數，誰查到5誰贏。
比如紅方先查，他可以說 1 藍方接著查 2或2，3；或者紅方查或 1， 2，藍方接著查 3或3，4 ，就這樣交替查下去。
誰查到5誰贏的話，有先手紅方必勝的查法：

紅點是輪到紅方查數時，藍點表示輪到藍方查數，紅方會盡量選擇走紅線，藍方會盡量選擇走藍線，所以能從頭走到底的顏色就是必勝方的走法。其它棋類也可以把所有走法列成勝、敗、平局的樹，找出是先後必勝還是後手必勝或者是有必和的走法。
誰查到6誰贏的話，有後手藍方必勝的查法：

在2*2的棋盤上輪流下子，第一個沒有地方可下的人為輸。

有限狀態且完全信息的情況下，應該是先手勝、平、負有確定的結果。
換句話說，兩台理想的超級計算機玩這個遊戲，一旦確定誰先手，勝負就已經揭曉。

但是足夠複雜的情況下，根本造不出那樣的計算機，具體的人無法知道是哪一種，也不知道優勢有多大。

比如圍棋，先手有優勢，用貼子來補償。
貼5目和貼6目之後，先手是不是必勝就說不清了。

跳棋

最明顯的一個例子是橋牌的「投入」，利用後手優勢。

並非如此，最近玩爐石傳說，潛行者就是後手優勢，因為存在一枚法力硬幣可以觸發連擊。
我覺得這個問題應該改為討論這種遊戲是否要麼有後手優勢要麼有先手優勢，那麼我認為答案是肯定的。

圍棋先手不是有貼目？

爐石傳說很多時候是後手優勢吧。。。。

這麼解釋：
有限步數內雙方平等條件的智力遊戲，若沒有運氣因素。先手必勝。這是被證實的。
但是這裡需要強調的是 1、平等條件 2、智力無限大
首先條件平等的意思是沒有針對先手後手的特殊的限制條件。
例如：國際象棋、象棋、五子棋、圍棋都有先手後手不能使用的步數，這就是不平等條件。否則先手優勢是明顯巨大，並且幾乎有必勝路線。
其次人的智力無限大，其實意思是完全避免失誤。因為博弈類競技，一個失誤可能導致先手後手的優勢對換或者完全喪失。只要不失誤，先手的優勢就是必定的。永遠走最正確的步數，後手永遠無法挽回1步優勢的先手。
所以在現實的博弈遊戲中，幾乎所有的遊戲都有特殊規則限制先後手，圍棋的讓目，五子棋的禁手，象棋的和局，都是在不停平衡先後手的勝負比率中逐漸調整出的附加規則條款。
若拋開平等條件，其實圍棋和五子棋經常出現某種開局後手優勢大的局面。

田忌賽馬，先確定出戰的馬的一方必敗。

黑白棋至少是均勢，但普遍相信後手有極細微的優勢。

黑白棋後手有優勢

愚人愚見。
五子棋，象棋，國際象棋，壓枝，跳棋很好解釋。但不見得所有2人回合遊戲都是先手勝。而且不同遊戲，對於先後手步數都有不同的優劣勢。
並且，不同遊戲之間規律不同，是離散型。所以用放在一起解釋，有瑕疵。
===========================================================================
在每個有限回合內可獲勝的二人回合遊戲中，對於技術完全一樣的兩個人來說，先手有優勢。
1，首先，回合制遊戲的勝利生效時間是什麼時候呢？
答：是在某一回合。不是奇數回合就是偶數回合。
2，從生效時間入手分析先手優勢。
答：先手代表的即是奇數回合，後手便是偶數回合，後手若要贏，便贏在偶數回合，此時先手步數等於後手步數；先手若要贏，贏在奇數回合，此時先手比後手多一步。這就是說，後手比先手有多一步的優勢，在回合有限的遊戲里，先手獲勝概率便大於後手。因此，五子棋，象棋，國際象棋，壓枝，跳棋這類有限回合的遊戲規則里，略見一斑
3，從第一回合本來具有的優勢來分析。第一回合與其他回合有什麼區別呢？
答：第一回合，是公開前提條件的，意思就是說，第一步，是無需考慮對手的意圖，在第一步之前，對方沒有出招，所以不用研究對方的意圖，擁有主動性。而第二到N回合中，出招者要受上一回合的影響，還要做出下一步。與無前提的第一步比較，顯得吃力。
4，將雙方棋力調到了一樣，經過多次模擬後：
答：
無禁手五子棋（未平衡先手後手）：先手明顯
象棋先手明顯，國際象棋明顯，跳棋最明顯。
附圖：

五子棋大師2，很好的軟體，也是很好的模擬相同棋力下的先手優勢軟體，大家可以試試。

國際五子棋比賽為了平衡先手優勢，增加三手交換，五手兩打的規則，還增加了禁手。

明顯。國際象棋比賽中，先後手評分不同，循環賽中也要記錄先後手順序。

明顯。中國的象棋先後手規則與國際象棋類似。

很明顯。對於棋力相同的玩家，先走幾乎不輸。

============================================================================
無限回合下的遊戲，先手不具有優勢，但是要適遊戲現實情況分析。
我試著將這些放在一個模型里解釋。
無限回合的遊戲：棋盤棋子無限大多的五子棋，圍棋。車馬炮無限多的象棋········
他們到底在同水平玩家的輸贏上有什麼不同呢？
在結果方面分析：

這就是某個遊戲。有一個小球向右滾，不知道在哪回停，停了就說明某人贏了。
那麼面積就代表第N步獲勝的概率有多大，因此先手不具有優勢，換句話說，誰知道無限大的數是奇數還是偶數呢？
當然不同的遊戲，面積分布不一定是均等的。因此才要適遊戲現實情況分析。=============================================未完待編輯=================

先手的一方是有先行的優勢，但其實是相對的，後手也有後手的優勢。如果實力一樣的兩人，不管誰先走，最後都會出現和局。萬物相生相剋。不懂數學，說不出什麼例子來舉證，自己深入去研究過就會明白，當年浪潮天梭的伺服器大戰許銀川，也只是和棋收場。千古無重局，如果能用演算法算完誰都知道怎麼玩了。我不太會說話，解釋不清，只能用這個圖來表示：

顯然也有很多是後手優勢的，LS說的那種遊戲也有不少，小學奧數什麼的都有這種題吧
因為大家都是理性的，所以後手可以根據第一個人的策略而選擇自己的優勢策略啊，當然先手也相對的有優勢，比如根據博弈的自己最終有利結果來倒推選擇最初的優勢策略。具體誰佔優還要看具體的規則才行
當然這不局限在雙人的博弈中，但是雙人的反覆回合制博弈考慮起來會容易吧