Games and Directed Graphs¶
In many strategic and board games, the sequence of moves and possible choices of each player can be modeled using directed graphs. In these graphs, each node represents a game state, and edges show valid transitions between states based on game rules.
1# Function to check connectivity in directed graph
2def check_connectivity(graph):
3 visited = set()
4 # Depth-First Search (DFS) implementation
5 def dfs(node):
6 if node not in visited:
7 visited.add(node)
8 for neighbor in graph.get(node, []):
9 dfs(neighbor)
10 # Start DFS from the first node
11 dfs(list(graph.keys())[0])
12 return len(visited) == len(graph)
In the example above:
The Python code checks strong connectivity in a directed graph using DFS
The image shows a directed graph where node relationships represent game moves
Edge directions determine valid transitions between game states
Important note: In such models, cycles in the graph indicate the possibility of infinite loops in the game, requiring special handling in game design.
Introduction¶
In this section, we examine the connection between games and directed graphs.
We begin with a simple example:
Ali and Matin are playing a game. A bag containing 10 pebbles lies before them. On each turn, the player whose turn it is takes 1 or 2 pebbles from the bag. The loser is the one who faces an empty bag and cannot take any pebbles.
Suppose Matin starts the game. If both players play optimally, who will win the game?
Examining an Example¶
In this section, we explain the example introduced in the introductory section.
We create an 11-vertex graph where the vertices are numbered from 0 to 10. We draw a directed edge from vertex \(i\) to vertex \(j\) if we can reach \(j\) by removing 1 or 2 pebbles from \(i\).
Next to each vertex, we write the letter \(L\) (Lose) or \(W\) (Win) (or leave it blank, meaning the status of this vertex hasn't been determined yet).
Suppose we write the letter \(L\) next to vertex \(i\). This means if the initial bag played by two players contains \(i\) pebbles, and both play optimally, the first player will lose the game.
Conversely, suppose we write the letter \(W\) next to vertex \(i\). This means if the initial bag contains \(i\) pebbles, and both play optimally, the first player will win the game.
Now, at the start of the game, which vertices can we label as \(L\) or \(W\)?!
With some thought, we realize vertex 0. This means if the initial bag contains 0 pebbles, according to the game rules, the first player loses because they cannot remove any pebbles.
Thus, we assign \(L\) to vertex 0.
Now, which vertex should be determined next?
Consider vertex 1. If the bag has only 1 pebble, the first player can only remove 1 pebble. Observe that the remaining bag after this move contains 0 pebbles, whose status we already determined.
We previously stated that vertex 0 has status \(L\). Therefore, vertex 1's status becomes \(W\). Notice that when the first player removes 1 pebble, the roles of the first and second players switch (since the turn changes). Thus, vertex 0 represents the loss of the second player (Ali) in the game.
Result¶
The status of the vertices, which are \(L\) or \(W\), is determined in the order of the vertices' indices.
To do this: If vertex \(u\) (among the vertices to which \(v\) has a directed edge) exists such that its status is \(L\), then the status of vertex \(v\) becomes \(W\). If all vertices to which \(v\) has edges have status \(W\), then the status of vertex \(v\) becomes \(L\).
Using this method, we can determine the status of all vertices. Now, it suffices to check the initial state of the game and see whether it is \(L\) or \(W\). If it is \(L\), it means the first player loses the game. If the status is \(W\), it means the first player wins. With this approach, we can determine whether Ali or Matin wins the game we described earlier!
Token Movement Game on a Graph¶
Our game is as follows: we have a graph with a token initially placed on the starting vertex. Players take turns moving, and each player moves the token to an adjacent vertex on their turn. The player who cannot make a move loses the game.
Generalization¶
If you pay attention to the nature of most games, you'll find such a graph within them! In fact, the essence of combinatorial games is that two or more players make changes to shared resources (shared resources could be a chessboard where we move pieces, or a bag from which we take stones).
Now suppose we create a vertex for each state of the shared resources and whose turn it is, and draw a directed edge from vertex \(A\) to \(B\) if and only if the player whose turn it is in state \(A\) can move to \(B\) during their turn. Now we have a graph! We've managed to define our game on a graph.
Thus we intuitively accept that most games can be converted into moving pieces on a graph (as we described above). For example, consider the game of chess. Each state of this game is a chessboard with different arrangements of pieces.
# Create graph structure
graph = Graph()
graph.add_node(0) # Node for initial state
graph.add_node(1) # Node for secondary state
graph.add_edge(0, 1) # here the edge is adjacent
Solving the Game on a Graph¶
If we can solve the game of moving a token on a graph, we will have taken a major step in understanding the solution methods for most games. To solve this game, we proceed as follows: We assign each vertex a label of Win (W), Loss (L), or Draw (D). Pay attention to the following three points:
A vertex with no outgoing edges is definitely labeled L.
A vertex adjacent to an L is definitely labeled W.
If a player has a non-losing strategy, they cannot move the token to a vertex labeled W (because then their opponent could win).
Thus, we implement this algorithm on our graph. As long as there exists a vertex \(u\) with no outgoing edges, we label it \(L\). Then we label all vertices \(v\) that have an edge to \(u\) as W. Next, we remove all labeled vertices from the graph. Why? Because we are certain that if a player wants to move the token to \(v\), they must first reach a vertex labeled W, and neither player wants to move the token to W-labeled vertices.
Eventually, we reach a stage where every remaining vertex in the graph has at least one outgoing edge. Starting from any of these remaining vertices, the game will never end, and both players can continue playing indefinitely! Thus, we have partitioned the vertices into three categories, and for each category, we know the game's outcome (win, loss, or draw) if started from a vertex in that category. Therefore, we have algorithmically solved the game of moving a token on a graph.
Some Useful Conclusions¶
If a vertex has a loop edge (an edge pointing to itself), then it certainly cannot be an L vertex. According to the algorithm, we only label a vertex as L when it has no outgoing edges. More precisely, the player whose piece is currently on this vertex can easily "steal" the opponent's strategy. That is, if they realize the other player can win, they can simply use the loop edge to swap turns with the opponent, effectively switching their own turn with the next player's. After this move, they can adopt the opponent's strategy. Examples of strategy stealing are provided in the problems of this section.
The algorithm we described can be analyzed differently for directed acyclic graphs (DAGs) due to their topological ordering property. We arrange the vertices of the graph in topological order. Starting from the end, we remove vertices one by one. If the vertex being removed has an edge to a previously labeled L vertex, we mark it as W. Otherwise, we mark it as L. Eventually, all vertices are assigned a win (W) or loss (L) status, as such games always terminate.
Final Note¶
At first glance, converting games into graphs seems like an effective method for solving them, but in reality, this is not the case.
This is because, in practice, many games will have an extremely large (or even infinite) number of vertices when converted into graphs. Since solving games requires memory and runtime proportional to the number of vertices and edges, solving many games in this manner becomes impractical. (Can you estimate how many distinct vertices a chess game would have after being converted into a graph?!).
On the other hand, for many games, converting them into graphs can provide better intuition for solving the problem, or the resulting graph may become highly specialized. Thus, the conclusion is that converting to graphs is a relatively powerful tool for solving and gaining intuition about games, but it will not always meet our needs.
This book is made by The Shaazzz contributors.
It is publicly available with cc-by-sa license.
Last updated at آوریل 19, 2025.
Rendered by Sphinx (4.3.2) and Minoo theme (Beta 0.9.7).
