注：下列游戲都建立在雙方都有最優策略的情況下，若未加以說明，則每人每次至少取一個石子。

例1：取石子游戲之一

有兩個游戲者：A和B。有n顆石子。
約定：兩人輪流取走石子，每次可取1、2或3顆。A先取，取走最后一顆石子的人獲勝。
問題：A有沒有必勝的策略？

分析：這是小學必備奧數題之一，我們可以很容易的知道，當n為0,4,8,12……時，A必定會輸，因為不論A取多少，B只要和A共同取走4即可；當n不為0,4,8,12……時，A只需要將n取成4的倍數，這樣就變成了B先取，B一定會輸，所以A一定會贏。

經過我們的分析發現，對這個游戲而言，0,4,8,12……這些狀態是對于先手的必敗狀態，而其他狀態是對于先手的必勝狀態，因此，我們現在介紹一下有關博弈的一些名詞和概念

1、平等組合游戲

• 兩人游戲。
• 兩人輪流走步。
• 有一個狀態集，而且通常是有限的。
• 有一個終止狀態，到達終止狀態后游戲結束。
• 游戲可以在有限的步數內結束。
• 規定好了哪些狀態轉移是合法的。
• 所有規定對于兩人是一樣的。

因此我們的例1提到的游戲即為一個平等組合游戲，但是我們生活中常見的棋類游戲，如象棋、圍棋等，均不屬于平等組合游戲，因為雙方可以移動的棋子不同，不滿足最后一個條件；而我們后續提到的游戲，以及博弈中的其他游戲，基本屬于平等組合游戲

2、N狀態（必勝狀態），P狀態（必敗狀態）

像例1的分析一樣，0,4,8,12……等狀態就是對于先手的P狀態（必敗狀態），其他的則是對于先手的N狀態（必勝狀態）。

那么我們定義兩個狀態之間的轉換：

• 所有的終止狀態都為P狀態
• 對于任意的N狀態，存在至少一條路徑可以轉移到P狀態
• 對于任意的P狀態，只能轉移到N狀態

證明過于簡單，這里不再贅述，我們只需要明白一點，每個人都會選擇最策略即可。

當然這里所說的都是最后走步的人獲勝的游戲，至于那些走到最后失敗的游戲，我們在最后做了一個簡單的講解（Anti Nim）。

例2：取石子游戲之二

將例1的游戲擴展一下，我們定義一個集合$S=p1,p2,...,pk(k\in Z?)S=p1,p2,...,pk(k\in Z?)S=\{p_1,p_2,...,p_k\}(k\in Z^{?})$a=ak?,b>bk?，那么，取走

總結

以上是生活随笔為你收集整理的浅谈算法——博弈论的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。