Algorithm 版 (精华区)

发信人: Lerry (戒网·学习), 信区: Algorithm
标  题: 五子棋——博弈树的原理
发信站: 哈工大紫丁香 (2001年12月13日09:40:39 星期四), 站内信件

要使程序达到6、7段棋力、且落子速度在2、3秒以内，我认为有一定难度，原因是五子
棋的博弈树过于庞大，不剪枝的话，结点总数为225的阶乘，要让电脑考虑所有的结点，
显然受限于空间和时间上。如果采用棋谱库，当然可以让电脑落子如飞，但同时也失去
了“电脑思考”的意义。目前我所见到的最厉害的五子棋程序BlackStone，棋力约莫为
初段吧（我也没遇到过初段棋手，呵呵）？思考速度......唉，不提也罢，另一个强力
程序LWS编写的“连珠妙手”Fiver6，速度比较快，棋力也不弱，目前我持黑能胜它，持
白就死多活少了，不如它是不是部份采用了棋谱库。
　　本贴的最后，应一元兄的要求，将博弈树的原理和具体源码呈上，能力有限，难免
贻笑方家，如有缪误，敬请指正。我编程一般是用C＋＋或PASCAL，而现在着手编写的程
序用的是DELPHI，所以下面就主要以PASCAL为例。
　　还是采用自顶向下法，逐步细分。首先，我们假定有这样一个函数：
function StaticValue(const Phases: TPhases): Integer;
（函数原型用C表示为：int StaticValue(PHASES * pPhases);）
　　其中，TPhases是我们定义的一个类或结构，总之是一种数据类型，用来表示某一种
盘面状态，例如，可以将TPhases简单定义为一个记录：
type
TPhases = packed record
Board: array[0..14, 0..14] of Integer;
end;
　　也可以定义为一个类：
type
TPhases = class(TObject)
private
FBoard: array[0..14, 0..14] of Integer;
public
...
end;
　　具体怎样定义，可以根据各人喜好，结合实际情况而定。回过头来看我们的函数St
aticValue，它的功能是：返回一个对指定盘面的静态估值。所谓静态，意为不考虑下一
步，通过某种数学方法，将当前盘面换算成一个特定的整数，这个整数与对己方有利程
序成正比，即，越是对己方有利，其值越大，反之越是对己方不利，值越小。根据模块
化、自顶向下原则，这个函数具体是怎么做的，我们暂且不管，以后再来慢慢讨论，现
在只需要知道有这么一个函数，能够根据指定的一个盘面状态，返回一个整数值，当值
为“正无穷大”时，表示己方胜利，为“负无穷大”时，表示对方胜利。这里的“己方
”表示正在思考的一方，即电脑方。
　　现在有如下的盘面状态（浦月开局），电脑持白，轮到电脑走棋，下一步它将有22
2种可能的走法，即222种盘面状态，电脑要做的就是在这222种盘面状态中，根据Stati
cValue函数，挑出一个静态值最大的盘面，做为下一步走法，这就是电脑思考的雏形。

　　　　┼┼┼┼┼┼
　　　　┼┼┼○┼┼
　　　　┼┼●┼┼┼
　　　　┼┼┼●┼┼
　　　　┼┼┼┼┼┼
　　在实际应用中，我们引入第二个函数，名为GenerateChildren()，这个函数的原型
如下：
function GenerateChildren(const CurrentPhases: TPhases): TPhasesArray;
其中，TPhasesArray定义为：array of TPhases，即一个动态数组，数组的每一项为一
个盘面状态，即TPhases。PASCAL的动态数组可以理解为一个可变长度的普通数组，C里
面没有动态数组的概念，不过可以转化为一个链表，或一块动态分配空间的内存区域。
GenerateChildren函数的功能是：根据当前盘面状态，返回所有可能的下一步盘面状态
。有了上述两个函数，我们的五子棋程序
就成形了：
function FindBest(const CurrentPhases: TPhases): TPhases;
var
children: TPhasesArray;
i, v, max: Integer;
begin
children := GenerateChildren(CurrentPhases); // 生成所有可能的下一步盘面
max := Low(Integer); // max赋初值：负无穷大
for i:=0 to Length(children)-1 do // 遍历每一个盘面
begin
v := StaticValue(children[i]); // 对盘面静态求值
if max < v then // 找最大值
begin
max := v;
Result := children[i]; // 返回值最大的一个盘面状态
end;
end;
end;
　　这个函数将返回静态值最大的一个盘面做为下一步最好的走法。这种算法的效果嘛
，就是落子如飞，棋力嘛，臭不可闻，呵呵，原因在于它只考虑了下面一步，而没有纵
深考虑，即没有考虑“如果我走这里，对手将会怎样应？如果对手这样应了，我又该走
哪里”，换言之，只对下一步进行静态估值，是很不准确的，要进行准确的估值，还得
根据对手的应法做调整，这就是下面要讲的“博弈树最大最小值”方法。

--
　　不在乎天长地久，就怕你从来没有！

※ 来源:·哈工大紫丁香 bbs.hit.edu.cn·[FROM: 天外飞仙]