神之一招

幾年前在下於《明報》撰寫了〈圍棋有常勝策略?〉一文(見連結[1],[2]), 談及漫畫《棋魂》中各棋手所追求的神之一招。

近日先後見有網友重溫《棋魂》, 又見科大有文章〈象棋有必不敗之法〉討論象棋的神之一招的數學意義, 再加上之前三神問題解說數學這麼過癮, 決定把神之一招的存在證明, 說明一下。

Zermelo 定理 (1928)
一個雙人博奕遊戲符合

• 條件一: 全局步數有固定上限;


• 條件二: 玩家清楚對奕雙方的所有可行步法及可行對應,
  

則先下子者(簡稱先手)或後下子者(簡稱)會有不敗策略。

先談條件一。 過三關(打井)的上限是九步。 圍棋有可能出現永不完之局, 但因為現實比賽都是限時的, 即使比賽是三小時, 且玩家都是一秒鐘一步, 到終局的步數也不會超過3600x3x2=10800。

再談條件二。 二人麻將, 玩家不知對方手牌; 飛行棋, 玩家不知跟着的可行步法, 因這要靠擲骰決定; 這兩者都不符合條件二。 可以說, 符合條件二的, 都是純智力比拼。

那何謂不敗策略呢? 即是機械化的下棋方法, 無論對方怎麼走, 都有一個固定的對應方法, 立於不敗之地。 當然, 若該遊戲沒有和局, 不敗策略就是必勝方略!

哼! 若《棋魂》中的鬼魂佐維真的找到神之一招, 他在世在遇有甚麼趣味, 不如消失好了! 我想這樣子的結局, 肯定比漫畫的結局更傷感。

定理證明

一步棋

假如遊戲是一步完, 即先手一下子就終局。 則要麼先手有一步可以致勝或致和, 要麼他怎麼下也要輸。前者即先手有不敗策略, 後者即後手有不敗策略。

N步棋

現假設對於"上限不過N步的傳奕遊戲", 其中一方有不敗策略。

N+1步棋

考慮"上限不過N+1步的博奕遊戲"。當先手走了一步, 他便成了一個"上限不過N步的傳奕遊戲"的後手, 而根據假設, 他或對手會有不敗策略。

換而言之, 對奕開始時, 要麼先手有一步可以得到一個他有不敗策略的新遊戲, 要麼他怎麼下也會得到一個對手有不敗策略的新遊戲。 前者即先手有不敗策略, 後者即後手有不敗策略。

根據歸納法, 證明畢。

後註
我在明報中稱它為組合遊戲數學(combinatorical game theory)的定理, 而不是科大文章中的博奕理論(game theory), 是因為後者通常談及的不知對方行動的博奕方法, 如猜拳及談判。 雖然如此, 兩者的討論也有很大的重疊空間。