l4m2 发表于 2025-5-16 15:13:37

围棋盘随机下子

19*19的围棋盘，每次随机一个点和颜色试着下子，如果吃子或被吃就下不了重试。求最后空数期望
Dim A(18, 18)
Do
X = Int(Rnd * 19)
Y = Int(Rnd * 19)
C = Rnd < 0.5
If 颜色C下在A棋盘(X,Y)出合法且不吃 Then
    A(X, Y) = C
End If
Loop Until 不再可能下子

mathe 发表于 2025-5-17 07:23:32

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

mathe 发表于 2025-5-20 13:41:01

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

KeyTo9_Fans 发表于 2025-5-20 18:25:14

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

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

例如，当n=2时，一共有24种终局：
011011110220222201020102102010201121122211122122
111101102222022021112212121122210201020120102010
终局的权重好像也有计算公式：

终局的权重 = (终局的棋子数)! = (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 发表于 2025-5-20 22:33:52

n=2
Output final result:
C=24

n=3
Output final result:
C=664
C=113

n=4
Output final result:
C=50539
C=64561
C=6207
C=47

n=5
Output final result:
C=12106804
C=47621004
C=22126228
C=2038049
C=13531

n=6
Output final result:
C=9886124405
C=85116220799
C=112295955363
C=36952249892
C=2406830842
C=33132126
C=63527
C=9

n=7
Output final result:
C=28125915255313
C=443448285941567
C=1260254228170987
C=1029824778380447
C=249271024590446
C=20107771285277
C=533159995247
C=3957433675
C=4668619
C=114

n=8
Output final result:
C=284152648451800656
C=7334983103215417821
C=38077152915164635754
C=62777744303032103866
C=37147266636842206917
C=8870489721728753398
C=896433997094503689
C=37921715491987159
C=619624664241364
C=3391423965715
C=5191401457
C=1842280
C=123

real        1m39.846s

mathe 发表于 2025-5-21 06:10:45

n=9
Output final result:
C=10290966725767350045775
C=403013044575473610240020
C=3430940849435449851443897
C=9975404662211221145563271
C=11637529111141409411731606
C=6117174995041931037652630
C=1544393947543666064715062
C=192110850664562661947524
C=11704141302721136836722
C=339284632752847348424
C=4466147050623919965
C=24704192974035913
C=50887234905181
C=32894770413
C=5826555
C=9

再上去16G内存不够了

mathe 发表于 2025-5-21 08:12:48

需要记录状态有:
typedef short settype;
class LineStatus{
   settype color;//bit value for color of each SET
   short ec;
   char setid;//The set ID of each open CELL, -1 if it is EMPTY
   char set_empty;//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 发表于 2025-5-21 10:17:09

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

mathe 发表于 2025-5-21 12:40:47

n=10
C=6180603631233917536
C=24022874686699990223582
C=4622886434754944179097342
C=146138066090402654492730430
C=1327834887913693084413766554
C=4491184331326378584984339498
C=6574619181954628073812510486
C=4552295062534978216379341752
C=1568046166604763165407380712
C=275760306951859519243042626
C=24958274814268548571946088
C=1151298221763969453009992
C=26270510260424529055850
C=280977752271099968722
C=1300346172054190136
C=2375078339346608
C=1680603062730
C=615818526
C=204696
C=64

l4m2 发表于 2025-5-21 19:42:53

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


状态：空；（白/黑）*（活了/与右边第x块相连/右边没有相连的）吗？
页: [1] 2
查看完整版本: 围棋盘随机下子