已解遊戲

已解遊戲（已經解決咗嘅遊戲）係博弈論同遊戲相關研究上講到嘅一個概念。如果話某隻遊戲係一隻已解遊戲，意思係話喺呢隻遊戲嘅任何一個位，假設兩位玩家都識用同會用最好（令自己贏面有咁大得咁大）嘅策略，觀察者可以完美噉預測結果會係點，即係會完美估到邊個贏定係打和。

井字過三關好簡單，係一隻解咗嘅遊戲。

類型

睇埋：決策樹

已解遊戲可以按「有幾已解」嚟分三大類型^{[1]:3 [2]}：

• 極弱已解：淨係知道個結果（邊個贏定係打和？），唔知要用咩策略達到嗰個結果。
• 弱已解：由起始狀態開始玩，已經知道結果同策略。
• 強已解：由是但一點開始玩，都會知道結果同策略。

遊戲

圖解：用兩難嘅方法贏井字過三關。留意一過咗第五步，無論 X 填乜都會輸。

睇埋：井字過三關、遊戲同解國際象棋

例如井字過三關就係一隻已解遊戲。井字過三關係一隻好簡單嘅遊戲，喺第一步得嗰三個可能性咁少—

• 填中間、
• 填角落（填左上角、填右上角、填左下角同填右下角功能上等同）同
• 填側邊（填左側、填右側、填上側同填下側功能上等同）。

用以下噉嘅策略玩，可以達致包保坐底打和，永遠都唔會輸。想像而家輪到一位玩家填，無論佢係交叉定圓圈都好，佢都要由以下嘅列表度揀位置最高嗰一步嚟行（如果 1 執行唔到，就用 2；如果 2 執行唔到，就用 3... 如此類推）^[3]：

1. 贏：如果自己已經有兩個符號成一條線，填第三個落去，贏。
2. 擋：如果對手已經有兩個符號成一條線，要即刻喺第三個位嗰度填自己符號。
3. 兩難：要營造一個局勢，令自己跟住落嚟有兩個贏位（填咗就即贏）可以填。
4. 擋兩難：如果對手下一步可以製造一個兩難，自己就要郁手阻擋佢個兩難；擋兩難嘅一個特殊情況係，如果自己霸住中間而對手霸咗兩隻相反嘅角（即係對手霸咗左上右下或者左下右上），自己填角落會即輸，應該要填側邊。
5. 填正中央。
6. 填同對手相反嘅角落。
7. 填角落。
8. 填側邊。

好似井字過三關噉嘅遊戲，算係強已解。

有關複雜啲嘅已解遊戲，可以睇睇跳棋^[1]。

解法

内文：窮舉搜尋

睇埋：期望值、可運算度同優勢策略

要達致弱已解或者強已解，最簡單直接嘅方法係窮舉搜尋^[2]：窮舉搜尋係演算法一類，泛指靠住「將啲可能性逐個逐個攞嚟睇」解決問題嘅演算法；呢種做法可以輕易噉解決一啲簡單嘅遊戲—例如井字過三關噉，井字過三關喺第一步得三個可能性，而可能性少就表示，電腦唔使嘥好多工夫就可以睇勻晒所有可能性。相比之下，國際象棋淨係第一步白棋行嗰刻已經有 20 個可能性咁多，而跟住落嚟可能性嘅數量會有爆發性嘅增長，喺十步之前已經會超過 100 萬個可能性^{[註 1]}，廿一世紀初嘅電腦仲未有足夠嘅運算能力，做唔到「將咁多個可能性逐個逐個攞嚟睇，喺合理咁短嘅時間內畀答案」。

睇吓

• 複雜度
• 演算法
• 遊戲平衡：遊戲平衡得唔好，好易會搞到隻遊戲出現「勁用某種策略就包贏或包打和」嘅情況。
• 有關運算能力「夠唔夠」以及係「會點增長」嘅問題，可以睇睇運算複雜度、摩亞定律同埋量子運算。

文獻

• Jäger, F. (2019, April). Checkers Solved (PDF). In Seminar: Artifical Inelligence for Games.
• Schaeffer, J., Burch, N., Bjornsson, Y., Kishimoto, A., Muller, M., Lake, R., ... & Sutphen, S. (2007). Checkers is solved (PDF). Science, 317(5844), 1518-1522.

註釋

1. 有關可能性嘅數量要點計，可以睇睇階乘等嘅概念。