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

Misère combinatorial games are two-player, perfect-information games where the last player to move loses. In contrast to the well-developed normal-play theory characterized by the Sprague–Grundy theorem, misère play introduces substantial analytical challenges due to its nontrivial endgame behavior. In this paper, we explore their structural, algorithmic, and complexity-theoretic properties, beginning with a detailed examination of Misère Nim and a proof of the Misère Nim Theorem. We present a computational implementation that efficiently determines game outcomes, illustrating the role of algorithmic insight in misère analysis. Extending this foundation, we study misère quotients as a structural tool, classify games according to tame / wild dynamics, and explore algebraic connections to ordinal arithmetic and surreal numbers. These investigations place misère games at the intersection of combinatorial game theory and theoretical computer science, offering new perspectives on algorithmic tractability, complexity classification, and algebraic modeling.