The sabotage game has two players: Blocker and Runner, Every turn, Blocker erases one edge and then Runner moves one step. Runner wins the game iff they can reach the ‘exit’ of the graph.
In the graph below, who wins the game?
Answer below.
For clearness: the start is at the upper left corner, and the exit is at the lower right corner. The graph is non directed multigraph, so there are two paths from the start to the center and so on.
This puzzle is originally by van Benthem,
More on this game can be found in van Benthem’s “An essay on sabotage and obstruction” and Aucher et al. “Modal logics of sabotage revisited”. There is quite a lot more about these sabotage games and its related sabotage logic in the literature. This logic allows us to erase edges from a graph, and gives a formalization of the sabotage game. (I’ve been reading about them this week, trying to find something amenable to work on.)
Answer (long)
Blocker first cuts one edge connecting the center to the bottom right. He then erases the nodes connecting Runner’s current position and the exit node (if there is no such edge, he may erase any edge).