华容道游戏怎么通关?自动在线解题程序,华容道游戏图解

作者:半瓶墨水   链接:http://www.2maomao.com/blog/youxi-hrd-online-resolver/

=====================================
插播一则广告

发芽网华容道精装版App发布啦(iPhone和iPad版), 点击查看
https://itunes.apple.com/cn/app/fa-ya-wang-hua-rong-dao-jing/id599917734

还是一样的精装版,一样的过关记录回放,精致的过关特效,方便的操作,精美的配乐。
包含发芽网华容道在线版的所有布局以及许多首手机程序独有的布局。
=====================================

先给地址吧:华容道游戏在线求解程序,已证明是最短路径
华容道在线游戏,游戏发芽网
(注意需要登录才能使用,因为担心不加限制的使用会导致服务器端繁忙)

前些日子黄志华先生跟我联系过程中,得知我有求解华容道过关最短路径的程序(其实是Leo Jay编写的),便拟了几个开局让我帮忙看看最快的解决方案。
几封Email之后,我想,何不做个在线求解的呢?

说起来容易,做起来难,世事皆是如此

在十一回天津的路上,我就已经想清楚如何做这个程序,如何移植到linux主机上(发芽网放在一个linux 64位机上),网页如何组织。

Leo Jay的程序写的很不错,不过是Python的,本身就受到很多限制,所以求解一个布局往往要很多秒,这在一个在线求解程序来说是无法接受的(会被主机提供商K的)

最后决定用C++(其实是better C)改写,并用matrix变换的方式以及布局镜像的方式减少了很多计算。
经过两天的调试(嗯,时间长了一些,大多时候在逗小宝宝和睡觉吃饭),终于可以把求解时间限制在10毫秒左右。

然后是开始做网页版,这才是令人头大的问题,IE的兼容性问题,javascript的调试,python与C++程序沟通的方式,网页布局的调整等等等等,放到后面去讨论。

最终,经过漫长的调试,老婆在旁边不断地关心和支持下,在十一结束一天的时候搞定了,发给黄志华先生看了一下,发现在IE下还有些小问题,立马改正,现在已经可用了

十一假期之中,除了哄小宝宝、陪猫猫逛街、唠嗑、吃饭、睡觉、看电视、修电脑等等家事之外,有长时间空闲的时候,都在做这个,做的累,老婆看着也累,希望有用吧。

———————–下面进入技术问题的探讨————————-

华容道的求解代码(C++版本)在这里:http://www.fayaa.com/code/view/418/
最终版只是输出格式有些不同,为了更好的python-C++交互

1. 求解原理
原理说起来一点都不复杂,不过需要一点点计算机专业知识(知道人工智能就更好了)。
步骤1:对开局中每个棋子进行移动,这会产生很多新的局面,全放到队列里
步骤2:所有的局面都存储下来,产生的新局面如果曾经到达过,就放弃了
步骤3:重复步骤1和2,直到出现曹操到达出口的局面出现,即可求出最终解
为什么这样可以保证是最快的解法呢?
说到这里,你可能看出来了,这就是一个求解树的宽度优先遍历嘛,第一个找到的答案当然是最快的,否则前面早就找到了。

2. 几个关键问题
(这两个问题的解答都可以参照代码来看)
Q1:中间局面如何存储?
A1:共五类方块:空块,1×1, 2×1, 1×2, 2×3,编号为0|1|2|3|4,然后把布局看成一个5×4的数组,里面的每个元素都是编号。
  这个数组就是布局

Q2:求到最终解以后如何得出求解路径?
A2:每个局面都指向父局面即可,然后用个while循环遍历到头,一路记下来就行。
  需要特别注意的是,在华容道的步骤计算中,多次连续移动一个方块只算一步的,所以每次移动一个方块以后要看它能否再次移动,如果可以再次移动,就再移动一步。

3. 如何加速求解
加速求解的方法无外乎几种:
1. 消除重复计算
2. 利用成型的算法,比如二分查找、快排、hash等等
3. 空间换时间

我做的c++解华容道的代码中试用了下面方法:
方法1:压缩局面存储空间:每个类别可以用3-bit表示,5x4x3=60,为了方便可以用一个64bit的整形表示
方法2:使用hash
方法3:新局面产生过程采用推演的方式而不是重新计算:我在生成新的matrix的时候不是遍历所有方块,而只是遍历空块周围的方块
方法4:对镜像局面进行处理:一个左右镜像的局面,其最短路径一定是一致的,对布局的表示值做hash的时候要把镜像布局的值也加进去,可以加速计算

