1. 首頁 > 生活雜燴 > 游戲 > >

象棋和圍棋都是中華文明的瑰寶|什么？象棋和圍棋都存在不敗策略？

象棋和圍棋都是中華文明的瑰寶 ， 更是訓練和測試思維能力的方式之一 ， 那些在這兩種棋類上取得成就的人們 ， 其智商普遍得到公眾認可 。 但是 ， 我們是否想過 ， 在這兩種棋類上是否存在必勝或者平局的策略？答案是存在的 ， 這是策梅洛關于雙人完全信息博弈的一個定理的結論 。 本文將詳細介紹這個定理的證明 ， 并將其用于諸如五子棋的分析中 。 如無特殊說明 ， 后文所提及的游戲都是雙人游戲 。
什么是最優策略
為了讓大家對最優策略有一個直觀的理解 ， 這里舉一個小游戲作為例子 。 這個小游戲叫Chop ， 在游戲的最開始有一個m×n的網格(下圖是一個4×6網格示例) ， 游戲由兩位玩家輪流操作 ， 每位玩家每輪可以沿著一整根豎網格線或者一整根橫網格線將網格割掉一塊 ， 割到只剩下一個小方格的玩家為勝者 。 注意 ， 不能沿著剩余網格的邊界線做切割 ， 例如不能沿著下圖的AB線切割 ， 但是沿著CD線或者EF線切割都是可以的 。 每次切割完之后網格會被分成兩塊 ， 由操作切割的玩家決定留下哪一塊 。
象棋和圍棋都是中華文明的瑰寶|什么？象棋和圍棋都存在不敗策略？
文章圖片
對于這類雙人游戲 ， 一般會有最先進行操作的玩家 ， 我們將其稱為先手 ， 另一位被稱為后手 。 如果一開始的時候m和n其中一個數為1 ， 比如n=1 ， 先手玩家可以直接切割掉(m-1)個格子即可獲得勝利 ， 這個策略就是先手玩家的最優策略 。 如果對于一般的m和n ， 先手或者后手怎樣才能保證獲勝呢？讀者可以稍作思考 ， 再接著往下看 。
其實很簡單 ， 如果m和n不相等 ， 那么先手的最優策略會導致必勝的結果：這時候先手玩家只要割掉其中一塊使得剩下的網格是個長和寬相等的網格即可 。 這樣 ， 無論后手切割哪條線 ， 都是在長和寬相等的基礎上進行切割 ， 最后必然得到一個長寬不相等的網格 ， 也就不可能是單獨一個網格 。 先手玩家只要每一步實行這個策略 ， 無論后手玩家怎么操作 ， 先手玩家都會獲勝 。 這時候讀者肯定明白了 ， 當m=n的時候 ， 無論先手玩家怎么操作 ， 后手玩家都可以借助前述一樣的策略獲勝 。
完全信息博弈和策梅洛定理
【象棋和圍棋都是中華文明的瑰寶|什么？象棋和圍棋都存在不敗策略？】現在回到一般游戲的討論上 。 策梅洛定理適用于被稱為完全信息博弈的一類游戲 。 所謂完全信息博弈 ， 指的是游戲的所有信息都是公開的 ， 游戲雙方都能清楚了解到目前游戲所處的狀態信息 ， 并且游戲的每一步都不涉及概率因素 。 這個條件把撲克、飛行棋、暗棋和翻棋玩法下的軍棋都排除掉了 。 然后 ， 我們還需要這個游戲能在有限步內結束 ， 并且 ， 游戲的結局要么是平局要么有一方是勝者 。 很明顯 ， 圍棋是屬于完全信息博弈的 。 至于象棋 ， 有可能會進入循環狀態從而整個游戲沒完沒了 。 為了避免這一點 ， 我們可以加入一些新規則使得象棋不會出現循環 ， 比如 ， 設定一個很大的數N ， 只要連續N步雙方都沒有被吃掉棋子就判為和棋 ， 或者不允許超過N次進入同一種棋子狀態 ， 否則判為和棋 。 加入這些規則或者類似的規則之后 ， 象棋就滿足要求了 。
下面給出策梅洛定理的嚴格表述：在雙人完全信息博弈下 ， 只有三種情況：要么先手具有必勝策略 ， 要么后手具有必勝策略 ， 要么雙方的最優策略會導致平局 。 比如前面所說的Chop游戲 ， 當m≠n時 ， 先手玩家具有必勝策略；如果m=n ， 后手玩家具有必勝策略 。 Chop游戲沒有平局 。 策梅洛定理是一個結論很強的定理 ， 下面我們會發現 ， 它的證明非常簡單 ， 不需要用到很高深的知識 。

相關經驗推薦