较高人工智能的人机博弈程序实现(多个算法结合)含C++源码

<iframe align="center" marginwidth="0" marginheight="0" src="http://www.zealware.com/csdnblog336280.html" frameborder="0" width="336" scrolling="no" height="280"></iframe>

较高人工智能的人机博弈程序实现(多个算法结合)含C++源码

本文由恋花蝶最初发表于http://blog.csdn.net/lanphaday上，您可以转载、引用、打印和分发等，但必须保留本文完整和包含本声明，否则必究责任。

到昨天晚上，Topcoder Marathon Match 6结束了，我取得了第18名的成绩，已经是自己参加Marathon四次以来的最好名次啦，高兴ing，这次终于中国人的成绩超过日本人了。因为这次的题目比较偏：写一个人工智能程序和服务器端的程序进行博弈。人机博弈是一门比较专的学科，我们因为英文劣势，大部分中国高手都不能快速的在比赛中学习和实现一些复杂的算法，以致成绩不太如意；我挟之前对这方面的了解，做得还算行，所以把代码公开出来，可以多一点中文方面的资料和源码给大家参考，我也感到非常荣幸。
比赛的题目请看这里：http://www.topcoder.com/longcontest/?module=ViewProblemStatement&rd=10118&pm=6759主要的游戏规则也是在这里的，我就不在这里重复啦，主要讲讲我的代码用到了什么算法。麻将虽小，五脏俱全，主要应用的算法有主要变量搜索(PVS)、历史启发(HH)、杀手启发(KH)、Null Move和迭代深化(ID)，可惜后来不够时间实现置换表(TT)，不然可以多一个算法了。代码里还实现了时间控制策略，可以几乎用尽20秒的测试时间，为争取更好的着法提供了保证。还有值得一提的是棋盘表示，我使用了棋盘表、棋子位置表结合的方式来表示，后来发现加上空位表的话，可以加快不少走法生成和估值的速度。反正棋盘表示是一切的基础，一种好的表示方法可以带来很大的性能提升。对于代码，大家注意class SE里的search_move和pvs两个函数，上述的算法和策略都在那里。class MG是关于棋盘表示、走法生成和估值的，class KH和class HH分别是杀手启发和历史启发。Null Move是简单有效的算法，不过我的实现里是比较简单的那种，如果有兴趣，可以查询其它资料。

讲了这么多，应该说一下这份代码的计算能力：以6*6的棋盘为例，这份代码在VC6的release模式下编译运行可以在1秒内搜索并评估83万个叶子节点，计算层次在8-9层；如果用MiniMax算法不进行剪枝，只能搜索到3-4层（测试机器皆为超线程P4 3.0G＋1G内存）。这就是算法的力量吧。另声明一下，本代码未作优化，不代表我不懂，只是没有时间，看的朋友请海涵了。

下面是代码，在VC和G++上皆可编译、执行

因为比赛期间写的，代码比较乱，但整体的风格还是可以的，复制到IDE上看可能会更好看些

#includeiostream>
#includecstdlib>
#includectime>
#includecassert>
#includevector>
#includealgorithm>

usingnamespacestd;

typedefunsignedintUINT;
typedefUINTMOVE;

constintINFINITY=100000000;
constintMAX_DEPTH=16;

constUINTmax_board_size=256;
constUINTmax_stones_cnt=256;

constUINTempty=0;
constUINTmy_color=1;
constUINTsvr_color=2;

#ifdefWIN32
constclock_tall_time=19200;
#else
constclock_tall_time=19200000;
#endif

constUINTcheck_time_cnt=0x00001fff;

#defineis_empty(x)(x==empty)

#defineopp_color(x)(x==my_color?svr_color:my_color)

intleaf_cnt=0;

classMG
...{
private:
UINTN_;
UINTboard_[max_board_size];
UINTstones_[max_stones_cnt];
private:
voidextend(UINTpos,unsignedchar*eht,unsignedchar*est,UINT&area,UINT&round);

public:
MOVEmove_table[MAX_DEPTH][max_board_size];
UINTcurr_stones_cnt;
UINTcurr_board_size;
voidset_N(intn)...{
N_=n;
curr_board_size=n*n;
curr_stones_cnt=0;
memset(board_,0,sizeof(UINT)*max_board_size);
memset(stones_,0,sizeof(UINT)*max_stones_cnt);
}
voidmake_move(intidx,intcolor)...{
board_[idx]=color;
stones_[curr_stones_cnt++]=idx;
}
voidunmake_move(intidx)...{
board_[idx]=empty;
--curr_stones_cnt;
}
inlineboolis_game_over()...{returncurr_stones_cnt==curr_board_size;}
UINTgen_move(intdepth);
intevaluatoin(intcolor);
intevaluatoin_4_end(intcolor);
voidprint_board()
...{
intcnt=0;
for(UINTi=0;icurr_board_size;++i)
...{
if(is_empty(board_[i]))
cout"o";
else
cout((board_[i]==my_color)?"@":"-");
++cnt;
if(cnt==N_)
...{
cnt=0;
coutendl;
}
}
}
boolcan_move(MOVEmove)...{returnis_empty(board_[move]);}
voidremove_killers(intdepth,intmove_cnt,MOVE*killers,intkillers_cnt)
...{
for(inti=0;ikillers_cnt;++i)
...{
MOVEm=killers[i];
for(intj=0;jmove_cnt;++j)
...{
if(move_table[depth][j]!=m)
continue;
for(intk=j+1;kmove_cnt;++k)
...{
move_table[depth][k-1]=move_table[depth][k];
}
break;
}
}
}
};

