無限大的圍棋盤上某個子的存活概率是多少？

09-01

假設有個無限大的圍棋棋盤，某個位置上已經下了一個黑子。其他每個位置上，以1/3的概率隨機落下黑子，白子和空點（不落子），問這個黑子存活的概率是多少？這裡「存活」的（遞歸）定義是：一個子存活，當且僅當與其相鄰的位置有至少一個空點或者同色「存活」的子。另外，不考慮其他所有子的存活情況，也就是不會先「提走」其他子。

假設第一個黑棋的位置叫天元。

注意到棋盤稍微大一點，天元一子死在邊角上的概率會指數地減小，所以用有限棋盤模擬就行了，如果碰到了棋盤的邊界就拋出個異常。跑了3000萬盤，這個概率是0.98470±0.00004，而且一次邊界都沒碰到。

考慮一維情況，天元的死活相當於天元處聯通黑棋的死活。這塊黑棋左右各有一個邊界，可能是白棋也可能是空位，概率各為1/2。所以一維下天元黑子的存活概率為

$P=1-left(frac{1}{2} ight)^2=frac{3}{4}$

再回到二維的情況。考慮最簡單的情形，天元處聯通黑棋只有一子，那麼周圍4口氣都被白棋填上它才會死，其存活概率為

$P_1=1-frac{1}{2^4}=frac{15}{16}$

這個演算法是漏算了黑棋活法， @Turing 的方法是漏算了黑棋的死法，所以正好一個上界一個下界

$0.9375simeqfrac{15}{16}<P<frac{80}{81}simeq0.98765$

想再逼近的話就要多考慮几子，挺麻煩

更新

在二維下，把天元處聯通的黑棋的棋塊叫做B。B的面積是 $N(B)$ ，B的邊界的位置數是 $L(B)$ ，那麼B對黑棋死亡概率的貢獻是

$ewcommand{paren}[1]{left({#1} ight)} ewcommand{pfrac}[2]{paren{frac{#1}{#2}}} P_B = pfrac{1}{3}^{N(B)-1}pfrac{1}{3}^{L(B)}$

第一項是要求B的內部全部是黑棋（天元處已經給定是黑棋了），第二項要求B的氣全部被白棋填上。考慮B可以通過平移得到 $N(B)$ 個僅天元位置不同的棋塊，每個棋塊對死亡概率的貢獻都相同。把B對應的平移不變的「形狀」叫做S，則S對死亡概率的貢獻是

$ewcommand{paren}[1]{left({#1} ight)} ewcommand{pfrac}[2]{paren{frac{#1}{#2}}} P_S = N(S) pfrac{1}{3}^{N(S)+L(S)-1}$

對所有形狀 $S$ 求和，存活概率就是

$ewcommand{paren}[1]{left({#1} ight)} ewcommand{pfrac}[2]{paren{frac{#1}{#2}}} P =1- sum_S { N(S) pfrac{1}{3}^{N(S)+L(S)-1}}$

這裡面的「形狀」在數學上叫做fixed polyomino。考慮到目前我們還不知道n元polyomino有多少個，這個求和應該是沒有顯式解的。所以也只能照著下面這個圖挨個枚舉，枚舉得項數越多就越接近準確值。

拋塊磚頭。不妨以黑子為研究對象，不研究單個的棋子，而是用整個棋盤上的死子與活子的數量來表示概率。

對於 $n imes n$ 的棋盤區間，考慮邊界。如果邊界是「壁面」（普通棋盤，與棋盤邊角接觸的地方不算氣，最角上的子只有兩口氣，「爬一路」的子有三口氣。），存活概率會小於目標概率。如果邊界是通氣的（在棋盤邊角上，棋盤一角的棋子仍然是四口氣。），由於漏算了在棋盤之外可能被圍死的概率，故存活概率會大於目標概率。

若邊界條件為壁面，則6個黑子全死，若邊界條件為通氣，則有兩口氣，若為無限大棋盤則死活不明

死活不明概率多大？

n=2

對於n=2的棋盤，一共有81種下法。採用壁面邊界條件，黑棋總數為 $81div3 imes4=108$ ，而活著的黑子數為76，（圖可以參考 @不會功夫的潘達的專欄《迷你圍棋之奧妙（一）：二路圍棋》則存活概率為 $frac{19}{27}$ （ $P>frac{19}{27}$ ）。採用通氣條件的話，黑子全部存活（ $P<1$ ）。