推箱子游戏和其自动求解.doc

推箱子游戏的自动求解

简介
推箱子，又称搬运工，是一个十分流行的单人智力游戏。玩家的任务是在一个仓库中操纵一个搬运工人，将N个相同的箱子推到N个相同的目的地。推箱子游戏出现在计算机中最早起源于1994年台湾省李果兆开发的仓库世家，又名仓库番，箱子只可以推, 不可以拉, 而且一次只能推动一个。它的规则如此简单，但是魅力却是无穷的。但是人毕竟思考的深度和速度有限，我们是否可以利用计算机帮助我们求解呢？
游戏的基础部件
首先，我选择了C++来做这个程序。这一步并没有太大的难度，不少编程爱好者肯定也写过不少的小游戏。所以这里我只简要的为后面的叙述必要的铺垫。
我将推箱子游戏的数据和操作封装为一个BoxRoom类，下面是后面的自动求解算法用到的成员函数和数据结构。
①
//移动一格,如果有箱子就推
short MovePush(Direction);
//移动到一点,并返回一个移动的路径
short Goto(Position p, MovePath& path);
以上两个是用来让搬运工移动的，它们返回人走过的步数，失败则返回-1。其中Goto用到了MovePath结构。
typedef vector MovePath;
关于Goto算法，即最短路径算法可以参考《CSDN开发高手》2004年第10期的《PC游戏中的路径搜索算法讨论》。考虑到推箱子的地图规模不大所以我采用了经典的Dijkstra算法。这在数据结构的教科书中应该可以找到，故不多着笔墨。
②
为了记忆已经搜索过的状态，BoxRoom还提供了记录和保存状态的函数：
void SaveState(BoxRoomState& s)const;
void LoadState(const BoxRoomState& s);
其中的BoxRoomState结构将在后文中讨论。
③
用来检测是否已经胜利。
bool IsFinished()const{
return m_nbox == std::count(m_map.begin(),m_map.end(),EM_BOX_TARGET);
}
自动求解算法的框架
人工智能的精髓从某种意义上就是穷举，但是如何有效的穷举就是一个好的智能算法所要解决的问题。已知的事实是推箱子问题是NP-Hard的。第一个问题是，我们所要搜索的空间是相当的巨大，“傻傻”的搜索是相当费时的，我们所要做的就是动用各种手段减少不必要的搜索来节省时间。还有一个问题是这么大的搜索空间，我们如何利用有限的空间有效的保存，并且快速的判断出某个状态已经搜索过
上面多次提到了搜索空间，那么我们如何来描述推箱子问题的搜索空间呢。
上面提到BoxRoom类的SaveState和LoadState函数用到了BoxRoomState。它描述的就是问题空间中的节点。首先，它的实现要尽量节省空间，因为自动求解过程中要记录相当数量的状态。我用了boost::dynamic_bitset,因为标准库的bitset的有一个弱点就是不能动态的决定其位数，而我们又不想让BoxRoom模板化。
class BoxRoomState{
friend class BoxRoom;
boost::dynamic_bitset<> m_extracted_map;
Position m_manpos;
short m_totlestep;
//比较状态是否等价
//等价：如果状态A中能够在箱子保持不动的情况下达到状态状态B，那么A<=>B
//性质：自反性，传递性，对称性
//
//注意：其充要条件比较难表示，所以我们暂时只能用其充分条件!所以严格的说这里不符合==的定义，也就是说!operator == ()不代表!
public:
bool operator==(const BoxRoomState& oth)const{
return m_manpos == oth.m_manpos && m_extracted_map == oth.m_extracted_map;
}
inline int GetTotlestep()const{return m_totlestep;}
inline void SetTotlestep(int s){m_totlestep = s;}
};
SetTotlestep似乎有些奇怪（你甚至可以把它改为1而不考虑其合理性），提供它纯粹是为了算法的需要。注释已经说明了如何判断两个状态是否等价，特别提到了这只是充分条件而非必要条件。提供一个加强的充分条件（如果是充要条件那将更加完美）将能够进一步减小搜索的空间。
这些状态之间的转移就是边，这样就构成了一个有向图。对一般的有向图的搜索是十分麻烦的，因为这样容易造成回路。考虑这样一种情况，把一个箱子向左推一格和向右推一格再向左推推两格达到的状态明显是等价的，对后一种情况继续搜索所需要的步数明显大于前者，所以这一支可以去掉。也就是说，我们只保留状态A->状态B所需要的路径中人走过的步数最少的一个（我的算法只解决最优移动，当然也有很多人需要最优推动）。如此一来，我们就得到了更特殊的有向图——树。
对树的搜索，大家应该相当熟悉。一般可以分为深度优先搜索和广度优先搜索。由于要得到（步数）最优解，我采用的算法的基本思路属于广度优先搜索。
算法的框架：
//表示解中的一次有效移动:表示走到一个箱子旁,并推动他
struct ValidStep{
Position p;
Direction d;
ValidStep():p(-1),d(EAST){}
ValidStep(int pp, Direction dd):p(pp),d(dd){}
};
typedef vector SolveResult;

