Games at Harlow

There will be a discussion about bridges between Chess and Combinatorial Game Theory, while also paying a small tribute to Richard K. Guy (1916–2020) through a short story.

The two-player game of lazy cops and robbers is played on a graph. In the initial round, the cops choose an initial vertex for each of their $k$ pieces. Then the robber chooses an initial vertex for his piece. Each round after that, the cops must move up to one of their pieces along an edge, after which the robber can also either move his piece or remain stationary. The cops have won if they reach the current robber position in some round. The robber wins otherwise.

For each graph $G$, the lazy-cop-number of $G$ is the smallest integer $k$, such that $k$ lazy cops have a winning strategy on $G$. It is currently unknown whether this number is bounded for graphs of bounded genus. Known constructions of genus 0 with lazy-cop-number at least four exist. We present graphs of genus 0 and lazy-cop-number at least five and graphs of genus 1 and lazy-cop-number at least six. Both are confirmed by computer to have this trait. There further exists a computer-free argument for the genus 1 case with some hope to extend it to larger lazy-cop-numbers. Both graph classes are build up from triangle grids.

In an impartial combinatorial game, both players have exactly the same options at every position of the game. Classical Sprague–Grundy theory provides a fundamental framework for the analysis of short impartial games, where play is finite, the number of options is limited, and no special moves occur. Over the years, several extensions of this theory have been developed to address more general settings. Notably, the Smith–Frankel–Perl theory applies to games in which infinite play is possible, while the Larsson–Nowakowski–Santos theory accommodates entailing moves that disrupt the usual behavior of the disjunctive sum. This talk introduces a generalization that combines these two approaches, making it possible to analyze cyclic impartial games with carry-on moves. Carry-on moves constitute a special class of entailing moves in which the responding player has no freedom of choice. The theory is illustrated through green-lime hackenbush, a game inspired by the classical game of green hackenbush.

(Joint work with: Tomoaki Abuku, Urban Larsson, Richard J. Nowakowski, Carlos P. Santos, Koki Suetsugu)