Structure, Algorithmic, and Complexity-Theoretic Analyses of Misère Combinatorial Games

Prashanth Prabhala

Dec 2024 · Prashanth Prabhala

About this ebook

This work, written by Prashanth Prabhala, is a focused monograph that guides you from the foundations of impartial game theory into the intricate world of misère play. This manuscript begins with a clear review of positions under normal‑play and the Sprague–Grundy framework, later unveiling the unexpected twists that arise when “last move loses” replaces “last move wins”.

At its heart lies a streamlined proof of the Misère Nim Theorem, and a C++14 implementation that validates every theoretical claim against concrete test cases. Beyond Nim, the paper explores algebraic structures and equivalence relations unique to misère sums.

This paper balances rigorous definitions and inductive proofs with algorithmic insights, making it ideal for mathematicians seeking a deep dive into combinatorial game theory, as well as researchers building automated analysis tools. Along the way, you’ll find illustrative gameplay tables and pointers to open problems, guaranteed to be an interesting read!

About the author

Prashanth Prabhala (b. 2008) is a computer scientist and machine learning researcher. Particularly interested in solving real-world issues, he has published research on mathematics and applied artificial intelligence in Elsevier and IEEE journals, etc. He is also the founder and CEO of ExpertiseNPO, a nonprofit initiative he started to educate students alongside invited industry experts. He started ExpertiseNPO in 2022 due to his passion for STEM topics and to empower students to explore in a free learning space. Currently a junior at Irvington High School, he is excited about sharing knowledge! His hobbies include competitive programming - earning USACO Platinum and USAPhO medals, building projects - creating fairHealth, Infinity404, and winning hackathons, hiking, and hanging out with friends. He believes that crafting with creativity can uplift the world, and that we should revel in every moment of the process.