text: 圍棋是世界上最流行的遊戲之一。由於其規則優美而簡單，圍棋一直是數學研究的靈感11世紀的中國學者沈括在《夢溪筆談》中估計，圍棋所有可能的局面數量為 10172 左右。近年來，約翰·H·康威在對圍棋的研究中發明了超現實數，並促進了的發展。計算複雜性.廣義圍棋是在 "n x n" 的棋盤上進行的，在廣義圍棋的給定位置確定贏家的計算複雜性主要取決於打劫規則。圍棋的複雜性“幾乎”是在PSPACE內的，這是因為在對弈的非打劫階段，每一手都是不可逆的，只有透過吃子才有可能出現重複的棋形，使得複雜性提高。沒有打劫的情況.沒有打劫的話，圍棋是PSPACE困難的。 這是透過把PSPACE完全的TQBF簡化到，到平面廣義地理，到最高3階的廣義地理，最後簡化到圍棋棋盤位置。有打劫的圍棋則不在PSPACE中。儘管實際的棋局似乎從沒超出過 formula_1 手，但一般而言，沒有人知道圍棋棋局的手數是否有一個多項式上限。如果有的話，圍棋就會是PSPACE完全的。就目前而言，圍棋可能是PSPACE完全，EXPTIME完全，甚至EXPSPACE完全的。日本打劫規則.日本規則只規定了基本的劫，即一手棋下了之後，如果會恢復這手棋下之前的那個棋盤狀態，那麼這手棋是不允許下的。如果重複多手之前的棋盤狀態是允許的，這也就意味著一局棋可以永久迴圈，如三劫迴圈，即同時有三個劫，經過12手就可以迴圈。在日本打劫規則下，圍棋是EXPTIME完全的。禁止全域性同形規則.禁止全域性同形規則是說重複出現任何先前棋盤狀態都是不允許的。這是大多數中國和美國規則中使用的打劫規則。在禁止全域性同形規則下圍棋的複雜性類為何，是一個未解決的問題。雖然日本打劫規則下圍棋的複雜性為EXPTIME完全已被證明，但Robson的這個證明中，無論是上界還是下界的EXPTIME完全性的證明，都打破了禁止全域性同形規則。至少現在已知，其複雜性至少是PSPACE困難，因為中對圍棋的PSPACE困難性的證明是不依賴於打劫規則的，或者說即便是沒有打劫規則，也是PSPACE困難的。現在還知道圍棋的複雜性是在EXPSPACE內的。Robson證明了如果在EXPTIME完全的雙人遊戲的基礎上，加上“禁止全域性同形”的規則，遊戲複雜性將會變為EXPSPACE完全。直觀地說，這是因為對加入新規則的遊戲來說，即便是確定一個局面下符合規則的下法，都需要指數級別的空間，因為從開局下到某一局面的長度是有可能達到指數級別的。因此，廣義國際象棋和西洋跳棋的禁止全域性同形版本都是EXPSPACE完全的，因為廣義國際象棋和西洋跳棋都是EXPTIME完全的。不過這個結果不適用於圍棋。圍棋特定情形的複雜性.當棋盤被活子把棋盤分割成若干孤立的區域的時候，圍棋就進入了官子階段，這時每個區域性區域都會有一個多項式級別的規範博弈樹。用的話來說，當圍棋分解成具有多項式級別規範博弈樹的子博弈之和時，就會進入官子。在這個定義下，圍棋的收官是PSPACE困難的。這可以透過將PSPACE完全的QBF圍棋子游戲的總和來證明。請注意，論文並未證明圍棋是在PSPACE中的，所以就有不是PSPACE完全的可能性。確定哪一方徵子有利是PSPACE完全的，無論是日本打劫規則還是禁止全域性同形規則。 這一點可以透過模仿QBF證明。合法局面.由於棋盤上每個位置都可以為空、白棋、黑棋三種情況，所以對於邊長為 n 的棋盤總共有 3n2 種可能的局面；但只有一部分是合法的。Tromp和Farnebäck推導了長 m 寬 n 的矩形棋盤的合法局面 formula_2 的遞迴公式。 在2016年算出了 formula_3 的準確數字。他們還發現了一個漸進公式 formula_4，其中 formula_5，formula_6，formula_7。據估計，可觀測宇宙包含大約 1080 個原子，遠小於常規圍棋棋盤上所有可能的合法局面的數目。隨著棋盤變大，合法局面的比例也會降低。博弈樹複雜性.電腦科學家Victor Allis指出，職業棋士之間對弈一般在150手左右，平均每手約250種選擇，這就意味著博弈樹複雜性為 10360。 對於"理論上可能"的棋局數量，包括在實際中不可能下出的棋局，Tromp和Farnebäck分別給出 10480 的下限和 101710 的上限。人們聽到最多的所有可能的棋局數量為 10700， 這個數字是361手棋的簡單排列種可能的棋局。所有可能的對局總數是棋盤大小和手數的函式。雖然大多數棋局都在400手以內，甚至200手都不到，但棋局是有可能更長的。所有可能的對局總數可以透過多種方式從棋盤大小估算，有些方式會比另外一些更嚴格。最簡單的，棋盤大小的簡單排列 (N)L，沒有考慮到非法吃子，以及非法的盤面。令 N 為棋盤大小，L 為最長的棋局長度，NL 構成了下界。在Tromp/Farnebäck的論文中給出了更精確的限制。10700 這個數字對於200手以內的所有棋局來說是一種高估，但對361手以內的所有棋局來說是一種低估。而4700萬手的棋，在一秒一手、每天下16個小時的情況下，也要下2¼年。
metadata: erhwenkuo/wikipedia-zhtw
metadata: 圍棋與數學
metadata: https://zh.wikipedia.org/wiki?curid=6129846