8 papers · 1 filter
A Tractability Gap Beyond Nim-Sums: It's Hard to Tell Whether a Bunch of Superstars Are Losers
Kyle Burke, Matthew Ferland, Svenja Huntemann +1
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 in…
Forced Capture Hnefatafl
Kyle Burke, Craig Tennenhouse
We define a new, partizan, loopy combinatorial game, Forced-Capture Hnefatafl, similar to Hnefatafl, except that players are forced to make capturing moves when available. We show…
Winning the War by (Strategically) Losing Battles: Settling the Complexity of Grundy-Values in Undirected Geography
Kyle Burke, Matthew Ferland, Shanghua Teng
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 nimbe…
Transverse Wave: an impartial color-propagation game inspired by Social Influence and Quantum Nim
Kyle Burke, Matthew Ferland, Shanghua Teng
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, co…
Quantum Combinatorial Games: Structures and Computational Complexity
Kyle Burke, Matthew Ferland, Shang-Hua Teng
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-suc…
Computational Properties of Slime Trail
Matthew Ferland, Kyle Burke
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. E…