围棋盘随机下子

l4m2

19*19的围棋盘，每次随机一个点和颜色试着下子，如果吃子或被吃就下不了重试。求最后空数期望

1. Dim A(18, 18)
   
2. Do
   
3.   X = Int(Rnd * 19)
   
4.   Y = Int(Rnd * 19)
   
5.   C = Rnd < 0.5
   
6.   If 颜色C下在A棋盘(X,Y)出合法且不吃 Then
   
7.     A(X, Y) = C
   
8.   End If
   
9. Loop Until 不再可能下子

复制代码

mathe

蒙特卡洛法肯定是最简单的近似方法，不过既然提出来，肯定是想得出精确解，那么可以用DP试验一下，不确保能够达到19*19的规模。
使用DP, 我们可以在棋盘上每次增加一个格子，形成一个已经处理了前s-1行，第s行处理了前t个格子的状态，这时我们需要保存这时:
边界上格子之间的颜色，连通关系，这些连通区间是否有空格相邻，以及已经产生的内部空格数目，以及每个状态对应的计数。
当然动归过程中可以将包含死子的那些状态直接淘汰出去。
发现还有一个麻烦之处是需要判断是否存在可以继续落子的空格，所以对每个边界上的空格，我们还需要记录，它是否是某个区域已知唯一相邻的空格。

mathe

维护信息稍微有些讨厌，我们需要维护当前开放行如下信息：
每个格子是黑、白、空？
如果是黑白，需要记录它们是否连通，并且每个连通集是否和已知空白格子相邻。如果这个白格子和连通都还处于开放状态，还需要记录它们之间的具体位置，因为后面连通集还可以继续扩张，新增加棋子还可能和这个空白格子相邻。
所以主要问题就是要如何较高效维护这个状态信息

KeyTo9_Fans

计算公式好像可以这样写：

最后空数期望 = (第1种终局的空数*第1种终局的权重+第2种终局的空数*第2种终局的权重+......+第m种终局的空数*第m种终局的权重) / 总权重

例如，当n=2时，一共有24种终局：

1. 01  10  11  11  02  20  22  22  01  02  01  02  10  20  10  20  11  21  12  22  11  12  21  22
   
2. 11  11  01  10  22  22  02  20  21  11  22  12  12  11  22  21  02  01  02  01  20  10  20  10

复制代码

终局的权重好像也有计算公式：

终局的权重 = (终局的棋子数)! = (n^2 - 空格数)!

例如，当n=2时，上面24种终局的权重好像都是 (2^2-1)! = 3! = 6

这样我们就得到了当n=2时最后空数期望：

(1*6+1*6+1*6+......+1*6)/(6+6+6+...+6) = 144/144 = 1

对于更大的n，好像只需要想办法把m(0)、m(1)、m(2)、……、m(n^2)求出来就可以了

其中m(i)表示恰好有i个空格的终局数目

动态规划好像可以做到，存储的这些信息不知道够不够：

目前的空格个数、边缘格颜色、有色格所属的连通块编号及其死活状态

还需要存储更多的信息吗？

#####

呃……终局权重的计算公式好像不太对，我目前尚未找到正确的终局权重公式……

mathe

n=2
Output final result:
C[1]=24

n=3
Output final result:
C[1]=664
C[2]=113

n=4
Output final result:
C[1]=50539
C[2]=64561
C[3]=6207
C[4]=47

n=5
Output final result:
C[1]=12106804
C[2]=47621004
C[3]=22126228
C[4]=2038049
C[5]=13531

n=6
Output final result:
C[1]=9886124405
C[2]=85116220799
C[3]=112295955363
C[4]=36952249892
C[5]=2406830842
C[6]=33132126
C[7]=63527
C[8]=9

n=7
Output final result:
C[1]=28125915255313
C[2]=443448285941567
C[3]=1260254228170987
C[4]=1029824778380447
C[5]=249271024590446
C[6]=20107771285277
C[7]=533159995247
C[8]=3957433675
C[9]=4668619
C[10]=114

