AF:Small: Transformation of Mathematical Games: Quantum Inspiration

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.