基于Visual Studio C# 2008的八数码游戏的设计与实现
龙之梦
1 引言
搜索是人工智能中的一个基本问题，也是模拟仿真中研究的一般性问题，是推理不可分割的一部分。现实世界中的大多数问题都是结构不良或非结构化的问题，一般不存在现成的求解方法，而只能利用已有的知识一步步地摸索着前进，如梵塔问题、MC问题、猴子摘香蕉、八数码难题等。
八数码难题一般描述：在3×3的方格棋盘上，分别放置标有数字1、2、3、4、5、6、7、8的八张牌，第九张牌不标数字，记为空格，给定一种初始状态和目标状态，通过移动空格，使得棋盘从初始状态向目标状态转换（其中操作空格可用的操作有：左移、上移、右移、下移，但不能移出棋盘之外），通过搜索策略寻从初始状态到目标状态的解路径。
解决八数码问题的搜索策略有很多，归纳起来主要有三种：深度优先搜索（Depth First Search，DFS）、宽度优先搜索（Breadth First Search，BFS）、A*算法。前两种是经典的
盲目搜索算法，后一种是经典的启发式搜索算法。对于八数码问题，深度优先搜索一般不能保证得到最优解，A*算法又与其启发式函数息息相关，也无法保证得到最优解。而宽度优先搜索算法可以得到从初始状态到目标状态的最短解路径。虽然宽度搜索算法效率相对较低，搜索点数较多，但考虑到计算机技术的飞速发展，运算速度已经不是影响搜索效率的重要瓶颈了。因此，展开宽度优先搜索算法的研究，不但对解决八数码难题有着实际的意义，而且对解决人工智能中的其它问题，也可以起到积极的参考作用。
2 宽度优先搜索算法
2.1算法一般描述
宽度优先搜索是—种先生成的节点先扩展的搜索策略，其一般过程是：从初始状态节点开始逐层向下扩展，在第N层节点还没有全部搜索结束之前，不进人第N+1层节点的搜索。
设TreeNodes表中的节点是根据生成的先后进行排序的，先进人TreeNodes表中的节点排在前面，后进入TreeNodes表的节点排后面，则算法可以进行一般描述：
(1)把初始节点StartState放入TreeNodes表中，作为当前节点；
(2)如果TreeNodes表中当前节点指向为空，则问题无解，失败退出；
(3)把TreeNodes表的当前节点取出，并记该节点为CurrentState；
(4)检查当前节点CurrentState是否为目标节点。若是，则得到问题的解，成功退出；否则进行第（5）步；
(5)若节点CurrentState无法扩展，设定TreeNodes的下一个节点为当前节点，转第(2)步；
(6)对当前节点CurrentState进行扩展，将其子节点存放入TreeNodes表的尾部，并为每一个子节点设置指向父节点CurrentState的指针，然后设定TreeNodes的下一个节点为当前节点，转第(2)步。
2.2针对八数码问题的宽度优先搜索算法分析
对于求解八数码问题，首先要给出一个起始状态和结束状态，如图1所示。那么，宽度优先搜索算法的目标就是寻一条从起始状态到结束状态的解路径。
图1 八数码问题的起始状态和结束状态
根据算法的一般描述，首先把起始状态加入到TreeNodes表中，作为根节点0。然后，把0节点取出，和结束状态比较，如图1来看，明显不是目标节点。所以对节点0进行扩展，根据空格上下左右移动，得到四个子节点，即节点1、2、3、4，并加入到TreeNodes表的尾部。再取出节点1作为当前节点，也不是目标节点，对其进行子节点扩展，得到2个节点，即节点5、6，并加入到TreeNodes表的尾部。然后，取出节点2作为当前节点，以此类推，进行下去，整个搜索节点过程，如图2所示。
图2 八数码问题宽度优先搜索过程
图2给出了搜索到节点12时，整个TreeNodes表的节点情况。然后继续搜索节点13，根据算法过程，直到发现目标节点结束。这样的搜索过程，就是宽度优先搜索算法。最坏情况下，该算法将搜索整个状态空间，即搜索9!/2=181440个节点。但从图2可以看出，只要从根节点到目标节点构建一个路径，则该路径一定是最短的一条解路径。
3 八数码问题的VS2008实现
3.1编程环境简介
我们的软件实验开发软件选用了Visual Studio 2008，它是基于.NET框架的软件开发平台，.NET开发环境是流行的基于Windows平台的编程平台。Visual Studio 2008可以为项目指定.NET Framework 的版本：.NET Framework 2.0、3.0 或 3.5。应用程序的.NET Framework 目标是指为使该应用程序能够在计算机上运行而需要在该计算机上安装的 .NET Framework 版本。
Visual Studio 2008中的 C# 代码编辑器提供了语句结束和快速信息功能，以支持 C# 3.0 中
的下列新语言构造：
⏹隐式类型的局部变量
⏹查询表达式
⏹扩展方法
⏹对象/集合初始值设定项
⏹匿名类型
⏹Lambda 表达式
⏹分部方法
C#语言简单易学，C#3.0语言和编译器引入了多种新的语言功能，为快速开发实现八数码问题的BFS算法提供了方便。
3.2界面设计
求解八数码问题是一个智力型的游戏，基于这样的考虑，给出界面设计如图3所示。为了美观，在不影响系统运行性能的情况下，引用了第三方皮肤控件IrisSkin2.dll。从界面可以看出，除了起始状态和结束状态之外，还给出了存放中间状态的棋盘。另外一些关键的按钮，如“随机初始状态”、“随机结束状态”、“无解判断”、“宽度搜索”、“状态演示”等，其按钮作用比较明显。
图3 八数码问题的界面设计
作为游戏，在设计上，考虑了手动移动空格的操作方法。在中间状态情况下，棋盘上每个按钮可以按下操作，按下空格的上下左右按钮，如同空格的上移、下移、左移、右移。在信息记录里面显示操作步骤。游戏过程如图4所示。
图4 八数码问题的游戏操作界面
3.3算法设计
宽度优先搜索算法设计主要包括状态编码、状态比较函数、无解判定、状态树构建算法、核心搜索算法等几个部分。
由于界面设计采用了按钮的形式，在状态编码上，按照顺时针顺序，使用整型数组存储每个按钮上的数字来表示某个状态，代码如下：
int[] astate = new int[9] { 0, 1, 2, 3, 4, 5, 6, 7, 8 };
vs编程软件空格对应于按钮上无数字，在数组中值记为0。
通过状态比较才能判定是否已经达到目标状态。基于整型数组的状态编码方式，可以很方便进行状态比较，只要检查两个状态对应的数组是否相等即可。
无解判定可以避免无解的情况下盲目搜索。可以证明，八数码问题有解的充分必要条件是两个状态的逆序列奇偶性相同。为此，无解判定问题转化为计算两个状态的逆序列奇偶性问题，给出代码如下：
private bool ExistAns(int[] start, int[] end)
{
int sequence_start = 0, sequence_end = 0;
for (int i = 0; i < start.Length; i++)
{
if (start[i] != 0)
for (int j = i + 1; j < start.Length; j++)
{
if (start[j] != 0 && start[j] < start[i])
sequence_start++;
}
if (end[i] != 0)
for (int j = i + 1; j < start.Length; j++)
{
if (end[j] != 0 && end[j] < end[i])
sequence_end++;
}
}
return (sequence_start + sequence_end) % 2 == 0;
}
状态树构建问题主要是对当前节点构建其子节点的问题，分三种情况考虑：第一种情况，空格在棋盘中间；第二种情况，空格在棋盘的四个角上；第三种情况，空格在除前两种情况之外的位置。每一种情况构建子节点的数量不同。程序实现代码如下：
private long getStates(int[] astate22)
{
int i = 0, j = 0, k = 0,inter = 0;
long listOpencountx = 0;
for (i = 0; i < astate22.Length; i++)
{
if (astate22[i] == 0 && i % 2 == 0 && i != 8) //四个角的情况
{
listOpencountx = 2;
for (j = 0; j < listOpencountx; j++)
{
for (k = 0; k < astate22.Length; k++)
{
listOpenTemp[j, k] = astate22[k];
}
版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。
发表评论