论文部分内容阅读
摘要：针对Android移动终端人机实时交互的特点，结合中国象棋的特点，牵涉到Android开发和Java程序设计以及算法分析等相关知识。即勾勒了整个程序的结构框架，又详细分析和设计了其中的功能模块，例如棋子绘制，局面状态变量的意义和变化逻辑，人机交互的全过程等。全面讲解了搜索算法，从棋局表示、走法生成、局面估计到搜索树的遍历和Alpha-Beta剪枝算法。
关键词：Android；局面估值；Alpha-Beta搜索；历史表；人机交互
中图分类号：TP391 文献标识码：A 文章编号：1009-3044（2014）32-7742-02
Abstract： This is the feature which is real-time human-computer interaction about android mobile terminal .Combined with the characteristics of Chinese Chess， involving many knowledge of Android development and Java program design and algorithm analysis. Draw the outline of the structure of the entire application framework， and analysis and design of the module in detail， such as chess， situation of state variables and change the meaning of logic， the whole process of human-computer interaction. There is comprehensive interpretation of the search algorithm， from chess said， move generation， situation estimate to search tree traversal and Alpha - Beta pruning algorithm.
Key words：Android； Situation to valuation； Alpha-Beta Search； History lists； Human-computer interaction
1 概述
计算机博弈是博弈游戏与计算机决策系统的结合，是人工智能里一个重要的研究领域，是机器智能、兵棋推演等领域的科研基础。中国象棋是中国古老的游戏，逻辑性极强，中国象棋模拟涵盖场景建模、状态表示、棋局分布、走法生成、搜索算法等方面，如何实现中国象棋的人机对弈显得尤其重要。
随着3G技术和android系统的发展，智能手机的市场占有率极高，智能手机游戏在人们生活中占有重要的位置。中国象棋以它的趣味性、逻辑性、哲理性在棋牌游戏中首屈一指，深受多数玩家的青睐和热衷。基于此，本课题的研究和开发应运而生，并且更加注重人性化（例如多步悔棋、将军等棋局状态提示）、友好操作接口的设计和开发。程序中随时都能进行难度设置，符合多种玩家的技艺要求，并且可以伴随玩家棋艺水平竞相成长。总之，本课题的开发，以逼真的视角，简便的操作方式，人性化的设计，生动的下棋环境，定能让玩家体验到中国象棋的智慧和乐趣。
2 需求分析與设计
2.1 欢迎界面
对事物评价的好坏，第一印象至关重要。程序是通过设置两张精美的中国象棋图片来启动的，就像放映电影一样，使游戏更加有厚重感、故事性和趣味性，从而使玩家进入纯净高远而且玄妙有趣的象棋世界。
2.2 游戏界面
游戏界面是玩家和计算机对弈的阵地，是程序绘制棋盘，排布棋子，并走动棋子的界面。
游戏界面具有动态智能性，要时刻反应人机双方走棋落子的信息，同时熟知走棋规则，对玩家的不合理落子予以拒绝，及时的提醒玩家将军和被将军等重要信息。此外还将对玩家举棋和落子添加声效处理，对人机双方的走棋都标识出走棋位置和落子位置，使整个下棋过程更逼真生动，交互更加清晰明确。
2.3菜单
菜单处于Android的系统级别。提供人机下棋的难度等级“容易”、“中等”和“困难”，并给以选择提示。此外提供悔棋功能，即使在实物象棋对战中，棋手们的悔棋也是不可避免的，甚至是人性化的、无可厚非的，更何况程序是通过不总是精确到像素点的触屏操作呢，并且设置悔棋步数限制。玩家在有悔棋需求时，点击菜单选项中的“悔棋亦君子”来返回上一步的棋局状态，并同时计入悔棋步数中。
3 搜索算法分析
象棋搜索算法是象棋程序的灵魂，体现程序的健壮性和高效性，是整个程序设计和开发的关键。
3.1局面表示
局面表示是象棋程序的基础，它的好坏直接关系到走法生成、局面评估和搜索算法的效率。本象棋程序采用的是16*16的二维数组表示法。
3.2走法和全局走法生成
走法就是一个棋子按照象棋的规则从一个位置移动到另一个位置。棋子走法所遵循的的走棋规则被逻辑映射成一个走棋方向数组，从棋子的原位置出发，朝着走棋数组的值所标识的方向前进并得到棋子的落子位置，记录这个走法即可。
在走法数据结构和各种棋子走法生成的基础上，遍历整个棋盘，找出当前走棋方的棋子，然后逐个棋子生成其所有可能的走法，全部保存下来，就得到了整个局面的全部走法。
3.3局面评估
局面评估是判断局面对红方（或者黑方）的优势，并把这个优势量化。目的是为了在多个局面之间进行比较，然后选择对应局面的走法，从而得到有利的局面。 棋盘上棋子的存在本身就是一种价值，这种价值随兵种不同而有大小之分。我们会根据人们的下棋经验来分配给棋子不同的存在价值。在计算棋子的存在价值时，把当前下棋方所有棋子的价值累加起来即可。
一个棋子在棋局的真正价值，不仅与固定的分值有关，还与所处的位置有联系。程序中我们可以定义一个二维数组，来表示不同棋子在不同位置的分值。该分值数组也是由人们从经验中总结而来的。计算局面价值时，把当前下棋方所有棋子在其对应的数组位置上的分值全部累加起来。
4 搜索算法
搜索算法就是计算机的思考下棋的过程。计算机根据当前局面，生成所有可能的走法，试走每一个走法来到不同的新局面。在每一个新局面的基础上，同样再生成所有走法，并试走下去，走到更新局面。如此递归下去到达一定的深度。根据数据结构的知识我们知道，这正是以一颗树的形式来对问题展开讨论。我们把这颗精致的树叫做“搜索树”。
4.1遍历搜索树
搜索树正是计算机的整个思考空间，遍历它的意义就是得到思考空间中的最佳思考分支。由于一次只能走一步棋，所以我们只需要得到最佳分支的第一层走法即可，不必对整个从根节点到叶子节点的分支进行存储。
4.2搜索剪枝
对整棵搜索树进行完全搜索肯定能够得到最佳走法，但效率上却是事倍功半的。搜索的目的是为了获得一个可能的最佳局面，从而得到当前要走的最佳走法。如果沿着一个结点搜索下去，绝对不可能有比当前已经搜索到的最佳局面更优，那么可以断定这就是一个无用结点，应该减掉。
4.3 Alpha-Beta搜索
为了在搜索过程中引起剪枝，在递归过程中向下传递两个参数。第一个参数是Alpha，表示当前搜索结点走棋方已经搜索到的最优值，任何比它小的局面估值都没有意义。第二个参数是Beta，表示对手目前的劣势，这是对手所能够承受的最坏的结果。Beta值越大，表示对方的劣势越明显。在对手看来，他总是希望找到一个不比Beta值更坏的对策。如果当前结点返回一个比Beta更大的值，作为父节点的对方是绝对不会选择的，这个时候也会发生剪枝。
4.4搜索辅助工具
除了上面介绍的局面表示、走法生成和局面评估等之外，搜索算法还需要一些小帮手。例如交换走子方，在棋盘上放置、拿走一枚棋子，历史表，走法生成函数、是否过河、获得走法的起点和落子点等。这些功能可以看成搜索算法的几种不同的单位操作，以函数形式提供给搜索算法调用。
5 結论
本文从象棋程序设计的背景讲起，牵涉需求分析中界面的设计、菜单设计等知识，从基本的局面表示，到关键的搜索引擎，最后到具体的代码实现，完成了游戏的框架，并且通过测试进行正常独立运行。
参考文献：
[1] 吴亚峰，苏亚光，等. Android游戏开发大全[M]. 北京： 人民邮电出版社， 2013.
[2] 高彩丽，许黎民，袁海，等.Android开发范例精解[M]. 北京：清华大学出版社，2012.
[3] Cay S.Horstmann（美），Gary Cornell（美）等.Java核心技术[M].北京：机械工业出版社，2008.
[4] 吴健，胡振国， 邓郑工，等.编程方法论[M].北京：国防工业出版社，2008.
[5] 余志龙，陈立勋，等. Android SDK开发范例大全[M]. 2版.北京：人民邮电出版社，2010.
[6] 李华明，等. Android游戏开发之从零开始[M]. 北京：清华大学出版社，2011.
[7] 臧利萍，刘燕美，高振.基于Android的飞行射击游戏的模拟[J]. 电子世界， 2014，6
[8] 臧利萍， 李玲玲， 管涛.基于GPU的大规模水域场景的动态模拟[J]. 中原工学院学报， 2013（8）.
[9] 谷歌Android开发者. Android的编程指南. http：//developer.android.com/guide/topics/fundamentals.html.
关键词：Android；局面估值；Alpha-Beta搜索；历史表；人机交互
中图分类号：TP391 文献标识码：A 文章编号：1009-3044（2014）32-7742-02
Abstract： This is the feature which is real-time human-computer interaction about android mobile terminal .Combined with the characteristics of Chinese Chess， involving many knowledge of Android development and Java program design and algorithm analysis. Draw the outline of the structure of the entire application framework， and analysis and design of the module in detail， such as chess， situation of state variables and change the meaning of logic， the whole process of human-computer interaction. There is comprehensive interpretation of the search algorithm， from chess said， move generation， situation estimate to search tree traversal and Alpha - Beta pruning algorithm.
Key words：Android； Situation to valuation； Alpha-Beta Search； History lists； Human-computer interaction
1 概述
计算机博弈是博弈游戏与计算机决策系统的结合，是人工智能里一个重要的研究领域，是机器智能、兵棋推演等领域的科研基础。中国象棋是中国古老的游戏，逻辑性极强，中国象棋模拟涵盖场景建模、状态表示、棋局分布、走法生成、搜索算法等方面，如何实现中国象棋的人机对弈显得尤其重要。
随着3G技术和android系统的发展，智能手机的市场占有率极高，智能手机游戏在人们生活中占有重要的位置。中国象棋以它的趣味性、逻辑性、哲理性在棋牌游戏中首屈一指，深受多数玩家的青睐和热衷。基于此，本课题的研究和开发应运而生，并且更加注重人性化（例如多步悔棋、将军等棋局状态提示）、友好操作接口的设计和开发。程序中随时都能进行难度设置，符合多种玩家的技艺要求，并且可以伴随玩家棋艺水平竞相成长。总之，本课题的开发，以逼真的视角，简便的操作方式，人性化的设计，生动的下棋环境，定能让玩家体验到中国象棋的智慧和乐趣。
2 需求分析與设计
2.1 欢迎界面
对事物评价的好坏，第一印象至关重要。程序是通过设置两张精美的中国象棋图片来启动的，就像放映电影一样，使游戏更加有厚重感、故事性和趣味性，从而使玩家进入纯净高远而且玄妙有趣的象棋世界。
2.2 游戏界面
游戏界面是玩家和计算机对弈的阵地，是程序绘制棋盘，排布棋子，并走动棋子的界面。
游戏界面具有动态智能性，要时刻反应人机双方走棋落子的信息，同时熟知走棋规则，对玩家的不合理落子予以拒绝，及时的提醒玩家将军和被将军等重要信息。此外还将对玩家举棋和落子添加声效处理，对人机双方的走棋都标识出走棋位置和落子位置，使整个下棋过程更逼真生动，交互更加清晰明确。
2.3菜单
菜单处于Android的系统级别。提供人机下棋的难度等级“容易”、“中等”和“困难”，并给以选择提示。此外提供悔棋功能，即使在实物象棋对战中，棋手们的悔棋也是不可避免的，甚至是人性化的、无可厚非的，更何况程序是通过不总是精确到像素点的触屏操作呢，并且设置悔棋步数限制。玩家在有悔棋需求时，点击菜单选项中的“悔棋亦君子”来返回上一步的棋局状态，并同时计入悔棋步数中。
3 搜索算法分析
象棋搜索算法是象棋程序的灵魂，体现程序的健壮性和高效性，是整个程序设计和开发的关键。
3.1局面表示
局面表示是象棋程序的基础，它的好坏直接关系到走法生成、局面评估和搜索算法的效率。本象棋程序采用的是16*16的二维数组表示法。
3.2走法和全局走法生成
走法就是一个棋子按照象棋的规则从一个位置移动到另一个位置。棋子走法所遵循的的走棋规则被逻辑映射成一个走棋方向数组，从棋子的原位置出发，朝着走棋数组的值所标识的方向前进并得到棋子的落子位置，记录这个走法即可。
在走法数据结构和各种棋子走法生成的基础上，遍历整个棋盘，找出当前走棋方的棋子，然后逐个棋子生成其所有可能的走法，全部保存下来，就得到了整个局面的全部走法。
3.3局面评估
局面评估是判断局面对红方（或者黑方）的优势，并把这个优势量化。目的是为了在多个局面之间进行比较，然后选择对应局面的走法，从而得到有利的局面。 棋盘上棋子的存在本身就是一种价值，这种价值随兵种不同而有大小之分。我们会根据人们的下棋经验来分配给棋子不同的存在价值。在计算棋子的存在价值时，把当前下棋方所有棋子的价值累加起来即可。
一个棋子在棋局的真正价值，不仅与固定的分值有关，还与所处的位置有联系。程序中我们可以定义一个二维数组，来表示不同棋子在不同位置的分值。该分值数组也是由人们从经验中总结而来的。计算局面价值时，把当前下棋方所有棋子在其对应的数组位置上的分值全部累加起来。
4 搜索算法
搜索算法就是计算机的思考下棋的过程。计算机根据当前局面，生成所有可能的走法，试走每一个走法来到不同的新局面。在每一个新局面的基础上，同样再生成所有走法，并试走下去，走到更新局面。如此递归下去到达一定的深度。根据数据结构的知识我们知道，这正是以一颗树的形式来对问题展开讨论。我们把这颗精致的树叫做“搜索树”。
4.1遍历搜索树
搜索树正是计算机的整个思考空间，遍历它的意义就是得到思考空间中的最佳思考分支。由于一次只能走一步棋，所以我们只需要得到最佳分支的第一层走法即可，不必对整个从根节点到叶子节点的分支进行存储。
4.2搜索剪枝
对整棵搜索树进行完全搜索肯定能够得到最佳走法，但效率上却是事倍功半的。搜索的目的是为了获得一个可能的最佳局面，从而得到当前要走的最佳走法。如果沿着一个结点搜索下去，绝对不可能有比当前已经搜索到的最佳局面更优，那么可以断定这就是一个无用结点，应该减掉。
4.3 Alpha-Beta搜索
为了在搜索过程中引起剪枝，在递归过程中向下传递两个参数。第一个参数是Alpha，表示当前搜索结点走棋方已经搜索到的最优值，任何比它小的局面估值都没有意义。第二个参数是Beta，表示对手目前的劣势，这是对手所能够承受的最坏的结果。Beta值越大，表示对方的劣势越明显。在对手看来，他总是希望找到一个不比Beta值更坏的对策。如果当前结点返回一个比Beta更大的值，作为父节点的对方是绝对不会选择的，这个时候也会发生剪枝。
4.4搜索辅助工具
除了上面介绍的局面表示、走法生成和局面评估等之外，搜索算法还需要一些小帮手。例如交换走子方，在棋盘上放置、拿走一枚棋子，历史表，走法生成函数、是否过河、获得走法的起点和落子点等。这些功能可以看成搜索算法的几种不同的单位操作，以函数形式提供给搜索算法调用。
5 結论
本文从象棋程序设计的背景讲起，牵涉需求分析中界面的设计、菜单设计等知识，从基本的局面表示，到关键的搜索引擎，最后到具体的代码实现，完成了游戏的框架，并且通过测试进行正常独立运行。
参考文献：
[1] 吴亚峰，苏亚光，等. Android游戏开发大全[M]. 北京： 人民邮电出版社， 2013.
[2] 高彩丽，许黎民，袁海，等.Android开发范例精解[M]. 北京：清华大学出版社，2012.
[3] Cay S.Horstmann（美），Gary Cornell（美）等.Java核心技术[M].北京：机械工业出版社，2008.
[4] 吴健，胡振国， 邓郑工，等.编程方法论[M].北京：国防工业出版社，2008.
[5] 余志龙，陈立勋，等. Android SDK开发范例大全[M]. 2版.北京：人民邮电出版社，2010.
[6] 李华明，等. Android游戏开发之从零开始[M]. 北京：清华大学出版社，2011.
[7] 臧利萍，刘燕美，高振.基于Android的飞行射击游戏的模拟[J]. 电子世界， 2014，6
[8] 臧利萍， 李玲玲， 管涛.基于GPU的大规模水域场景的动态模拟[J]. 中原工学院学报， 2013（8）.
[9] 谷歌Android开发者. Android的编程指南. http：//developer.android.com/guide/topics/fundamentals.html.