AF:Small: Transformation of Mathematical Games: Quantum Inspiration

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

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.