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的法定使命，并通过使用基金会的智力价值和更广泛的影响审查标准进行评估，被认为值得支持。