42Papers

Cutting-Edge Computer Science and AI Papers

Absolute Combinatorial Game Theory

Urban Larsson, Richard J. Nowakowski, Carlos P. Santos

We propose a unifying additive theory for standard conventions in
Combinatorial Game Theory, including normal-, mis\`ere- and scoring-play,
studied by Berlekamp, Conway, Dorbec, Ettinger, Guy, Larsson, Neto, Nowakowski,
Milley, Renault, Santos, Siegel, Sopena, Stewart (1976-2019), and others. A
game universe is a set of games that satisfies some standard closure
properties. Here, we reveal when the fundamental game comparison problem, "Is
$G\ge H$?", simplifies to a constructive `local' solution, which generalizes
Conway's foundational result in ONAG (1976) for normal-play games. This happens
in a broad and general fashion whenever a given game universe is absolute. An
absolute universe of games satisfies a property, dubbed parentality: any pair
of non-empty finite sets of games is admissible as options. This property
implies that a universe is saturated with respect to the outcomes, basically,
given a game, any outcome is attainable in a disjunctive sum. Game comparison
is at the core of combinatorial game theory, and for example efficiency of
potential reduction theorems rely on a local comparison. We distinguish between
three levels of game comparison; superordinate (global), basic
(semi-constructive) and subordinate (local) comparison. In proofs, a sometimes
tedious challenge faces a researcher in CGT: in order to disprove an
inequality, an explicit distinguishing game might be required. Here, we explain
how this job becomes obsolete whenever a universe is absolute. Namely, it
suffices to see if a pair of games satisfies a certain Proviso together with a
Maintenance of an inequality.

Share

Related Papers

More

More