博弈树搜索算法

姓名：李嘉蔚 学号16020520034

【嵌牛导读】:通过讨论人工智能中用于计算机博奕的一 般技术如极大极小搜索、Alpha—Beta剪枝、小窗口 搜索，对五子棋博奕的内在规律进行了分析研究，给 出解决五子棋博奕的2种优化算法，这2种优化算 法大大提高了搜索效率，相比之下引入置换表后的 化算法的搜索效率更高。

【嵌牛鼻子】：极大极小搜索；Alpha—Beta剪枝；小窗口 搜索 。

【嵌牛提问】：什么是博弈树搜索算法？为什么要研究搜索？

【嵌牛正文】:搜索是人工智能中的一个基本问题，是推理不可分割的一部分，它直接关系到智能系统的性能与效率，尼尔逊把它称为人工智能研究中4个核心问题之一。根据问题的实际情况不断寻找可利用的知识，从而构造一条代价较小的推理路径，使问题得到

解决的过程称之为搜索。搜索分为盲目搜索和启发

式搜索H_J。盲目搜索是在预先控制策略中进行搜

索，在搜索过程中获得的中间信息不用来改进控制

策略。启发式搜索是在搜索过程中引入了与问题有

关的启发式信息，以指导搜索的方向，加速问题的求

解过程并找到最优解。

博弈事件千差万别，但在具体的博弈事件背后

都有着共同的特性：二人零和、全信息、非偶然。博

弈树是一棵“与或”树，此“与或”树是始终站在某一

方的立场上得出的，与或节点交替出现，在博弈事件

中，每一个格局可供选择的行动方案都有很多种，因

收稿日期：2007—05—27 ‘‘

基金项口：成阳师范学院科研基金项目(06XSYK272)

作者简介：李红(1976，一)，女(汉)，陕西咸阳，硕士研究生

主要研究图像处理与人工智能。

此会生成一个十分庞大的博弈树。

1博弈树搜索算法

博弈树搜索可以脱离具体的博弈事件，完全在

算法的级别上进行研究。博弈树只是实现求解的一

部分，在搜索过程中还要注意其它问题，如行为的产

生、搜索的方法及搜索的顺序。

估值函数对于一个具体的博弈事件来说是机器

求解是否准确的关键，博弈树搜索效率的高低，最后

作为行动优劣的取舍都是根据估值函数的结果确定

的。在博弈事件中·，估值函数很难确定，它要根据具

体情况的不断变化来确定，所以在整个过程中它是

需要反复被验证的，权值需要反复修改，最终确定一

个最佳值。

1．1极大极小搜索算法

假设有2个博弈者甲和乙(甲为计算机，乙为棋

手)，在这个博弈事件中我们要为甲找到最佳的走

步。现假设甲方先下，乙方后下，深度为奇数的节点

为甲方下了一子之后的局面(即乙方选择下法的局

面)，称之为极小节点；深度为偶数的节点为乙方下

一子之后的局面(即甲方选择下法的局面)，称为极

大节点；博弈树的顶节点深度为0。‘

一个最佳走步可以由一个极大极小化过程产

生，甲方要从搜索树中选择拥有最大值的节点，因

此。一个标有“甲”的节点的估计值可以由它的标有

“乙”的子节点的最大值确定。另一方面，乙方从叶

节点中选择时，由于估计值越小对它越有利，因此必

然选取估计值最小的节点(即最负的估计值)，因此，

标有“乙”的节点估计值可由它的标有“甲”的子节点

的最小值确定。综上所述，可由博弈树的叶节点出

发向上一层层倒推，得到上一层的估计值，从而得出

根节点的估计值，这样就可以确定从根节点出发的

最佳走步，称之为极大极小算法，其伪代码如下：

double ji da ji xiao(int depth)

