Abstract
In the commercial one-player game Lights Out™ a grid of lights is randomly generated with some lights on and some lights off. The player can press a light to flip its on/off state as well as the state of its neighbors. Toggle seeks to transform Lights Out™ into a variety of impartial two-player games. Two players take turns toggling the on/off state of lights in an attempt to leave the other player with no available legal moves. We analyze Toggle on various finite simple graphs and use impartial game theory to determine which player has a winning strategy given an initial Toggle configuration. Finally, we prove that determining the winning player given an arbitrary Toggle configuration is PSpace-complete.
- Peer Researchers
- Nathan Hurtig
- Djenaba Djeob
- Mentors
- Dr. Eugene Fiorini
- Dr. Andrew Woldar
- Dr. Patrick Cesarz
Demo
I wrote a small demo site for path graphs.
Presentations
Publications
- A363934 Table read by ascending antidiagonals. T(n,k) is the Sprague-Grundy value for the Heat Toggle game played on an n X k grid where each vertex has initial weight 1.
- A364489 Values of n for which the Sprague-Grundy value of Heat-Charge Toggle on an (n+2)-vertex path with initial weights -1,1^n,-1 is evil for odd n or odious for even n.
- A364503 Sprague-Grundy values for Heat-Charge Toggle on paths from A364489 where paths with an even number of vertices are odious, or paths with an odd number of vertices are evil.