华容道游戏解法的研究与实现

华容道游戏解法的研究与实现 李瑞民,蒋昌俊 2012-07-19################2012-07-19#####2#0#1#2-07-19########LI Rui- min, JIANG Chang- jun 同济大学 电子与信息 工程 路基工程安全技术交底工程项目施工成本控制工程量增项单年度零星工程技术标正投影法基本原理 学院, 上海 201804 Electronics and Information Engineering, Tongji University, Shanghai 201804, China E- mail: rm_li@sbl.sh.cn LI Rui- min , J IANG Chang- jun.Resear ch and implementation of Chinese Game( Hua Rongdao) .Computer Engineer ing and Applications, 2007, 43( 13) : 108- 110. Abstr act : Hua Rongdao is a very famous puzzled of China.In this thesis, we will try to find a general algorithm for all games like this, this algorithm is Advanced Non- Recursion Depth First Search.Meanwhile we verify its feasibility and effective.At last, we design a program to realize the algorithm, and confirm the analysis by the program. Key wor ds: Hua Rongdao; DFS algorithm; game 摘 要: “华容道”是中国古代传统单人玩的拼板类游戏。虽然以前多次见到报刊、网络有具体解法的报道, 但未见到有对此游戏全 面的 分析 定性数据统计分析pdf销售业绩分析模板建筑结构震害分析销售进度分析表京东商城竞争战略分析 和通用局的计算机解法的描述。为此, 作者采用改进的非递归深度优先算法对《华容道》通用局的解法进行了全面的分析 和论证。随后通过编程实现了这一通用解法, 并通过对当前常见的几十个布局进行了测试, 从而验证了分析结论及其有效性。 关键词: 华容道; 深度优先算法; 电脑游戏 文章编号: 1002- 8331( 2007) 13- 0108- 03 文献标识码: A 中图分类号: TP311 10 棋子在棋盘上的任意一种摆法称为一个布局。其 由这 1 引言 中将曹操放置到第一二排正中位置的一个棋局就构成了一个 华容道游戏的名称来源于中国古典四大名著之一《三国演 “开局”, 当将曹操移动第四五排正中位置时即为“赢局”。此时, 义》中的情节。传说曹操赤壁大战失败后, 诸葛亮派关羽、张飞、 由开局到赢局棋子移动的次数称为本局的赢局步数。所有的赢 赵云、马超、黄忠围追堵截曹操, 但最后关羽因为以前曾受过曹 局步数中, 步数最少的称为最佳解法或最少步数。游戏玩家的 操的恩惠而在华容道放走了曹操。该游戏和七巧板、九连环被 合称为“中国古代三大不可思议的游戏”, 极富益智性和趣味性。 任务就是通过行走移动拼板由开局走到赢局。 该游戏属于单人玩的拼板类游戏。如图 1 所示, 棋盘是由 最早的华容道游戏只有一种布局, 习惯上称为经典布局, 如图 1 就是经典布局。其中关羽是 2×1, 其他四将是 1×2, 表面 4×5 的矩形区域构成, 棋子共 4 种类型 10 块拼板: 2×2 的矩形板 上看关羽是“挡”曹操的, 但曹操若想赢, 必然需要关羽横着让 一个( 曹操) 、1×1 的矩 形 板 4 个 ( 兵 ) , 2×1 和 1×2 的 矩 形 拼 板 道, 曹操 才 有 可 能 通 过 向 下 走 , 这 正 好 符 合 小 说 “关 羽 义 释 曹 共有 5 个( 关张赵马黄五将) 。这 4 种棋子每个单位的大小与棋 操”的情节。如果将经典布局中除曹操之外的其他诸棋子位置 盘的单位大小完全一样, 只能与空格“交换”位置完成棋子的移作了不同布局, 就生成不同的开局。如果张赵马黄四将中部分 动, 棋子在移动的过程中不能超出棋盘范围, 也不能出现重叠。 或全部象关羽一样横着放, 然后再调整各自的位置, 就又创造 了更多的开局, 从而大大增加整个游戏的难度和趣味性。 本文所讨论的内容就是针对上述所说的所有开局, 找到一 个 有 效 的 通 用 解 法 , 在 有 限 时 间 内 , 自 动 找 到 每 一 局 的 最 佳 解法。 2 游戏算法的研究与实现 2.1 对游戏的分析 游戏最初只有一个版本, 随后游戏玩家将本游戏中各棋子 的不同组合扩展至几十个版本,并为给每一局起了一个名字。 2012-07-19################2012-07-19#####2#0#1#2-07-19######## 因而效率不高, 所以放弃前一思路而采用后一个思路。 ( 1) 游戏中棋子的等价关系 游戏中, 四个兵无疑是等价的, 因为无论怎么放置, 当互换 有一个要考虑的重要因素就是回对于通常的 DFS 算法, 他们之间的位置时, 并不能改变任何难度, 也改变不了到达赢 溯条件, 也就是当检索到什么程度时, 不再沿着检索方面继续 局的步数。同样的方法也可以证明, 所有的横将也是相互等价 找下去, 而是换一条路找更合适的方法。一个很明显的回溯条 的, 所有竖将也是等价的。此后的说明及证明都直接使用这个 件就是当找到一个解法时回溯。再考虑在检索过程中, 某一布 理论。 局前面检索时已出现过, 如果不回溯, 而是继续走下去的话, 很 ( 2) 没有横将的开局无解 可能还会走到这一布局, 走下去就形成死循环, 永远无法找到 没有横将时将有 5 个竖将, 整个棋盘共 5 行 4 列, 易知这 解法。但是不是一遇到此前走过的布局就一定要回溯呢? 答案 5 个竖将必将同时占据至少 3 列。而曹操本身占了两列, 因此 是否定的。因为当某次走到某一布局的步数大于此前走到这一 布局的步数时就应该回溯了, 相反, 当小于时就表示到这一布 无论怎么排列, 只要曹操在棋盘的前 3 行( 这是开局前提) , 曹 局, 现在的方法还不如此前的方法, 因此可以放弃继续找, 而用 操的下面将始终有一个竖将, 该竖将移动到曹操未占据的两列 此前的到这一布局的方法继续找。 的前提是: 这两列中某个竖将绕到曹操上面而腾出位置给这个 竖将, 而此时, 曹操将上下各有两员竖将, 两竖将加曹操的长度 有了上述的描述, 理论上已可以完成算法。但分析 设计 领导形象设计圆作业设计ao工艺污水处理厂设计附属工程施工组织设计清扫机器人结构设计 目 标, 很容易发现: 要想在最短时间内找到算法就是减少检索深 将达到 6 行长度, 这与棋盘只有 5 行矛盾, 因此该竖将无法被 度; 找到最佳算法就必须把检索空间全搜索一遍。分析上述算 移动到曹操未占据的两列中。同时由于这一竖将的存在, 曹操 法, 并结合前面一些测试结论可知: “三横将开局”的可检索空 将始终无法向下移动到最下两行, 而这又是到达赢局的前提。 间有七十多万种布局数, 如果找到所有解法, 然后从中找出最 由此可知, 五竖将无论怎么排列的开局都是无解的。 短的方法, 一则检索量太大而浪费很多时间, 二则其中有很多 ( 3) 华容道所有布局有多少? 重复的局部检索路径。可见纯 DFS 算法不合适, 因此需要采用 如前所述, 棋子的不同组合就有不同的布局, 似乎游戏的 一种改进算法。 开局有无穷多个。为了准确计算出其个数, 编写了一个程序进 改进的突破点一是在检索深度上, 这里有两处可以改进, 行统计, 得到表 1。 一是最大深度, 二是动态设置深度。前者是指在算法运行前就 表 1 华容道所有布局统计图 设定一个深度, 这个深度是预估的最大深度( 此后称为首次最 大深度) , 虽然这可能导致当最大深度大于一个布局实际深度 时找不到检索算法, 但最大深度的使用可以大大减少不必要的 检索分枝, 使算法加速。另一处改进就是动态设置深度, 比如算 法已找到一个 120 步的解法, 再找一个 125 步的解法并无太大 四兵等价横将等价、竖将等价、四兵等价 的意义, 因此此时, 应该把“最大深度”动态地改为 120 步, 即大 横将选项 所有布局等价因子等价布局赢局剩余布局 于 这 个 深 度 的 检 索 不 再 进 行 , 使 检 索 深 度 逐 渐 “逼 近 ”最 小 一横将开局1 888 200 P( 4, 4) 78 675 6 795 71 880 步 数 。 二横将开局 6 387 840 P( 2, 2) *P( 3, 3) 532 320 8 250 524 070 改进的第二个突破点在减少重复的局部检索路径。这一改 三横将开局 9 460 800 P( 3, 3) *P( 2, 2) 788 400 6 030 782 370 进的关键是如何解决深度优先算法是递归算法本身的不足。深 四横将开局 ( , )6 347 520 P44 264 480 1 590 262 890 度优先算法是严格按“检索树”的路径走, 走不通则必然回到上 五横将开局 ( , )2 230 200 P55 18 585 135 18 450 层分枝, 如果想到同一层另一分枝, 则不停回退到上一层, 一直 总计 ? 26 314 560 1 682 460 22 800 1 659 660 退到和要到的同层分枝共同的父母节点, 再沿到另一分枝的路 径找到另一分枝节点。如果能直接“跳跃”到要去的分枝上, 则 表中公式: 所有布局/等价因子=等价布局 等价布局- 赢局=剩余布局 可以减少很多检索路径。在本算法中, 当检索到某一布局, 发现 在表 1 中, “所有布局”表示只考虑 4 兵等价, 而张赵马黄 由开局走到这一布局, 此次用的步数比此前到此布局用的布数 不等价情况下所有可能布局数。“等价因子”是指在某个布局 多时, 就可以用以前的路径继续找下去。实现这一功能, 则必然 下, 将横将等价、竖将等价看待时, 需要除以的数。例如“两横将 要打破递归 DFS 本身的检索结构, 本人采用的是非递归的方 开局”, 两个 横 将 等 价 , 同 时 另 外 三 竖 将 也 等 价 , 所 以 “所 有 布 法。具体实现方法是: 当发现某一布局此前已走过, 并且前面的 局”除以两横将等价的排列( P( 2, 2) ) , 再除以两竖将等价的排 步数少于当前步数时, 就直接跳转到这一布局处, 并恢复这一 列( P( 3, 3) ) 即得到“等价布局”。在横将等价、竖将等价的情况 布局的堆栈信息, 由于算法本身就是针对任意布局的, 所以从 下, 已走过布局的的上限是“剩余布局”的最大值 782 370。假设 跳转后的布局继续下去无任何影响。此处保存的堆栈主要是步 每秒可测 2 000 个布局, 把所有“剩余布局”遍历一遍, 最多需 数、当前布局、和调用此堆栈的下一条指令入口。 要 782 370/2 000/60=6.5 min, 经实测, 最多的遍历时间用了 6 顺便需要指出的是对查找当前局是否是已走过的布局的 分 45 秒, 相差不大。 算法。一则是因为如图 2 所述, “三将横开局”的有效检索空间 有 78 万之多, 虽然空间是逐渐增大, 但因为每走一步都要查一 2.2 算法分析- 非递归改进 DFS 算法遍, 所以这部分数据如果没有合理的组织, 效率也会很低。在经 本算法的设计目标是对任意布局在尽量短的时间内检索 过一番比较, 并通过程序具体执行后发现, 采用二叉检索树 到最佳算法。对于这类游戏解法检索, 一般采用广度优先查找 算 法 ( Breadth First Search , BFS) 或 深 度 优 先 查 找 算 法 ( Depth First Search, DFS) 。BFS 的优点是找到的第一个解法就是最佳 解法, 但在这个游戏中, 每一局一般要有 100 步以上, 如果采用 BFS, 要记录的信息量惊人, 因此无法采用。采用 DFS 时, 有两 个思路, 一个思路是从棋子的角度考虑, 依次考虑每个棋子的 布局的检索空间, 在查找时, 采用 HASH 算法, 直接转为了各维 160 后算法得 下编译运行。并且每局的首次最大深度都设置为 数组的索引, 然后在这一具体数组中查找或添加。经过实际测 到的参数表。 试, 此方法虽然浪费了不少空间, 但速度约为只采用一个数组 与其他《华容道》游戏相比, 某些参数值会有出入。可能的 的 1 000 倍以上。 原因如下: ( 1) 步数的计法不一样: 有些游戏认为同一棋子连走两步 经测试, 加大 DFS 搜索深度, 可更快 找 到 第 一 个 解 法 ; 减算一步, 比如某兵连向下走了两步, 或向下一步向右一步, 都算 小 DFS 搜索深度, 可更快找到最佳步数解法。由于赢局的条件 成一步, 而本程序则计算为两步。据国外资料声称, 美国数学家 是只考虑曹操位置, 不考虑其他棋子的位置, 所以加大搜索深 马丁?加德纳曾创造经典布局步数最少的世界记录是 81 步, 但 度, 减少了 回 溯 次 数 , 在 众 多 的 解 法 中 , 找 到 任 意 一 个 解 法 即 转化为本程序计数法时, 却是 118 步, 比本算法找出的解法还 可, 所以速度较快。减小搜索深度后, 搜索深度一项产生了大量 因深度超过而产生的回溯, 所以速度较慢。 多 2 步。 ( 2) 上面所有参数值的前提是首次最大检索深度为 160, 减 小此值, 会使最佳检索和遍历时间减小( 不能小于本身最佳步 数值, 否则系统将找不到解法) 。增加此值, 会使找到第一个解 法的时间减小。经测试, 最大深度为 1 999 时, 绝大多数局都可 3 各局实际执行效果 理论上, 任何一个有效开局都能称为一个游戏局, 但通常 以在 10 秒之内找到首个解法。 ( 3) 本程序自动检索线程采用了很高的优先级, 在运行的 情况下, 如果其中一个局能很快地转换为另一局, 通常只取其 中一个局作为开局。下面为了验证算法的可行性和效率, 对民 间常用的开局进行了测试, 并得到了结论。对于未列在其中的 开局, 由于算法是针对任何布局的, 所以只要改一下程序中的 所以如果在测试的时候, 时候, CPU 使用率一般在 95%以上, } else { enque( pkt) ; } } 随后, 要建立一个 C++类到 Otcl 类的连接类 SREDClass: static class SREDClass: public TclClass { public: SREDClass( ) : TclClass( "Queue/SRED ) " {} TclObject* create( int, coNSt char*coNSt*) { return ( new SRED) ; 从图 3 中可看出, 在新算法 SRED 中, 瞬时队列长度的变 } 化率要明显小于 RED 算法中的瞬时队列长度变化率, 这表明 } class_sred; 即新算法的改进 措施 《全国民用建筑工程设计技术措施》规划•建筑•景观全国民用建筑工程设计技术措施》规划•建筑•景观软件质量保证措施下载工地伤害及预防措施下载关于贯彻落实的具体措施 新算法的稳定性要明显好于 RED 算法, 该类主要是将 C++实现的类 SRED 与 Tcl 类 Queue/SRED 是有效的。 联系起来, 以支持它们之间的互操作。 NS2 中的仿真实验表明, 设计的 SRED 算法在稳定 通过在 ( 1) ns- default.tcl 的修改 性方面较 RED 算法有较大改进。 可以在 ns- 2/tcl/lib/ns- default.tcl 文件中对类 SRED 的一些 属性设置缺省的初值, 但这一步不是必须的, 用户可以在实验 脚本中进行设置。 5 结论 ( 2) makefile 的修改 本文结合一个新的队列管理算法详述了如何在 NS2 中实 将 sred.o 加入到编译工程文件 makefile 中。重新编译连接 现新协议和新算法, 并对新协议进行测试和验证, 这在网络研 ( make) 即可, 这样新的 NS2 内核就能支持 SRED 算法了。 究中是非常重要的一项工作, 仿真实验也验证了新算法的有效 性。网络仿真是检验网络协议、算法的正确性和有效性, 以及测 试网络性能的有效的和必不可少的方法, 它能帮助我们更直 观、更灵活地分析和研究网络。通过在 NS2 中实现一些新协 4 仿真实验议、新算法进行网络仿真研究大大提高了效率、降低了成本, 并 为了测试新算法的稳定性, 编写了一些 Otcl 脚本在多种 更具灵活性。( 收稿日期: 2006 年 11 月) 网络环境下进行了仿真实验, 以便对算法的效果和性能进行检 验, 这也是对 NS2 进行扩展的目的。因为若在实际的路由器上 实现该算法, 并进行实验, 工作量和代价都要大得多, 而且缺乏 灵活性。 参考文献:仿真实验的拓扑如图 2。其中左边为多个发送端, 右边为 [1] Network simulator( NS- 2.28) [EB/OL].http: //www.isi.edu/NSnam/NS, 一个接受端, 瓶颈链路的带宽为 2 Mbps, 延时为 1 ms。 University of California at Berkeley, 2006. [2] Floyd S, Jacobson V.Random early detection gateways for congestion avoidance[J].IEEE/ ACM Transactions on Networking, 1993 , 1 ( 4 ) : 397- 413. [3] Feng W, Shin K G, Kandlur D D, et al.The BLUE active queue management algorithms[J].IEEE/ACM Transactions on Networking, 2002, 10( 4) : 513- 528. [4] Bitorika A, Robin M.A comparative study of active queue manage- ment schemes[C]//ICC’04, c2004: 153- 158. [5] 高文宇, 王建新, 陈松乔.PFED: 一种基于预测的公平的主动队列管 Senders 和 Receiver 之间建立的 TCP 连接个 在实验中, 当 理算法[J].计算机研究与发展, 2006, 43( 2) : 204- 210. 数分别为 50、60、70、80、90、100 时, 考察了不同算法下瓶颈链 也许随着本人对算法和编程的理解, 将来可以得到更高效、更 ( 上接 110 页) 同时运行其他占用 CPU 资源较大的程序时, 合理的算法。( 收稿日期: 2006 年 8 月) 测试值有时会差距很大, 上述值都是单独运行时所测的值。 参考文献:[1] 魏仲良, 林顺喜.利用计算机探讨中国古代益智游戏?「华容道」之 4 结束语 解法[EB/OL].http: // 140.122.185.131/icewise/docs/hua.doc. 通过本游戏分析及程序开发, 本人切实地感受到了算法的 [2] 佚名.游戏华容道的历史[EB/OL].http: //qzc.zgz.cn/huarongdao1.htm. 重要性, 一个好的算法是解决问 题 快递公司问题件快递公司问题件货款处理关于圆的周长面积重点题型关于解方程组的题及答案关于南海问题 的关键。经过几次程序算法 [3] 佚名.闯过华容道[EB/OL].http: //www.math.sdu.edu.cn/html/sxjm/ex- 改进和代码优化, 目前对于任意布局都可以在 10 分钟内找到 amples/ex5.htm. 最佳解法。但就本程序, 部分代码的高效源于大量内存的耗费, Your requestcould not be processed becauseof a configurationerror: "Could not connect to LDAPserver." For assistance,contact your network support team. file:///C|/Users/Administrator/Desktop/新建文本文档.txt 涵盖各行业最丰富完备的资料文献,最前瞻权威的行业动态,是专业人士的不二选择。 file:///C|/Users/Administrator/Desktop/新建文本文档.txt2012/8/26 12:19:58