Game-Theoretic Variance

博弈论方差

• 批准号: 0103811
• 负责人: Jozsef Beck
• 金额: $ 8.85万
• 依托单位: Rutgers University New Brunswick
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2001
• 资助国家: 美国
• 起止时间: 2001-07-15 至 2006-06-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0103811&HistoricalAwards=false
• 关键词: Game; Theoretic; Variance

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.

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