Shang‐Hua Teng

Winning the War by (Strategically) Losing Battles: Settling the Complexity of Grundy-Values in Undirected Geography

2022

We settle two long-standing complexity-theoretical questions—open since 1981 and 1993—in combinatorial game theory (CGT). We prove that the Grundy value of Undirected Geography is PSPACE-complete to compute. This exhibits a stark contrast with a result …

“Intelligent Heuristics Are the Future of Computing”

2023 · ACM Transactions on Intelligent Systems and Technology

Back in 1988, the partial game trees explored by computer chess programs were among the largest search structures in real-world computing. Because the game tree is too large to be fully evaluated, chess programs must …