Asymptotic Properties of Minimax Trees and Game-Searching Procedures
Asymptotic Properties of Minimax Trees and Game-Searching Procedures
复制标题
DOI：
10.1145/3501714.3501723
复制
发表时间：
1980-09
期刊：
影响因子：
--
通讯作者：
J. Pearl
中科院分区：
文献类型：
--
作者：
J. Pearl
最常用于评估游戏搜索方法的行为的模型由高度为h和分支度为d的均匀树组成，其中终端位置被分配随机、独立和同分布的值。本文强调了一些奇怪的属性，这样的树时，h是非常大的，并探讨其影响的复杂性，各种游戏搜索方法。如果终端位置分别被分配为概率为P0和1-P0的赢-输状态，则根节点几乎是确定的MIN或确定的LOSS，这取决于P0是高于还是低于某个定点概率P（d）。当终端位置被赋予连续的真实的值时，根节点的极大极小值迅速收敛到唯一的预定值v，v是终端分布的（1-P）分位数。利用这些属性，我们表明，如果P 0 ≠ P *，则平均检查O [（d）h 2 ]终端位置，如果P 0 = P *，则平均检查O [（P *（1-P *））h ]位置，可以解决具有赢-输终端的游戏，前者的性能对于所有搜索算法都是最佳的。我们进一步证明了一个具有连续终值的博弈可以通过检查O [（P <$（1 − P <$））h ]位置的平均值来评估，并且这是所有方向算法的下界。在几乎所有的情况下，具有离散终端值的游戏都可以通过检查O [（d）h 2 ]终端位置的平均值来评估。这种性能是最佳的，也是通过ALPHA-BETA程序实现的。
Abstract The model most frequently used for evaluating the behavior of game-searching methods consists of a uniform tree of height h and a branching degree d, where the terminal positions are assigned random, independent and identically distributed values. This paper highlights some curious properties of such trees when h is very large and examines their implications on the complexity of various game-searching methods. If the terminal positions are assigned a WIN-LOSS status with the probabilities P0 and 1 − P0, respectively, then the root node is almost a sure MIN or a sure LOSS, depending on whether P0 is higher or lower than some fixed-point probability P∗(d) . When the terminal positions are assigned continuous real values, the minimax value of the root node converges rapidly to a unique predetermined value v∗ , which is the (1 − P∗)- fractile of the terminal distribution. Exploiting these properties we show that a game with WIN-LOSS terminals can be solved by examining, on the average, O [(d) h 2 ] terminal positions if positions if P 0 ≠ P∗ and O [( P∗ (1 − P∗) ) h ] positions if P 0 = P∗ , the former performance being optimal for all search algorithms. We further show that a game with continuous terminal values can be evaluated by examining an average of O [( P∗ (1 − P∗) ) h ] positions, and that this is a lower bound for all directional algorithms. Games with discrete terminal values can, in almost all cases, be evaluated by examining an average of O [(d) h 2 ] terminal positions. This performance is optimal and is also achieved by the ALPHA-BETA procedure.