{

int i；

double best，n；

if(比赛结束)

return evaluation()；

if(depth==0)

return evaluation()；／*叶节点*／

if(甲方)

best=一1 000：

else

best=1 000；／*初始化当前最优值，假设1

000为一个不可能达到的值*／

for(i=1；i<=w；i++)

{

n=ji_da—ji—xiao(depth一1)；

if(n>best&＆甲方)

best=n；

if(n<best&&棋手)

best=n；

}

return best；

}

1．2 a—p剪枝算 法

使用极大极小搜索进行搜索时，随着搜索深度

的增加，所花费的时间也大大增加，这是因为搜索过

程中存在着大量的数据冗余，a—B剪枝算法解决的

主要是数据冗余问题。a(alpha)和p(beta)剪枝的惟

一区别在于分析的两层中极大极小值的先后顺序，a

是用来取极大值时的情况，p是在取极小值时的情

况，其伪码如下：

double Alpha—Beta(double alpha，double beta，

int depth)；

{

int i；

double fl，best；

if(比赛结束)

return evaluation()；

if(depth==0)

retum evaluation()；／*叶结点*／

if(极大节点)

{

for(i=1；i<=W；i++)

{

n=Alpha—Beta(alpha，beta，depth一

1)；

if(best>alpha)

alpha=best；

return alpha；

}

else／*极小节点*／

{

for(i=l；i<=w；i++)

{

n=Alpha—Beta(alpha，beta，depth一1)；

if(best<beta)

beta=best；

}

return beta；

}

}

1．3小窗口搜索算法

小窗口搜索是一种为了缩小搜索范围而实现的

算法，它是将a—B剪枝看作是一种对求解的范围不

断缩小的过程。在一定范围内，如果能够精确对搜

索进行估值，那么搜索的效率将会大大提高，在极限

情况下，如果估计完全准确，那么剪枝的效率将和原

来的树的总节点数相同。小窗口搜索是将估计的结

果增加一个范围，来提高搜索效率。

窗口越小则可能减去的枝会越多，那么当窗口

为0会怎么样呢?极小窗口搜索是根据搜索第1个

节点作为估计值的，即在最好的情况下第1个节点

就是最优解，它也就是树的最优解。

小窗121搜索算法中存在的一个问题是如果估计

值落在区域之外，那就不能得到最优解，引人一个标

志value，它能够记录失败的原因。

double search(double alpha，double beta，-int depth

)；

{

int i；

double n，best；

if(比赛结束)

retum evaluation()；

if(depth==0)

retum evaluation()；／*叶结点*／

i=N一1search(alpha，beta，depth一1)；／*n

一1层的最佳值*／

alpha=x—window；

beta=x+window：

value=N—Isearch(alpha，beta，depth)；／*

确定左右边界再搜索*／

if(value<alpha)

valudepth)；

if(value>beta)

value=N一1search(beta，1 000，depth)；

Return value；

}

2算法优e=N—lsearch(alpha，一1 000。

depth)；

if(value>beta)

value=N一1search(beta，1 000，depth)；

Return value；

}

2算法优化

博弈事件在整个阶段是不相同的，在初期可以

采取的行动也很多，随着阶段的发展，双方可采取的

行动越来越少，到最后几步可以推算出一些规律，通

过多次叠代，从而得到最优解，这种技术称为基于

Alpha—beta的叠代方法。最常见到的方法是将／／,一

1层搜索出的走步作为／7,层搜索的开始走步，邻近

两层间的走步有一定的相似性。

2．1 基于Alpha—beta的叠代方法与小窗口搜索

算法

改进搜索算法的目标在于将不必搜索的(冗余)

分枝从搜索的过程中尽量剔除，以达到尽量搜索少

的分枝来降低运算量。Alpha—beta剪枝相对于极

大极小算法已经有了很大程度的改善，减少大量的

冗余节点，但是节点排列顺序没有考虑，在最坏的情

况下可以退化为极大极小算法；小窗口搜索缩小了

