Synchronous Combinatorial Games

Abstract

Synchronous combinatorial games are a variant of combinatorial games in which both players move simultaneously. This simultaneous decision-making introduces uncertainty, since each player must act without knowing the opponent’s choice. As a consequence, synchronous games do not admit additive inverses in the way that classical combinatorial games do. However, a subclass of synchronous games introduced by De Mol (2021) exhibits no such uncertainty and therefore forms a group. We call these games stackers, and we show that they play a role similar to that of numbers in classical Combinatorial Game Theory (CGT). Using stackers, we develop a method to quantify the uncertainty present in any synchronous game, analogous to the use of stops and confusion intervals in CGT. We then apply this framework to Synchronized Hackenbush to find rewriting rules for Hackenbush strings. Applying the framework to synchronized Cherries allows us to make progress on a conjecture by De Mol (2021) which rewrites any Synchronized Cherries position in terms of stackers. Finally, we uncover a surprising connection between stackers and Lyndon words. This leads us to conjecture that stackers give rise to a variant of the Burrows–Wheeler transform, which is used in data compression algorithms.