On Optimal Game-Tree Search using Rational Meta-Reasoning
On Optimal Game-Tree Search using Rational Meta-Reasoning
复制标题
使用理性元推理进行最优博弈树搜索
DOI：
--
复制
发表时间：
1989
期刊：
影响因子：
--
通讯作者：
Eric Wefald
中科院分区：
文献类型：
--
作者：
Stuart J. Russell;Eric Wefald
在本文中，我们概述了研究问题解决的一般方法，其中搜索步骤被认为是与世界上的行动相同意义上的决策。与文献中的其他度量不同，搜索步骤的值被定义为实际效用，而不是准效用，因此可以直接从基础级问题解决器的模型中计算。我们使用单步假设开发了游戏环境中搜索步骤期望值的公式，即计算步骤可以在最后执行时进行评估。我们证明了一些元级定理，这些定理使开发一种低开销算法MGSS*成为可能，该算法按照最高估计效用的顺序选择搜索步骤。尽管我们证明单步假设在一般情况下是站不住脚的，但为奥赛罗游戏实现的程序在扩展更少节点的情况下完全击败了α - β搜索，即使两个程序使用相同的评估函数。
In this paper we outline a general approach to the study of problem-solving, in which search steps are considered decisions in the same sense as actions in the world. Unlike other metrics in the literature, the value of a search step is defined as a real utility rather than as a quasi-utility, and can therefore be computed directly from a model of the base-level problem-solver. We develop a formula for the expected value of a search step in a game-playing context using the single-step assumption, namely that a computation step can be evaluated as it was the last to be taken. We prove some meta-level theorems that enable the development of a low-overhead algorithm, MGSS*, that chooses search steps in order of highest estimated utility. Although we show that the single-step assumption is untenable in general, a program implemented for the game of Othello soundly beats an alpha-beta search while expanding significantly fewer nodes, even though both programs use the same evaluation function.