Foundations of positional games
Foundations of positional games
复制标题
阵地博弈的基础
DOI：
--
复制
发表时间：
1996
期刊：
影响因子：
--
通讯作者：
J. Beck
中科院分区：
文献类型：
--
作者：
J. Beck
这是关于一种新的、准概率的位置博弈（即“组合博弈”）理论的系列论文中的第三篇。奇怪的是我们写这些论文的顺序是相反的。从时间顺序来看，第一篇论文“Deterministic Graph Games and a Probabilistic Intuition”是一篇技术性很强的文章，可以看作是该系列的第三部分。下一篇论文《成就游戏和概率方法》是一篇试图解释这一主题在离散数学中的作用的调查。然而，我们觉得我们并没有完全成功，而且不知怎的，我们的基础并不十分牢固。这就是为什么我们必须写这篇论文，这应该被视为该系列的第一部分。我们这里的主要目的是解释什么是位置博弈论的基本问题。众所周知的类尼姆博弈的代数理论（称为“组合博弈理论”）和准概率理论代表了两种完全不同的观点，它们在某种意义上是互补的。事实上，组合博弈论（游戏邦注：例如，类似于《nimi》的游戏）是一种精确的局部理论，即看似复杂的游戏如何从复合游戏开始，或如何迅速发展成若干简单局部游戏的复合游戏。另一方面，准概率理论试图解决“极其复杂的”井字棋类游戏，这些游戏通常在整个游戏过程中保持单一连贯的实体。它是一种有效的全局方法，粗略地说，它通过损失概率进行评估。由于通过博弈树的耗尽搜索的难以处理的复杂性，一种有效的评估方法必须近似。所以我们不能指望准概率理论能够解决平衡的“正面博弈”，在这种博弈中，一个错误就可能是致命的，但它可以有效地识别并解决大量困难的“单边博弈”。位置游戏是有限的2人技巧游戏（即没有机会移动），具有完美的信息，并且收益函数只有三个值1,0,−1（“赢”，“平局”，“输”）。因此，这些博弈是确定性的，因为有完美的信息，最优策略也是确定性的。那么随机性是如何进入故事的呢？为了回答这个问题，我们非常简单地总结了准概率论的最简单的例子：多数原则。多数原则分为两部分。第一部分是概率直觉，简而言之，在许多复杂游戏中，两个完美玩家之间的结果与两个“随机玩家”（随机游戏）之间的“多数结果”相同。关键在于，即使是相对简单的游戏也太过复杂，无法进行深入分析，但描述“典型”行为通常是一个可以利用概率论解决的问题。然而，多数原则不仅仅是预测复杂游戏的结果。第二部分是将概率直觉，通过潜在技术，转化为有效的确定性策略，即贪婪算法。©1996 John Wiley & Sons, Inc
This is the third piece of a series of papers about a new, quasiprobabilistic theory of positional games (i.e., “combinatorial games”). The strange thing is that we wrote these papers in reverse order. Chronologically the first paper, “Deterministic Graph Games and a Probabilistic Intuition,” was a highly technical one, and can be considered as part III of the series. The next paper, “Achievement Games and the Probabilistic Method,” was a survey that attempted to explain the role of the subject in discrete mathematics. We felt, however, that we did not quite succeed, and somehow the foundations were not very solid. This is why we had to write this paper, which should be considered as part I of the series. Our main object here is to explain what the basic questions of positional game theory are. The well-known algebraic theory of Nim-like games (called “combinatorial game theory”) and the quasiprobabilistic theory represent two entirely different viewpoints, and they in some sense complement each other. Indeed, combinatorial game theory (i.e., Nim-like games) is an exact local theory in the sense how seemingly complicated games start out as composites, or quickly develop into composites of several simple local games. On the other hand, the quasi-probabilistic theory attempts to solve “hopelessly complicated” Tic-Tac-Toe-like games which usually remain as single coherent entities throughout play. It is an efficient global approach which, roughly speaking, evaluates via loss probabilities. Because of the intractable complexity of the exhausting search through the game-tree, an efficient evaluation method has to approximate. So one cannot really expect from the quasi-probabilistic theory to solve evenly balanced “head-to-head games,” where a single mistake could be fatal, but it can effectively recognize and solve large classes of difficult “one-sided games.” Positional games are finite 2-player games of skill (i.e., no chance moves) with perfect information, and the payoff function has three values 1, 0, −1 only (“win,” “draw,” “loss”). These games, therefore, are deterministic, and because of the perfect information, the optimal strategies are deterministic. How can randomness then enter the story? To answer this, we very briefly summarize the simplest case of the quasi-probabilistic theory: the majority principle. The majority principle is in two parts. The first part is a probabilistic intuition that says in a nutshell that, in many complicated games, the outcome between two perfect players is the same as the “majority outcome” between two “random players” (random game). The point is that even relatively simple games are too hopelessly complicated to analyze in full depth, but to describe the “typical” behavior is usually a tractable problem to solve by using probability theory. However, the majority principle is more than merely predicting the outcomes of complicated games. The second part is to convert the probabilistic intuition, via potential techniques, into effective deterministic strategies, in fact, greedy algorithms. © 1996 John Wiley & Sons, Inc.