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 analysis shows that the game Paint Can is intractable and also yields a new intractable game, Blackout . We present web-playable versions of both games.

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).

Chapel is a programming language being developed for high-performance applications. It is well suited for teaching parallelism in a wide variety of undergrad courses. Chapel is easy to learn since it supports a low-overhead style like a scripting language as well as a full OO style. It is concise, needing a single keyword to launch an asynchronous task, run a parallel loop, or perform a reduction. This helps undergrads focus on the main point of examples and lets them quickly try different parallel algorithms. It is also versatile, usable on both multicore systems and clusters. In this workshop, attendees will learn basics of Chapel, complete hands-on exercises, and see possible uses in algorithms, programming languages, and parallel programming courses. Laptop with SSH client required.