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

javayestome

较高人工智能的人机博弈程序实现(多个算法结合)含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上看可能会更好看些
<div style="padding: 4px 5.4pt; width: 95%;">#include<iostream>
#include<cstdlib>
#include<ctime>
#include<cassert>
#include<vector>
#include<algorithm>

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;i<curr_board_size;++i)
...{
if(is_empty(board_))
cout<<"o";
else
cout<<((board_==my_color)?"@":"-");
++cnt;
if(cnt==N_)
...{
cnt=0;
cout<<endl;
}
}
}
boolcan_move(MOVEmove)...{returnis_empty(board_[move]);}
voidremove_killers(intdepth,intmove_cnt,MOVE*killers,intkillers_cnt)
...{
for(inti=0;i<killers_cnt;++i)
...{
MOVEm=killers;
for(intj=0;j<move_cnt;++j)
...{
if(move_table[depth][j]!=m)
continue;
for(intk=j+1;k<move_cnt;++k)
...{
move_table[depth][k-1]=move_table[depth][k];
}
break;
}
}
}
};

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

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

intmy_score=0,svr_score=0;
for(UINTi=0;i<curr_stones_cnt;++i)
...{
UINTpos=stones_;
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;i<curr_stones_cnt;++i)
...{
UINTpos=stones_;
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<span style="color: #000000;">;
http://images.csdn.net/syntaxhighlighting