AF:Small: Transformation of Mathematical Games: Quantum Inspiration

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

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.