英语原文共 21 页，剩余内容已隐藏，支付完成后下载完整资料

博弈树剪枝回顾

1. 介绍

典型的国际象棋程序包含三个确定的元素：棋盘表示和走法生成，树搜索/修剪和位置评估。对棋盘表示来说必要的好的描述表和数据结构存在于容易获得的书^【1，2】和文章^【3，4】中。即使如此，对最好的或最有效的代表也没有普遍的一致意见。从这些表中，生成每个位置的移动列表。有时，生成函数会立即生成所有可行的移动，其优点是它们可以按最可能的成功顺序排序和尝试。另一方面，在小型存储器计算机中，每次产生一个移动。这节省了空间，并且如果早期移动驳斥当前的走子线路可能更快。由于只能进行有限的排序（可能首先生成lsquo;捕获rsquo;）搜索效率通常较低。建议不要重新解决这些问题，第一次建造国际象棋程序的初学者应该建议遵循Larry Atkin 优秀的 Pascal-based 模型^【5】。

国际象棋程序最重要的部分在于评价函数。评价函数在博弈树搜索中用来评估每一步移动的指数，其中许多是lsquo;吃法rsquo;或是为了避免死亡的被迫移动。通常必须执行有限搜索（称为静态搜索）以确定这种主动移动的未知潜在性。评估过程估计了不能完全探索的象棋位置的价值。在最简单的情况下，评估仅计算棋子差异，但是为了优越的游戏，还必须测量许多位置因素，例如卒的组织。这些方面仍然没有被正式化，但是计算机国际象棋实践者的充分描述可以在书中找到^【2，6】。

在搜索和修剪领域，所有象棋程序符合以下一般模式。在游戏树的前几层进行全宽度“穷举”搜索（考虑所有移动）。在超出该穷尽区域的深度处，使用某种形式的选择性搜索。通常，不可能或不自然的移动从移动列表中简单地删除。更复杂的程序基于广泛的分析选择哪些移动应该被丢弃。不幸的是，这种类型的前向修剪被认为是容易出错和危险的;它是有吸引力的，因为随之而来的树的大小减少。最后，在一些搜索的最大深度处，调用评估函数;这又通常需要进一步搜索指定的动作，如捕获走法。因此，所有程序采用具有搜索宽度的隐含逐渐变细的模型，因为变化被越来越深地探索。一个程序与另一个程序的区别在于评估的质量，以及逐渐变细的操作的严重程度。本文集中在树的搜索和修剪方面，特别是那些被确切表达和证明的方法。

2. 博弈树搜索组成

由于大多数国际象棋程序会检查巨大的博弈树，通常使用深度优先搜索。也就是说，当前节点的直接后继者的第一分支被递归地扩展，直到到达叶节点（没有后继节点的节点），再回退到根节点进行其他分支的搜索。其他扩展方案是可能的，并且该领域对于测试新的搜索算法是有益的。由于计算机象棋是明确定义的，并且存在性能的绝对度量，它是测量算法效率的有用的测试工具。在最简单的情况下，最佳算法是在确定树的真实值时访问最少的节点的算法。对于两人游戏树，该值是侧移动的得分（或优点）上的最小上限，可以通过极小搜索找到。在国际象棋中，这个所谓的极小值是“MaterialBalance”（即，每一方持有的棋子的价值的差异）和“StrategicBalance”（对战略的综合测量如灵活性，区域控制，卒的排列结构和国王安全）的组合。通常，评估函数以这样的方式计算这些分量：即MaterialBalance支配所有位置因素。

2.1 最小最大搜索

对于象棋，两人游戏树中的节点代表位置，分支对应于移动。搜索的目的是在双方最佳移动的假设下找到从根到可以到达的最高价值叶节点的路径。为了表示树中的一个层次（一局或半局），术语“ply（层）”是由Arthur Samuel在他的机器学习的主要文章^【7】中介绍的。如何选择这个词是不清楚的，也许是作为“游戏”的缩写，或者是通过胶合板产生的联想。在任何一种情况下，都是合适的，它已被普遍接受。

游戏树的真实极小搜索可能是昂贵的，因为每个叶节点必须被访问。对于在每个节点处具有恰好w移动的均匀树，在D层存在w^D个节点。在这个最深层的节点将被称为终端节点，在我们的讨论中被称作叶节点。一些游戏，如Fox和Geese^[8]，产生通常可以彻底解决的窄树（每个节点少于10个分支）。相比之下，国际象棋产生“茂密的树“（平均分支因子，W，约为35^【9】）。因为游戏树的大小，它是不可能搜索直到到达配对或僵局位置（真叶节点），因此指定了一些最大搜索深度（即，水平）。即使如此，对于每一侧都涉及多个移动的所有象棋游戏树的详尽搜索是不可能的。幸运的是，可以减少工作，因为有一些节点是不需要搜索的。

2.2算法

随着对国际象棋博弈树的不断搜索，目前已经找到了最佳终端节点值的改变过程。但根据Knuth和Moore，John McCarthy和他在麻省理工学院的小组，1958年就利用最大最小搜索算法实现了这件事。对这个话题的第一次彻底的处理似乎是Brudno 1963年的论文^[11]。 -算法对树的期望值采用较低（）和较高（）边界。这些边界可以用于证明某些移动不会影响搜索的结果，并且因此它们可以被“修剪“。作为早期关于如何修剪子树的一部分，深切割和浅切割已经被进行了区分。某些版本的-算法仅使用单个边界（），并重复将绑定到无穷大，因此无法实现较深的截止。为了纠正这个缺陷，Knuth和Moore引入了一个称为F2^[12]的递归算法，并用它来证明-算法的属性。还使用了一个“negamax”框架，其主要优点是通过总是传回子树值的负值，只需要最大化操作。在图1中，类似Pascal的伪码用于在同一个negamax框架中呈现我们的-函数AB。返回语句被引入作为退出函数并返回最佳子树值或分数的约定。省略了游戏特定功能Make和Undo（更新游戏板），Generate（查找移动）和Evaluate（评估终端节点）的详细信息。在图1的伪代码中，max（，score）运算表示Fishburn的“fail-soft”条件，并且确保返回最佳可用值（而不是或边界），甚至如果它位于-窗口之外。这个想法在-算法的一些更新的改进中是有用的。