4. python-C++交互
首先想到的是python调用C++的库,Google了一下,好象不是半个小时能搞定的,而且做成dll以后放在linux上怎么弄还不知道哦
然后就想到了更简单的方案:C++的解题程序做成命令行可执行程序,直接输入位置串,输出的是最短步数和求解过程串
为了让这个方案更加简洁,我修改了好几次输入输出方案
python里面用用popen执行程序并截获命令行输出就行了

5. 网页表现层
这个费的时间最多,偏偏没什么可说的东西。
首先我想用拖放的形式做布局,实现了一半的时候,觉得javascript支持拖动以及验证太费劲了。碰巧小宝宝开始闹了,抱着她哄来哄去的时候,突然想到,何必这么烦呢?这个页面的目标用户都应该有一些基础知识了,做个不是那么弱智的程序就行了呗,遂有了现在的版本。
中间调试firefox/IE兼容性,加上浏览器缓存带来的问题,很是恼火了一番,不过还是忍着做完了。

好啦,整个过程就是这样,欢迎在下面留言。

相关链接:游戏发芽网的在线华容道游戏

11 条评论 发表在“华容道游戏怎么通关?自动在线解题程序,华容道游戏图解”上

  1. You Xu说道:

    发芽兄: 我想华容道是极度受限的搜索模型, Python+Graphsesrch 绝对不出100毫秒的. 所以我想你用Python 搞或许更加方便一点.

  2. 半瓶墨水说道:

    @You Xu
    当时为了保证速度,就没有选直接用Python这条路
    服务商限制诸多,100ms已是上限,要保证服务的话必须要把时间压缩到更低
    像现在这样在服务端差不多10ms的样子,内存占用都在几个Mega,符合我最初的要求了,或许Python可以很好做,也不愿再改了
    BTW:用popen捕获输出很方便,由于要求简单,python-C++这样交互很方便

  3. RedNax说道:

    python-C++最方便做法应该是boostpython,这个能在半小时内搞定。
    P.s. boostpython在boost中还算是比较独立的东西,用起来不复杂。

  4. 半瓶墨水说道:

    @RedNax 呵呵感谢你介绍boost.python
    Python-C++交互的部分我采用的是捕获输出的方式,也很简单,也就几分钟吧
    Boost.python用在这里有点儿牛刀切豆腐了

  5. skier说道:

    博主,我现在尝试用回溯(DFS)来求解华容道,只是单纯的想用回溯来解这个算题,不考虑时间效率。
    现在遇到的问题就是再搜索布局的时候经常会进入循环,就是在若干种特定情况下几个棋子在不停的循环移动,考虑良久也没有什么好的解决办法,不知博主可否指教一二? 多谢!

  6. 半瓶墨水说道:

    @skier
    DFS也要考虑走过没走过啊,因为华容道走起来不是一棵树(Tree),而是一张图(Graph)

  7. skier说道:

    多谢博主赐教!

  8. ZaakDov说道:

    老大
    除了朴素BFS之外,没想过其他的了?

    IBA*之类的,或者说剪枝

    还想说俄能不能将状态不设定为每一块的形状,而设置为某几块的组合,因为那样的话,能够减少很多的计算,相当于将整个求解过程划分为好几个阶段,先预处理各种组合到达各种目标的最大最小步数,然后重复利用该结果,这样先利用BFS一次,累计最大步数最小步数,时间会非常快(zh指数级别的时间复杂度直接大幅度降掉指数,因该期望是原本时间的1/4次方),然后在依据步数限制剪枝,基本上能够做到O(e*log(minstep)),所以复杂度由原来的:
    O(e^minstep)
    降到:
    O(e^(minstep/4))+O(e*log(minstep))=O(e^(minstep/4))
    开了大概4次方,很爽的
    实际上估算了一下,那个常数4换成6更合适

  9. ZaakDov说道:

    比如如下的一些组合:
    类别一:min[state]=2,max[state]=19
    12 xx
    12 14
    34 15
    35 23
    xx 23
    类别二:min[state]=1,max[state]=6
    1x 2x xx
    1x 1x 21
    23 13 31
    显然等价

  10. ZaakDov说道:

    还有,根据解答树的分布规律,好像Beam Search也很不错的

  11. 半瓶墨水说道:

    @ZaakDov
    你可以试试写一下,并将结果共享出来
    这篇blog写完有许多人提出不同的方案,但只有一个人真正做到了(我是说实现)了更快的方案

留下回复