魔方吧·中文魔方俱乐部

标题: 扫雷游戏的概率问题? [打印本页]

作者: tiawing 时间: 2009-1-29 22:54:46 标题: 扫雷游戏的概率问题?

如果把windows中的扫雷游戏的雷场大小调整为20乘30 , 地雷数量调整为10个,随机生成雷场后,只点击一下鼠标左键,就把雷场全部自动翻开的概率是多少?

作者: o嗬飽彈o 时间: 2009-1-29 22:59:40

600份之一
不知道对不对

作者: 阿星 时间: 2009-1-29 23:00:32

没算过。。不知道他翻开的条件是什么。。。不过我试过几次。。不是很大哦。。。

作者: Xwam 时间: 2009-1-29 23:02:37

这个概率应该是确定的，因为扫雷的地图不是纯随机的，而是伪随机的，这样相当于地图确定了，只要知道这点，应该就能算出来。但很麻烦。

作者: 阿星 时间: 2009-1-29 23:03:04

刚刚实验了五十次。。。两次成功了。。。还有五次。。点了一个格。。就只翻了一个格。。。囧。。。目前的实验概率是4% 呵呵。。。

作者: cod 时间: 2009-1-29 23:04:20

我个人认为，不存在这种概率，雷场说不定是在一次点击后才生成的。
我不是太懂啦，欢迎拍砖。这个东西，我觉得问问张砷镓比较好吧。

[ 本帖最后由 cod 于 2009-1-29 23:07 编辑 ]

作者: Xwam 时间: 2009-1-29 23:10:37

我认为还是确定的。。。。。。

作者: 阿星 时间: 2009-1-29 23:11:14

楼主可以把贴发到那个扫雷网去。。呵呵

作者: 一不死生 时间: 2009-1-29 23:18:35

这个问题可以去问老张

他是专业的！

作者: ursace 时间: 2009-1-29 23:52:55

原帖由 cod 于 2009-1-29 23:04 发表
我个人认为，不存在这种概率，雷场说不定是在一次点击后才生成的。
我不是太懂啦，欢迎拍砖。这个东西，我觉得问问张砷镓比较好吧。

对啊，感觉是点一次才生成的，从来没有第一次就点中雷过

作者: 骰迷 时间: 2009-1-30 12:31:18

不是點一次才產生的，有個密技，按SHIFT+XXYYZ，左上角的點會變成黑或白其中一個（我忘了），滑鼠指在方格上，如果該方格有雷，左上角會變色。但是如果你第一下就按在雷上，大概雷會換換位置吧，這個不清楚啊。但雷是位開始已經定了的。

作者: juventus66 时间: 2009-1-30 12:45:15

好帖,支持了

作者: kexin_xiao 时间: 2009-1-30 14:52:51

不太明白,如果地图是伪随机的,什么意思?

作者: tiawing 时间: 2009-1-30 16:27:38

可能我没有把题目说清楚,我的意思是:假如玩1000局,会有多少局?你只用点一下,不用点第二次鼠标或更多次,就能把雷场排完.
条件:
第一次就按到地雷不算在内;
认为地雷是随机分布的,不考虑伪随机问题.

作者: 骰迷 时间: 2009-1-30 17:00:11

第一次按到地雷的機率根本是零，這情況只會在某些便宜翻譯機的小遊戲上出現，設計程式的哪有這麼笨。

作者: oboe 时间: 2009-2-1 23:21:32

狠早的WINDOWS版本, 扫雷就是在你点第一下之后,再生成雷的分布图.
确保你不会第一下被炸.

楼主的意思, 要一下全开,
第一必要条件是, 雷的分布不能有环.
第二必要条件是, 点第一下的周围不能有雷.

作者: oboe 时间: 2009-2-1 23:22:03

连击了. 编辑掉

如果定下每次都是点击左上角, 这样概率会大一些吧.

[ 本帖最后由 oboe 于 2009-2-1 23:25 编辑 ]

作者: 骰迷 时间: 2009-2-2 14:37:35

求的這個概率，是隨便按一格的概率呢，還是指定按一格的最大概率呢？

作者: lulijie 时间: 2009-2-2 23:13:15

