随机摆放和随机消除的zuma游戏

KeyTo9_Fans

向一个队列中不断地插入各种颜色的小球。 当有若干个同色小球连在一起时，这些小球会从队列中消除，留下的空位会被后面的小球补上。 消除可以造成连锁反应，直到剩下的小球不能继续消除为止。 为了简化问题，我们不妨假设只有黑色和白色两种小球。 当队列中有$n$个小球的时候，如果再来一个小球，这个小球有$(n+1)$种插入方案。 我们随机选取其中一种插入方案，即插入到每一处的概率均为$1/(n+1)$。 当有$5$个或$5$个以上的同色小球连在一起的时候，这些连在一起的小球会从队列中消除，留下的空位会被后面的小球平移过来填补掉。 消除可以造成连锁反应，即填补后又有$5$个或$5$个以上的同色小球连在一起，则继续消除。 这一过程连续进行，直到不能再消除。 初始时队列为空，然后小球是一个一个地加进来的。 即每加入一个小球，要等消除工作全部结束，再加入下一个小球。 新来的小球有$p$的概率是黑色的，$(1-p)$的概率是白色的。 小球是源源不断地加进来的，永远不会停止。 好了，现在提出问题一： 当$p$取何值时，队列呈变短趋势（即无限多次被清空）？ 当$p$取何值时，队列呈变长趋势（即有限次被清空后再也不会被清空，最终达到无限长）？ 是否存在$p$值使得队列表现为上述两种状态之间的临界状态？ （看起来是$3$个问，不过似乎本质一样，就统称为问题一吧。） 下面假设新来的小球有$50%$的概率是黑色的，$50%$的概率是白色的。 但不一定非要$5$个或$5$个以上的同色小球连在一起的时候才能消除。 如果新来了一个小球之后，有$4$个同色小球连在一起，那么就抛一枚硬币。 如果抛到正面，则把这$4$个同色小球消除，否则放着不管。 当然，如果是$5$个或$5$个以上的同色小球连在一起，是用不着抛硬币的，直接消除就是了。 消除并填补之后，如果只有$4$个同色小球连在一起，那么同样抛一枚硬币。 如果抛到正面，则认为连续消除有效，把这$4$个同色小球消除，否则认为不能连消，消除阶段结束。 当然，如果消除并填补之后还有$5$个或$5$个以上的同色小球连在一起，也是用不着抛硬币的，直接继续消除就是了。 好了，下面提出问题二： 由于那枚硬币比较神奇，有$p$的概率会抛到正面向上，$(1-p)$的概率抛到反面向上。 当$p$取何值时，队列呈变短趋势（即无限多次被清空）？ 当$p$取何值时，队列呈变长趋势（即有限次被清空后再也不会被清空，最终达到无限长）？ 是否存在$p$值使得队列表现为上述两种状态之间的临界状态？ （看起来是$3$个问，不过似乎本质一样，就统称为问题二吧。） 好了，我的问题问完了。我承认我比较罗嗦，不过很期待这些问题在不久的将来能完美解决。

KeyTo9_Fans

这个问题提出至今，已经被我搁置了14年半了，最近才想起来可以咨询一下AI：

=======
问：（略）
答：（略）
=======

根据AI的建议，使用蒙特卡洛模拟（Monte Carlo simulation）方法，模拟大量的游戏过程来估计pc的值。

我选取了50种p值：p=0.01,0.02,0.03,...,0.50，然后编写程序将每种p值模拟106局游戏，每局游戏分别发射50000个球和100000个球

然后测量每局游戏结束后，队列的长度（用L50000和L100000表示）和清空次数（用C50000和C100000表示），

106局游戏一共有106个长度和106个清空次数。我对这106个数值求均值，结果如下表所示：

1. p           L50000         L100000        C50000         C100000
   
2. 0.01        7.99057        7.54717        1243.95        2462.93
   
3. 0.02        8.74528        9.77358        882.085        1779.93
   
4. 0.03        10.8208        9.73585        684.745        1352.12
   
5. 0.04        11.8302        11.9528        543.283        1065.44
   
6. 0.05        12.9528        15.1415        424.566        860.604
   
7. 0.06        14.8679        15.2736        341.019        679.330
   
8. 0.07        16.6226        15.9434        277.094        568.000
   
9. 0.08        18.9717        18.3585        226.311        447.896
   
10. 0.09        23.5000        20.8113        171.670        363.783
    
11. 0.10        24.6698        23.0283        145.160        287.887
    
12. 0.11        25.0943        26.3585        116.887        227.896
    
13. 0.12        28.9057        29.1792        88.0377        178.868
    
14. 0.13        39.1792        39.5472        69.8302        134.613
    