范围，提高收敛的效率；通过置换表记录已经分析过

的节点；使用基于Alpha—beta的叠代方法可以利用

不同层次的分析结果。但是单独使用哪一种方法都

有其不利的方面。基于对博弈搜索算法特点的研

究，以及对五子棋博奕知识和规则的细致分析，提出

一种优化的算法，即多种算法结合的方法。

多种算法结合，采用的是基于Alpha—beta的叠

代方法与小窗口算法结合，选择这2种方法的原因

是，叠代算法的作用是将／'t一1次走步的点在搜索

前移动到博弈树的前端，而小窗口搜索算法是基于

第1个节点是最优节点的思想，所以这2种方法的

结合，不但缩小了叠代时间，分析的节点数目也有所

减少，并且大大提高了搜索效率。

2．2 引入置换表的基于Alpha—beta的叠代方法与

小窗口搜索算法

在博弈树搜索时，可能存在这样的情况，就是不

同的分枝上可能存在相同的节点，那么能否将搜索

过的节点不再被重复搜索，即需要把搜索过的节点

记录下来，在以后的搜索过程中，可以查看记录表中

的结果，如果有记录那就直接用记录的结果，这种方

法称之为置换表法，可以采用哈希表作为存储数据

的数据结构。

置换表的引入避免了对重复节点的搜索，但仍

存在多个问题：首先，是否每次搜索都需要清空哈希

表；第二，层次如何处理；第三，哈希函数如何选择。

在对这些问题深入研究时，发现采用哈希表作为存

储数据的数据结构时，不需要每次搜索时都清空哈

’希表；在定义哈希表时，需要存储搜索深度，因为同

一个局面可能在搜索树中的不同层上出现；Zobrist

哈希技术是一种在博弈程序中广泛被使用的随机哈

希方法，它有着良好的速度及良好的散列度。

本算法在五子棋程序上验证，因为棋盘是15×

15，故可将棋盘状态用一个15×15的二维数组表

示。

数据表示为：

BYTE WUZIQI[Xing：}[Lie]=

{

{一1，一l，一I，一1，一1，一1，一l，一1，一1，一

1，一1，一1，一1，一1，一1}，{一1，一1，一1，一1，～l，

一1，一1，一1，一1，一1，一l，一1，一1，一1，一1}，

{一1，一1，一1，一1，一1，一1，一1，一1，一1，一

1，一1，一1，一1，一1，一1}i{一1，一l，一1，一1，一1，

一1，一1，一1，一1，一1，一1，一1，一1，一1，一1}，

{一1，一1，一1，一1，一1，一l，一1，一1，一1，一

l，一1，一1，一1，一l，一1}，{一1，一1，一1，一1，一1，

一1，一1，一1，一1，一1，一1，一1，一1，一1，一1}，

{一1，一1，一1，一1，一1，一1，一1，一1，一1，一

1，一1，一I，一1，一1，一1}，{一I，一1，一1，一1，一1，

一1，一1，一1，一1，一1，一1，一1，一l，一1，一1}，

{一1，一l，一1，一1，一1，一1，一1，一1，一1，一

1，一l，一1，一1，一1，一1}，{一1，一1，一1，一1，一1，

一1，一1，一1，一1，一1，一1，一1，一1，一1，一l f，

{一1，一1，一1，一1，一1，一l，一1，一1，一1，一

1，一1，一1，一1，一1，一1}，{一1，一1，一1，一1，一1，

一1，一1，一1，一1，一1，一l，一1，一1，一1，一1}，

{一1，一1，一l，一1，一1，一1，一1，一1，一1，一

l，一1，一1，一1，一l，一1}，{一1，一1，一l，一l，一1，

一1，一1，一1，一1，一1，一1，一1，一I，一1，一1}，

}

五子棋的位置表示为：

typedef Struct STONEPOSITION

{

BYTE X；

BYTE Y；

}；