在遊戲AI的緣起與進化一文中我們講到，遊戲 AI 的進化始終與 AI 研究相生相伴，這是由於遊戲種類豐富，難度和複雜性也很多樣，人工智能攻克不同類型的遊戲自然也反映了 AI 研究的進展，因此長期以來遊戲一直是 AI 研究的黃金測試平臺。
隨著人工智能逐個攻克雙陸棋、國際跳棋、國際象棋、圍棋等棋類遊戲，AI 仍在繼續挑戰難度更高的遊戲，例如撲克、橋牌、麻將這類不完美信息遊戲。那麼為什麼這類遊戲的難度更高呢？如何衡量不同類型遊戲的複雜度和難度？在這篇文章裡，我們將會為大家仔細解讀。
遊戲複雜度與遊戲難度並不等價
首先需要提醒大家，遊戲的複雜度與難度並不完全等價，遊戲難度除了與遊戲本身的複雜度有關以外，還與戰略等多種要素相關，也就是說，數學上更復雜的遊戲，玩起來不一定更難。
一般來說，我們可以根據信息的暴露程度將遊戲分為兩大類：完美信息遊戲（Perfect-Information Games）和不完美信息遊戲（Imperfect-Information Games）。如果所有的參與者，在遊戲的任何階段都可以訪問所有關於遊戲（包括對手）狀態及其可能延續的信息，那麼稱這類遊戲為完美信息遊戲；否則稱為不完美信息遊戲。圍棋、象棋等棋類遊戲，對局雙方可以看到局面的所有信息，屬於完美信息遊戲；而撲克、橋牌、麻將等遊戲，雖然每個參與者都能看到對手打過的牌，但並不知道對手的手牌和遊戲的底牌，也就是說各個對局者所掌握的信息是不對稱的，因此屬於不完美信息遊戲。
完美信息遊戲和不完美信息遊戲難度的衡量指標通常是有區別的。對於完美信息遊戲，通常遊戲的複雜度就決定了難度，我們可以用狀態空間複雜度（State-Space Complexity）和遊戲樹複雜度（Game-Tree Complexity）對其難度進行衡量；而對於不完美信息遊戲，隱藏信息對於遊戲的難度影響很大，我們可以用信息集（Information Set）數目和信息集平均大小對其難度進行衡量。
完美信息遊戲：狀態空間和遊戲樹的複雜度
狀態空間複雜度（State-Space Complexity）
遊戲的狀態空間複雜度（SSC）是指從遊戲的初始狀態開始，可以達到的所有符合規則的狀態的總數。例如棋類遊戲中，每移動一枚棋子或捕獲一個棋子，就創造了一個新的棋盤狀態，所有這些棋盤狀態構成遊戲的狀態空間。通常情況下，很難精確地計算出遊戲的狀態空間大小，只能給出一個粗略的估計。一種最常用的估計方法是通過包含一些不符合規則或不可能在遊戲中出現的狀態, 從而計算出狀態空間大小的一個上界（Upper Bound）。例如在估計圍棋狀態數目上界的時候，允許出現棋面全部為白棋或者全部為黑棋的極端情況。
事實上，即便像井字棋這樣簡單的遊戲，其狀態空間也是很大的。井字棋的盤面上共有9（3x3）個位置，每個位置可能的取值有三種：X，O或空白，因此總的狀態數目為3的9次方即19863個。當然，這其中包含許多不符合規則的狀態，因為我們在這裡估計的是狀態空間大小的上界。由此，我們可以得到井字棋的狀態空間複雜度約為10^4（即19863≈10^4）。這種計算方法可以很容易地推廣到更大的棋盤和更加複雜的棋類遊戲。比如圍棋有361（19x19）個位置，每個位置可以放置白子或黑子或者空置，利用上述方法，可以確定圍棋的狀態空間複雜度約為10^172 (即3^361≈10^172)。在表1中，我們給出了常見的完美信息棋類遊戲的狀態空間複雜度。
在遊戲AI的緣起與進化一文中我們講到，遊戲 AI 的進化始終與 AI 研究相生相伴，這是由於遊戲種類豐富，難度和複雜性也很多樣，人工智能攻克不同類型的遊戲自然也反映了 AI 研究的進展，因此長期以來遊戲一直是 AI 研究的黃金測試平臺。
隨著人工智能逐個攻克雙陸棋、國際跳棋、國際象棋、圍棋等棋類遊戲，AI 仍在繼續挑戰難度更高的遊戲，例如撲克、橋牌、麻將這類不完美信息遊戲。那麼為什麼這類遊戲的難度更高呢？如何衡量不同類型遊戲的複雜度和難度？在這篇文章裡，我們將會為大家仔細解讀。
遊戲複雜度與遊戲難度並不等價
首先需要提醒大家，遊戲的複雜度與難度並不完全等價，遊戲難度除了與遊戲本身的複雜度有關以外，還與戰略等多種要素相關，也就是說，數學上更復雜的遊戲，玩起來不一定更難。
一般來說，我們可以根據信息的暴露程度將遊戲分為兩大類：完美信息遊戲（Perfect-Information Games）和不完美信息遊戲（Imperfect-Information Games）。如果所有的參與者，在遊戲的任何階段都可以訪問所有關於遊戲（包括對手）狀態及其可能延續的信息，那麼稱這類遊戲為完美信息遊戲；否則稱為不完美信息遊戲。圍棋、象棋等棋類遊戲，對局雙方可以看到局面的所有信息，屬於完美信息遊戲；而撲克、橋牌、麻將等遊戲，雖然每個參與者都能看到對手打過的牌，但並不知道對手的手牌和遊戲的底牌，也就是說各個對局者所掌握的信息是不對稱的，因此屬於不完美信息遊戲。
完美信息遊戲和不完美信息遊戲難度的衡量指標通常是有區別的。對於完美信息遊戲，通常遊戲的複雜度就決定了難度，我們可以用狀態空間複雜度（State-Space Complexity）和遊戲樹複雜度（Game-Tree Complexity）對其難度進行衡量；而對於不完美信息遊戲，隱藏信息對於遊戲的難度影響很大，我們可以用信息集（Information Set）數目和信息集平均大小對其難度進行衡量。
完美信息遊戲：狀態空間和遊戲樹的複雜度
狀態空間複雜度（State-Space Complexity）
遊戲的狀態空間複雜度（SSC）是指從遊戲的初始狀態開始，可以達到的所有符合規則的狀態的總數。例如棋類遊戲中，每移動一枚棋子或捕獲一個棋子，就創造了一個新的棋盤狀態，所有這些棋盤狀態構成遊戲的狀態空間。通常情況下，很難精確地計算出遊戲的狀態空間大小，只能給出一個粗略的估計。一種最常用的估計方法是通過包含一些不符合規則或不可能在遊戲中出現的狀態, 從而計算出狀態空間大小的一個上界（Upper Bound）。例如在估計圍棋狀態數目上界的時候，允許出現棋面全部為白棋或者全部為黑棋的極端情況。
事實上，即便像井字棋這樣簡單的遊戲，其狀態空間也是很大的。井字棋的盤面上共有9（3x3）個位置，每個位置可能的取值有三種：X，O或空白，因此總的狀態數目為3的9次方即19863個。當然，這其中包含許多不符合規則的狀態，因為我們在這裡估計的是狀態空間大小的上界。由此，我們可以得到井字棋的狀態空間複雜度約為10^4（即19863≈10^4）。這種計算方法可以很容易地推廣到更大的棋盤和更加複雜的棋類遊戲。比如圍棋有361（19x19）個位置，每個位置可以放置白子或黑子或者空置，利用上述方法，可以確定圍棋的狀態空間複雜度約為10^172 (即3^361≈10^172)。在表1中，我們給出了常見的完美信息棋類遊戲的狀態空間複雜度。
圖1：井字棋
遊戲樹複雜度（Game-Tree Complexity）
遊戲樹複雜度（GTC）表示某個遊戲的所有不同遊戲路徑的數目。遊戲樹複雜度比狀態空間複雜度要大得多，因為同一個狀態可以對應於不同的博弈順序。例如，在圖1的井字棋遊戲中，棋面上有兩個 X 和一個 O，這個狀態可能由兩種不同的方式形成，具體的形成過程由第一個 X 的下子位置所決定。
在遊戲AI的緣起與進化一文中我們講到，遊戲 AI 的進化始終與 AI 研究相生相伴，這是由於遊戲種類豐富，難度和複雜性也很多樣，人工智能攻克不同類型的遊戲自然也反映了 AI 研究的進展，因此長期以來遊戲一直是 AI 研究的黃金測試平臺。
隨著人工智能逐個攻克雙陸棋、國際跳棋、國際象棋、圍棋等棋類遊戲，AI 仍在繼續挑戰難度更高的遊戲，例如撲克、橋牌、麻將這類不完美信息遊戲。那麼為什麼這類遊戲的難度更高呢？如何衡量不同類型遊戲的複雜度和難度？在這篇文章裡，我們將會為大家仔細解讀。
遊戲複雜度與遊戲難度並不等價
首先需要提醒大家，遊戲的複雜度與難度並不完全等價，遊戲難度除了與遊戲本身的複雜度有關以外，還與戰略等多種要素相關，也就是說，數學上更復雜的遊戲，玩起來不一定更難。
一般來說，我們可以根據信息的暴露程度將遊戲分為兩大類：完美信息遊戲（Perfect-Information Games）和不完美信息遊戲（Imperfect-Information Games）。如果所有的參與者，在遊戲的任何階段都可以訪問所有關於遊戲（包括對手）狀態及其可能延續的信息，那麼稱這類遊戲為完美信息遊戲；否則稱為不完美信息遊戲。圍棋、象棋等棋類遊戲，對局雙方可以看到局面的所有信息，屬於完美信息遊戲；而撲克、橋牌、麻將等遊戲，雖然每個參與者都能看到對手打過的牌，但並不知道對手的手牌和遊戲的底牌，也就是說各個對局者所掌握的信息是不對稱的，因此屬於不完美信息遊戲。
完美信息遊戲和不完美信息遊戲難度的衡量指標通常是有區別的。對於完美信息遊戲，通常遊戲的複雜度就決定了難度，我們可以用狀態空間複雜度（State-Space Complexity）和遊戲樹複雜度（Game-Tree Complexity）對其難度進行衡量；而對於不完美信息遊戲，隱藏信息對於遊戲的難度影響很大，我們可以用信息集（Information Set）數目和信息集平均大小對其難度進行衡量。
完美信息遊戲：狀態空間和遊戲樹的複雜度
狀態空間複雜度（State-Space Complexity）
遊戲的狀態空間複雜度（SSC）是指從遊戲的初始狀態開始，可以達到的所有符合規則的狀態的總數。例如棋類遊戲中，每移動一枚棋子或捕獲一個棋子，就創造了一個新的棋盤狀態，所有這些棋盤狀態構成遊戲的狀態空間。通常情況下，很難精確地計算出遊戲的狀態空間大小，只能給出一個粗略的估計。一種最常用的估計方法是通過包含一些不符合規則或不可能在遊戲中出現的狀態, 從而計算出狀態空間大小的一個上界（Upper Bound）。例如在估計圍棋狀態數目上界的時候，允許出現棋面全部為白棋或者全部為黑棋的極端情況。
事實上，即便像井字棋這樣簡單的遊戲，其狀態空間也是很大的。井字棋的盤面上共有9（3x3）個位置，每個位置可能的取值有三種：X，O或空白，因此總的狀態數目為3的9次方即19863個。當然，這其中包含許多不符合規則的狀態，因為我們在這裡估計的是狀態空間大小的上界。由此，我們可以得到井字棋的狀態空間複雜度約為10^4（即19863≈10^4）。這種計算方法可以很容易地推廣到更大的棋盤和更加複雜的棋類遊戲。比如圍棋有361（19x19）個位置，每個位置可以放置白子或黑子或者空置，利用上述方法，可以確定圍棋的狀態空間複雜度約為10^172 (即3^361≈10^172)。在表1中，我們給出了常見的完美信息棋類遊戲的狀態空間複雜度。
圖1：井字棋
遊戲樹複雜度（Game-Tree Complexity）
遊戲樹複雜度（GTC）表示某個遊戲的所有不同遊戲路徑的數目。遊戲樹複雜度比狀態空間複雜度要大得多，因為同一個狀態可以對應於不同的博弈順序。例如，在圖1的井字棋遊戲中，棋面上有兩個 X 和一個 O，這個狀態可能由兩種不同的方式形成，具體的形成過程由第一個 X 的下子位置所決定。
圖2：井字棋遊戲中統一狀態的不同形成過程
與狀態空間類似，遊戲樹複雜度的精確值也很難計算。常用的方法是估計其合理的下界：GTC≥b^p，其中 b 表示玩家每回合可用的平均合法移動數目，p 表示平均遊戲長度。由此可以看出，擁有更多合法移動的遊戲比合法移動較少的遊戲更復雜，另外遊戲的平均長度也是影響遊戲樹複雜度的關鍵因素。
根據經驗，井字棋、象棋以及圍棋每一步的平均合法移動數目分別為4、35和250；平均遊戲長度分別為9、80和150。因此利用上面的公式，可以得出井字棋的遊戲樹複雜度為10^5 (即4^9≈10^5)，國際象棋是10^123 (即35^80≈10^123)，而圍棋是10^360 (即250^150≈10^360)。更多完美信息棋牌類遊戲的遊戲樹複雜度參見表1。
在遊戲AI的緣起與進化一文中我們講到，遊戲 AI 的進化始終與 AI 研究相生相伴，這是由於遊戲種類豐富，難度和複雜性也很多樣，人工智能攻克不同類型的遊戲自然也反映了 AI 研究的進展，因此長期以來遊戲一直是 AI 研究的黃金測試平臺。
隨著人工智能逐個攻克雙陸棋、國際跳棋、國際象棋、圍棋等棋類遊戲，AI 仍在繼續挑戰難度更高的遊戲，例如撲克、橋牌、麻將這類不完美信息遊戲。那麼為什麼這類遊戲的難度更高呢？如何衡量不同類型遊戲的複雜度和難度？在這篇文章裡，我們將會為大家仔細解讀。
遊戲複雜度與遊戲難度並不等價
首先需要提醒大家，遊戲的複雜度與難度並不完全等價，遊戲難度除了與遊戲本身的複雜度有關以外，還與戰略等多種要素相關，也就是說，數學上更復雜的遊戲，玩起來不一定更難。
一般來說，我們可以根據信息的暴露程度將遊戲分為兩大類：完美信息遊戲（Perfect-Information Games）和不完美信息遊戲（Imperfect-Information Games）。如果所有的參與者，在遊戲的任何階段都可以訪問所有關於遊戲（包括對手）狀態及其可能延續的信息，那麼稱這類遊戲為完美信息遊戲；否則稱為不完美信息遊戲。圍棋、象棋等棋類遊戲，對局雙方可以看到局面的所有信息，屬於完美信息遊戲；而撲克、橋牌、麻將等遊戲，雖然每個參與者都能看到對手打過的牌，但並不知道對手的手牌和遊戲的底牌，也就是說各個對局者所掌握的信息是不對稱的，因此屬於不完美信息遊戲。
完美信息遊戲和不完美信息遊戲難度的衡量指標通常是有區別的。對於完美信息遊戲，通常遊戲的複雜度就決定了難度，我們可以用狀態空間複雜度（State-Space Complexity）和遊戲樹複雜度（Game-Tree Complexity）對其難度進行衡量；而對於不完美信息遊戲，隱藏信息對於遊戲的難度影響很大，我們可以用信息集（Information Set）數目和信息集平均大小對其難度進行衡量。
完美信息遊戲：狀態空間和遊戲樹的複雜度
狀態空間複雜度（State-Space Complexity）
遊戲的狀態空間複雜度（SSC）是指從遊戲的初始狀態開始，可以達到的所有符合規則的狀態的總數。例如棋類遊戲中，每移動一枚棋子或捕獲一個棋子，就創造了一個新的棋盤狀態，所有這些棋盤狀態構成遊戲的狀態空間。通常情況下，很難精確地計算出遊戲的狀態空間大小，只能給出一個粗略的估計。一種最常用的估計方法是通過包含一些不符合規則或不可能在遊戲中出現的狀態, 從而計算出狀態空間大小的一個上界（Upper Bound）。例如在估計圍棋狀態數目上界的時候，允許出現棋面全部為白棋或者全部為黑棋的極端情況。
事實上，即便像井字棋這樣簡單的遊戲，其狀態空間也是很大的。井字棋的盤面上共有9（3x3）個位置，每個位置可能的取值有三種：X，O或空白，因此總的狀態數目為3的9次方即19863個。當然，這其中包含許多不符合規則的狀態，因為我們在這裡估計的是狀態空間大小的上界。由此，我們可以得到井字棋的狀態空間複雜度約為10^4（即19863≈10^4）。這種計算方法可以很容易地推廣到更大的棋盤和更加複雜的棋類遊戲。比如圍棋有361（19x19）個位置，每個位置可以放置白子或黑子或者空置，利用上述方法，可以確定圍棋的狀態空間複雜度約為10^172 (即3^361≈10^172)。在表1中，我們給出了常見的完美信息棋類遊戲的狀態空間複雜度。
圖1：井字棋
遊戲樹複雜度（Game-Tree Complexity）
遊戲樹複雜度（GTC）表示某個遊戲的所有不同遊戲路徑的數目。遊戲樹複雜度比狀態空間複雜度要大得多，因為同一個狀態可以對應於不同的博弈順序。例如，在圖1的井字棋遊戲中，棋面上有兩個 X 和一個 O，這個狀態可能由兩種不同的方式形成，具體的形成過程由第一個 X 的下子位置所決定。
圖2：井字棋遊戲中統一狀態的不同形成過程
與狀態空間類似，遊戲樹複雜度的精確值也很難計算。常用的方法是估計其合理的下界：GTC≥b^p，其中 b 表示玩家每回合可用的平均合法移動數目，p 表示平均遊戲長度。由此可以看出，擁有更多合法移動的遊戲比合法移動較少的遊戲更復雜，另外遊戲的平均長度也是影響遊戲樹複雜度的關鍵因素。
根據經驗，井字棋、象棋以及圍棋每一步的平均合法移動數目分別為4、35和250；平均遊戲長度分別為9、80和150。因此利用上面的公式，可以得出井字棋的遊戲樹複雜度為10^5 (即4^9≈10^5)，國際象棋是10^123 (即35^80≈10^123)，而圍棋是10^360 (即250^150≈10^360)。更多完美信息棋牌類遊戲的遊戲樹複雜度參見表1。
表1：完美信息遊戲的狀態空間複雜度和遊戲樹複雜度
在傳統的完美信息棋牌遊戲中，圍棋不管從狀態空間複雜度，還是遊戲樹複雜度上都遠遠領先其他棋牌類遊戲。2017年，AlphaZero 利用 MCTS 和深度強化學習，成功解決了包括圍棋在內的多個完美信息遊戲。目前，學術界研究的熱點則轉向不完美信息遊戲和即時策略遊戲等。
不完美信息遊戲：信息集數目和平均大小
對於不完美信息遊戲，我們仍然可以同完美信息遊戲一樣計算其狀態空間複雜度和遊戲樹複雜度。然而，在不完美信息遊戲中，由於信息是不完全、非對稱的（例如撲克和麻將中對手的手牌和遊戲剩餘的底牌都是未知的），因此對於參與者來說許多不同的遊戲狀態看起來是無法區分的。例如在撲克遊戲中，自己拿了兩張 K，對方拿了不同的牌對應不同的狀態；但是從自己的視角看，這些狀態其實是不可區分的。我們把每組這種無法區分的遊戲狀態稱為一個信息集。
顯然，對於不完美信息遊戲而言，合理的遊戲策略應該建立在信息集而不是遊戲狀態之上，因為我們依賴未知信息來細粒度出招是沒有意義的。相應地，當我們衡量不完美信息遊戲的難度的時候，也應該依據信息集的數目，而不是遊戲狀態空間的大小。信息集的數目通常小於狀態空間的數目。對於完美信息遊戲，由於所有信息都是已知的，每個信息集只包含一個遊戲狀態，因此它的信息集數目與狀態空間數目是相等的。
除了信息集的數目，還有一個重要的指標：信息集的平均大小，即在信息集中平均有多少不可區分的遊戲狀態。以兩人德州撲克為例，假定我們的手牌是 AA，考慮對手的手牌為 AK 或者 AQ 兩種不同情況。因為信息不完全，我們無法區分當前局勢到底處在哪個狀態，因此會把兩種情況都歸到同一個信息集。在兩人德州撲克中，信息集的大小最多為1326（從52張牌中選擇2張：C_52^2），也就是約為10^3。容易看出，信息集的數目反映了不完美信息遊戲中所有可能的決策節點的數目，而信息集的平均大小則反映了遊戲中每個局面背後隱藏信息的數量。顯然，信息集平均大小越大，其中包含的未知信息就越多，因此決策的難度就越高。事實上，信息集的平均大小直接影響採用搜索算法的可行性：當對手的隱藏狀態非常多時，傳統的搜索算法基本上是無從下手的。因此信息集的平均大小也可以作為遊戲難度的衡量指標。
在遊戲AI的緣起與進化一文中我們講到，遊戲 AI 的進化始終與 AI 研究相生相伴，這是由於遊戲種類豐富，難度和複雜性也很多樣，人工智能攻克不同類型的遊戲自然也反映了 AI 研究的進展，因此長期以來遊戲一直是 AI 研究的黃金測試平臺。
隨著人工智能逐個攻克雙陸棋、國際跳棋、國際象棋、圍棋等棋類遊戲，AI 仍在繼續挑戰難度更高的遊戲，例如撲克、橋牌、麻將這類不完美信息遊戲。那麼為什麼這類遊戲的難度更高呢？如何衡量不同類型遊戲的複雜度和難度？在這篇文章裡，我們將會為大家仔細解讀。
遊戲複雜度與遊戲難度並不等價
首先需要提醒大家，遊戲的複雜度與難度並不完全等價，遊戲難度除了與遊戲本身的複雜度有關以外，還與戰略等多種要素相關，也就是說，數學上更復雜的遊戲，玩起來不一定更難。
一般來說，我們可以根據信息的暴露程度將遊戲分為兩大類：完美信息遊戲（Perfect-Information Games）和不完美信息遊戲（Imperfect-Information Games）。如果所有的參與者，在遊戲的任何階段都可以訪問所有關於遊戲（包括對手）狀態及其可能延續的信息，那麼稱這類遊戲為完美信息遊戲；否則稱為不完美信息遊戲。圍棋、象棋等棋類遊戲，對局雙方可以看到局面的所有信息，屬於完美信息遊戲；而撲克、橋牌、麻將等遊戲，雖然每個參與者都能看到對手打過的牌，但並不知道對手的手牌和遊戲的底牌，也就是說各個對局者所掌握的信息是不對稱的，因此屬於不完美信息遊戲。
完美信息遊戲和不完美信息遊戲難度的衡量指標通常是有區別的。對於完美信息遊戲，通常遊戲的複雜度就決定了難度，我們可以用狀態空間複雜度（State-Space Complexity）和遊戲樹複雜度（Game-Tree Complexity）對其難度進行衡量；而對於不完美信息遊戲，隱藏信息對於遊戲的難度影響很大，我們可以用信息集（Information Set）數目和信息集平均大小對其難度進行衡量。
完美信息遊戲：狀態空間和遊戲樹的複雜度
狀態空間複雜度（State-Space Complexity）
遊戲的狀態空間複雜度（SSC）是指從遊戲的初始狀態開始，可以達到的所有符合規則的狀態的總數。例如棋類遊戲中，每移動一枚棋子或捕獲一個棋子，就創造了一個新的棋盤狀態，所有這些棋盤狀態構成遊戲的狀態空間。通常情況下，很難精確地計算出遊戲的狀態空間大小，只能給出一個粗略的估計。一種最常用的估計方法是通過包含一些不符合規則或不可能在遊戲中出現的狀態, 從而計算出狀態空間大小的一個上界（Upper Bound）。例如在估計圍棋狀態數目上界的時候，允許出現棋面全部為白棋或者全部為黑棋的極端情況。
事實上，即便像井字棋這樣簡單的遊戲，其狀態空間也是很大的。井字棋的盤面上共有9（3x3）個位置，每個位置可能的取值有三種：X，O或空白，因此總的狀態數目為3的9次方即19863個。當然，這其中包含許多不符合規則的狀態，因為我們在這裡估計的是狀態空間大小的上界。由此，我們可以得到井字棋的狀態空間複雜度約為10^4（即19863≈10^4）。這種計算方法可以很容易地推廣到更大的棋盤和更加複雜的棋類遊戲。比如圍棋有361（19x19）個位置，每個位置可以放置白子或黑子或者空置，利用上述方法，可以確定圍棋的狀態空間複雜度約為10^172 (即3^361≈10^172)。在表1中，我們給出了常見的完美信息棋類遊戲的狀態空間複雜度。
圖1：井字棋
遊戲樹複雜度（Game-Tree Complexity）
遊戲樹複雜度（GTC）表示某個遊戲的所有不同遊戲路徑的數目。遊戲樹複雜度比狀態空間複雜度要大得多，因為同一個狀態可以對應於不同的博弈順序。例如，在圖1的井字棋遊戲中，棋面上有兩個 X 和一個 O，這個狀態可能由兩種不同的方式形成，具體的形成過程由第一個 X 的下子位置所決定。
圖2：井字棋遊戲中統一狀態的不同形成過程
與狀態空間類似，遊戲樹複雜度的精確值也很難計算。常用的方法是估計其合理的下界：GTC≥b^p，其中 b 表示玩家每回合可用的平均合法移動數目，p 表示平均遊戲長度。由此可以看出，擁有更多合法移動的遊戲比合法移動較少的遊戲更復雜，另外遊戲的平均長度也是影響遊戲樹複雜度的關鍵因素。
根據經驗，井字棋、象棋以及圍棋每一步的平均合法移動數目分別為4、35和250；平均遊戲長度分別為9、80和150。因此利用上面的公式，可以得出井字棋的遊戲樹複雜度為10^5 (即4^9≈10^5)，國際象棋是10^123 (即35^80≈10^123)，而圍棋是10^360 (即250^150≈10^360)。更多完美信息棋牌類遊戲的遊戲樹複雜度參見表1。
表1：完美信息遊戲的狀態空間複雜度和遊戲樹複雜度
在傳統的完美信息棋牌遊戲中，圍棋不管從狀態空間複雜度，還是遊戲樹複雜度上都遠遠領先其他棋牌類遊戲。2017年，AlphaZero 利用 MCTS 和深度強化學習，成功解決了包括圍棋在內的多個完美信息遊戲。目前，學術界研究的熱點則轉向不完美信息遊戲和即時策略遊戲等。
不完美信息遊戲：信息集數目和平均大小
對於不完美信息遊戲，我們仍然可以同完美信息遊戲一樣計算其狀態空間複雜度和遊戲樹複雜度。然而，在不完美信息遊戲中，由於信息是不完全、非對稱的（例如撲克和麻將中對手的手牌和遊戲剩餘的底牌都是未知的），因此對於參與者來說許多不同的遊戲狀態看起來是無法區分的。例如在撲克遊戲中，自己拿了兩張 K，對方拿了不同的牌對應不同的狀態；但是從自己的視角看，這些狀態其實是不可區分的。我們把每組這種無法區分的遊戲狀態稱為一個信息集。
顯然，對於不完美信息遊戲而言，合理的遊戲策略應該建立在信息集而不是遊戲狀態之上，因為我們依賴未知信息來細粒度出招是沒有意義的。相應地，當我們衡量不完美信息遊戲的難度的時候，也應該依據信息集的數目，而不是遊戲狀態空間的大小。信息集的數目通常小於狀態空間的數目。對於完美信息遊戲，由於所有信息都是已知的，每個信息集只包含一個遊戲狀態，因此它的信息集數目與狀態空間數目是相等的。
除了信息集的數目，還有一個重要的指標：信息集的平均大小，即在信息集中平均有多少不可區分的遊戲狀態。以兩人德州撲克為例，假定我們的手牌是 AA，考慮對手的手牌為 AK 或者 AQ 兩種不同情況。因為信息不完全，我們無法區分當前局勢到底處在哪個狀態，因此會把兩種情況都歸到同一個信息集。在兩人德州撲克中，信息集的大小最多為1326（從52張牌中選擇2張：C_52^2），也就是約為10^3。容易看出，信息集的數目反映了不完美信息遊戲中所有可能的決策節點的數目，而信息集的平均大小則反映了遊戲中每個局面背後隱藏信息的數量。顯然，信息集平均大小越大，其中包含的未知信息就越多，因此決策的難度就越高。事實上，信息集的平均大小直接影響採用搜索算法的可行性：當對手的隱藏狀態非常多時，傳統的搜索算法基本上是無從下手的。因此信息集的平均大小也可以作為遊戲難度的衡量指標。
表2：不完美信息遊戲的信息集數目和信息集平均大小
無限注德州撲克的信息集數目很大，但是因為只有兩張不可見的牌，其隱藏信息很少，信息集的平均大小很小。橋牌和麻將由於是每個玩家手裡可以有13張未知的手牌，因此隱藏信息的數量遠遠超過了德州撲克。表2給出了德州撲克、橋牌和麻將的信息集數目和信息集的平均大小。
如果我們以信息集數目和信息集平均大小為準則，來對比像圍棋這樣的完美信息遊戲和表2中的幾種不完美信息遊戲，會得到非常有意思的結果。如圖3所示，圍棋和德州撲克的信息集平均大小遠遠小於橋牌和麻將。AI 在圍棋和德州撲克上的成功很大程度依賴於搜索算法，因為搜索可以最大程度地發揮計算機的計算優勢。但是因為巨大的信息集平均大小帶來的環境不確定性，傳統的搜索算法在橋牌和麻將面前很難發揮同樣的功效。
在遊戲AI的緣起與進化一文中我們講到，遊戲 AI 的進化始終與 AI 研究相生相伴，這是由於遊戲種類豐富，難度和複雜性也很多樣，人工智能攻克不同類型的遊戲自然也反映了 AI 研究的進展，因此長期以來遊戲一直是 AI 研究的黃金測試平臺。
隨著人工智能逐個攻克雙陸棋、國際跳棋、國際象棋、圍棋等棋類遊戲，AI 仍在繼續挑戰難度更高的遊戲，例如撲克、橋牌、麻將這類不完美信息遊戲。那麼為什麼這類遊戲的難度更高呢？如何衡量不同類型遊戲的複雜度和難度？在這篇文章裡，我們將會為大家仔細解讀。
遊戲複雜度與遊戲難度並不等價
首先需要提醒大家，遊戲的複雜度與難度並不完全等價，遊戲難度除了與遊戲本身的複雜度有關以外，還與戰略等多種要素相關，也就是說，數學上更復雜的遊戲，玩起來不一定更難。
一般來說，我們可以根據信息的暴露程度將遊戲分為兩大類：完美信息遊戲（Perfect-Information Games）和不完美信息遊戲（Imperfect-Information Games）。如果所有的參與者，在遊戲的任何階段都可以訪問所有關於遊戲（包括對手）狀態及其可能延續的信息，那麼稱這類遊戲為完美信息遊戲；否則稱為不完美信息遊戲。圍棋、象棋等棋類遊戲，對局雙方可以看到局面的所有信息，屬於完美信息遊戲；而撲克、橋牌、麻將等遊戲，雖然每個參與者都能看到對手打過的牌，但並不知道對手的手牌和遊戲的底牌，也就是說各個對局者所掌握的信息是不對稱的，因此屬於不完美信息遊戲。
完美信息遊戲和不完美信息遊戲難度的衡量指標通常是有區別的。對於完美信息遊戲，通常遊戲的複雜度就決定了難度，我們可以用狀態空間複雜度（State-Space Complexity）和遊戲樹複雜度（Game-Tree Complexity）對其難度進行衡量；而對於不完美信息遊戲，隱藏信息對於遊戲的難度影響很大，我們可以用信息集（Information Set）數目和信息集平均大小對其難度進行衡量。
完美信息遊戲：狀態空間和遊戲樹的複雜度
狀態空間複雜度（State-Space Complexity）
遊戲的狀態空間複雜度（SSC）是指從遊戲的初始狀態開始，可以達到的所有符合規則的狀態的總數。例如棋類遊戲中，每移動一枚棋子或捕獲一個棋子，就創造了一個新的棋盤狀態，所有這些棋盤狀態構成遊戲的狀態空間。通常情況下，很難精確地計算出遊戲的狀態空間大小，只能給出一個粗略的估計。一種最常用的估計方法是通過包含一些不符合規則或不可能在遊戲中出現的狀態, 從而計算出狀態空間大小的一個上界（Upper Bound）。例如在估計圍棋狀態數目上界的時候，允許出現棋面全部為白棋或者全部為黑棋的極端情況。
事實上，即便像井字棋這樣簡單的遊戲，其狀態空間也是很大的。井字棋的盤面上共有9（3x3）個位置，每個位置可能的取值有三種：X，O或空白，因此總的狀態數目為3的9次方即19863個。當然，這其中包含許多不符合規則的狀態，因為我們在這裡估計的是狀態空間大小的上界。由此，我們可以得到井字棋的狀態空間複雜度約為10^4（即19863≈10^4）。這種計算方法可以很容易地推廣到更大的棋盤和更加複雜的棋類遊戲。比如圍棋有361（19x19）個位置，每個位置可以放置白子或黑子或者空置，利用上述方法，可以確定圍棋的狀態空間複雜度約為10^172 (即3^361≈10^172)。在表1中，我們給出了常見的完美信息棋類遊戲的狀態空間複雜度。
圖1：井字棋
遊戲樹複雜度（Game-Tree Complexity）
遊戲樹複雜度（GTC）表示某個遊戲的所有不同遊戲路徑的數目。遊戲樹複雜度比狀態空間複雜度要大得多，因為同一個狀態可以對應於不同的博弈順序。例如，在圖1的井字棋遊戲中，棋面上有兩個 X 和一個 O，這個狀態可能由兩種不同的方式形成，具體的形成過程由第一個 X 的下子位置所決定。
圖2：井字棋遊戲中統一狀態的不同形成過程
與狀態空間類似，遊戲樹複雜度的精確值也很難計算。常用的方法是估計其合理的下界：GTC≥b^p，其中 b 表示玩家每回合可用的平均合法移動數目，p 表示平均遊戲長度。由此可以看出，擁有更多合法移動的遊戲比合法移動較少的遊戲更復雜，另外遊戲的平均長度也是影響遊戲樹複雜度的關鍵因素。
根據經驗，井字棋、象棋以及圍棋每一步的平均合法移動數目分別為4、35和250；平均遊戲長度分別為9、80和150。因此利用上面的公式，可以得出井字棋的遊戲樹複雜度為10^5 (即4^9≈10^5)，國際象棋是10^123 (即35^80≈10^123)，而圍棋是10^360 (即250^150≈10^360)。更多完美信息棋牌類遊戲的遊戲樹複雜度參見表1。
表1：完美信息遊戲的狀態空間複雜度和遊戲樹複雜度
在傳統的完美信息棋牌遊戲中，圍棋不管從狀態空間複雜度，還是遊戲樹複雜度上都遠遠領先其他棋牌類遊戲。2017年，AlphaZero 利用 MCTS 和深度強化學習，成功解決了包括圍棋在內的多個完美信息遊戲。目前，學術界研究的熱點則轉向不完美信息遊戲和即時策略遊戲等。
不完美信息遊戲：信息集數目和平均大小
對於不完美信息遊戲，我們仍然可以同完美信息遊戲一樣計算其狀態空間複雜度和遊戲樹複雜度。然而，在不完美信息遊戲中，由於信息是不完全、非對稱的（例如撲克和麻將中對手的手牌和遊戲剩餘的底牌都是未知的），因此對於參與者來說許多不同的遊戲狀態看起來是無法區分的。例如在撲克遊戲中，自己拿了兩張 K，對方拿了不同的牌對應不同的狀態；但是從自己的視角看，這些狀態其實是不可區分的。我們把每組這種無法區分的遊戲狀態稱為一個信息集。
顯然，對於不完美信息遊戲而言，合理的遊戲策略應該建立在信息集而不是遊戲狀態之上，因為我們依賴未知信息來細粒度出招是沒有意義的。相應地，當我們衡量不完美信息遊戲的難度的時候，也應該依據信息集的數目，而不是遊戲狀態空間的大小。信息集的數目通常小於狀態空間的數目。對於完美信息遊戲，由於所有信息都是已知的，每個信息集只包含一個遊戲狀態，因此它的信息集數目與狀態空間數目是相等的。
除了信息集的數目，還有一個重要的指標：信息集的平均大小，即在信息集中平均有多少不可區分的遊戲狀態。以兩人德州撲克為例，假定我們的手牌是 AA，考慮對手的手牌為 AK 或者 AQ 兩種不同情況。因為信息不完全，我們無法區分當前局勢到底處在哪個狀態，因此會把兩種情況都歸到同一個信息集。在兩人德州撲克中，信息集的大小最多為1326（從52張牌中選擇2張：C_52^2），也就是約為10^3。容易看出，信息集的數目反映了不完美信息遊戲中所有可能的決策節點的數目，而信息集的平均大小則反映了遊戲中每個局面背後隱藏信息的數量。顯然，信息集平均大小越大，其中包含的未知信息就越多，因此決策的難度就越高。事實上，信息集的平均大小直接影響採用搜索算法的可行性：當對手的隱藏狀態非常多時，傳統的搜索算法基本上是無從下手的。因此信息集的平均大小也可以作為遊戲難度的衡量指標。
表2：不完美信息遊戲的信息集數目和信息集平均大小
無限注德州撲克的信息集數目很大，但是因為只有兩張不可見的牌，其隱藏信息很少，信息集的平均大小很小。橋牌和麻將由於是每個玩家手裡可以有13張未知的手牌，因此隱藏信息的數量遠遠超過了德州撲克。表2給出了德州撲克、橋牌和麻將的信息集數目和信息集的平均大小。
如果我們以信息集數目和信息集平均大小為準則，來對比像圍棋這樣的完美信息遊戲和表2中的幾種不完美信息遊戲，會得到非常有意思的結果。如圖3所示，圍棋和德州撲克的信息集平均大小遠遠小於橋牌和麻將。AI 在圍棋和德州撲克上的成功很大程度依賴於搜索算法，因為搜索可以最大程度地發揮計算機的計算優勢。但是因為巨大的信息集平均大小帶來的環境不確定性，傳統的搜索算法在橋牌和麻將面前很難發揮同樣的功效。
圖3：圍棋、德州撲克、橋牌和麻將的信息集數目和信息集平均大小對比
回顧遊戲 AI 的歷史，目前大部分完美信息遊戲（如國際象棋、圍棋等）以及信息集平均大小較小的不完美信息遊戲（如兩人德州撲克和多人德州撲克等）都有了相當好的解決方法。然而，對於橋牌和麻將這類含有大量隱藏信息的不完美信息遊戲，需要我們發明全新的方法論，才能有所突破，而這需要 AI 算法的研究者們持之以恆地探索。
延伸閱讀：遊戲難度的計算方法
定約橋牌（只考慮打牌階段）
信息集數目：以防守一方為例，按照遊戲輪次來計算。第一輪，每個玩家只能看到自己的13張牌，因此第一輪信息集數目為C_52^13=6.3×10^11。第二輪，每個玩家剩餘12張牌，玩家只能看到自己的12張手牌以及第一輪出的四張牌，因此第二輪信息集數目為C_52^13 C_13^1 C_39^1 C_38^1 C_37^1=C_52^13 A_13^1 A_39^3。以此類推，第三輪信息集數目為C_52^13 C_13^1 C_12^1 C_39^1 C_38^1 C_37^1 C_36^1 C_35^1 C_34^1=C_52^13 A_13^2 A_39^6 … 第13輪信息集數目為C_52^13 A_13^12 A_39^36。總的信息集數目為各輪信息集的和，即C_52^13 (1+A_13^1 A_39^3+⋯+A_13^12 A_39^36)≈1.35×10^67。
信息集平均大小：以防守一方為例，第一輪，其他選手有13張牌，所以每個信息集大小為C_39^13 C_26^13 C_13^13。第二輪，每位對手還剩12張牌，因此每個信息集大小為C_36^12 C_24^12 C_12^12。以此類推，第13輪，每個信息集大小為C_3^1 C_2^1。對每一輪的信息集大小求平均，得到橋牌的信息集平均大小≈6.77×10^15。
麻將
信息集數目：每一局麻將結束的時候，底下有14張牌不會被用到，所以不考慮吃碰槓的情況下，每一局至多會進行17.5輪（136減去13x4共52張手牌再減去14張底牌，總共剩70張牌，每一輪出4張）。與橋牌類似，依然按照遊戲輪次來計算。第一輪，每個玩家只能看到自己的13張牌，因此第一輪信息集數目為C_136^13(為了計算方便，不考慮重複手牌)。第二輪，由於第一輪每個玩家各出一張牌，一副麻將總共有34種不同的牌，所以第一輪出的四張牌所有可能的情況至多為34^4，因此第二輪信息集數目為C_136^13 ∙34^4。以此類推，第18輪信息集數目為C_136^13 ∙34^68。總的信息集數目為各輪信息集的和，即C_136^13 (1+34^4+⋯+34^68)≈7×10^121。
信息集平均大小：第一輪，除去自己13張手牌，總共剩餘123張牌，每位對手13張牌，所以每個信息集大小為C_123^13 C_110^13 C_97^13（為了計算方便，不考慮重複手牌）。第二輪，除去自己13張手牌，以及第一輪出的四張牌，總共剩餘119張牌，因此每個信息集大小為C_119^13 C_106^13 C_93^13。以此類推，第18輪，每個信息集大小為C_55^13 C_42^13 C_29^13。對每一輪的信息集大小求平均，得到麻將的信息集平均大小≈1.07×10^48。
參考文獻：
[1]L.V. Allis, Searching for solutions in games and artificial intelligence, Ph.D.Thesis, University of Limburg, Maastricht, 1994.
[2]van den Herik, H., Uiterwijk, J. W. & van Rijswijck, J. Games solved: now and in the future. Artif. Intell. 134, 277–311 (2002).
[3]Game Complexity I: State-Space & Game-Tree Complexities
https://www.pipmodern.com/feed/state-space-game-tree-complexity
[4]Game Complexity III: Artificial Intelligence
https://www.pipmodern.com/feed/complexity-artificial-intelligence
[5]M. Johanson, Measuring the size of large no-limit poker games, Technical Report TR13-01, Department of Computing Science, University of Alberta (2013).
[6]Wiki: Game complexity
https://en.wikipedia.org/wiki/Game_complexity