From a181759e4a108c35fcf6898abbf17f2a424d85dc Mon Sep 17 00:00:00 2001 From: Jean-Pierre Appel Date: Mon, 25 Dec 2023 17:17:09 -0500 Subject: rewrite content and config --- content/research/toggle.md | 43 +++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 43 insertions(+) create mode 100644 content/research/toggle.md (limited to 'content/research/toggle.md') diff --git a/content/research/toggle.md b/content/research/toggle.md new file mode 100644 index 0000000..6e29ce0 --- /dev/null +++ b/content/research/toggle.md @@ -0,0 +1,43 @@ +--- +title: "Exploring Toggle Games on Graphs" +date: 2023-12-17T23:27:37-05:00 +summary: "Study of *Toggle*, an impartial game" +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. +categories: +- "Moravian REU 2023" +tags: +- "Combinatorics" +- "Game Theory" +- "Computational Complexity" +--- + +Peer Researchers +: [Nathan Hurtig](https://nathanhurtig.com/) +: *Djenaba Djeob* + +Mentors +: Dr. Eugene Fiorini +: Dr. Andrew Woldar +: Dr. Patrick Cesarz + +{{< presentations >}} +## Presentations + +* Poster + * [SACNAS NDiSTEM 2023](/research/posters/toggle_ndistem23.pdf) +{{< /presentations >}} + + +{{< publications >}} +## Publications + +* [A363934](https://oeis.org/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](https://oeis.org/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](https://oeis.org/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. +{{< /publications >}} -- cgit v1.2.3