文档介绍：搜索树中有三种类型的结点: (1)偶数层的中间结点,代表棋手甲要走的局面; (2)奇数层的中间结点,代表棋手乙要走的局面; (3)叶子结点,代表棋局结束的局面,即棋手甲或棋手乙获胜,或者是和局。博弈树的评价假设某个中间结点的所有子结点都是叶子结点,那么棋局会在一回合内结束。现在我们假设棋手会挑选最好的着法,如果有一个着法能使他赢下棋局,那么他一定会走这步。如果没有可以赢的着法,但是有取得和局的着法,那么他会走这步取得和局的着法。但是,如果所有的着法都使得对手获胜,那么无论如何他都会输。因此在叶子结点的上一层结点,我们就能知道棋局的结果。现在我们知道了这个结点的结果,那么我们可以用同样的方法作推演,知道叶子结点的上两层结点的结果,然后是上三层结点,等等,直到我们达到搜索树的根结点。在每个结点上,棋手只要找到一个子结点能让他获胜,那么他就可以赢下棋局;他只要找到一个形成和局的子结点,棋局就和了;如果获胜与和局的子结点都没有,那么肯定是输的。如果我们有足够多的时间来计算,那么这就给了我们一个可以下棋的完美算法。但是对于任何常规的棋类游戏,我们都不可能有足够的计算时间,因为搜索树实在太大了。另外,“正确”的评价函数只有三个值,赢、输或者和局。在实际的棋类程序中,我们通常使用一个更宽泛的实数来作评价值,就是因为赢、输或者和局是不确定的。如果棋手甲获胜的值用+1表示,和局的值用0表示,棋手乙获胜的值用-1表示,那么博弈树的每个中间结点的值就是子结点的最大值或最小值,这取决于棋手甲还是棋手乙着棋。部分的博弈树在实战中,我们的搜索算法只能对博弈树展开一部分。我们用一些“中止规则”来决定搜索树展开到哪个结点就停下来,例如我们在8步变化以后听下来。由于棋局没有在叶子结点结束,我们只能用评价函数来猜哪一方获胜。现在我们来假设在我们展开的结点中,棋手甲总是希望棋局到达评价函数大的局面,而棋手乙总是希望棋局到达评价函数小的局面。如果双方都用这种方法来下棋,那么我们可以使用同样的最小-最大过程,来确定到达的叶子结点的评价值,这个过程如下:对每个中间结点,计算子结点的最大值或最小值,这取决于是棋手甲还是棋手乙走棋。到达叶子结点的线路称为“主要变例”(PrincipalVariation)。最小-最大博弈树的基本原理,就是对博弈树作部分展开,去找主要变例,并走出变例中的第一步。广度优先和深度优先搜索,负值最大代码正如上面所讲的,计算博弈树的值是一个广度优先的过程(我们要自下而上地,一次一层地计算)。然而实战中,我们使用深度优先(即后序遍历)的递归过程来遍历搜索树,即要得到一个结点的值,就对子结点做递归,然后根据它们的返回值来决定自身的返回值。这样要节省很多空间,因为不需要来存储整个博弈树,而只是存储一条线路(相对来说非常短,例如上面提到的8步中止的规则)。下次我们讨论Alpha-Beta搜索时,会发现深度优先的遍历会有很大的优势,你可以用目前得到的信息来决定某些结点是不需要访问的,这样就节省下很多的时间。只要对搜索树的值作一个很小的改动,就可以用一个求最大值的操作来代替最小值和最大值交替的过程。在搜索树的奇数层(即轮到棋手乙下棋的结点),就对上面提到的评价值取负数。因此在每个结点上,这些值都可以由子结点的负值求得。我把博弈树搜索的源代码写出来,恐怕就会清楚很多了。//将博弈树搜索到