假设雷区在点击之前就生成，第一次点击点中地雷，算失败。
用电脑模拟，试验600次，成功（全部打开）的次数为
随机点，45次       概率 45/600=7.5%
固定点击角，44次
固定点击中心点，48次。                         概率与点击方式基本无影响。
------------------------------------
若雷区在点击之后生成，那么上述试验600次中平均有10次是直接点中地雷造成失败的。所以有效次数为590次。
随机点，45次       概率 45/590=7.6%

作者: unknownzone 时间: 2009-2-2 23:16:53

这个应该找老张出来作答

作者: alabing11 时间: 2009-2-2 23:18:56

这个问老张啊，他就靠扫雷过日子呢！

作者: lulijie 时间: 2009-2-2 23:33:44

雷区中除了地雷的格子外，每个格子上都是1个数字，该数字代表这个格子周围相邻的8个格子中的地雷数。
当我们用鼠标左键点击一个格子时，若该格子上的数字为0，那么就显示该格子周围全部格子上的数字，若其中也有数字0的格子，那么它周围全部格子的数字也全部显示，依次类推，直至没有新的数字为0 的格子被显示。
当我们用鼠标双击点击一个已显示数字的格子时，若该格子上的数字与周围地雷数相等，且标记的地雷位置都正确，那么显示该格子周围不是地雷的格子上的数字，若其中有数字0的格子，那么它周围全部格子的数字也全部显示，依次类推，直至没有新的数字为0 的格子被显示。
-------------------------------------------------------
所以单击就全部打开雷区的条件就是，首次必须点击中数字0的格子，并且数字为0的格子必须全部相连，并且全部数字不是0的格子必须至少与其中一个数字0格子相连。

作者: lulijie 时间: 2009-2-3 00:16:47

用电脑模拟，试验六万次，成功（全部打开）的次数为
随机点，4537次       概率 4537/60000=7.56%
固定点击角，4429次                               7.38%
固定点击中心点，5205次                         8.675%
--------------------------------------------------------------
试验次数足够多时，还是可以看出，点击中心全部打开的概率比点击角落概率大些。
因为数字0的格子分布在中心的概率比分布在角落大。

作者: lulijie 时间: 2009-2-3 00:44:28

电脑模拟的程序是这样的：
创建20*30的二重变量Z(i,j)，初始值都为0 ，（对应20*30雷区中相对应的格子）
随机选出其中的十个变量（代表地雷所在的格子），每个被选择的变量周围的变量的值都加1，
完毕后，被选择的十个变量的值设为9。
这样处理后，这600个变量的值从0至9。每个数值就代表相应格子周围的地雷数，数值为9的变量其实代表地雷格。
然后再随机选择其中的一个变量（代表点击该格子）
判断其值，若不是0，失败（不能全部打开雷区）。
若为0，则从第1个变量开始一直到最后一个变量，对每个变量进行以下判断：
      若为9，接着判断下一个；
      若不是9，判断其周围的变量中是否有0，有0判断下一个，无0则失败，直接退出判断。
设定试验总次数，累计其中成功的次数，就得出近似概率。

作者: oboe 时间: 2009-2-3 09:53:13

"点击中心全部打开的概率比点击角落概率大些。"

看来还是事实说话.
感觉上,
在边上时, 因为周围只有3个点有机会出现雷, 这时会显示1, 这时是打不开图的.
而在中间时,因为有8个点有机会出现雷,
看来感觉是错了.

作者: lulijie 时间: 2009-2-3 13:23:18

单击就全部打开雷区的条件就是:首次必须点击中数字0的格子，并且数字为0的格子必须全部相连，并且全部数字不是0的格子必须至少与其中一个数字0格子相连。
-----------------------------------------------------
原先模拟600次得出的结果，就是按照上述条件得出的。但电脑运行速度慢。
后来模拟60000次时，改进的程序的设计，把其中数字为0的格子必须全部相连的条件换成数字为0的格子周围必须有0的格子。
实际上这样变换有点问题。因为前一个条件可以推导出后一个条件，但后一个条件不能推导出前一个条件，也就是它们不等价。比如有两个0格子相连，但不与其他格子相连，满足后面的条件，但不满足前面的条件。所以，上述得出的概率应该再小些。
-----------------------------------------------
重新修正程序，但运行速度慢了，让它运行6000次，得出以下结果：
固定点击角：第一次484次，第二次522次，第三次526次，平均511次。概率8.5%
固定点击边：第一次481次，第二次493次，第三次518次，平均497次。概率8.28%
固定点击中心：第一次441次，第二次413次，第三次420次，平均425次。概率7.08%
随机点击：第一次435次，第二次478次，第三次445次，平均453次。概率7.55%
---------------------------------------------------------------------------------------------
好像跟楼上的直觉相符，角概率最高，边次之，中心最低。
等我费时间给它们都运行60000次，看看。

