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

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


從下往上的勝負信息推導
如何確定誰才具有必勝策略：策略竊取
想必讀者已經躍躍欲試了 ， 如果知道了象棋或者圍棋的最優策略 ， 豈不是在棋壇上橫著走？可惜的是 ， 雖然策梅洛定理的證明是構造性的 ， 但是構造過程需要我們先得到整個游戲樹 ， 而像圍棋這類棋 ， 游戲的路徑(指從根節點到末端節點的一條路徑)比宇宙的原子數目還要多 ， 要想通過整個游戲樹來得到最優策略是不可能的了 。 如此說來 ， 策梅洛定理僅僅給必勝或者平局策略提供了存在性 。 不過 ， 借助策梅洛定理所提供的存在性 ， 我們可以利用被稱為策略竊取的方法證明在某些游戲上后手不存在必勝策略 ， 換言之 ， 先手有不敗策略 。
本文將以著名的五子棋為例介紹策略竊取是怎么一回事 。 很明顯 ， 五子棋滿足策梅洛定理的條件 ， 于是有且僅有三種可能性：先手具有必勝策略、后手具有必勝策略、雙方的最優策略會導致平局 。 接下來我們使用反證法 。 假如后手具有必勝策略 ， 我們把這個策略稱為S 。 這時候無論先手玩家怎么走 ， 后手玩家只要使用策略S ， 先手玩家必輸 。
策略竊取的要點就是把對方的策略“竊取”過來 。 先手玩家先在棋盤上隨便放一個棋子 ， 位置記為P1 ， 然后假裝這個棋子不存在 。 這時候輪到后手玩家放子了 ， 由于假裝P1上的棋子不存在 ， 后手玩家成了“先手” ， 而先手玩家成了“后手” ， 于是先手玩家可以使用必勝策略S 。 根據這個策略的必勝性質 ， 無論對方怎么走 ， “后手”玩家(也就是先手玩家)都將獲勝 。 不過 ， 事情似乎沒那么簡單 。 我們只是假裝P1上的棋子不存在而已 ， 實際上這個棋子是存在的 。 P1位置上的棋子會怎么影響到策略S的使用呢？假如走到了某一步 ， 策略S要求“后手”玩家將棋子放在P1位置 ， 這時候P1已經存在“后手”玩家的棋子了 ， 但是游戲要求玩家每一步都不能不下棋子 ， 此時“后手”玩家可以在這一步把棋子下在其他的任意位置 ， 記為P2 。 這樣的話P1和P2都占據了“后手”玩家的棋子 ， 這就等價于游戲一開始“后手”玩家將棋子下在了P2 ， 并且在目前這一輪“后手”玩家根據策略S的要求把棋子下在了P1位置 。 如果接下來策略要求棋子下在P2 ， 那么“后手”玩家可以任意把棋子下在P3位置……如此類推 ， 先手玩家可以完美使用策略S ， 于是會必勝 。 這和反證法的假設相矛盾 。 于是 ， 五子棋只能存在兩種情況：先手具有必勝策略、雙方的最優策略會導致平局 。 或者更簡潔地表述為 ， 先手具有不敗策略 。
回顧前述關于五子棋的討論 ， 這個“五”字完全沒有體現出來 ， 我們完全可以把相關結論推廣到四子棋、六子棋等等 。 特別地 ， 井字棋本質上是一種三子棋 ， 由于它的游戲樹很簡單 ， 我們甚至可以通過窮舉法證明在井字棋上確實是先手玩家具有不敗策略 。
象棋和圍棋都是中華文明的瑰寶|什么？象棋和圍棋都存在不敗策略？
文章圖片
在哪都能玩的井字棋
轉載內容僅代表作者觀點
不代表中科院物理所立場
來源：中科院理論物理研究所
原標題：DoctorCurious26:什么？象棋和圍棋都存在不敗策略？
編輯：藏癡
來源：中科院物理所

相關經驗推薦