西西软件下载最安全的下载网站、值得信赖的软件下载站!

首页编程开发其它知识 → 自动扫雷游戏中的概率分析之程序实现和数学实现

自动扫雷游戏中的概率分析之程序实现和数学实现

相关软件相关文章发表评论 来源:西西整理时间:2012/11/24 23:45:31字体大小:A-A+

作者:西西点击:6次评论:11次标签: 自动扫雷

  • 类型:PUZ 益智游戏大小:3.2M语言:英文 评分:2.1
  • 标签:
立即下载

自动扫雷——概率分析之程序实现

说到自动游戏,即用程序自动去玩某个游戏。这主要会涉及到三个部分:获取游戏数据,分析数据、得到有用数据,控制游戏。

mineTerminator中用分析游戏窗口像素信息得到游戏数据,而控制游戏而是用SendMessage给游戏窗口发送按键消息。现在的难点既是分析游戏数据:通过下面几部分来说明如何利用数学之美,成功地解决问题。

先来分析一下扫雷中可以存在的情况,总结出了四种不同的模型:

第一种、第二种模型

分析右上角的的2,其周围的未知块a,b两块,等于其周围雷数,故可判断出a,b都是雷;接下来,分析下面的2,其周围共有3个未显示的块a,b,c,其中a,b已判断出为雷,即周围已判断的雷数等于其雷数时,则可判断剩下的块都不是雷,即c块不是雷。

 这两种模型,一种是判断出雷、一种是判断出没有雷,这是地球人都知道的扫雷方法。而接下来的模型或许只有扫雷高手或者数学高手才知道~~

第三种模型

我先做一个大胆的判断,c块没有雷!!且听我慢慢道来~

根据两个显示为1的块,可得如下的式子:

a+b=1                 (1)  

d+e=1                 (2)

表示a,b中有且只有一个雷,d,e有且只有一个雷,

根据显示为2的块,可得:

a+b+c+d+e=2         (3)

表示abcde中有且只有两个雷

根据(1)(3),可得

c+d+e=1      (4)

根据(2)(4)可得, c=0  ,所以c块肯定无雷,可放心地揭开。

这种模型可以说在扫雷中应用得最精妙,看似无法判断的情况,通过这样的计算就可确定出哪里是雷或者哪里不是雷。

第四种模型

上面三种模型都属于可确定判断的范畴,而在扫雷中经常会遇到无法确定判断的死局。这时就得用到数学工具——概率,来进行最优判断。

如图所示显示为3周围有雷的概率很容易计算出:3/8(这是比较简单的情况)。再看下面的图

当点开两个"8邻接"距离小于等于2的块时,它们周围有雷的概率就不那么容易判断了(上面a,b,c有雷的概率分别是多少),这种情况留在后文详细分析。《编程之美》的最后一题也就是这个问题, 三年前自己一直在想这个概率如何来求,以及如何用程序实现。现在总算是想明白了~~~

这篇将介绍如何使用数学中的概率知识来玩扫雷游戏,也正是本人最想介绍的地方,即《前言》中所说的第四种扫雷模型的分析。

先看游戏界面,如下:   

在游戏开始时,如何出现这样的情况,我们可以认为游戏中未显示块按概率相等可分为四个区域,其中a,b,c是其中的三个区域(a区域指上面的5个块,b区域指中间的3个块,c区域指下面的5个块),再加上不与已揭开块相邻的所有块构成一个区域d(d区域含有465块)。那么这四个区域中哪个区域有雷的概率最小呢?

这里直接说明所使用的数学方法叫做——条件概率和全概率公式。

条件概率可以说是计算机领域的一个功臣,由其发展而来的“统计语言模型”实现了机器翻译、语音识别、汉字识别等一系列的用传统方法很难解决的问题。而以其为基础的“贝叶斯公式”在图像处理、决策支持系统和博弈论中有着广泛的应用。

维基百科中给的定义是:条件概率就是事件A在另外一个事件B已经发生条件下的发生概率。条件概率表示为P(A|B),读作“在B条件下A的概率”。

而全概率为:

假设{ Bn : n = 1, 2, 3, ... } 是一个概率空间的有限或者可数无限的分割,且每个集合Bn是一个可测集合,则对任意事件A有全概率公式

又因为

此处Pr(A | B)是B发生后A的条件概率,所以全概率公式又可写作:

用自己的话说,条件概率是在某件事发生的情况下,另一件事的概率;全概率是将所有情况的概率加起来。

而在扫雷游戏中有什么“所有情况”呢?

看上面的游戏场景,a,b,c所占的13个块,如果仅仅根据上面所显示的"1","2",可以说这13个块中,雷的总数可以有2个,也可以有3个!!并且有2个或者3个的概率分别是1/2。

 那么其情况如下:

上表说明当雷数为2时,abc有雷的概率分别为0,1/3,1/5;当雷数为3时,abc有雷的概率分别为1/5,0,2/5。

可算出

a区域有雷的概率为0*1/2+(1/5)*(1/2)=1/10

b区域有雷的概率为(1/2)*(1/3)+0*1/2=1/6

c区域有雷的概率为(1/2)*(1/5)+(1/2)*(2/5)=3/10

而d区域的概率同理也算出为(1/2)*(97/465)+(1/2)*(96/465)=193/930

可知,a区域有雷的概率最小,故可以在此5块中随机选一块点击了,然后一切就交给上苍了~~(在不用类似查看内存的方法的情况下,人做的就只有这么多了)

到此,数学原理已介绍完毕,用一句话总结,即,先找出按区域划分的未显示块,然后分类讨论这些区域中雷的总个数。接下来的一篇博文(也是本系列最后一篇),将介绍如何将上面的数学运算用程序代码实现。

批注:从自己想到数学实现到想明白如何用程序代码实现,应该有两年之多,当然只是偶尔无聊时才思考一下。不过,在思考这个实现过程中,自己开始一直在用数学的思路而没有用代码的思路去思考,故一直行不通。当自己用代码实现后,感觉自己的思维又有了新的提高~~

    益智类单机游戏
    (81)益智类单机游戏
    益智类游戏是非常大众化的一种游戏类型,其有趣的游戏设定能激发人的斗志与潜力,十分具有探索意义,是非常积极健康的游戏类型。这类游戏其实也是一种是重要的教育形式,是小儿智力发展的动力,它能激发小儿的求知欲与创造力,并且可使小儿掌握一些知识技能,形成对待事物的正确态度,促进小儿全面发展。多玩完这样的游戏对身心都非常有益,大家闲暇之余可以试试哦。益智类单机游戏多是锻炼玩家的反应能力,协调性以及逻辑思维能力...更多>>

    相关评论

    阅读本文后您有什么感想? 已有人给出评价!

    • 8 喜欢喜欢
    • 3 顶
    • 1 难过难过
    • 5 囧
    • 3 围观围观
    • 2 无聊无聊

    热门评论

    最新评论

    发表评论 查看所有评论(11)

    昵称:
    表情: 高兴 可 汗 我不要 害羞 好 下下下 送花 屎 亲亲
    字数: 0/500 (您的评论需要经过审核才能显示)
    推荐文章

    没有数据