UINTMG::gen_move(intdepth)
...{
intcnt=0;
for(UINTi=0;icurr_board_size;++i)
...{
if(is_empty(board_[i]))
move_table[depth][cnt++]=i;
}
returncnt;
}

intMG::evaluatoin(intcolor)
...{
if(curr_stones_cnt+1==curr_board_size)
...{
for(inti=0;icurr_board_size;++i)
...{
if(is_empty(board_[i]))
...{
board_[i]=color;
intvalue=-evaluatoin_4_end(opp_color(color));
board_[i]=empty;
returnvalue;
}
}
}
++leaf_cnt;
unsignedcharextended_hash_table[max_board_size]=...{0};

intmy_score=0,svr_score=0;
for(UINTi=0;icurr_stones_cnt;++i)
...{
UINTpos=stones_[i];
if(extended_hash_table[pos])
continue;
UINTarea=0,round=0;
unsignedcharextended_space_table[max_board_size]=...{0};
extend(pos,extended_hash_table,extended_space_table,area,round);
if(board_[pos]==my_color)
...{
my_score+=area*area*round;
}
else
...{
svr_score+=area*area*round;
}
}
if(color==my_color)
returnmy_score-svr_score;
returnsvr_score-my_score;
}

intMG::evaluatoin_4_end(intcolor)
...{
++leaf_cnt;
unsignedcharextended_hash_table[max_board_size]=...{0};

intmy_score=0,svr_score=0;
for(UINTi=0;icurr_stones_cnt;++i)
...{
UINTpos=stones_[i];
if(extended_hash_table[pos])
continue;
UINTarea=0,round=0;
unsignedcharextended_space_table[max_board_size]=...{0};
extend(pos,extended_hash_table,extended_space_table,area,round);
if(board_[pos]==my_color)
...{
my_score+=area*area;
}
else
...{
svr_score+=area*area;
}
}
if(color==my_color)
returnmy_score-svr_score;
returnsvr_score-my_score;
}

voidMG::extend(UINTpos,unsignedchar*eht,unsignedchar*est,UINT&area,UINT&round)
...{
constUINTround_cnt=4;
intis[round_cnt]=...{-N_,-1,1,N_};

++area;
eht[pos]=1;

for(UINTi=0;iround_cnt;++i)
...{
intnew_idx=pos+is[i];
if(new_idx0||new_idx>=curr_board_size)
continue;
if(i==1&&pos%N_==0)
continue;
if(i==2&&new_idx%N_==0)
continue;
if(is_empty(board_[new_idx])&&(!est[new_idx]))
...{
++round;
est[new_idx]=1;
continue;
}
if(eht[new_idx])
continue;
if(board_[new_idx]==board_[pos])
extend(new_idx,eht,est,area,round);
}
}

classHH
...{
private:
UINTboard_[2][max_board_size];
public:
voidreset()...{memset(board_,0,sizeof(UINT)*max_board_size);}
voidupdate_value(intdepth,intcolor,MOVEmove);
MOVEget_best(MOVE*move_list,intcolor,intcnt);
};

voidHH::update_value(intdepth,intcolor,MOVEmove)
...{
board_[color-1][move]+=(1depth);
}

MOVEHH::get_best(MOVE*move_list,intcolor,intcnt)
...{
intreal_color=color-1;
MOVE*p=move_list;
intbest=board_[real_color][*move_list];
intbest_idx=0;
for(inti=1;icnt;++i)
...{
++move_list;
if(board_[real_color][*move_list]best)
continue;
best=board_[real_color][*move_list];
best_idx=i;
}
MOVEtmp=*p;
*p=p[best_idx];
p[best_idx]=tmp;
return*p;
}

structKH_item
...{
MOVEmove;
intcnt;
};

