已解遊戲

井字過三關好簡單，截至 2023 年為止已經係一隻解咗嘅遊戲。

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

類型

[編輯]
睇埋：決策樹

已解遊戲可以按「有幾已解」嚟分三大類型[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. ↑ 有關可能性嘅數量要點計，可以睇睇階乘等嘅概念。

引咗

[編輯]

以下係文中用咗嘅重要概念嘅英文名：

  • 已解遊戲：solved game
  • 極弱已解：ultra-weakly solved
  • 弱已解：weakly solved
  • 強已解：strongly solved
  • 窮舉搜尋：brute-force search

篇文引用咗以下呢啲文獻同網頁：

  1. ↑ 1.0 1.1 Jäger, F. (2019, April). Checkers Solved (PDF). In Seminar: Artifical Inelligence for Games.
  2. ↑ 2.0 2.1 Allis, Louis Victor (1994-09-23). Searching for Solutions in Games and Artificial Intelligence (PhD thesis). Maastricht: Rijksuniversiteit Limburg.
  3. ↑ Kevin Crowley, Robert S. Siegler (1993). "Flexible Strategy Use in Young Children's Tic-Tac-Toe". Cognitive Science. 17 (4): 531-561. 佢個 Table 1 講咗以下嘅技巧。