圍棋的總盤數是多少？

01-02

突然想到，圍棋的總盤數一共有多少？如果出現一台電腦儲存了所有這些可能性，人類還能不能戰勝它？

圖為在1*1-18*18的棋盤下所有可能的合法局面數。John Tromp 通過動態規劃計算出了這些精確的值（Counting Legal Positions in Go）。受限於計算力，19*19的所有合法局面數仍為一個未解問題，但是保守估計也就是十年以內可以解決。表中19*19一欄給出了一個估計的上界和下界。

2016年更新： John Tromp已經完成19路棋盤所有合法局面數的精確值。

208168199381979984699478633344862770286522453884530548425639456820927419612738015378525648451698519643907259916015628128546089888314427129715319317557736620397247064840935

2.08*10^170.

顯然不可能有任何「計算機」能夠儲存這麼多棋局，不管是現在還是未來。

當然，合法局面數和所有可能的局數之間的差距，就好像霓虹燈到月亮的距離。。

要想計算所有可能的局數，首先要明確一下規則。目前已有的所有規則都已經對單獨的劫爭做出了規定，但是對於一些複雜而本質上屬於劫爭的棋形（三劫循環、長生、雙提二子等）存在嚴重分歧。日本、韓國規則對於三劫循環、長生等判和；中國規則在理論上非常嚴謹，在實際執行上卻曖昧不清。我們這裡採用理論上的中國規則，即所謂」禁全同「：禁止重複在同一局棋中已經出現過的棋形。」禁全同「規則同時保證了①一盤棋在有限步之內結束②在非整數貼目規則下，必然會分出勝負。一盤普通的收完官子的棋局一般在200-250步左右會結束。然而，即使有禁全同規則，理論上一盤棋可以達到多長呢？

。。。

10^48。。

據此，我們給出一個所有可能局面數的下界。。

。。

10^(10^48)

沒錯，它讀作10的10的48次方。。

而一個對應的上界是

10^(10^171)

...

可能這麼大的數已經讓人麻木了。。那麼我們來看一下最簡化的棋盤--2*2

你們猜2*2棋盤上，在禁全同規則下，所有可能的局面數是多少呀？

10^2？

10^3？

都錯。。

答案是：386,356,909,593 （不信的話戳這裡Google 網上論壇）

用科學計數法表示是。。3.86*10^11

嚇得我都傅里葉變換了。

弄一台電腦儲存2*2的所有可能的棋局應該還行，不過棋盤稍微大一點就不現實了。儲存19*19棋盤上的所有可能局面嘛，估計就算地球文明有能力殖民三體星了也做不到呢。

我覺得題主的問題應該首先定義什麼是一盤棋。

可以有幾種定義方法

0. 一步步下出來，終局後所有棋子的擺放形式。(終局指後續變化不在改變雙方目數差)

1. 一步步下出來，終局後所有棋子的擺放形式。 (終局指沒棋可下)

2. 一步步下出來，從開始到終局棋子放置的位置以及順序。(手割還原後不能算同一盤棋)

3. 所有在棋盤上棋子合規則的擺放形式。要求在此擺放形式的基礎上不能繼續落子。

4. 所有在棋盤上棋子合規則的擺放形式。棋盤不一定填滿。

另外，黑白互換為同一盤棋，4個朝向和他們的4個鏡像也算同一盤棋。

這樣答案會有意義很多呀！比如規則0。雖然我都算不出。

就在前幾天(2016年1月20號），John Tromp已經算出了19路棋盤的精確結果，結果是：

208168199381979984699478633344862770286522453884530548425639456820927419612738015378525648451698519643907259916015628128546089888314427129715319317557736620397247064840935

壓縮一下格式後，是這個樣子的：

2081681993819799846 9947863334486277028 6522453884530548425 6394568209274196127 3801537852564845169 8519643907259916015 6281285460898883144 2712971531931755773 6620397247064840935

論文在此：Counting Legal Positions in Go

361！（這還不包括在同一位置重複下子如打劫的情況）

算了一下，大概=1.43e+768盤，也就是14後面跟767個0

大概需要1.0e+756 PB存儲空間（按每個點2位元組計算），也就是需要用1後面跟744個0塊1T盤存儲，好了你可以算一下成本了，別忘了還要發明一個能在這麼大數據量上做實時運算的系統

（我算錯了嗎？）

這就是為什麼目前圍棋程序只能用隨機抽樣演算法的原因。

補充一下：

2011年IDC統計的全球數據量是1.8ZB，而PCWorld預測到2020年時數據量將達到新高度——屆時全球數據總量將達到40ZB。

也就是說圍棋全部變化（盤數）數據量比2020年全球數據總量還多1後面跟730多個0的倍數（難以置信，我算錯了嗎？）

從古至今，人類一共對局了10^11~10^12局，而alphago從發明至今自我訓練的大概也是這個盤數。

所以alphago這麼牛逼。

當然這比圍棋理論上的總局數也是微微……微微一小點。

所以alphago執白勝率只有76%

總盤數？我最初以為是能下成的所有的對局（不管多少步、是否終局）的非重複之後的總局數

後面感覺可能是只不同的局面的數量

（前者比後者還要多很多吧。。。。這個不知道怎麼算）

總局面數，基本討論的比較多，就是：不計打劫

361階乘再扣除重複的部分（不過，會出現：提子後，可下的位置數可能會變多了）；

或者 3的361次方再扣除重複的部分