classless_than
...{
public:
inlinebooloperator()(constKH_item&lhs,constKH_item&rhs)
...{
returnlhs.cntrhs.cnt;
}
};

constintmax_kh_item_cnt=4;

classKH
...{
private:
KH_itemKH_table[MAX_DEPTH][max_kh_item_cnt];
intcnt_table[MAX_DEPTH];
public:
voidadd_to_kh(MOVEmove,intdepth)
...{
intcnt_mini_idx=0;
intcnt_mini=KH_table[depth][0].cnt;
inti=0;
for(i=0;icnt_table[depth];++i)
...{
KH_item&tmp=KH_table[depth][i];
if(tmp.move==move)
...{
++tmp.cnt;
return;
}
if(tmp.cntcnt_mini)
...{
cnt_mini_idx=i;
cnt_mini=tmp.cnt;
}
}
if(imax_kh_item_cnt)
...{
KH_table[depth][i].move=move;
++(cnt_table[depth]);
}
else
...{
KH_item&tmp=KH_table[depth][cnt_mini_idx];
tmp.move=move;
tmp.cnt=1;
}
}
intget_killers(MOVE*killers,intdepth)
...{
sortKH_item*>(KH_table[depth],KH_table[depth]+cnt_table[depth],less_than());
inti=0;
for(i=0;icnt_table[depth];++i)
...{
killers[i]=KH_table[depth][i].move;
}
returni;
}
voidreset()
...{
memset(cnt_table,0,sizeof(int)*MAX_DEPTH);
memset(KH_table,0,sizeof(KH_item)*MAX_DEPTH*max_kh_item_cnt);
}
};

classSE
...{
private:
MGmg;
HHhh;
KHkh;
intN_;
intbest_move;
intmax_depth_;
public:
voidprint_board()
...{
mg.print_board();
}
voidset_N(intN)
...{
N_=N;
used_time=0;
best_move=0xffff;
mg.set_N(N);
}
vectorint>get_best_move()
...{
introw=best_move/N_;
intcol=best_move%N_;
vectorint>move;
move.push_back(row);
move.push_back(col);
returnmove;
}
voiddo_move(introw,intcol,intcolor)
...{
mg.make_move(row*N_+col,color);
}
voidmake_sure_best_move_first(MOVE*moves,intcnt,MOVEbest_move);
vectorint>search_move(intmax_depth);
intpvs(int,int,int,int,int);
private:
clock_tbgn_time;
clock_tused_time;
clock_tcurr_time_limit;
};

voidSE::make_sure_best_move_first(MOVE*moves,intcnt,MOVEbest_move)
...{
for(inti=0;icnt;++i)
...{
if(moves[i]==best_move)
...{
moves[i]=moves[0];
moves[0]=best_move;
}
}
}

vectorint>SE::search_move(intmax_depth)
...{
leaf_cnt=1;
bgn_time=clock();//³õʼʱ¼ä
//¼ÆËã±¾´ÎʱÏÞ
UINTleave_space_cnt=mg.curr_board_size-mg.curr_stones_cnt;
if(leave_space_cnt>=2)
leave_space_cnt/=2;
curr_time_limit=(all_time-used_time)/leave_space_cnt;
if(curr_time_limit>all_time||curr_time_limit0)
...{
curr_time_limit=1;
}

if(leave_space_cntmg.curr_board_size/3)
curr_time_limit=((double)curr_time_limit)*(1.4);
elseif(leave_space_cntmg.curr_board_size/2)
curr_time_limit=((double)curr_time_limit)*(1.3);

if(N_>12)
curr_time_limit=((double)curr_time_limit)*(0.9);

hh.reset();
kh.reset();
intmd=0;
intbackup_max_depth=max_depth;
while(mdmax_depth)
...{
++md;
max_depth_=md;
pvs(md,my_color,0,-INFINITY,INFINITY);

if(max_depth>=backup_max_depth)
...{
//»¹ÓÐʱ¼ä£¿
if(clock()-bgn_timecurr_time_limit)
...{
//²»»á¶ÑÕ»Òç³ö£¿ÔÙËã¶àÒ»²ã
if(max_depthMAX_DEPTH-1)
++max_depth;
}
}
if(clock()-bgn_time>=curr_time_limit)
...{
break;
}
}
clock_tcurr_used=clock()-bgn_time;
used_time+=curr_used;//Ôö¼ÓÓõôµÄʱ¼ä
returnget_best_move();
}

