A Deterministic Model for Simultaneous Play Games: The Cheating Robot and Insider Information

摘要

Combinatorial games are two-player games of pure strategy where the players, usually called Left and Right, move alternately. In this paper, we introduce simultaneous-play combinatorial games except that Right has extra information: he knows what move Left is about to play and can react in time to modify his move. Right is `cheating' and we assume that Left is aware of this. This knowledge makes for deterministic, not probabilistic, strategies. The basic theory and properties are developed, including showing that there is an equivalence relation and partial order on the games. Whilst there are no inverses in the class of all games, we show that there is a sub-class, simple hot games, in which the `integers' have inverses. In this sub-class, the optimal strategies are obtained by the solutions to a minimum-weight matching problem on a graph whose number of vertices equals the number of summands in the disjunctive sum. This is further refined, in a version of simultaneous toppling dominoes, by reducing the number of edges in the underlying graph to be linear in the number of vertices.