AF:Small: Transformation of Mathematical Games: Quantum Inspiration

AF:Small：数学游戏的转变：量子灵感

• 批准号: 2308744
• 负责人: Shanghua Teng
• 金额: $ 19.27万
• 依托单位: University of Southern California
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2023
• 资助国家: 美国
• 起止时间: 2023-06-01 至 2026-05-31
• 项目状态: 未结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=2308744&HistoricalAwards=false
• 关键词: AF; Small; Transformation; Mathematical; Games

This research project seeks to understand deep strategic reasoning in mathematical board games. These games -- like their real-world counterparts: Tic-Tac-Toe, Chess, GO -- usually have elegant and succinct rulesets. These rulesets are often inspired by practical phenomena, and distill fundamental mathematical structures from graph theory, logic, topology, etc. As a result, research on them is highly interdisciplinary. Mathematical board games require deep strategic reasoning (about long alternation down to the last level of their game trees), making them more challenging in general than traditional decision/optimization problems. Thus, mathematical board games are also deeply connected with a wide range of computational complexity classes. This research project will develop theory and algorithms for a new subarea of mathematical board games where quantum-inspired principles based on superposition and entanglement are incorporated into game rulesets. The quantum-inspired transformation introduces intriguing strategic options and hence impacts the outcome and complexity of these games. This research project also involves the mentorship of PhD students. The recreational nature of mathematical games in this project will also help engage students of all levels (including K-12) to broaden their participation in mathematical and computational thinking.The specific goals of this project are to characterize the impact of quantum-inspired rules on a broad family of combinatorial games. At a high level, the quantum-inspired transformation can be viewed as an operator on mathematical games, introducing superpositions of “classical moves.” Mathematically, it expands the strategic-decision space by creating a superposition of “entangled classical game positions,” introducing “nondeterminism” into traditional games. Philosophically, the new framework models real-world online decision phenomena in which multiple future scenarios might still be achievable. However, the decision in each step may expand possibilities while eliminating others. In other words, the consequence of each decision is multifaceted. The impact of this operator to the complexity of the games is highly nonmonotonic, which provides a rich subject for complexity-theoretical characterization. In addition, another goal of this research is to explore other forms of nondeterminism in mathematical games and expand a matching-theory-based algorithmic technique to these deep-logic strategic decision problems.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.

该研究项目旨在了解数学棋盘游戏中的深层战略推理，就像现实世界中的井字棋、国际象棋、围棋一样，这些游戏通常具有优雅而简洁的规则集，这些规则集通常受到实用的启发。现象，并从图论、逻辑、拓扑等中提炼出基本的数学结构。因此，对它们的研究是高度跨学科的，需要深入的策略推理（关于游戏树的最后一级的长期交替），让他们更加因此，数学棋盘游戏也与广泛的计算复杂性类别密切相关，该研究项目将为受量子启发的数学棋盘游戏新领域开发理论和算法。基于叠加和纠缠的原理被纳入游戏规则集中，量子启发的转换引入了有趣的策略选择，从而影响了这些游戏的结果和复杂性。该项目还将有助于吸引各个级别的学生（包括 K-12）以扩大他们对数学和计算思维的参与。该项目的具体目标是描述量子启发规则对广泛的组合游戏家族的影响。可以被视为数学博弈的算子，引入了“经典走法”的叠加。从数学上来说，它通过创建“纠缠的经典博弈位置”的叠加来扩展战略决策空间，将“非决定论”引入到传统博弈中。从哲学上讲，新框架模拟了现实世界的在线决策现象，其中多种未来场景仍然是可以实现的，但是，每个步骤中的决策都可能会扩大可能性，同时消除其他决策的影响。该算子对博弈复杂性的影响是高度非单调的，这为复杂性理论表征提供了丰富的主题。此外，本研究的另一个目标是探索数学博弈中其他形式的非确定性并扩展数学博弈的不确定性。基于理论的算法技术来解决这些深层逻辑战略决策问题。该奖项反映了 NSF 的法定使命，并通过使用基金会的智力价值和更广泛的影响审查标准进行评估，被认为值得支持。