较高人工智能的人机博弈程序实现(多个算法结合)含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上看可能会更好看些
#include <
iostream
>
#include
<
cstdlib
>
#include
<
ctime
>
#include
<
cassert
>
#include
<
vector
>
#include
<
algorithm
>
using
namespace
std;
typedef unsigned
int
UINT;
typedef UINT MOVE;
const
int
INFINITY
=
100000000
;
const
int
MAX_DEPTH
=
16
;
const
UINT max_board_size
=
256
;
const
UINT max_stones_cnt
=
256
;
const
UINT empty
=
0
;
const
UINT my_color
=
1
;
const
UINT svr_color
=
2
;
#ifdef WIN32
const
clock_t all_time
=
19200
;
#else
const
clock_t all_time
=
19200000
;
#endif
const
UINT check_time_cnt
=
0x00001fff
;
#define
is_empty(x) (x==empty)
#define
opp_color(x) (x==my_color?svr_color:my_color)
int
leaf_cnt
=
0
;
class
MG
...
{
private
:
UINT N_;
UINT board_[max_board_size];
UINT stones_[max_stones_cnt];
private
:
void
extend(UINT pos, unsigned
char
*
eht, unsigned
char
*
est, UINT
&
area, UINT
&
round);
public
:
MOVE move_table[MAX_DEPTH][max_board_size];
UINT curr_stones_cnt;
UINT curr_board_size;
void
set_N(
int
n)
...
{
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);
}
void
make_move(
int
idx,
int
color)
...
{
board_[idx]
=
color;
stones_[curr_stones_cnt
++
]
=
idx;
}
void
unmake_move(
int
idx)
...
{
board_[idx]
=
empty;
--
curr_stones_cnt;
}
inline
bool
is_game_over()
...
{
return
curr_stones_cnt
==
curr_board_size;}
UINT gen_move(
int
depth);
int
evaluatoin(
int
color);
int
evaluatoin_4_end(
int
color);
void
print_board()
...
{
int
cnt
=
0
;
for
(UINT i
=
0
; i
<
curr_board_size;
++
i)
...
{
if
(is_empty(board_[i]))
cout
<<
"
o
"
;
else
cout
<<
((board_[i]
==
my_color)
?
"
@
"
:
"
-
"
);
++
cnt;
if
(cnt
==
N_)
...
{
cnt
=
0
;
cout
<<
endl;
}
}
}
bool
can_move(MOVE move)
...
{
return
is_empty(board_[move]);}
void
remove_killers(
int
depth,
int
move_cnt, MOVE
*
killers,
int
killers_cnt)
...
{
for
(
int
i
=
0
; i
<
killers_cnt;
++
i)
...
{
MOVE m
=
killers[i];
for
(
int
j
=
0
; j
<
move_cnt;
++
j)
...
{
if
(move_table[depth][j]
!=
m)
continue
;
for
(
int
k
=
j
+
1
; k
<
move_cnt;
++
k)
...
{
move_table[depth][k
-
1
]
=
move_table[depth][k];
}
break
;
}
}
}
}
;
UINT MG::gen_move(
int
depth)
...
{
int
cnt
=
0
;
for
(UINT i
=
0
; i
<
curr_board_size;
++
i)
...
{
if
(is_empty(board_[i]))
move_table[depth][cnt
++
]
=
i;
}
return
cnt;
}
int
MG::evaluatoin(
int
color)
...
{
if
(curr_stones_cnt
+
1
==
curr_board_size)
...
{
for
(
int
i
=
0
; i
<
curr_board_size;
++
i)
...
{
if
(is_empty(board_[i]))
...
{
board_[i]
=
color;
int
value
=
-
evaluatoin_4_end(opp_color(color));
board_[i]
=
empty;
return
value;
}
}
}
++
leaf_cnt;
unsigned
char
extended_hash_table[max_board_size]
=
...
{
0
}
;
int
my_score
=
0
, svr_score
=
0
;
for
(UINT i
=
0
; i
<
curr_stones_cnt;
++
i)
...
{
UINT pos
=
stones_[i];
if
(extended_hash_table[pos])
continue
;
UINT area
=
0
, round
=
0
;
unsigned
char
extended_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