并行博弈树搜索算法-第1篇 什么是博弈树搜索算法

博弈树的搜索是人工智能领域一个重要的研究课题.许多完全信息的二人零和博弈问题都可以用博弈树搜索算法解决。

那么什么是二人零和博弈问题呢？

有一系列的博弈问题拥有以下性质^[1]:

1. 有两个对抗者:对抗者1和对抗者2.

2. 两个对抗者交替移动.在博弈的每一个位置,对于正在移动的参与者,都存在有限个可能的移动.

3. 游戏是决定性的,即游戏中不存在随机性.

4. 游戏是完全信息的,即在任意时刻,博弈双方知道所处状态的所有信息.例如国际象棋是完全信息的,因为博弈双方知道所有的棋子所处位置,而两人玩的扑克牌游戏则是非完全信息的,因为一个人看不到对方手上的扑克牌.

5. 游戏有三种可能结局:对抗者1获胜,对抗者2获胜,或者平局.有一些游戏不存在平局,只有两种可能解决:对抗者1获胜,或者对抗者2获胜.由于这个性质,所以一个对抗者的损失对另一个对抗者来说是受益,故此这类的博弈游戏称为零和博弈（zero-sum game）.

对于具有上述性质的博弈问题,可以用博弈树来表示两个对抗者在博弈过程可能遇到的状态和移动选择.在对抗树（adversarytree）或者博弈树（gametree）中,两个对抗者交替移动.处于树底层的结点称为叶结点（leaf node）,叶结点的祖先称为内部结点（interior node）.

使用的^[2]术语,一个问题空间（problem space）看以看做是一个状态（state）和实现状态之间映射的操作(state)的集合.在博弈问题中,博弈树上的一个内部结点或叶结点就是一个状态,一般使用位置（position）来表述.移动（move）就是将一个位置转化为其子位置（successor position）的操作.如果一个位置是博弈树的叶结点,可以用评价者（evaluator）来对其优劣进行评分（evaluate）.有了评价者,博弈树中的每个叶结点都有一对应值（value）.

博弈树搜索或者对抗搜索的目的就是找出博弈树的值（game tree value）.博弈树的值（gametree value,下面简称博弈值）指的是博弈树中一个子结点的值,该值对于博弈双方都是最优的.博弈树的子树（subtree）在该子树搜索完成之后也会返回一个博弈值,虽然该值对于该子树来说最优的,但是对整个博弈树来说并不是全局最优的.

找出一棵博弈树的博弈值,可以使用基本的Min-Max方法.为了减少Min-Max方法需要搜索的结点个数,可以使用Alpha-Beta算法进行剪枝.根据博弈树的性质,在Alpha-Beta算法的基础上,各种改进方法被先后提出来.为了进一步提高搜索速度,Alpha-Beta算法又可以基于不同的思想进行并行化.在博弈树搜索算法方面,前人做了许多丰富而充满意义的研究工作.

本文重点在于讨论博弈树并行搜索算法的设计和分析.但是一方面由于博弈树搜索的并行算法与串行算法的紧密内在联系,一方面为了对博弈树的搜索问题进行全面和深入的认识,本文不仅将讨论并行的博弈树搜索算法,而且将总结关于博弈树的串行搜索算法的许多其他问题.从最基本的Min-Max方法开始,到Alpha-Beta串行算法,再到Alpha-Beta算法的并行化,本文沿着博弈树搜索问题的脉络,将进行细致的分析和总结.

本文章欢迎转载，请保留原始博客链接http://blog.csdn.net/fsdev/article

-------------------------------------------------

[1] Valavan Manohararajah(2001). Parallel Alpha-Beta Search on SharedMemory Multiprocessors. Master’s thesis, Graduate Department of Electrical andComputer Engineering, University of Toronto, Canada.

[2] A. Newell and H.A. Simon (1972). Human Problem Solving.Prentice-Hall, 1972.