2023/12/26 by Aaron N. Siegel, Siegel, Aaron N. · 1 citation
Computer Science · Decision Sciences · #05A99 #91A46 #Artificial Intelligence in Games #Combinatorics (math.CO) #Computability, Logic, AI Algorithms #FOS: Mathematics #Game Theory and Applications
paper · pdf · doi:10.48550/arxiv.2312.16259
openalex publication_date 2023/12/26 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The universe E of dead-ending partizan games has emerged as an important structure in the study of misère play. Here we attempt a systematic investigation of the structure of E and its subuniverses. We begin by showing that the dead-ends exhibit a rich "absolute" structure, in the sense that they behave identically in any universe in which they appear. We will use this result to construct an uncountable family of dead-ending universes and show that they collectively admit an uncountable family of distinct comparison relations. We will then show that whenever the ends of a universe U ⊂ E are computable, then there is a constructive test for comparison modulo U. Finally, we propose a new type of generalized simplest form that works for arbitrary universes (including universes that are not dead-ending), and that is computable whenever comparison modulo U is computable. In particular, this gives a complete constructive theory for subuniverses of E with computable ends. This theory has been implemented in cgsuite as a proof of concept. As an application of these results, we will characterize the universe generated by misère Domineering, and we will compute the misère simplest forms of 2 × n Domineering rectangles for small values of n.