A Probabilistic Theory of Positional Games
A Probabilistic Theory of Positional Games
批准号:
9626151
负责人:
Jozsef Beck
金额:
$12.0万
依托单位国家:
美国
项目类别:
Continuing Grant
财政年份:
1996
资助国家:
美国
项目状态:
已结题
起止时间:
1996-07-15 至 2000-06-30
中文摘要
9626151贝克摘要在本提案中,研究人员概述了位置游戏(即棋盘游戏或组合游戏)的一种新的概率方法。分析头寸的直接方法是检查它的所有期权和这些期权的所有期权,这些期权的所有期权和所有...显而易见的困难是,这种令人精疲力竭的游戏树搜索即使对于非常简单的游戏也要花费大量的时间(根据棋盘大小计算的指数运行时间)。请注意,传统博弈论的博弈矩阵法要糟糕得多:通常需要双指数时间。为了弥补时间的不足,一种不顾一切的尝试是研究博弈树上的随机游动。现在,研究者的概率理论的基本思想是,对随机游动(即随机博弈)的概率分析通常是一个容易处理的问题,并且人们从这种分析中学到的东西通常可以通过潜在的论点(比如具有损失概率的资源计数)转化为确定性的最优策略。概率理论基本上是组合数学中所谓的概率方法在博弈论上的改编,适用于代数和其他精确方法无法工作的极其复杂的游戏。令人惊讶的是,这种孤注一掷的尝试在大型、有趣的位置类游戏中非常成功。该提案的主要章节是:位置博弈的基础(一个令人惊讶的非平凡任务),博弈论Ramsey理论,博弈论随机图理论,博弈论Lovasz局部引理,以及在算法和复杂性中的应用。传统博弈论,即冯·诺伊曼的博弈论,本质上是不完全信息博弈论。它为经济学和社会科学的许多领域(管理学、军事战略等)提供了很好的见解。同样,L关于完全信息博弈(即位置博弈)的成功理论也将带来许多新的应用。这正是调查员的建议的全部内容。研究位置游戏的一个非常令人兴奋的方面是,它可能会更好地理解人类智力是如何工作的。它可能会对基本问题产生一些影响,比如人类的理解是计算性的还是非计算性的。请注意,在日本有几个“完美”的棋手,当他们下第一盘棋时,他们可以始终如一地赢得围棋-Moku(在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.
期刊论文(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
-
依托单位:
Game-Theoretic Variance
-
批准号:0103811
-
项目类别:Continuing Grant
-
资助金额:$8.85万
-
财政年份:2001
-
负责人: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
-
依托单位:
国内基金
海外基金
登录
查看更多内容
Research on Quantum Field Theory without a Lagrangian Description
-
批准号:24ZR1403900
-
项目类别:省市级项目
-
资助金额:--
-
批准年份:2024
-
负责人:SATOSHI NAWATA
-
依托单位:
基于isomorph theory研究尘埃等离子体物理量的微观动力学机制
-
批准号:12247163
-
项目类别:专项项目
-
资助金额:18.00万元
-
批准年份:2022
-
负责人:黄栋
-
依托单位:
Toward a general theory of intermittent aeolian and fluvial nonsuspended sediment transport
-
批准号:--
-
项目类别:--
-
资助金额:55万元
-
批准年份:2022
-
负责人:Thomas Pahtz
-
依托单位:
英文专著《FRACTIONAL INTEGRALS AND DERIVATIVES: Theory and Applications》的翻译
-
批准号:12126512
-
项目类别:数学天元基金项目
-
资助金额:12.0万元
-
批准年份:2021
-
负责人:李常品
-
依托单位:
基于Restriction-Centered Theory的自然语言模糊语义理论研究及应用
-
批准号:61671064
-
项目类别:面上项目
-
资助金额:65.0万元
-
批准年份:2016
-
负责人:史树敏
-
依托单位: