Game-Theoretic Variance

研究者概述了如何继续他在之前的建议中开始的工作，以开发一种新的概率方法来研究位置游戏（即组合棋盘游戏）。分析一个头寸最直接的方法就是检查它的所有选项这些选项的所有选项以及这些选项的所有选项，以此类推。这种彻底搜索游戏树的明显困难在于，它需要耗费大量时间。弥补时间不足的一种尝试是研究游戏树上的随机游走，即两个玩家都随机玩的随机游戏。其基本思想是，随机博弈的统计分析可以通过潜在参数有效地转化为确定性最优策略。它基本上是对所谓的组合学中的概率方法（“Erdos理论”）的博弈论改编，应用于毫无希望的复杂游戏，在这些游戏中，精确的方法不起作用。令人惊讶的是，这种“孤注一掷”的尝试竟然在大型有趣的位置游戏中取得了成功。研究者在之前的提案中提出了一种公平博弈的“博弈论第二矩方法”，并将其应用于解决图和超图博弈中长期存在的开放问题。另一个巨大的成功是他对“博弈论独立性”（即博弈论洛瓦兹局部引理）的研究。在这个方向上，研究者取得了一个重要的部分结果，从而解决了长期存在的关于多维井字游戏的Hales-Jewett猜想。在这个新的提议中，研究者的目标是对他的博弈论第二矩方法进行有偏见的推广，这将在“博弈论随机图论”中创造一个突破。此外，研究者希望继续他的工作，以证明一个完美的博弈论模拟概率洛瓦兹局部引理。传统博弈论关注的是不完全信息博弈。传统理论为经济学和许多社会科学领域（管理学、军事战略等）提供了很好的见解。一个成功的完全信息博弈理论至少可以带来同样多的新应用。位置游戏，即象棋和围棋等两名玩家的“纯冲突”技巧游戏，是完全信息游戏中最自然、最有趣的子类。研究位置游戏的一个非常令人兴奋的方面是，它们提供了对人类智力如何运作的独特见解。它涉及一些基本问题，比如人类的理解是一个计算过程还是一个非计算过程。或者更具体的问题，比如理解为什么（比如说）计算机程序与最好的人类棋手相差甚远。与围棋相比，最好的国际象棋程序已经达到了人类大师的水平。游戏计算机程序在决定下一步行动之前，会检查数百万个位置。另一方面，即使是最优秀的大师也不会在每一步棋中搜索超过50个位置。在人类国际象棋中，特别是在人类围棋中，模式识别扮演着比搜索重要得多的角色。如何将人类的知识提供给计算机是一个至今无人能解的谜题。这一提议的一个更具体的理论意义是，它以一种意想不到的方式将看似分离的概率论、组合学和博弈论拉近了距离。

The investigator outlines how to continue his work started in the prior proposal to develop a new, probabilistic approach to positional games (i.e. combinatorial board 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 so on. The obvious difficulty of this exhaustive search through the game-tree is that it takes enormous amount of time. An attempt to make up for the lack of time is to study the random walk on the game-tree, i.e. the randomized game where both players play randomly. The basic idea is that the statistical analysis of the randomized game can be efficiently converted via potential arguments into deterministic optimal strategies. It is basically a game-theoretic adaptation of the so-called Probabilistic Method in Combinatorics ("Erdos theory") applied to hopelessly complicated games where the exact methods fail to work. It is very surprising how this ``desperate'' attempt turns out to be successful for large, interesting classes of positional games. Carrying out the program sketched in his prior proposal the investigator have developed a "game theoretic second moment method" for fair games, and applied it to solve long-standing open problems in graph and hypergraph games. Another great success was his work toward "game-theoretic independence" (i.e. game theoretic Lovasz Local Lemma). In this direction the investigator achieved an important partial result, which led to the solution of the long-standing Hales-Jewett conjecture about the multi-dimensional Tic-Tac-Toe game. In this new proposal the investigator aims for a biased generalization of his game-theoretic second moment method, which would create a breakthrough in "game-theoretic random graph theory". Also the investigator wants to continue his work to prove a perfect game-theoretic analogue of the probabilistic Lovasz Local Lemma.Traditional game theory focuses on games of incomplete information. The traditional theory provided good insights to Economics, and many areas of social science (Management, Military Strategy, etc.). One can expect at least as many new applications from a successful theory of games of complete information. Positional games, i.e. 2-player "pure conflict" games of skill like Chess and Go, form the most natural and interesting subclass of games of complete information. An extremely exciting aspect of studying positional games is that they give unique insight to how human intelligence works. It concerns fundamental questions like whether human understanding is a computational or non-computational process. Or more specific problems like to understand why (say) Go playing computer programs are nowhere close to the best human players. In contrast to Go, the best Chess-playing programs have reached the level of human Grandmasters. Game-playing 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 50 positions per move. In human Chess and particularly in human Go pattern recognition plays a far more important role than search. How to supply this human knowledge to a computer is a puzzle that no one has solved yet. A more concrete theoretical significance of this proposal is that it brings the seemingly separated subjects of Probability Theory, Combinatorics, and Game Theory closer to each other in an unexpected way.