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 from 1993 that Undirected Geography is polynomial-time solvable. By distilling to a simple reduction, our proof further establishes a dichotomy theorem, providing a sharp "phase transition to intractability": The Grundy value of the game over any degree-three graph is polynomial-time computable, but over degree-four graphs-even when planar & bipartite-is PSPACE-hard. Additionally, we show, for the first time, how to construct Undirected Geography instances with Grundy value *n and size polynomial in n. We strengthen a result from 1981 showing that sums of tractable partisan games are PSPACE-complete in two fundamental ways. First, we extend the result to impartial games, a strict subset of partisan. Second, the 1981 construction is not built from a natural ruleset, instead using a long sum of tailored short-depth game positions. We use the sum of two Undirected Geography positions. Our result also has computational ramification to Sprague-Grundy Theory (1930s) which shows that the Grundy value of the disjunctive sum of any two impartial games can be computed-in polynomial time-from their Grundy values. In contrast, we prove that, assuming PSPACE is not equal to P, there is no general polynomial-time method to summarize two polynomial-time solvable impartial games to efficiently solve their disjunctive sum. Our proof enables us to answer another long-term structural question in the field. We establish the following complexity independence: Unless \mathrm{P}= \text{PSPACE} , there is no polynomial-time reduction from winnability in misere-play setting to the Grundy value, and vice versa (in Undirected Geography).
The concept of nimbers—a.k.a. Grundy-values or nim-values—is fundamental to combinatorial game theory. Beyond the winnability, nimbers provide a complete characterization of strategic interactions ...among impartial games in disjunctive sums. In this paper, we consider nimber-preserving reductions among impartial games, which enhance the winnability-preserving reductions in traditional computational characterizations of combinatorial games. We prove that Generalized Geography is complete for the natural class, IP, of polynomially-short impartial rulesets, under polynomial-time nimber-preserving reductions. We refer to this notion of completeness as Sprague-Grundy-completeness. In contrast, we also show that not every PSPACE-complete ruleset in IP is Sprague-Grundy-complete for IP.
By viewing every impartial game as an encoding of its nimber—a succinct game secret richer than its winnability alone—our technical result establishes the following striking cryptography-inspired homomorphic theorem: Despite the PSPACE-completeness of nimber computation for IP, there exists a polynomial-time algorithm to construct, for any pair of games G1,G2 in IP, a Generalized Geography game G satisfying:nimber(G)=nimber(G1)⊕nimber(G2).
We replicated and expanded on previous work about how well students learn dynamic programming, a difficult topic for students in algorithms class. Their study interviewed a number of students at one ...university in a single term. We recruited a larger sample size of students, over several terms, in both large public and private universities as well as liberal arts colleges.
Our aim was to investigate whether the results of the previous work generalized to other universities and also to larger groups of students.
We interviewed students who completed the relevant portions of their algorithms class, asking them to solve problems. We observed the students' problem solving process to glean insight into how students tackle these problems.
We found that students generally struggle in three ways, "technique selection," "recurrence building," and "inefficient implementations." We then explored these themes and specific misconceptions qualitatively. We observed that the misconceptions found by the previous work generalized to the larger sample of students.
Our findings demonstrate areas in which students struggle, paving way for better algorithms education by means of identifying areas of common weakness to draw the focus of instructors.
In this paper, we give simple NP-hardness reductions for three popular video games. The first is Baba Is You, an award winning 2D block puzzle game with the key premise being the ability to rewrite ...the rules of the game. The second is Fez, a puzzle platformer whose main draw is the ability to swap between four different 2-dimensional views of the player's position. The final is Catherine, a 3-dimensional puzzle game where the player must climb a tower of rearrangeable blocks.
The concept of nimbers--a.k.a. Grundy-values or nim-values--is fundamental to combinatorial game theory. Nimbers provide a complete characterization of strategic interactions among impartial games in ...their disjunctive sums as well as the winnability. In this paper, we initiate a study of nimber-preserving reductions among impartial games. These reductions enhance the winnability-preserving reductions in traditional computational characterizations of combinatorial games. We prove that Generalized Geography is complete for the natural class, \(\cal{I}^P\) , of polynomially-short impartial rulesets under nimber-preserving reductions, a property we refer to as Sprague-Grundy-complete. In contrast, we also show that not every PSPACE-complete ruleset in \(\cal{I}^P\) is Sprague-Grundy-complete for \(\cal{I}^P\) . By considering every impartial game as an encoding of its nimber, our technical result establishes the following striking cryptography-inspired homomorphic theorem: Despite the PSPACE-completeness of nimber computation for \(\cal{I}^P\) , there exists a polynomial-time algorithm to construct, for any pair of games \(G_1\), \(G_2\) of \(\cal{I}^P\) , a prime game (i.e. a game that cannot be written as a sum) \(H\) of \(\cal{I}^P\) , satisfying: nimber(\(H\)) = nimber(\(G_1\)) \(\oplus\) nimber(\(G_2\)).
We settle two long-standing complexity-theoretical questions-open since 1981 and 1993-in combinatorial game theory (CGT). We prove that the Grundy value (a.k.a. nim-value, or nimber) of Undirected ...Geography is PSPACE-complete to compute. This exhibits a stark contrast with a result from 1993 that Undirected Geography is polynomial-time solvable. By distilling to a simple reduction, our proof further establishes a dichotomy theorem, providing a "phase transition to intractability" in Grundy-value computation, sharply characterized by a maximum degree of four: The Grundy value of Undirected Geography over any degree-three graph is polynomial-time computable, but over degree-four graphs-even when planar and bipartite-is PSPACE-hard. Additionally, we show, for the first time, how to construct Undirected Geography instances with Grundy value \(\ast n\) and size polynomial in n. We strengthen a result from 1981 showing that sums of tractable partisan games are PSPACE-complete in two fundamental ways. First, since Undirected Geography is an impartial ruleset, we extend the hardness of sums to impartial games, a strict subset of partisan. Second, the 1981 construction is not built from a natural ruleset, instead using a long sum of tailored short-depth game positions. We use the sum of two Undirected Geography positions to create our hard instances. Our result also has computational implications to Sprague-Grundy Theory (1930s) which shows that the Grundy value of the disjunctive sum of any two impartial games can be computed-in polynomial time-from their Grundy values. In contrast, we prove that assuming PSPACE \(\neq\) P, there is no general polynomial-time method to summarize two polynomial-time solvable impartial games to efficiently solve their disjunctive sum.
We investigate the combinatorial game Slime Trail.This game is played on a graph with a starting piece in a node. Each player's objective is to reach one of their own goal nodes. Every turn the ...current player moves the piece and deletes the node they came from. We show that the game is PSPACE-complete when played on a planar graph.
In this paper, we study a colorful, impartial combinatorial game played on a two-dimensional grid, Transverse Wave. We are drawn to this game because of its apparent simplicity, contrasting ...intractability, and intrinsic connection to two other combinatorial games, one inspired by social influence and another inspired by quantum superpositions. More precisely, we show that Transverse Wave is at the intersection of social-influence-inspired Friend Circle and superposition-based Demi-Quantum Nim. Transverse Wave is also connected with Schaefer's logic game Avoid True. In addition to analyzing the mathematical structures and computational complexity of Transverse Wave, we provide a web-based version of the game, playable at https://turing.plymouth.edu/~kgb1013/DB/combGames/transverseWave.html. Furthermore, we formulate a basic network-influence inspired game, called Demographic Influence, which simultaneously generalizes Node-Kyles and Demi-Quantum Nim (which in turn contains as special cases Nim, Avoid True, and Transverse Wave). These connections illuminate the lattice order, induced by special-case/generalization relationships over mathematical games, fundamental to both the design and comparative analyses of combinatorial games.
In this paper, we address a natural question at the intersection of combinatorial game theory and computational complexity: "Can a sum of simple tepid games in canonical form be intractable?" To ...resolve this fundamental question, we consider superstars, positions first introduced in Winning Ways where all options are nimbers. Extending Morris' classic result with hot games to tepid games, we prove that disjunctive sums of superstars are intractable to solve. This is striking as sums of nimbers can be computed in linear time. Our analyses also lead to a family of elegant board games with intriguing complexity, for which we present web-playable versions of the rulesets described within.
Recently, a standardized framework was proposed for introducing quantum-inspired moves in mathematical games with perfect information and no chance. The beauty of quantum games-succinct in ...representation, rich in structures, explosive in complexity, dazzling for visualization, and sophisticated for strategic reasoning-has drawn us to play concrete games full of subtleties and to characterize abstract properties pertinent to complexity consequence. Going beyond individual games, we explore the tractability of quantum combinatorial games as whole, and address fundamental questions including: Quantum Leap in Complexity: Are there polynomial-time solvable games whose quantum extensions are intractable? Quantum Collapses in Complexity: Are there PSPACE-complete games whose quantum extensions fall to the lower levels of the polynomial-time hierarchy? Quantumness Matters: How do outcome classes and strategies change under quantum moves? Under what conditions doesn't quantumness matter? PSPACE Barrier for Quantum Leap: Can quantum moves launch PSPACE games into outer polynomial space We show that quantum moves not only enrich the game structure, but also impact their computational complexity. In settling some of these basic questions, we characterize both the powers and limitations of quantum moves as well as the superposition of game configurations that they create. Our constructive proofs-both on the leap of complexity in concrete Quantum Nim and Quantum Undirected Geography and on the continuous collapses, in the quantum setting, of complexity in abstract PSPACE-complete games to each level of the polynomial-time hierarchy-illustrate the striking computational landscape over quantum games and highlight surprising turns with unexpected quantum impact. Our studies also enable us to identify several elegant open questions fundamental to quantum combinatorial game theory (QCGT).
PDF