int SolveBoxRoom(BoxRoom room, SolveResult& path){
//保存根状态
SolveState startstate(room);
SolveSearchTree searchtree(startstate);
SolveState包含BoxRoomState，它在SolveSearchTree中保存，这在后面将作讨论。
//步数的限制，每次递增，这样保证得到解的是步数最优解
int limit= room.GetTotlestep();
bool no_solution;
do{
SolveState curstate = startstate;
int curdepth = -1;
//保存每一层已经搜索到的节点的index
vector indexlist(1,0);
no_solution = true;
limit++;
do{
++curdepth;
//一开始初状态还没有展开
if(curdepth != 0){
//第一次搜索到这一层，让indexlist[curdepth] = -1
if((int)indexlist.size() <= curdepth)indexlist.push_back(-1);
searchtree.getnextchild(curdepth - 1, indexlist[curdepth-1],indexlist[curdepth],curstate);
//这一层已经无法得到可用的节点了
if(indexlist[curdepth] == -1){
//已经到头了
if(curdepth <= 1)break;
//什么？什么都没做？废了这一支
if(no_solution)
searchtree.set_disabled(curdepth - 1,indexlist[curdepth - 1]);
//没有到头,向上回朔
curdepth-=2;continue;
}
}

//已经超过深度的限制,换同一深度的其他节点
if(limit < curstate.roomstate.GetTotlestep()){
no_solution = false;
--curdepth;continue;
}
room.LoadState(curstate.roomstate);

if(curstate.isfinished){
SolveResult result;
for(int i = curdepth; i > 0; i = curstate.depth){
result.push_back(curstate.laststep);
searchtree.getfather(curstate.depth,curstate.depthindex,curstate);
}
path.insert(path.end(),result.rbegin(),result.rend());
return room.GetTotlestep();
}
//展开一个节点，如果还没有展开过
if( searchtree.have_not_been_expanded(curdepth,indexlist[curdepth])){
//展开这个节点
BoxRoom::BoxRoomState tmpstate;
room.SaveState(tmpstate);
for(Position i = 0; i < room.GetSize(); ++i){
if(room.IsNotBox(i))continue;
//表示四个方向
for(int j = 0; j < 4; ++j){
Position nman = i - room.GetOffset(static_cast(j));
if(room.Goto(nman) != -1){
//注意IsBoxRoomDead，事实证明这个函数的好坏能够大大的影响我们的搜索范围从而影响我们求解的速度。
if((room.MovePushstatic_cast(j)) != -1)
&& IsBoxRoomDead(room)){
SolveState ss(room);
ss.laststep = ValidStep(nman,static_cast(j));
searchtree.insert(curdepth,indexlist[curdepth],ss);
}
room.LoadState(tmpstate);
}
}
}
searchtree.set_expanded(curdepth,indexlist[curdepth]);
no_solution false;
}
}while(true);
}while(!no_solution);
//求解失败
return -1;
}
状态树和Hash表
注意到上面的代码中：
SolveState startstate(room);
SolveSearchTree searchtree(startstate);
我用了SolveState ，SolveSearchTree两个类来保存和组织状态。
上面提到，我们的算法要判断那些状态已经出现过，那么如何高效的搜索就是一个问题了。状态直接在树中保存的话，那么搜索起来将耗费大量的时间。我们先看一下SolveState的定义：
struct SolveState{
BoxRoom::BoxRoomState roomstate;
int hash;
int depth;
int depthindex;
bool isfinished;
ValidStep laststep;
SolveState(const BoxRoom& room);
bool operator == (const SolveState& oth)const{
return hash == oth.hash && roomstate == oth.roomstate;
}
inline int GetTotlestep()const{ return roomstate.GetTotlestep(); }
inline void SetTotlestep(int s){ roomstate.SetTotlestep(s); }
};
它只是BoxRoom::BoxRoomState类型的一个包装。roomstate保存了状态值；为了从节点映射回树，depth、depthindex保存了状态在树中的必要信息；isfinished为了避免多次调用BoxRoom::IsFinished()；laststep表示从父状态到该状态，搬运工应该如何移动。还有一个成员hash，一看名字就知道，它和hash表有关，是的，它是这个状态的hash值，也就是说我们将节点的存储和节电间的关系的表示分开来实现了。来看SolveSearchTree你就会明白了：
class SolveSearchTree{
class StateLib{
typedef vector HashNode;
vector m_hash_table;
public:
StateLib(int rank):m_hash_table(HASH_SIZE(rank)){}
int Add_state(const SolveState& ns)；
SolveState& Get_state(int stateindex)；
}statelib;

struct Node{
int stateindex;//状态在StateLib中的索引值
vector children; //所有孩子在下一层数据中的index的节点表
int fatherindex;
bool is_expanded;
bool is_disabled;
Node():is_expanded(false),is_disabled(false){}
};

//类似于广义表的方式作为树的表示方式。data[n]代表树的第n层，data[n][m]代表第n层的第m个成员
vector > data;
SolveState dummystate;

public:
SolveSearchTree(SolveState& r);
void insert(int fatherdepth ,int fatherindex, SolveState);
void getnextchild(int fatherdepth, int fatherindex, int& lastchildindex, SolveState&);
void getfather(int childepth, int childindex, SolveState&);
bool have_not_been_expanded(int depth,int index)const{return !(data[depth][index].is_expanded);}
void set_expanded(int depth,int index){data[depth][index].is_expanded = true;}
bool have_not_been_disabled(int depth,int index)const{return !(data[depth][index].is_disabled);}
void set_disabled(int depth,int index);
};
如图所示：
通过用stateindex调用Get_state我们可以得到唯一个SolveState，通过Add_state加入新的状态，这时hash表的威力就显示出来了:
#define HASH_RANK 16
#define HASH_SIZE(rank) (1 << rank)
//对一个值求模使它小于HASH_SIZE
#define HASH_MOD(hash) (hash & ( (1 << HASH_RANK) - 1))
……
int Add_state(const SolveState& ns){
HashNode& data = m_hash_table[ns.hash];
HashNode::iterator iter = find(data.begin(),data.end(),ns);
long h1;
if( iter == data.end() ){
data.push_back(ns);
h1 = (long)data.size() - 1;
return (h1<< HASH_RANK)+ns.hash;
}else{
if(ns.GetTotlestep() < (*iter).GetTotlestep()){
h1 = (long)(iter - data.begin());
(*iter).SetTotlestep(ns.GetTotlestep());
(*iter).laststep = ns.laststep;
return -((h1<< HASH_RANK)+ns.hash)
}
//Magic Number,表示无法加入这个新状态,因为已经存在步数更优的等价状态
//因为hash!=0,所以说下面的(h1<< HASH_RANK)+ns.GetHash()肯定不会等于0
return 0;
}
}
SolveState& Get_state(int stateindex){
HashNode& data = m_hash_table[HASH_MOD(stateindex)];
return data[stateindex >> HASH_RANK];
}
stateindex用位操作来提高速度，它的思想不难理解。通过hash表我们可以大大减少搜索状态的时间，那么hash值又是什么呢？我选择了一个相当简单的方法：