15. 0.14        42.0566        39.7170        52.6415        101.962
    
16. 0.15        45.2358        51.2264        39.4151        74.7830
    
17. 0.16        59.0377        61.9151        26.7170        54.4811
    
18. 0.17        72.5755        81.9151        19.0094        36.4340
    
19. 0.18        97.0943        92.5755        11.6321        21.8868
    
20. 0.19        121.066        111.689        7.05660        13.3679
    
21. 0.20        183.943        177.009        4.16038        6.11321
    
22. 0.21        329.679        367.509        1.72642        2.65094
    
23. 0.22        649.387        731.925        0.89623        1.16981
    
24. 0.23        1263.74        1913.18        0.63208        0.50000
    
25. 0.24        1994.64        3633.77        0.73585        0.43396
    
26. 0.25        2942.64        5423.52        0.62264        0.58491
    
27. 0.26        3589.29        7162.94        0.51887        0.47170
    
28. 0.27        4466.62        8708.95        0.47170        0.43396
    
29. 0.28        5351.03        10316.8        0.51887        0.30189
    
30. 0.29        5915.55        12000.4        0.46226        0.33962
    
31. 0.30        6768.78        13532.1        0.26415        0.33019
    
32. 0.31        7582.35        14944.4        0.38679        0.20755
    
33. 0.32        8177.23        16195.6        0.33962        0.22642
    
34. 0.33        8825.17        17686.5        0.34906        0.39623
    
35. 0.34        9478.38        18790.0        0.26415        0.14151
    
36. 0.35        9918.42        19950.2        0.14151        0.24528
    
37. 0.36        10707.5        21072.3        0.21698        0.30189
    
38. 0.37        11202.0        22152.2        0.19811        0.21698
    
39. 0.38        11601.3        22964.8        0.10377        0.23585
    
40. 0.39        11983.5        23993.0        0.22642        0.12264
    
41. 0.40        12428.8        24739.1        0.14151        0.18868
    
42. 0.41        12749.1        25504.2        0.21698        0.25472
    
43. 0.42        13120.5        26159.9        0.12264        0.25472
    
44. 0.43        13414.7        26757.1        0.17924        0.15094
    
45. 0.44        13589.4        27268.4        0.17924        0.13208
    
46. 0.45        13837.6        27846.6        0.15094        0.18868
    
47. 0.46        14040.9        27932.0        0.17924        0.12264
    
48. 0.47        14143.3        28164.6        0.07547        0.09434
    
49. 0.48        14276.3        28432.1        0.12264        0.15094
    
50. 0.49        14410.7        28608.6        0.14151        0.12264
    
51. 0.50        14336.3        28752.0        0.12264        0.15094

复制代码

根据上表可以看出，p的临界值应该大于0.22，因为当p=0.22时，射出5万球后队列的长度为649，射出10万球后队列的长度为732，队列没有明显变长，据此推断射出无穷多球后队列不会无限长

另一方面，p的临界值应该小于0.23，因为当p=0.23时，射出5万球后队列的清空次数是0.632，射出10万球后队列的清空次数是0.5，清空次数没有变多，据此推断射出无穷多球后队列不能无限多次被清空

接下来需要在p=0.22和p=0.23之间进行更多的模拟，才能求出更精确的阈值

KeyTo9_Fans

为了求出更精确的阈值pc，到目前为止我已经累计花费了5.33元的巨资：



在云CPU上一共模拟发射了(171亿*25)个球，然后测量发射了0.5B、1B、2B、4B、8B、16B球时的队列长度，结果如下表所示：

（本来用我自己的电脑可以免费算，但是我的电脑一直在算这个期望距离：https://bbs.emath.ac.cn/thread-19502-1-1.html，根本忙不过来）



根据上表中的数据，更精确的阈值为p=0.22362(1)

根据蒙卡的效率，阈值每多精确1位小数，投入的计算量（机时费）就要翻100倍

所以后续的买卖不划算了（产出投入比太低了），应该想办法用数学方法求出解析解

ejsoon

結論是？

KeyTo9_Fans

问题一：

当p取何值时，队列呈变短趋势（即无限多次被清空）？

当p取何值时，队列呈变长趋势（即有限次被清空后再也不会被清空，最终达到无限长）？

是否存在值使得队列表现为上述两种状态之间的临界状态？

结论如下：

当p<0.223625时，队列呈变短趋势（即无限多次被清空）

当p>0.223625时，队列呈变长趋势（即有限次被清空后再也不会被清空，最终达到无限长）

当p=0.223625时，队列表现为上述两种状态之间的临界状态（无限多次被清空 且 平均长度无限长）

上面这个数据（0.223625）的最后两位（25）是不准的，接下来你应该把这两位数算得更准确一些，甚至多算几位