iFlxnk
2020-03-13T07:41:40+00:00
前情提要：[url]https://bbs.nga.cn/read.php?tid=20842680&_ff=-7[/url]
问题描述：15乘15的棋盘上黑白交替纯随机落子，最后能形成五子连珠(包括五子以上连珠)的概率是多少？
我的解法：
保证任何时刻棋盘每个格点至多只有一枚棋子，不考虑禁手规则，考虑n*n棋盘上的情况。
使用蒙特·卡罗方法，在n*n的棋盘上随机取10^8个样本，即10^8次独立随机取样。
如何取样？我的做法是构造长度为n*n的排列到操作序列的双射，那么，只要随机一个长度为n*n的排列，就可以通过这个映射得到对应的操作序列，从而得到最终的棋盘情况。
对每一个取出的样本判断其中是否存在五子连珠(包括五子以上连珠)即可。
当n=5时，所选的10^8个样本中有39870733个存在五子连珠，估算存在五子连珠的概率为39.87%
当n=10时，所选的10^8个样本中有99964638个存在五子连珠，估算存在五子连珠的概率为99.96%
当n=15时，所选的10^8个样本都存在五子连珠，估算存在五子连珠的概率为100%--我们当然知道实际的概率达不到1,所以这里我用Hoeffding bound算了一下：我们有99.99%的把握认为，当n=15时，存在五子连珠的概率大于99.98%
最后附上代码[url]https://paste.ubuntu.com/p/TYGc5jcWdx/,[/url]希望各位不吝赐教，谢谢！
问题描述：15乘15的棋盘上黑白交替纯随机落子，最后能形成五子连珠(包括五子以上连珠)的概率是多少？
我的解法：
保证任何时刻棋盘每个格点至多只有一枚棋子，不考虑禁手规则，考虑n*n棋盘上的情况。
使用蒙特·卡罗方法，在n*n的棋盘上随机取10^8个样本，即10^8次独立随机取样。
如何取样？我的做法是构造长度为n*n的排列到操作序列的双射，那么，只要随机一个长度为n*n的排列，就可以通过这个映射得到对应的操作序列，从而得到最终的棋盘情况。
对每一个取出的样本判断其中是否存在五子连珠(包括五子以上连珠)即可。
当n=5时，所选的10^8个样本中有39870733个存在五子连珠，估算存在五子连珠的概率为39.87%
当n=10时，所选的10^8个样本中有99964638个存在五子连珠，估算存在五子连珠的概率为99.96%
当n=15时，所选的10^8个样本都存在五子连珠，估算存在五子连珠的概率为100%--我们当然知道实际的概率达不到1,所以这里我用Hoeffding bound算了一下：我们有99.99%的把握认为，当n=15时，存在五子连珠的概率大于99.98%
最后附上代码[url]https://paste.ubuntu.com/p/TYGc5jcWdx/,[/url]希望各位不吝赐教，谢谢！