Game-Theoretic Variance
Game-Theoretic Variance
批准号:
0103811
负责人:
Jozsef Beck
金额:
$8.85万
依托单位国家:
美国
项目类别:
Continuing Grant
财政年份:
2001
资助国家:
美国
项目状态:
已结题
起止时间:
2001-07-15 至 2006-06-30
中文摘要
研究人员概述了如何继续他在先前提案中开始的工作,以开发一种新的、概率的方法来处理位置游戏(即组合棋盘游戏)。分析头寸的直接方法是检查它的所有期权和这些期权的所有期权,以及这些期权的所有期权等等。在博弈树中进行这种穷尽搜索的明显困难在于它需要大量的时间。为了弥补时间的不足,一种尝试是研究博弈树上的随机游走,即两个参与者随机玩的随机游戏。其基本思想是,随机化博弈的统计分析可以通过势参数有效地转化为确定性的最优策略。它基本上是对组合学中所谓的概率方法(“鄂尔多斯理论”)的博弈论改编,适用于精确方法无法奏效的极其复杂的游戏。非常令人惊讶的是,这种“绝望”的尝试在大型、有趣的位置游戏中竟然取得了成功。根据他先前提出的方案,研究人员提出了一种公平博弈的“博弈论二阶矩方法”,并将其应用于解决图形和超图博弈中长期存在的公开问题。另一个巨大的成功是他对“博弈论独立性”(即博弈论Lovasz局部引理)的研究。在这个方向上,研究人员获得了一个重要的部分结果,这导致了长期存在的关于多维Tic-Tac-Toe博弈的Hales-Juett猜想的解。在这个新的建议中,研究人员旨在对他的博弈论二阶矩方法进行有偏向的推广,这将在“博弈论随机图理论”中创造一个突破。此外,研究人员还想继续他的工作,以证明一个完美的博弈论类似的概率洛瓦兹局部引理。传统的博弈论关注的是不完全信息的博弈。传统理论为经济学和社会科学的许多领域(管理学、军事战略等)提供了很好的见解。人们可以预期,一个成功的完全信息博弈理论至少会有同样多的新应用。位置游戏,即像国际象棋和围棋这样的两人“纯冲突”技巧游戏,构成了完全信息游戏中最自然和最有趣的子类。研究位置游戏的一个非常令人兴奋的方面是,它们为人类智力是如何工作的提供了独特的见解。它涉及一些基本问题,比如人类的理解是计算性的还是非计算性的。或者更具体的问题喜欢理解为什么(比方说)玩计算机程序与最好的人类玩家相去甚远。与围棋形成对比的是,最好的象棋程序已经达到了人类特级大师的水平。玩游戏的计算机程序在决定下一步做什么之前,会检查数百万个位置。另一方面,即使是最好的特级大师每次移动也不会搜索超过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.
期刊论文(0)
专著(0)
科研奖励(0)
会议论文
Tic-Tac-Toe Theory-An Escape From The Combinatorial Chaos
-
批准号:0701432
-
项目类别:Continuing Grant
-
资助金额:$14.82万
-
财政年份:2007
-
负责人:Jozsef Beck
-
依托单位:
Positional Games and Random Structures--A mathematical paradox
-
批准号:0406597
-
项目类别:Standard Grant
-
资助金额:$11.2万
-
财政年份:2004
-
负责人:Jozsef Beck
-
依托单位:
A Probabilistic Theory of Positional Games
-
批准号:9626151
-
项目类别:Continuing Grant
-
资助金额:$12.0万
-
财政年份:1996
-
负责人:Jozsef Beck
-
依托单位:
Mathematical Sciences: Probabilistic Diophantine Approximation
-
批准号:9304280
-
项目类别:Standard Grant
-
资助金额:$8.88万
-
财政年份:1993
-
负责人:Jozsef Beck
-
依托单位:
Mathematical Sciences: Super Irregularity and Ramsey Theory
-
批准号:9106631
-
项目类别:Continuing Grant
-
资助金额:$5.36万
-
财政年份:1991
-
负责人:Jozsef Beck
-
依托单位:
海外基金