FUNCTION AB (p : position;  ,  , depth : integer) : integer;

{ p is pointer to the current node }

{  and  are window bounds }

{ depth is the remaining search length }

{ the value of the subtree is returned }

VAR score, j, value : integer;

posn : ARRAY [1..MAXWIDTH] OF position;

{ Note: depth must be positive }

BEGIN

IF depth = 0 THEN { horizon node, maximum depth? }

Return(Evaluate(p));

posn := Generate(p); { point to successor positions }

IF empty(posn) THEN { leaf, no moves? }

Return(Evaluate(p));

{ find score of best variation }

score := -;

FOR j := 1 TO sizeof(posn) DO BEGIN

Make(posn[j]); { make current move }

value := -AB (posn[j], - , -max( ,score), depth-1);

IF (value gt; score) THEN{ note new best score }

score := value;

Undo(posn[j]); { retract current move }

IF (score   ) THEN{ a cut-off? }

GOTO done;

END ;

done:

Return(score);

END ;

Figure 1: 深度限制的算法

( ,  )

p depth = 3

( ,  )

( , 5)

1

depth = 2

2

( ,  )

( , 5)

(5,  )

(5, 9)

1. 1

1. 2

depth = 1

2. 1

2. 2

1. 2. 1

1. 2. 2

depth = 0

2. 1. 1 2. 1. 2

5 4 6 1 9 7 3 2

Figure 2: .

虽然涉及修剪的树搜索主题常规出现在标准的人工智能文本中，但棋程序仍然是-算法的主要应用。 在文本中，一个典型的关于游戏树搜索的讨论基于最小化和最大化操作的替代使用。 在实践中，negamax方法是优选的，因为编程更简单。 图2包含一个小的3层树，其中使用Dewey-decimal方案来标记节点，使得节点名携带关于返回根节点的路径的信息。 因此，p.2.1.2是隐藏子树的根，其值在图2中示为7.在图2的每个节点处还示出了搜索采用的初始alpha;-beta;窗口。 注意，用（，5）的初始窗口搜索节点p.1.2的后续节点。 因为节点p.1.2.1的值是6，大于5，所以称为出现截止，并且-算法不访问节点p.1.2.2。

2.3 最小博弈树

如果在每个节点首先检查“最佳”移动，则从最小博弈树的便利中就可以获得极大极小值。 这个最小树具有理论重要性，因为它的大小是搜索的下限。 对于每个节点有W分支和D 层的均匀树，Knuth和Moore提供了最优雅的证据，一共有

 D   D 

W  2   W  2   1

个终端节点在最小游戏树中^【13】，其中x是代表大于x的最小整数，x是代表小于x的最大整数。 由于这样的终端节点很少没有后继节点（即不是叶子），因此它也被称为水平节点，其中D是从根节点到水平线的距离^【14】。

2.4 渴望搜索

可以使用初始边界覆盖窄范围进行-搜索，该范围跨越树的期望值。在棋中，这些边界可能是（MaterialBalance - Pawn，MaterialBalance Pawn）。如果最小值落在该范围内，则不需要额外的工作，并且搜索通常以可测量的较少时间完成。该方法由Berliner提到的Brudno ^【15】进行分析，并由Gillogly ^[16]进行实验，但并不总是成功。缺点是有时初始边界不包含最小值，在这种情况下，搜索必须用校正的边界重复，如图3的轮廓所示。通常，这些失败只发生在棋子被赢得或丢失时，在这种情况下，更高级的搜索的增加的成本是可接受的。因为这些重新搜索使用半无限窗口，所以人们不时地试验（V，V PieceValue）的“滑动窗口”，而不是（V， ）。这种方法通常是有效的，但是当“将死“或大的物质损益在进行时可能导致过度的重新搜索。

{ Assume V = estimated value of position p, and }

{ e = expected error limit }

{ depth = current distance to horizon }

{ p = position being searched }

= V - e; { lower bound }

= V e; { upper bound }

V= AB (p,  , , depth);

IF (V gt;= ) THEN { failing high } V := AB (p, V, , depth)

ELSE

IF (Vlt;= ) THEN { failing low } V := AB (p, -, V, depth);

{ A successful search has now been completed }

{ V now holds the current value of the tree }

Figure 3: 窄窗口渴望搜索.

1974年之后，“迭代渴望搜索”被普遍使用，如下所示：“在每次迭代开始之前，和不像人们所期望的那样设置为-和 ，但是在窗口中只有几个棋子宽，大致集中在来自先前迭代的最终分数值（或在第一次迭代的情况下的先前移动）。 这种“高希望”的设置增加了-截断值的数量^【16】。 即使如此，虽然目标搜索仍然受欢迎，并且有很多值得称赞的，最小窗口搜索似乎更有效，并且不需要关于吸引窗口的选择的假设^【17】。

2.5 静止搜索

即使是最早的计算机

剩余内容已隐藏，支付完成后下载完整资料

资料编号：[138856]，资料为PDF文档或Word文档，PDF文档可免费转换为Word