下载文档原格式
围棋中的博弈树搜索二人完美信息博弈中典型的人工智能方法是搜索博弈树以决定走哪一步。
标准博弈树搜索由四部分组成：1．状态表示，2．候选走法产生，3．确定目标状态，以及4．一个确定相对优势状态的静态评估函数。
有效的博弈树剪枝方法（比如α-β）增强了程序的表现。
博弈树这条途径很成功，如我们在国际象棋程序中所看到的，基于典型的完全广度α-β剪枝博弈树搜索的程序甚至击败了世界冠军。
这一节我们从透视电脑围棋的角度检查博弈树搜索的四个构件。
2.1 状态表示从完全信息的角度看，围棋盘面有19X19的3次方格，每个交叉点要么空要么被黑子或白子占据。
状态空间的大小（例如可能的位置数）是3的361次方（或10的172次方），相比之下国际象棋大致为10的50次方而Othello棋为10的30次方（Allis，1994）。
另外，博弈树的大小（例如可能的博弈数）在10的575次方和10的620次方之间，对比国际象棋的10的123次方和Othello棋的10的55次方（Allis，1994）。
由于空间的组合尺寸，用19X19格的形式严格表示状态空间对人或机器来说都层次太低而不能有效使用。
接下来的层面的描述是把正交的邻接棋子组成串（或链）。
所有的程序把串搜集到更大的单元，然而没有通用的处理方法——即便是对专业棋手来说——把串组合到更大的单元中。
依靠他们的围棋理论，程序员开发了他们自己的启发式，当串有效的连接在一起时用做评估之用（叫做模糊组或块）。
另外，恰当层次的表示能改变对运行时子任务的依赖，例如，战术分析，死活分析，或实地评估。
2.2 走子棋手在禁止自杀和同型反复（劫）的规则限制下轮流把棋子投放在空的交叉点（包括角和边）。
象国际象棋一样，围棋在给定位置的上下文中只有所有合法走法中的一部分是有效的。
围棋的平均分枝因子是很大的，大约是国际象棋的六倍（200对35，Burmeister & Wiles，1995）。
注意这个分枝因子在全盘中的考虑。
