[Theory of Computer Game 1]
雙人零和對局名詞簡介
Chinese
遊戲AI
written by
LiaoWC
on 2022-02-17
做為和賽局理論主題的局隔，關於 computer game 方面的 game 中文會用「對局」稱呼為主。以下討論的是雙人的對局遊戲。
零和對局（zero-sum game）
雙方利益和為零。例如一方贏另一方就輸，不會有雙贏的局面。
完美資訊（perfect information）
雙方都了解遊戲規則、遊戲現在的狀態、對方做了什麼動作。
對局理論值（game-theoretic value）
遊戲結果，例如輸、贏、平手。
可以分成三種：
- Ultra-weakly solved：遊戲從初始狀態開始，已經被證明出先手和後手的最佳結果，但不知道如何走到這個結果。
- Weakly solved：遊戲從初始狀態開始，無論對手怎麼下，都能有方法走到自己的最佳結果。
- Strongly solved：從任何狀態開始都能知道到達最佳結果的路徑。
狀態空間複雜度（state-space complexity）
一個遊戲所有盤面狀態的數量。
- 例如井字遊戲為 $3^9$。因為全部九個位置每個位置可以是圈、叉、空白。
- 例如十九路圍棋為 $3^{361}$，361 個位置各可能是黑子、白子、沒有子。
對局樹複雜度（game-tree complexity）
從起始盤面開始搜尋的所有合法盤面組合數量。
- 例如井字遊戲為 9 階乘 = 362880。如果去掉旋轉對稱和不可能達到的盤面後會更少。