n=8
Output final result:
C[1]=284152648451800656
C[2]=7334983103215417821
C[3]=38077152915164635754
C[4]=62777744303032103866
C[5]=37147266636842206917
C[6]=8870489721728753398
C[7]=896433997094503689
C[8]=37921715491987159
C[9]=619624664241364
C[10]=3391423965715
C[11]=5191401457
C[12]=1842280
C[13]=123

real        1m39.846s

mathe

n=9
Output final result:
C[1]=10290966725767350045775
C[2]=403013044575473610240020
C[3]=3430940849435449851443897
C[4]=9975404662211221145563271
C[5]=11637529111141409411731606
C[6]=6117174995041931037652630
C[7]=1544393947543666064715062
C[8]=192110850664562661947524
C[9]=11704141302721136836722
C[10]=339284632752847348424
C[11]=4466147050623919965
C[12]=24704192974035913
C[13]=50887234905181
C[14]=32894770413
C[15]=5826555
C[16]=9

再上去16G内存不够了

mathe

需要记录状态有:
typedef short settype;
class LineStatus{
   settype color;//bit value for color of each SET
   short ec;
   char setid[W];//The set ID of each open CELL, -1 if it is EMPTY
   char set_empty[W+1];//0..W-1 for an open EMPTY associlate with a SET; W to 2W-1 for closed EMPTY; -1 for no EMPTY for the set;
   char num_set;

代码应该还有bug, n=3的时候出现了奇数数目，显然应该不对。任何局面应该可以奇偶互换。

mathe

修复了几个bug,更新一下
n=2
C[1]=24
n=3
C[1]=354
C[2]=112
n=4
C[1]=6780
C[2]=35090
C[3]=4686
C[4]=42
n=5
C[1]=233656
C[2]=7727492
C[3]=8077804
C[4]=1207592
C[5]=11000
n=6
C[1]=17632304
C[2]=2360958288
C[3]=11067888914
C[4]=8166228636
C[5]=955567888
C[6]=19998602
C[7]=49780
C[8]=8
n=7
C[1]=3263406030
C[2]=1298796311268
C[3]=19982404909034
C[4]=49769711831944
C[5]=27586399549138
C[6]=4238148096314
C[7]=187628472048
C[8]=2098845558
C[9]=3283654
C[10]=24
n=8
C[1]=1548286890984
C[2]=1483650338408822
C[3]=60892139836974738
C[4]=408478630769520604
C[5]=702558935467496230
C[6]=393556258444795840
C[7]=80514690458690188
C[8]=6188995645574026
C[9]=168248955126498
C[10]=1410369127872
C[11]=2990132948
C[12]=1276382
C[13]=96
n=9
C[1]=1910675094640348
C[2]=3848152557469078312
C[3]=362333410064546073988
C[4]=5593716932575619928976
C[5]=23794748857711904852132
C[6]=35828598891239850625260
C[7]=21949703823239278193178
C[8]=5871523436178282274362
C[9]=700911234991701766106
C[10]=36894836800948923310
C[11]=823912131176772020
C[12]=7217792736054936
C[13]=21745435058822
C[14]=18603973540
C[15]=3925182

mathe

n=10
C[1]=6180603631233917536
C[2]=24022874686699990223582
C[3]=4622886434754944179097342
C[4]=146138066090402654492730430
C[5]=1327834887913693084413766554
C[6]=4491184331326378584984339498
C[7]=6574619181954628073812510486
C[8]=4552295062534978216379341752
C[9]=1568046166604763165407380712
C[10]=275760306951859519243042626
C[11]=24958274814268548571946088
C[12]=1151298221763969453009992
C[13]=26270510260424529055850
C[14]=280977752271099968722
C[15]=1300346172054190136
C[16]=2375078339346608
C[17]=1680603062730
C[18]=615818526
C[19]=204696
C[20]=64

l4m2

mathe 发表于 2025-5-21 06:10
n=9
Output final result:
C[1]=10290966725767350045775

状态：空；（白/黑）*（活了/与右边第x块相连/右边没有相连的）吗？