VC中利用人工智能解决八迷宫问题
前言随着计算机技术的发展，人工智能（Artificial intelligence，下文简称"AI"）已经成为世界各国一个热门的研究方向。对于这一领域的内容，国内起步较晚，目前虽然网络上各种编程文章很多，但是关于如何编程解决人工智能问题的文章和资料少之又少。
近日，笔者有幸在国外网站上发现了这一篇出色文章，该文通过VC实例来说明如何解决及实现人工智能问题，例子程序虽然相对来说比较简单，但有一定的代表性，对有爱好研究这一领域的朋友们有借鉴意义。
一、"八迷宫"游戏简介
在大学进行AI模块开发的时候，我就开始着手写这篇文章，目的是介绍我所了解到的一些让人感爱好的问题。对于什么是人工智能，我想没有任何人愿意花费大量时间进行争论。
当你读到这里的时候，推荐你下源代码，因为粘贴和拷贝的代码与源代码的作用相比是远远不及的。在本文中，我将使用一个单人游戏"八迷宫"作为一个例子，这个游戏的规则如下：
有一个3X3的网格，包含1到8这几个数（因此，有一个格子是空的），最初这8个数的排列是随机的，例如，下面的排列是一种可能情况：
6 1 7 3 4 5 8 2
游戏玩家可以向东、南、西、北等方向移动这个空格，移动空格时，空格所占位置的数字将填补到原来空格的位置。例如，对于上图来说，假如向北移动空格，游戏的状态将如下图所示：
6 1 3 4 7 5 8 2
当游戏状态实现如下所示的状态时，游戏结束。
1 2 3 8 4 7 6 5
二、解决"八迷宫"问题的方法
解决上述问题的方法主要有以下几种：
1、Breadth First Search（按照"横向"原则搜索）.
2、Depth First Search（按照"深度"原则搜索）.
3、Heuristic Search（启发式搜索）.
4、A* search.
实现这些方法的代码非常相似，但是它们工作的方式是截然不同的。所有的上述方法都要使用一个链表，而且最初的链表都只有一个成员，它对应着游戏网格的最初状态。这个成员向它所有可能的子状态进行膨胀（每种移动所产生的结果都被考虑了进去），然后所有这些子状态都被添加到链表中。这种处理将在一个循环中进行持续处理，直到实现目标状态，也就是说直到游戏结束为止。
实现"八迷宫"单人游戏的伪代码如下：
Do
Current_Item = Remove_Item_From_List
Child_State_Array = EXPand (Current_State)
Add_to_List(Child_State_Array)
If child_State_Array Holds the solution then IsGameOver = true
Loop while (IsGameOver = false)
这个结构的代码可以在上述所有的人工智能方法中看到，各种方法的区别仅仅在于它们是如何在链表中进行排序。
1、在 breadth first search方法中，各个成员都是按照某一固定的方向被添加到链表中，删除时按相反方向进行。
2、在 depth first search方法中，各个成员的添加和删除都是在链表的同一个方向进行。
3、在heuristic search方法中，各个成员可以在链表的任意方向进行添加，然而，在从链表中删除一个成员时，每一个成员被"heuristic"函数进行打分（对于状态来说，分数越高越接近于最终状态），得分最高的项目将被从链表中删除。
4、A*方法使用两个heuristic函数，并将最终的两个得分加在一起。使用两个heuristics函数极大地提高了程序发现下步最佳状态的能力，但是却降低了程序的运行速度。
其实，三、四方法是第二种方法的延伸和变种，区别仅在于启发式搜索的方式不同罢了，这一点读者朋友们可以在后面的代码中细细体味。实际上"八迷宫"这种游戏的heuristic函数的可以是这么一个函数，它计算拥有正确位置的网格个数，或是100-状态深度。
使用启发式的搜索有利有弊，在这个例子中，使用启发式可能使程序的主循环降低10倍速度，然而，它降低了循环的次数，可能从6百万次降低到了4000次，这节省了内存的负荷，以及例子程序的运行时间。（这提醒了我，我使用的最初的状态使用了25步解决了问题），这看起来不是很多，但假如没有启发式搜索，搜索将1秒钟处理300兆的内存，除非你使用功能强大的处理机器，（我使用的是1.3G，256兆的机器），否则你可能需要减少结束游戏所需要的移动次数，要低于10。
三、程序代码
首先，要声明的是，游戏网格在程序中对应着一个拥有10个成员变量的数组，网格每个位置按照从左到右、从上到下的位置排序。对于网格状态，可实现一个状态类，它对应着网格的各种状态，并拥有所有操作网格时所需要的代码和变量，这个类命名为CState，代码如下：
/* 声明网格中空格所有可能移动的方向，至于为什么要包括"NONE"将在后面的代码中显现出来；*/
enum DIRECTION { NONE, NORTH, EAST, SOUTH, WEST };
// 声明CState类
class CState {
private:
// 使用1 to 9号索引来对应网格的每个位置, 定义为 char类型是为了节省内存；
char Grid[10];
char Depth; //Depth变量对游戏的最初原始状态演变到当前状态所经历的步数；
//我们需要记录下父状态是如何进行移动而得到当前状态的；
DIRECTION OperatorApplyed;
// 父状态指针，当程序结束时，我们可以利用它跟踪所经历的状态，从而给出答案；
CState *PrevState;
// 寻找当前网格中的空格位置或某一个具体数字的位置，默认状态是寻找空格位置；
inline int FindBlank(char Search=0) {
int Blank=1;
while (Grid[Blank] != Search) {
Blank++;
}
return Blank;
}
// 按照规定的方向移动空格；
void MoveBlank(DIRECTION Direction) {
int Blank = FindBlank();
// 我们需要记住本次操作所移动的方向；
OperatorApplyed = Direction;
switch (Direction) {
case NORTH:
Grid[Blank] = Grid[Blank - 3];
Grid[Blank - 3] = 0;
break;
case EAST:
Grid[Blank] = Grid[Blank + 1];
Grid[Blank + 1] = 0;
break;
case SOUTH:
Grid[Blank] = Grid[Blank + 3];
Grid[Blank + 3] = 0;
break;
case WEST:
Grid[Blank] = Grid[Blank - 1];
Grid[Blank - 1] = 0;
break;
}
}
/* 下面的函数将被用于第一种方法的heuristics函数的一部分，它得到两个索引位置的直角距离，它还用于确定一个数字当前位置与其应该所在位置的直角距离；
int GetDistanceBetween(int Tile1, int Tile2) {
int X1, X2;
int Y1, Y2;
int temp=0;
// 将grid位置转换为X,Y坐标；
Y1 = 1;
Y2 = 2;
X1 = Tile1;
X2 = Tile2;
if(Tile1 > 3) { Y1 = 2; X1 = Tile1 - 3; }
if(Tile1 > 6) { Y1 = 3; X1 = Tile1 - 6; }
if(Tile2 > 3) { Y2 = 2; X2 = Tile2 - 3; }
if(Tile2 > 6) { Y2 = 3; X2 = Tile2 - 6; }
//为了确保距离值为正说，进行必要的换位处理；
if(Y1 - Y2 < 0) {
temp = Y1;
Y1 = Y2;
Y2 = temp;
}
if(X1 - X2 < 0) {
temp = X1;
X1 = X2;
X2 = temp;
}
return ((Y1 - Y2) + (X1 - X2));
}
public:
// 异常处理；
class ERROR_ILLEGAL_MOVE{};
class ERROR_NO_MORE_DIRECTIONS{};
class ERROR_OUT_OF_BOUNDS{};
//用于heuristic函数；它代表了当前状态与前一状态的距离；这个数值越小越好。
int GetDepth() {
return Depth;
}
// CState类构造函数；
CState() {
Depth = 0;
Grid[1] = 6; // for slower machines use 4
Grid[2] = 1; // for slower machines use 1
Grid[3] = 7; // for slower machines use 3
Grid[4] = 3; // for slower machines use 2
Grid[5] = 0; // for slower machines use 0
Grid[6] = 4; // for slower machines use 5
Grid[7] = 5; // for slower machines use 8
Grid[8] = 8; // for slower machines use 7
Grid[9] = 2; // for slower machines use 6
PrevState = 0;
/*由于还没有以前移动的操作，所以这就是为什么我们需要声明NONE 变量的原因。*/
OperatorApplyed = NONE;
}
void SetPrevState(CState *Set) {
PrevState = Set;
}
CState* GetPrevState() {
return PrevState;
}
// 用于确定移动操作是否合法
bool CanBlankMove(DIRECTION Direction) {
int Blank = FindBlank();
switch (Direction) {
case NORTH:
if (Blank > 3) {
return true;
}
else {
return false;
}
break;
case EAST:
if (Blank != 3 && Blank != 6 && Blank != 9) {
return true;
}
else {
return false;
}
break;
case SOUTH:
if (Blank < 7) {
return true;
}
else {
return false;
}
break;
case WEST:
if (Blank != 1 && Blank != 4 && Blank != 7) {
return true;
}
else {
return false;
}
break;
default:
return false;
break;
}
}
void setgrid(int index, int value) {
Grid[index] = value;
}
/*该函数假如返回"true", 当前状态将是最终状态，以前的状态指针可以用往返退，从而得到解决问题的答案。*/
bool Solution() {
if (Grid[1] == 1 && Grid[2] == 2 && Grid[3] == 3 && Grid[4] == 8 && Grid[5]
== 0 && Grid[6] == 4 && Grid[7] == 7 && Grid[8] == 6 && Grid[9] == 5)
{
return true;
}
else {
return false;
}
}
char GetGridValue(int Index) {
if (Index < 1 Index > 9) {
throw ERROR_OUT_OF_BOUNDS();
}
else {
return Grid[Index];
}
}
// 含一个参数的构造函数；
CState(CState* Init) {
Depth = (Init->GetDepth());
OperatorApplyed = Init->GetLastOperator();
PrevState = Init->GetPrevState();
for (int n=1; n<=9; n++) {
Grid[n] = Init->GetGridValue(n);
}
}
DIRECTION GetLastOperator() {
return OperatorApplyed;
}
// 两个参数的构造 函数；
CState(CState* Init, DIRECTION Direction) {
int n;
PrevState = Init;
Depth = (Init->GetDepth() + 1);
for (n=1; n<=9; n++) {
Grid[n] = Init->GetGridValue(n);
}
MoveBlank(Direction);
}
// 另外一个heuristic函数，它计算错误网格的数量；
int GetWrongTiles() {
return ((Grid[1] != 1) +
(Grid[2] != 2) +
(Grid[3] != 3) +
(Grid[4] != 3) +
(Grid[5] != 3) +
(Grid[6] != 3) +
(Grid[7] != 3) +
(Grid[8] != 3) +
(Grid[9] != 3) +
(Depth )); // 也用于第二种heuristic (A*)的depth
}
/* ManhattanDistance是一个技术术语，它代表了所有当前位置数字与其应该处于的位置的直角距离之和*/
int GetManhattanDistance() {
int Result=0;
Result = GetDistanceBetween(1, FindBlank(1));
Result = Result + GetDistanceBetween(2, FindBlank(2));
Result = Result + GetDistanceBetween(3, FindBlank(3));
Result = Result + GetDistanceBetween(4, FindBlank(8));
Result = Result + GetDistanceBetween(5, FindBlank(0));
Result = Result + GetDistanceBetween(6, FindBlank(4));
Result = Result + GetDistanceBetween(7, FindBlank(7));
Result = Result + GetDistanceBetween(8, FindBlank(6));
Result = Result + GetDistanceBetween(9, FindBlank(5));
Result = Result + Depth;// 也用于第二种heuristic (A*)的depth；
return Result;
}
};
正如你所看到的，这是一个很"巨大"的类，但是，它一点都不复杂，仅仅是一些简单的数据操作。比较难的部分是跟踪各种状态，并按照正确的顺序操作它们，这将是我们下面要做的。
这部分与人工智能关系不大，但是人工智能程序不能没有它。假如你不了解为什么我们使用链表而不用数组，那末这里告诉你原因，数组在设计时有固定的尺寸，在运行时不能改变，所以假如程序一开始，你就拥有一个含有6 百万个Cstates类对象的数组的话，而且这时你还不需要它，那将浪费大量的内存。
链表仅在需要时才为新的对象申请空间，至于它是如何工作的就不具体介绍了，到处都有此类的例子，你只要知道它确实在工作，它是一个可变尺寸的数组。链表实际上并不保存状态，而保存指向各个状态的指针，这是因为，链表将是一个等待膨胀的状态队列，当一个状态膨胀时，它将从链表中删除，然而，我们需要在内存中保存这个状态，用于可能发生的回退或是用于报告从最初状态到解决问题时的解决路径。
当我们实际编写主循环代码时，我们将把膨胀状态放入到第二个队列中，这样我们才能跟踪它们在那里，什么时候从内存中删除状态（防止内存泄露） 。
好了，从现在起回到C++代码，生成一个新的头文件"Llist.h"，输入如下代码：
//列举链表的两个末端；
enum SIDE { LEFT, RIGHT };
// 链表由下面的Link结构对象组成；
strUCt Link {
Link *LeftLink; // 指向链表中左端LINK对象的指针；
Link *RightLink; //指向链表中右端LINK对象的指针；
CState *Data; // 指向状态数据的指针；
};
// 链表类；
class CLList {
private:
Link* LeFTPointer; // 指向一个永远是空的，并且是末端的link对象；
Link* RightPointer; //与上面的指针一样，但方向相反；
double ListLen; // 链表的长度；
// 清空内存；
void EmptyUsedMemory() {
CState *temp;
while(!IsListEmpty()) {
temp = Pop(LEFT);
delete temp;
}
}
public:
class ERROR_CANT_POP_EMPTY_LIST{}; // Error Exception
CLList() {
// initialise all private variables
LeftPointer = new Link;
RightPointer = new Link;
ListLen = 0;
LeftPointer->LeftLink = 0;
LeftPointer->RightLink = RightPointer;
RightPointer->RightLink = 0;
RightPointer->LeftLink = LeftPointer;
}
~CLList() {
EmptyUsedMemory();
}
inline double GetListLen() {
return ListLen;
}
inline bool IsListEmpty() {
return (LeftPointer->RightLink == RightPointer);
}
//从链表中弹出数据；
CState* Pop(SIDE Side) {
Link ForReturn;
Link* ForDelete;
if (!IsListEmpty()) {
ListLen--;
if (Side == LEFT) {
ForReturn = *(LeftPointer->RightLink);
ForDelete = LeftPointer->RightLink;
LeftPointer->RightLink = ForReturn.RightLink;
ForReturn.RightLink->LeftLink = LeftPointer;
}
else {
ForReturn = *(RightPointer->LeftLink);
ForDelete = RightPointer->LeftLink;
RightPointer->LeftLink = ForReturn.LeftLink;
ForReturn.LeftLink->RightLink = RightPointer;
}
delete ForDelete;
return ForReturn.Data;
}
return 0;
}
//向链表中压入数据
void Push(SIDE Side, CState* What) {
Link* NewLink = new Link;
NewLink->Data = What;
ListLen++;
if (Side == LEFT) {
NewLink->RightLink = LeftPointer->RightLink;
NewLink->LeftLink = LeftPointer;
LeftPointer->RightLink = NewLink;
NewLink->RightLink->LeftLink = NewLink;
}
else {
NewLink->RightLink = RightPointer;
NewLink->LeftLink = RightPointer->LeftLink;
RightPointer->LeftLink = NewLink;
NewLink->LeftLink->RightLink = NewLink;
}
}
//启发式搜索过程中，从链表中搜寻最佳状态；
CState* PopBestByHeuristics(HEURISTIC heuristic) {
int BestValue=9999;
int Temp=0;
Link* BestState = 0;
Link* Current = LeftPointer;
CState* ForReturn = 0;
if(!IsListEmpty()) {
//启发式搜索可以使用MANHATTAN_DISTANCE或WrongTile方式来搜寻最佳状态
while(Current->RightLink != RightPointer) {
Current = Current->RightLink;
if(heuristic == MANHATTAN_DISTANCE) {
Temp = Current->Data->GetManhattanDistance();
}
else {
Temp = Current->Data->GetWrongTiles();
}
if(Temp < BestValue) {
BestValue = Temp;
BestState = Current;
}
}
//从链表中删除最佳状态；
BestState->RightLink->LeftLink = BestState->LeftLink;
BestState->LeftLink->RightLink = BestState->RightLink;
ForReturn = BestState->Data;
delete BestState;
return ForReturn;
}
return 0;
}
CState* PeekByBestHueristics(HEURISTIC heuristic) {
int BestValue=9999;
int Temp=0;
Link* BestState = 0;
Link* Current = LeftPointer;
CState* ForReturn = 0;
if(!IsListEmpty()) {
// Find BEST State By Wrong tile number heuristic
while(Current->RightLink != RightPointer) {
Current = Current->RightLink;
if(heuristic == MANHATTAN_DISTANCE) {
Temp = Current->Data->GetManhattanDistance();
}
else {
Temp = Current->Data->GetWrongTiles();
}
if(Temp < BestValue) {
BestValue = Temp;
BestState = Current;
}
}
ForReturn = BestState->Data;
return ForReturn;
}
return 0;
}
接下来，创建另外一个头文件"Eightpuzz.h"，这里，除了main()，我将放入所有的东西，这些代码阅读起来有一定的难度，所以你要坚持住：
void gotoxy(int x, int y); //函数原型，使用光标的xy坐标；
// 枚举搜索的类型；
enum TYPE {BREADTH_FIRST, DEPTH_FIRST };
// 类举可能的A* 启发式方法，第二种启发式使用深度；
enum HEURISTIC {NOT_USED, MANHATTAN_DISTANCE, WRONG_TILES};
// include the header files we are going to need
#include<iostream.h> // for console i/o
#include<windows.h> // for sleep() and gotoxy()
#include"State.h" // for game state class
#include"Llist.h" // for a linked list class
CLList PrevStates; /* 用于跟踪以前的状态，程序结束时要及时删除，以免内存泄露*/
CLList MainQue; // 等待主队列；
SIDE PushSide;
SIDE PopSide;
// 膨胀函数；
CState* GeneralExpand(int DepthLimit, HEURISTIC heuristic);
// 膨胀的步数；
double Expanded = 0;
// 当发现解决方法后，该函数将结果显示在屏幕上；
void ShowSolution(CState* Solution) {
// 结果是回退得到的，所以实际结果应该是与之反向的，这时候可以使用后入先出的方法；
CLList Reverse;
bool EndLoop=false;
while(!EndLoop) {
Reverse.Push(LEFT, Solution);
if(Solution->GetPrevState() != 0) {
Solution = Solution->GetPrevState();
}
else {
EndLoop = true;
}
}
int NewLine = 0;
CState *Temp;
cout << "\n";
while(!Reverse.IsListEmpty()) {
Temp = Reverse.Pop(LEFT);
NewLine++;
if(NewLine > 10) { cout << "\n"; NewLine=0;}
switch(Temp->GetLastOperator()) {
case NORTH:
cout << "North, ";
break;
case EAST:
cout << "East, ";
break;
case SOUTH:
cout << "South, ";
break;
case WEST:
cout << "West, ";
break;
}
}
cout << "\n\n" << "Expanded: " << Expanded << endl;
}
}
// 设置控制台i/o x,y坐标
void gotoxy(int x, int y) {
// SET CONSOLE CURSOR POSITION.
COORD coord = {x,y};
HANDLE handle = GetStdHandle(STD_OUTPUT_HANDLE);
SetConsoleCursorPosition(handle,coord);
}
// 为主循环做预备；
void GeneralSearch(TYPE Type, HEURISTIC heuristic) {
CState *Solution;
int DepthLimit=0;
switch(heuristic) {
case NOT_USED:
// Breadth First Queing Type
if(Type == BREADTH_FIRST) {
PushSide = RIGHT;
PopSide = LEFT;
}
else {
// Depth First Search
cout << "Enter a Depth Limit :";
cin >> DepthLimit;
PushSide = RIGHT;
PopSide = RIGHT;
}
break;
case MANHATTAN_DISTANCE:
PushSide = RIGHT;
PopSide = RIGHT;
break;
case WRONG_TILES:
PushSide = RIGHT;
PopSide = RIGHT;
}
//将最初的状态放入链表中；
MainQue.Push(PushSide, new CState());
//调用主循环
Solution = GeneralExpand(DepthLimit, heuristic);
// returns pointer to soution.
// or null pointer (failure)
if(Solution != 0) {
cout << "FOUND SOLUTION!" << endl;
ShowSolution(Solution);
cout << "DONE" << endl;
}
else {
//Fail
cout << "FAIL" << endl;
}
}
// 主循环函数(YEP, it BITES !)
CState* GeneralExpand(int DepthLimit, HEURISTIC heuristic) {
CState *CurrentState = 0;
CState *TempState = 0;
int LastDepth=-1;
if(PushSide == PopSide) {cout << "THINKING...please wait." << endl;}
// Main loop
while(!MainQue.IsListEmpty()) {
if(heuristic == NOT_USED) {
CurrentState = MainQue.Pop(PopSide);
}
else {
CurrentState = MainQue.PopBestByHeuristics(heuristic);
}
PrevStates.Push(RIGHT, CurrentState);
//对取出的状态保持跟踪(需要防止内存)
/*可以让用户规定结束游戏所需要移动的最大步数，这仅限于"breadth first only"方法*/
if(LastDepth < CurrentState->GetDepth() && PushSide != PopSide) {
LastDepth = CurrentState->GetDepth();
cout << "EXPANDING LEVEL " << LastDepth << endl;
}
// 假如当前节点没有超出depth限制
if((CurrentState->GetDepth() < DepthLimit) (DepthLimit == 0 )) {
if((CurrentState->CanBlankMove(NORTH)) && (CurrentState->GetLastOperator() != SOUTH)) {
TempState = new CState(CurrentState, NORTH);
MainQue.Push(PushSide, TempState);
Expanded++;
if(TempState->Solution()) {
return TempState;
}
}
if((CurrentState->CanBlankMove(EAST)) && (CurrentState->GetLastOperator() != WEST)) {
TempState = new CState(CurrentState, EAST);
MainQue.Push(PushSide, TempState);
Expanded++;
if(TempState->Solution()) {
return TempState;
}
}
if((CurrentState->CanBlankMove(SOUTH)) && (CurrentState->GetLastOperator() != NORTH)) {
TempState = new CState(CurrentState, SOUTH);
MainQue.Push(PushSide, TempState);
Expanded++;
if(TempState->Solution()) {
return TempState;
}
}
if((CurrentState->CanBlankMove(WEST)) && (CurrentState->GetLastOperator() != EAST)) {
TempState = new CState(CurrentState, WEST);
MainQue.Push(PushSide, TempState);
Expanded++;
if(TempState->Solution()) {
return TempState;
}
}
}
}
return 0;
}
下面是主文件"EightPuzz.cpp" 的代码：
#include"Eightpuzz.h"
int main() {
char Choice=0;
cout << "Choose Search Method...\n"
<< " [1] Blind Breadth First Search\n"
<< " [2] Blind Depth First Search\n"
<< " [3] A*(Tiles in the wrong position)\n"
<< " [4] A*(Manhattan Distance)\n" << endl;
cin >> Choice;
switch(Choice) {
case ’1’:
// call Blind Breadth First Search
GeneralSearch(BREADTH_FIRST, NOT_USED);
break;
case ’2’:
// call Blind Depth First Search
GeneralSearch(DEPTH_FIRST, NOT_USED);
break;
case ’3’:
// call A* with wrong tiles heuristic
GeneralSearch(DEPTH_FIRST, WRONG_TILES);
break;
case ’4’:
// call A* with manhatten heuristic
GeneralSearch(DEPTH_FIRST, MANHATTAN_DISTANCE);
break;
}
return 0;
}
正如我前面所说的，还是推荐你看完本文中的代码，下载程序的源代码，并用VC打开，仔细看一看整个程序的结构及流程。通过这个例子程序，你应该明白，编写一个AI程序，所需要做的是：
1、 一个存储状态的方法；
2、 一个膨胀状态的方法；
3、 一个回退到原始状态的方法；
4、 一个排序状态的方法；
5、 一个给状态评分的函数；
6、 一个主循环，将一个状态从链表中移出，并将其所有的子状态添加到链表中；
上面的每个步骤都很简单，但将它们组合在一起，并使它易读易懂却不那么轻易了。
