diff options
| author | Jean-Pierre Appel <jeanpierre.appel01@gmail.com> | 2023-12-25 17:17:09 -0500 |
|---|---|---|
| committer | Jean-Pierre Appel <jeanpierre.appel01@gmail.com> | 2023-12-25 17:17:09 -0500 |
| commit | a181759e4a108c35fcf6898abbf17f2a424d85dc (patch) | |
| tree | 6b8d7454db70a1a8dec81fb138e7085e6541d9d6 /content/research/toggle.md | |
| parent | 5e24ef726bf10fac4ad24cee27b9b1fa796cd6eb (diff) | |
rewrite content and config
Diffstat (limited to 'content/research/toggle.md')
| -rw-r--r-- | content/research/toggle.md | 43 |
1 files changed, 43 insertions, 0 deletions
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 >}} |
