A Probabilistic Theory of Positional Games

位置博弈的概率理论

基本信息

  • 批准号:
    9626151
  • 负责人:
  • 金额:
    $ 12万
  • 依托单位:
  • 依托单位国家:
    美国
  • 项目类别:
    Continuing Grant
  • 财政年份:
    1996
  • 资助国家:
    美国
  • 起止时间:
    1996-07-15 至 2000-06-30
  • 项目状态:
    已结题

项目摘要

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

项目成果

期刊论文数量(0)
专著数量(0)
科研奖励数量(0)
会议论文数量(0)
专利数量(0)

数据更新时间:{{ journalArticles.updateTime }}

{{ item.title }}
{{ item.translation_title }}
  • DOI:
    {{ item.doi }}
  • 发表时间:
    {{ item.publish_year }}
  • 期刊:
  • 影响因子:
    {{ item.factor }}
  • 作者:
    {{ item.authors }}
  • 通讯作者:
    {{ item.author }}

数据更新时间:{{ journalArticles.updateTime }}

{{ item.title }}
  • 作者:
    {{ item.author }}

数据更新时间:{{ monograph.updateTime }}

{{ item.title }}
  • 作者:
    {{ item.author }}

数据更新时间:{{ sciAawards.updateTime }}

{{ item.title }}
  • 作者:
    {{ item.author }}

数据更新时间:{{ conferencePapers.updateTime }}

{{ item.title }}
  • 作者:
    {{ item.author }}

数据更新时间:{{ patent.updateTime }}

Jozsef Beck其他文献

Integral approximation sequences
  • DOI:
    10.1007/bf02591800
  • 发表时间:
    1984-09-01
  • 期刊:
  • 影响因子:
    2.500
  • 作者:
    Jozsef Beck;Joel Spencer
  • 通讯作者:
    Joel Spencer

Jozsef Beck的其他文献

{{ item.title }}
{{ item.translation_title }}
  • DOI:
    {{ item.doi }}
  • 发表时间:
    {{ item.publish_year }}
  • 期刊:
  • 影响因子:
    {{ item.factor }}
  • 作者:
    {{ item.authors }}
  • 通讯作者:
    {{ item.author }}

{{ truncateString('Jozsef Beck', 18)}}的其他基金

Tic-Tac-Toe Theory-An Escape From The Combinatorial Chaos
井字棋理论——摆脱组合混沌
  • 批准号:
    0701432
  • 财政年份:
    2007
  • 资助金额:
    $ 12万
  • 项目类别:
    Continuing Grant
Positional Games and Random Structures--A mathematical paradox
位置博弈与随机结构--一个数学悖论
  • 批准号:
    0406597
  • 财政年份:
    2004
  • 资助金额:
    $ 12万
  • 项目类别:
    Standard Grant
Game-Theoretic Variance
博弈论方差
  • 批准号:
    0103811
  • 财政年份:
    2001
  • 资助金额:
    $ 12万
  • 项目类别:
    Continuing Grant
Mathematical Sciences: Probabilistic Diophantine Approximation
数学科学:概率丢番图近似
  • 批准号:
    9304280
  • 财政年份:
    1993
  • 资助金额:
    $ 12万
  • 项目类别:
    Standard Grant
Mathematical Sciences: Super Irregularity and Ramsey Theory
数学科学:超不规则性和拉姆齐理论
  • 批准号:
    9106631
  • 财政年份:
    1991
  • 资助金额:
    $ 12万
  • 项目类别:
    Continuing Grant

相似国自然基金

Research on Quantum Field Theory without a Lagrangian Description
  • 批准号:
    24ZR1403900
  • 批准年份:
    2024
  • 资助金额:
    0.0 万元
  • 项目类别:
    省市级项目
基于isomorph theory研究尘埃等离子体物理量的微观动力学机制
  • 批准号:
    12247163
  • 批准年份:
    2022
  • 资助金额:
    18.00 万元
  • 项目类别:
    专项项目
Toward a general theory of intermittent aeolian and fluvial nonsuspended sediment transport
  • 批准号:
  • 批准年份:
    2022
  • 资助金额:
    55 万元
  • 项目类别:
英文专著《FRACTIONAL INTEGRALS AND DERIVATIVES: Theory and Applications》的翻译
  • 批准号:
    12126512
  • 批准年份:
    2021
  • 资助金额:
    12.0 万元
  • 项目类别:
    数学天元基金项目
基于Restriction-Centered Theory的自然语言模糊语义理论研究及应用
  • 批准号:
    61671064
  • 批准年份:
    2016
  • 资助金额:
    65.0 万元
  • 项目类别:
    面上项目

相似海外基金

Problems in Ramsey theory
拉姆齐理论中的问题
  • 批准号:
    2582036
  • 财政年份:
    2025
  • 资助金额:
    $ 12万
  • 项目类别:
    Studentship
CAREER: Structured Minimax Optimization: Theory, Algorithms, and Applications in Robust Learning
职业:结构化极小极大优化:稳健学习中的理论、算法和应用
  • 批准号:
    2338846
  • 财政年份:
    2024
  • 资助金额:
    $ 12万
  • 项目类别:
    Continuing Grant
EAGER: Generalizing Monin-Obukhov Similarity Theory (MOST)-based Surface Layer Parameterizations for Turbulence Resolving Earth System Models (ESMs)
EAGER:将基于 Monin-Obukhov 相似理论 (MOST) 的表面层参数化推广到湍流解析地球系统模型 (ESM)
  • 批准号:
    2414424
  • 财政年份:
    2024
  • 资助金额:
    $ 12万
  • 项目类别:
    Standard Grant
Conference: 9th Lake Michigan Workshop on Combinatorics and Graph Theory
会议:第九届密歇根湖组合学和图论研讨会
  • 批准号:
    2349004
  • 财政年份:
    2024
  • 资助金额:
    $ 12万
  • 项目类别:
    Standard Grant
REU Site: Computational Number Theory
REU 网站:计算数论
  • 批准号:
    2349174
  • 财政年份:
    2024
  • 资助金额:
    $ 12万
  • 项目类别:
    Continuing Grant
Testing Theorems in Analytic Function Theory, Harmonic Analysis and Operator Theory
解析函数论、调和分析和算子理论中的检验定理
  • 批准号:
    2349868
  • 财政年份:
    2024
  • 资助金额:
    $ 12万
  • 项目类别:
    Standard Grant
Conference: PDE in Moab: Advances in Theory and Application
会议:摩押偏微分方程:理论与应用的进展
  • 批准号:
    2350128
  • 财政年份:
    2024
  • 资助金额:
    $ 12万
  • 项目类别:
    Standard Grant
Conference: Arithmetic quantum field theory
会议:算术量子场论
  • 批准号:
    2400553
  • 财政年份:
    2024
  • 资助金额:
    $ 12万
  • 项目类别:
    Standard Grant
Spheres of Influence: Arithmetic Geometry and Chromatic Homotopy Theory
影响范围:算术几何和色同伦理论
  • 批准号:
    2401472
  • 财政年份:
    2024
  • 资助金额:
    $ 12万
  • 项目类别:
    Continuing Grant
Wonderful Varieties, Hyperplane Arrangements, and Poisson Representation Theory
奇妙的品种、超平面排列和泊松表示论
  • 批准号:
    2401514
  • 财政年份:
    2024
  • 资助金额:
    $ 12万
  • 项目类别:
    Continuing Grant
{{ showInfoDetail.title }}

作者:{{ showInfoDetail.author }}

知道了