The other day I found Alan Pike’s blog post from a few years ago which describes his iterative process for determining the order cities should be closed in the game Two Spies. Ultimately, finding a formal solution to city closing wasn’t necessary for the game, but it’s worth giving it a shot anyways since pruning by hand isn’t always convenient.
Closing cities is an important mechanic in the game, because as a sort of “battle royale” mechanic it prevents players from hiding in the corner of the map indefinitely. We can model the map as an undirected graph, where cities are vertices and travel routes are edges. Removing a city means deleting a vertex and its corresponding edges.
Closing cities without considering the resulting map can be suboptimal or unplayable. His post named two specific issues: disconnected graphs and path graphs (i.e. long lines of cities). A disconnected graph can result in a situation where the players can no longer interact. A path graph results in a map which isn’t very fun since the single path severely limits the strategies players can use.
The difficulty is that removing a city permanently changes the topology of the map. A choice might seem reasonable at one point but causes issues down the line. So picking the correct sequence of removals is important in maintaining a playable map.
With the four nodes a, b, c, and d, there are four pruning options. However, option 1 results in a disconnected graph, and options 3 and 4 result in suboptional path graphs. Option 2 is the only one which maintains a connected, non-path graph.
Avoiding disconnected graphs
This one is simple enough. We just need to pick a city and perform a breadth-first search to ensure that every other remaining city is reachable from it. Since the map starts as a connected graph, we can always find a city to remove where the remaining graph is connected. This is because we can always find a node which isn’t an articulation point.
Avoiding path graphs
This one is fuzzier because intuitively this seems to be the case of better and worse graphs, rather than the previous case. So if we can come up with some metric for “better”, we can search for the “best” option and select it.
Intuitively, the reason that path graphs aren’t great is because as a hidden information game, the strategy of Two Spies relies on the fact that the opponent could be in multiple places at once, but path graphs reduce strategic possibility space and hidden state uncertainty.
... continue reading