Fast algorithms for finding randomized strategies in game trees
Fast algorithms for finding randomized strategies in game trees
复制标题
DOI：
10.1145/195058.195451
复制
发表时间：
1994-05
期刊：
影响因子：
--
通讯作者：
D. Koller;N. Megiddo;B. Stengel
中科院分区：
文献类型：
--
作者：
D. Koller;N. Megiddo;B. Stengel
智能体之间的交互可以方便地用博弈树来描述。为了分析一个博弈，重要的是要为不同的参与者得出最优（或均衡）策略。一般来说，在不完全信息的博弈中找到这样的策略的标准方法在计算上是困难的。该方法是生成游戏的标准形式（包含每个策略组合的收益的矩阵），然后求解线性规划（LP）或线性互补问题（LCP）。然而，范式的大小通常是博弈树大小的指数，因此除了最简单的情况外，这种方法在所有情况下都不切实际。本文描述了一种新的策略表示，它导致了具有完美回忆的两人游戏问题的实用线性公式（即，玩家永远不会忘记任何事情，这是一个标准的假设）。然后可以应用标准LP或LCP求解器来找到最佳随机化策略。由此产生的算法，一般来说，指数优于标准的，无论是在时间和空间方面。IBM Almaden Research Center，650 Harry Road，圣何塞，CA 95120;以及特拉维夫大学数学科学学院。德国Neubiberg 85577，慕尼黑联邦武装部队大学信息学院5。研究部分由ONR合同N 00014 -91-C-0026，空军科学研究办公室（AFSC）根据合同F49620-91-C-0080和大众基金会支持。有些工作是在第一作者在斯坦福大学时完成的。美国政府有权出于政府目的复制和分发重印本。第26届ACM计算理论研讨会论文集，1994年，750-759
Interactions among agents can be conveniently described by game trees. In order to analyze a game, it is important to derive optimal (or equilibrium) strategies for the different players. The standard approach to finding such strategies in games with imperfect information is, in general, computationally intractable. The approach is to generate the normal form of the game (the matrix containing the payoff for each strategy combination), and then solve a linear program (LP) or a linear complementarity problem (LCP). The size of the normal form, however, is typically exponential in the size of the game tree, thus making this method impractical in all but the simplest cases. This paper describes a new representation of strategies which results in a practical linear formulation of the problem of two-player games with perfect recall (i.e., games where players never forget anything, which is a standard assumption). Standard LP or LCP solvers can then be applied to find optimal randomized strategies. The resulting algorithms are, in general, exponentially better than the standard ones, both in terms of time and in terms of space. ∗Computer Science Division, University of California, Berkeley, CA 94720; and IBM Almaden Research Center, 650 Harry Road, San Jose, CA 95120 †IBM Almaden Research Center, 650 Harry Road, San Jose, CA 95120; and School of Mathematical Sciences, Tel Aviv University, Tel Aviv, Israel. ‡Informatik 5, University of the Federal Armed Forces at Munich, 85577 Neubiberg, Germany. Research supported in part by ONR Contract N00014-91-C-0026, by the Air Force Office of Scientific Research (AFSC) under Contract F49620-91-C-0080, and by the Volkswagen Foundation. Some of the work was performed while the first author was at Stanford University. The United States Government is authorized to reproduce and distribute reprints for governmental purposes. In: Proceedings of the 26th ACM Symposium on the Theory of Computing, 1994, 750–759