SolveState::SolveState(const BoxRoom& room):hash(0){
room.SaveState(roomstate);
isfinished = room.IsFinished();
//求hash值
for(int i = 0;i < room.GetSize(); ++i){
if(room.IsBox(i)){
hash += i*(i+1)*(i+2);
hash = HASH_MOD(hash);
}
}
}
呵呵，简单吧，肯定有更好的hash值，但这里我偷个懒罢了。
树的insert操作要负责对等价节点的处理，保证等价节点只保留一个布数最优的：
void SolveSearchTree::insert(int fatherdepth ,int fatherindex,SolveState& ss){
int newchildstateindex = statelib.Add_state(ss);
//这个状态已经存在，而且以前的步数更优
if(newchildstateindex == 0)return;
//这个状态不是新状态，但它比以前的步数更优
if(newchildstateindex < 0){
newchildstateindex = -newchildstateindex;
SolveState& ts = statelib.Get_state(newchildstateindex);
set_disabled(ts.depth,ts.depthindex);
}
if((int)data.size() <= fatherdepth + 1)data.push_back(vector());
Node childnode;
childnode.stateindex = newchildstateindex;
childnode.fatherindex = fatherindex;
data[fatherdepth+1].push_back(childnode);
int newchilddepthindex = (int)data[fatherdepth+1].size() - 1;

SolveState& ts = statelib.Get_state(newchildstateindex);
ts.depth = fatherdepth + 1;
ts.depthindex = newchilddepthindex;
data[fatherdepth][fatherindex].children.push_back(newchilddepthindex);
}
树的getnextchild操作要跳过已经废除的枝：
void SolveSearchTree::getnextchild(int fatherdepth, int fatherindex, int& lastchildindex, SolveState& rt){
vector& childindex = data[fatherdepth][fatherindex].children;
vector::iterator iter;
if(lastchildindex == -1){
iter = childindexbegin();
}else{
iter = find(childindex.begin(),childindex.end(),lastchildindex) + 1;
}
do{
if(iter == childindex.end()){
lastchildindex = -1;
rt = dummystate;return;
}else{
lastchildindex = *iter;
if(data[fatherdepth+1][lastchildindex].is_disabled){
++iter;
continue;
}
rt = statelib.Get_state(data[fatherdepth+1][lastchildindex].stateindex);return;
}
}while(true);
}