intSE::pvs(intdepth,intcolor,intnullmove,intalpha,intbeta)
...{
if(mg.is_game_over())
returnmg.evaluatoin_4_end(color);
if(depth0)
returnmg.evaluatoin(color);
if((leaf_cnt&check_time_cnt)==0)//¼ì²âÊÇ·ñ³¬Ê±
...{
if(clock()-bgn_time>=curr_time_limit)
returnmg.evaluatoin(color);
}

//NullMove
if(depthmax_depth_&&nullmove==0)
...{
intvalue=-pvs(depth-2,opp_color(color),1,-alpha-1,-alpha);
if(value>=beta)
...{
returnvalue;
}
}

//killermove
intbest;
MOVEbm=0xffff;
MOVEkillers[max_kh_item_cnt];
intkillers_cnt=kh.get_killers(killers,depth);

if(killers_cnt>0&&depth==max_depth_)
make_sure_best_move_first(killers,killers_cnt,best_move);

for(intk=0;kkillers_cnt;++k)
...{
MOVEm=killers[k];
if(!mg.can_move(m))
continue;
mg.make_move(m,color);
best=-pvs(depth-1,opp_color(color),0,-alpha-1,-alpha);
if(best>=beta)
...{
if(depth==max_depth_)
best_move=m;
kh.add_to_kh(m,depth);
hh.update_value(depth,color,m);
mg.unmake_move(m);
returnbest;
}
elseif(best>alpha)
...{
alpha=best;
bm=m;
}
mg.unmake_move(m);
if((leaf_cnt&check_time_cnt)==0)//¼ì²âÊÇ·ñ³¬Ê±
...{
if(clock()-bgn_time>=curr_time_limit)
break;
}
}

//PVS
intmove_cnt=mg.gen_move(depth);

if(depth==max_depth_)
make_sure_best_move_first(mg.move_table[depth],move_cnt,best_move);

if(killers_cnt==0||bm==0xffff)//bm==0xffff±íʾkillersÎÞЧ£¡
...{
if(depth==max_depth_)
bm=mg.move_table[depth][0];
else
bm=hh.get_best(mg.move_table[depth],color,move_cnt);
mg.make_move(bm,color);
best=-pvs(depth-1,opp_color(color),0,-beta,-alpha);
mg.unmake_move(bm);
}
else
...{
//removekillersfrommove_table
if(killers_cnt>0)
mg.remove_killers(depth,move_cnt,killers,killers_cnt);
MOVEbm_;
if(depth==max_depth_)
bm_=mg.move_table[depth][0];
else
bm_=hh.get_best(mg.move_table[depth],color,move_cnt);
mg.make_move(bm_,color);
intbest_=-pvs(depth-1,opp_color(color),0,-beta,-alpha);
if(best_>best)
...{
best=best_;
bm=bm_;
}
mg.unmake_move(bm_);
}
for(inti=1;imove_cnt;++i)
...{
if(best>=beta)
break;
if(best>alpha)
alpha=best;

if((leaf_cnt&check_time_cnt)==0)//¼ì²âÊÇ·ñ³¬Ê±
...{
if(clock()-bgn_time>=curr_time_limit)
break;
}

MOVEm=hh.get_best(mg.move_table[depth]+i,color,move_cnt-i);
mg.make_move(m,color);
intvalue=-pvs(depth-1,opp_color(color),0,-alpha-1,-alpha);
if(value>alpha&&valuebeta)
...{
best=-pvs(depth-1,opp_color(color),0,-beta,-value);
bm=m;
}
elseif(value>best)
...{
best=value;
bm=m;
}
mg.unmake_move(m);
}
if(depth==max_depth_)
best_move=bm;
if(best>=alpha)
...{
kh.add_to_kh(bm,depth);
hh.update_value(depth,color,bm);
}
returnbest;
}

classPseudoTonga
...{
public:
vectorint>move(introw,intcol);
vectorint>init(intN,introw,intcol);
private:
intN_;
SEse;
voiddo_move(introw,intcol,intcolor);
};

vectorint>PseudoTonga::init(intN,introw,intcol)
...{
N_=N;
se.set_N(N);

intr=0,c=0;

if(row>=0||col>=0)
...{
returnmove(row,col);
}

vectorint>move;
r=c=N/2;
do_move(r,c,my_color);
move.push_back(r);
move.push_back(c);
cout"player:row="move[0]", col="move[1]"; ";
returnmove;
}

vectorint>PseudoTonga::move(introw,intcol)
...{
do_move(row,col,svr_color);
cout"server:row="row", col="col"; ";
vectorint>move;
intd=3;
move=se.search_move(d);
do_move(move[0],move[1],my_color);
cout"player:row="move[0]", col="move[1]"; ";
cout"leafcountis"leaf_cntendl;
returnmove;
}

voidPseudoTonga::do_move(introw,intcol,intcolor)
...{
se.do_move(row,col,color);
}

int main()
{
PseudoTonga pt;
pt.init(6, 2, 2);
pt.move(2,4);
return 0;
}