這邊貼公式有點麻煩，還得轉成圖，也不知道未來會不會有跑版的情況，就附上我原稿的版本吧！
hackMD原稿

電腦對局

電腦對局是AI領域中非常重要的一個分支，自電腦被發明以來，就有非常多人熱衷於研究如何讓電腦學會下棋，希望讓電腦能夠在各種遊戲中展現出「智慧」，電腦對局的研究也為AI在其他領域的應用奠定了基礎。

對局遊戲除了大家比較常見的棋牌類遊戲之外，還包含各式解謎遊戲，根據不同類型的對局會有不同的做法，每種類型的對局都有自己的特性，以下做一些簡單的分類跟名詞介紹。

依照人數分類：

• 單人對局
  數獨、魔術方塊、nonogram、15-puzzle等
• 雙人對局
  圍棋、象棋、將棋、西洋棋、愛因斯坦棋、暗棋、五子棋、六子棋、黑白棋、蜜月橋牌等
• 多人對局
  麻將、橋牌、鬥地主、德州撲克等

零和對局 (Zero-Sum Game)

雙方的利益和為0的對局，一方的利益會等於另一方的損失，雙方不存在合作關係的對局。

合作對局 (Cooperative Game)

所有玩家通過合作來共同達成某一目標，而非互相競爭。
大部分的棋牌類遊戲都還是互相競爭為主，就算是橋牌、鬥地主等中雖然有跟隊友合作的環節，但是同時存在著對手需要互相競爭，也不能算是合作對局。
像是桌遊花火就是所有人的目標一致，沒有任何競爭關係，這就是合作對局。
但我這次分享的內容都會以零和對局為主。

完全資訊對局 (Perfect Information Game)

玩家可以得知全局的資訊
例如：圍棋、象棋、西洋棋等

不完全資訊對局 (Imperfect Information Game)

玩家無法知道所有的資訊
例如：橋牌、鬥地主、麻將等

發散型對局 (Divergent Game)

合法盤面的可能組合數會隨著雙方移動次數增加而愈來愈多。

收斂型對局 (Convergent Game)

合法盤面的可能組合數會隨著雙方移動次數增加而愈來愈少。

其實很多遊戲都會同時存在發散與收斂的情況。
比如井字遊戲 (Tic-Tac-Toe)，每回合的合法盤面組合數總和算法為：

：表示目前雙方（X 和 O）移動的總步數。

：取上限表示 X 的移動步數。因為 X 先手，當總步數為奇數時，X 會比 O 多下一步。

：取下限表示 O 的移動步數。當總步數為奇數時，O 的步數比 X 少一步。

這邊公式的小括號就是計算組合的C，等於

	1	2	3	4	5	6	7	8	9
	9	72	252	756	1260	1260	756	252	72

可以看到井字遊戲一開始為發散型，盤面變化量會隨著 變大跟著變大，但到了有6手棋後就變成收斂型了，又開始漸漸變小。
通常發散型的對局會較收斂型來得複雜，很多遊戲到了最後都會變成收斂型對局，就有機會將其破解，然後儲存這些結果建立成殘局庫，我後面也會介紹到殘局庫的做法。

機率型對局 (Stochastic Game)

對局含有機率成分，玩家無法控制所有情況。
許多不完全資訊對局也都是機率型對局。
例如：麻將，你沒有辦法知道你下一張會摸到什麼牌，甚至連摸牌順序都有可能改變。
完全資訊對局的話有：愛因斯坦棋，能移動哪顆棋子是靠擲骰子決定的，所以不管優勢多大都有機會因為運氣不好而被逆轉，想起6年前曾經聽研究所學長說過愛因斯坦棋是個糞game好遊戲。

Reference

• 電腦對局導論