死锁检测
万事俱备，只欠东风。我们还差一个IsBoxRoomDead函数。死锁就是一旦把箱子推动到某些位置，一些箱子就再也无法推动或者无法推到目的点，比如四个箱子成2×2摆放。推箱子高手对何种情况引起死锁非常敏感，这样他们预先就知道决不能让某些局面形成，这也是高手高于常人的原因之一。
当然我不是推箱子的高手，所以我只给出了两个简单的判断规则：
规则一：
#B # # B# ## #B B# BB BB BB
# B# #B # BB #B B# ## BB BB
其中B表示箱子，#表示墙。如果出现了上面的任何一种情况，那么将一定死锁
规则二：
边缘上的箱子的个数大于边缘上的目标的数量。比如如下的情况：
#############
# T T B B B
T表示目标。

可能要令你失望的是，我的程序只解决了这两种显而易见的死锁情形的判断，V_V!。网上葛永高人（）有一个推箱子自动求解的程序，它的程序有相当先进的死锁检测算法，但可惜的是没有给出源代码。所以这一部分只能我也就不能再详细展开了。
结语
这个程序目前还不是很完备，我的实验证明，它的复杂度和箱子的个数有很大的关系，当箱子很多的时候还不能很好的解出。这篇文章的目的只是给出一个算法的框架，使它能够解决一些问题了，全当抛砖引玉。如果你有什么兴趣的话，欢迎与我交流：
关于作者：本文作者hellwolf，是东南大学大一计算机系的新生。主要对Linux编程和操作系统开发感兴趣（但是暂时水平不够），偶尔写些小游戏自娱。
EMAIL:hellwolf_ok@ hellwolf_ok@
MSN:hellwolf_ok@
QQ:406418169
blog:
联系地址：东南大学浦口校区090043信箱
邮编：210088