8 papers
Æquitas: Two-Player Counterfeit Coin Games
Kyle Burke, Tanya Khovanova, Joshua Lee +3
We discuss games involving a counterfeit coin. Given one counterfeit coin among a number of otherwise identical coins, two players with full knowledge of the fake coin take turns w…
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…
Single-Player and Two-Player Buttons & Scissors Games
Kyle Burke, Erik D. Demaine, Harrison Gregg +12
We study the computational complexity of the Buttons \& Scissors game and obtain sharp thresholds with respect to several parameters. Specifically we show that the game is NP-compl…