A Probabilistic Theory of Positional Games

9626151 Beck摘要在该提案中，研究人员概述了一种新的位置游戏（即棋盘游戏或组合游戏）的概率方法。分析一个头寸的最直接的方法是检查它的所有选项，以及这些选项中的所有选项，以及这些选项中的所有选项，以及所有......显而易见的困难是，即使对于非常简单的游戏，这种通过游戏树的令人疲惫的搜索也需要大量的时间（就棋盘大小而言，指数级的运行时间）。请注意，传统博弈论的博弈矩阵方法要糟糕得多：通常需要双指数时间。为了弥补时间上的不足，一个绝望的尝试是研究博弈树上的随机游走。现在，研究者的概率理论的基本思想是，随机游走（即随机博弈）的概率分析通常是一个易于处理的问题，而且人们从这种分析中学到的东西通常可以通过潜在的参数（如具有损失概率的资源计数）转换为确定性的最优策略。概率论基本上是一个博弈论的适应所谓的概率方法在组合应用于绝望复杂的游戏代数和其他确切的方法无法工作。令人惊讶的是，这种孤注一掷的尝试对于大型、有趣的位置游戏来说非常成功。该提案的主要章节是：位置游戏的基础（一个令人惊讶的非平凡的任务），博弈论拉姆齐理论，博弈论随机图论，博弈论洛瓦兹局部引理，以及算法和复杂性的应用。 传统的博弈论，即冯·诺依曼的理论，基本上是不完全信息博弈的理论。它为经济学和社会科学的许多领域（管理，军事战略等）提供了很好的见解。类似地，人们可以从完全信息博弈（即位置博弈）的成功理论中期待许多新的应用。这正是调查员的建议的全部内容。研究位置博弈的一个非常令人兴奋的方面是，它可能会更好地理解人类智能是如何工作的。它可能会对一些基本问题产生影响，比如人类的理解是一个计算过程还是一个非计算过程。请注意，在日本，有几个“完美”的棋手，当他们先下围棋时，可以一直赢得围棋（在19 × 19的棋盘上连续5局），但没有人能把这些理论变成精确的论点。同样，在一个足够大的棋盘上，两个相当优秀的玩家之间的6连牌总是一个无聊的平局游戏，但我们也不能准确地解释为什么。或者说，是什么原因导致电脑程序的围棋水平远不及人类最好的棋手呢？这些只是人类大脑“知道”超越严格数学的东西的许多例子中的三个。还有一件事：与围棋相比，最好的国际象棋计算机程序现在已经达到了人类大师的水平。但有一个基本的区别。计算机程序在决定下一步做什么之前会检查数百万个职位。另一方面，即使是最好的大师，每次移动也不会搜索超过100个位置。在人类的国际象棋中，模式识别扮演着比搜索更重要的角色。如何将人类的知识提供给计算机是一个至今还没有人解决的难题。除了其理论上的重要性，研究者的项目也可能是解决这些问题的关键一步。

9626151 Beck ABSTRACT In this proposal the investigator outlines a new, probabilistic approach to positional games (i.e. board-games, or combinatorial games). The straightforward way to analyze a position is to examine all of its options and all the options of these options and all the options of the options of these options and all the.... The obvious difficulty is that this exhausting search through the game-tree takes an enormous amount of time even for very simple games (exponential running time in terms of the board-size). Note that the game-matrix approach, the set-up of traditional game theory, is much worse: usually requiring double exponential time. A desperate attempt to make up for the lack of time is to study the random walk on the game-tree. Now the basic idea of the probabilistic theory of the investigator is that the probabilistic analysis of the random walk (i.e. the random game) is often a tractable problem, and also what one has learned from this analysis can often be converted, via potential arguments (like resource counting with loss-probabilities), into deterministic optimal strategies. The probabilistic theory is basically a game-theoretic adaptation of the so-called Probabilistic Method in Combinatorics applied to hopelessly complicated games where algebraic and other exact methods fail to work. The surprising thing is that this desperate attempt turns out to be very successful for large, interesting classes of positional games. The main chapters of the proposal are: the foundations of positional games (a surprisingly non-trivial task), game-theoretic Ramsey theory, game-theoretic random graph theory, game-theoretic Lovasz Local Lemma, and applications in algorithms and complexity. Traditional game theory, i.e. von Neumann's theory, is basically the theory of games of incomplete information. It provides good insights to Economics, and many areas of social science (Management, Military Strategy, etc.). Similarly, one can expect many new applications from a successfu l theory of games of complete information (i.e. positional games). This is exactly what the investigator's proposal is all about. An extremely exciting aspect of studying positional games is that it might give a better understanding of how human intelligence works. It might have some impact on fundamental questions like whether human understanding is a computational or a non-computational process. Note that in Japan there are several "perfect" players who, when playing first, can consistently win Go-Moku (5-in-a-row on the 19 by 19 Go board), but nobody can turn these heuristics into precise arguments. Similarly, 6-in-a-row on a sufficiently large board between two reasonably good players is always a boring draw-game, but again we cannot precisely explain why. Or what is the reason that Go-playing computer programs are nowhere close to the best human players? These are just three of many examples where the human mind "knows" something beyond rigorous mathematics. One more thing: in contrast to Go, the best Chess-playing computer programs have now reached the level of human Grandmasters. But there is a basic difference. Computer programs examine millions of positions before deciding what to do next. On the other hand, even the best Grandmasters do not search more than 100 positions per move. In human Chess, pattern recognition plays a more important role than search. How to supply this human knowledge to a computer is a puzzle that no one has solved yet. Beside its theoretical importance, the investigator's project could be a crucial step toward the solution of these questions, too.