作者: lulijie 时间: 2009-2-3 13:43:26

运行六万次，得出以下结果：
随机点击：成功4397次。概率7.33%。费时间啊！
其他固定点击方法等出结果后再公布。

作者: zhy3729 时间: 2009-2-3 13:46:51

不知道怎么算！！！！！！

作者: lulijie 时间: 2009-2-4 15:47:19

固定坐标：1，1
试验次数：60000
成功次数：5016
花费时间：4分5秒
-----------------
固定坐标：1，15
试验次数：60000
成功次数：4881
花费时间：3分57秒
-----------------
固定坐标：10，15
试验次数：60000
成功次数：4329
花费时间：3分25秒
------------------
随机取位：
试验次数：60000
成功次数：4378
花费时间：3分33秒
-------------------
固定坐标：10，1
试验次数：60000
成功次数：4888
花费时间：3分59秒
----------------------------------------------------
从上可以看出，固定点击角、边，比点击中心成功概率大些。

作者: oboe 时间: 2009-2-6 09:17:08

顶一下楼上。
ORZ

作者: zxl0714 时间: 2009-3-29 13:38:38

点击坐标（1，1）
数据规模：1000000
成功次数：59856
花费时间：87秒

点击坐标（1，15）
数据规模：1000000
成功次数：56643
花费时间：85秒

点击坐标（10，15）
数据规模：1000000
成功次数：50565
花费时间：81秒

29楼的程序应该还是欠妥。
不过看来应该是角落最高了。

作者: lulijie 时间: 2009-3-29 14:15:03

31楼的程序好快，不知如何设计的，可以透露一下么？

作者: zxl0714 时间: 2009-3-29 14:20:05

用floodfill算法，看打开的区域面积+10等不等于600

作者: lulijie 时间: 2009-3-29 14:35:05

floodfill我都不知是个什么东西，百度一下，才知与图形填充有关。这方面的东西太缺乏了。对程序我只知道了一般原理。然后根据要求，自己来设计代码，对于很多现成的代码不了解，所以运行速度方面差了很多。看来要好好补补这方面的东西。

作者: 122047397 时间: 2009-3-29 14:39:28

找老张

作者: zhy3729 时间: 2009-3-29 14:46:58

不会！！！！！！！！！！！！！！！！！！！！！！

作者: lulijie 时间: 2009-3-29 14:50:53

不过31楼算出的概率好像跟我算出的不同。
不知31楼面积判断法是如何实现的。

作者: lamianbu 时间: 2009-3-29 14:58:04

这东西，有几种解决方案。

一是找数学高手，算出来。但是感觉不是一般的数学题，可能像解魔方一样，设计群论等高深的数学知识。

二是找程序高手，编程，统计分析。（楼上有几位已经这么做了）

三是找个通信高手。我是学通信的，但不是高手。感觉和无线Ad hoc某些泛洪算法接近。（最后还是编程统计，或者Matlab仿真。归为第二种）

四是找老张，他那里国外网站资料全些，可能前人已经分析过了。直接拿现成的结果。

作者: zxl0714 时间: 2009-3-29 15:01:12

打开的算法是看与他相邻的8个格中有没有雷，如果没有就递归的打开着8个格，如果有就停止。

作者: blow201 时间: 2009-3-29 18:29:51

原帖由 cod 于 2009-1-29 23:04 发表我个人认为，不存在这种概率，雷场说不定是在一次点击后才生成的。我不是太懂啦，欢迎拍砖。这个东西，我觉得问问张砷镓比较好吧。

好像扫雷确实是像你所说这样实现的，第一次不可能踩到地雷，是因为在你点击第一次之后才开始布雷。

欢迎光临魔方吧·中文魔方俱乐部 (http://bbs.mf8-china.com/)