蒙特卡洛方法的应用——解决“彩色砖块”问题

同贝叶斯方法一样,蒙特卡洛方法与其说是一种算法,不如说是一种思想。

灵活的运用蒙特卡洛方法可以解决很多问题。比如可以用它来求pi,求pi肯定有比这更好的方法,但是蒙特卡洛方法是所需条件最少的,只是充分利用了计算机产生随机数的能力。我们不需要知道pi等于什么级数,只需要知道圆的面积等于pi*r**2。

下面来看如何用蒙特卡洛方法解决一个实际问题,而且其它的方法不太容易解决。

关于彩色砖块

http://www.3366.com/flash/1000132.shtml
是3366上的一个小游戏。
蒙特卡洛方法的应用——解决“彩色砖块”问题
界面如图所示。这是一个消除类的游戏。
小游戏目标:
十字消除的玩法。鼠标放到合适位置,在十字线区域能连接到两个或两个以上相同颜色的方块就能打碎得分。点击错误将会扣除时间,时间结束,游戏结束。

其实是一个很简单的,只是考验眼力和手速的游戏。
问题在于砖块总是不能全部消尽。
蒙特卡洛方法的应用——解决“彩色砖块”问题
一局游戏的结果往往是这样的,有一些砖块变得无法消去,即使还有时间。

那么,问题来了,如何得到一个最优解,把所有砖块全部消除掉?

基于蒙特卡洛方法的解决方案

总的方案的是,一次接一次的进行随机实验,直到某一次实验中,所有的砖块都被消去了。
重点在就在于随机实验,所谓的随机实验,是指一局以需要解决的局面为开局的,在计算机中模拟进行的游戏,这局游戏中每一次的点击操作都是从所有可能点击的点中随机选取的,没有任何专家意见和目标性。

代码写得比较粗糙,就不贴出了。

缺点:这个方法的时间复杂度是很高的。
优点:只需要知道规则就可以了,其它的一概不需要。