Games and Graphs: Searching for Victory

Last time, I showed a way of using a graph to model a particular kind of puzzle via
a search graph. Games and puzzles provide a lot of examples of how we can use graphs
to model problems. Another example of this is the most basic state-space search that we do in computer science problems.

In terms of a game, a state space is a set of equivalence classes over all possible board positions. For example, in chess, the state of a game at any point is represented by a set of mappings that assign either a position on the board or "captured" to each piece. The state space of chess consists of all possible board positions that can be reached by any sequence of legal moves. The state space
of tic-tac-toe consists of all marked boards, partitioned into equivalence classes of marked boards equivalent modulo rotation or reflection.

Given a state space, two states S₁ and S₂ are connected by a directed edge if and only if there is a legal move from one position to the other. When all possible moves are represented by edges, the resulting graph is a complete model of the game.

For some games simple games, the state spaces are necessarily tree-like; in other games (for example, Chess, in which a given board position can be reproduced, which creates a cycle in the graph) they can be general directed graphs. But in general, most games are directed acyclic graphs. But for some reason, the graph model of a game is generally referred to as a game tree.

For example, in the diagram below, I show a part of the game tree for tic-tac toe. From an empty board position, there are three possible unique moves. If the first move is putting an X in a corner, there are 5 possible unique moves. The diagram also includes an example of why the game tree is really a directed graph, not a tree: the game board after three moves, with X in a corner and center and O in a non-blocking
corner, can be reached by two different paths: X in corner, O in corner, X in center; and X in center, O in corner, X in corner.

Once you have the game laid out as a graph in game-tree form, you can use graph-search algorithms to traverse the graph, looking for a path that leeds to winning the game. We say that a game is solved in graph theoretic terms when we have the complete graph of the game, and we know every possible path through it.

Given a game in its graph form, for anything but the most trivial of games, it's not
feasible to use a real, complete graph search. For example, the game tree for checkers, which was recently solved, has 5×10²⁰ nodes. Solving checkers took 18 years of computation - and that was not actually a complete search of the state space!

What you typically do in searching a game tree is use directed search algorithms and graph-reduction heuristics. The idea of both of these is to try to reduce the search space. A couple of common examples are:

• Pruning: If you can show that a given edge in the search tree cannot possibly lead to an ideal solution, then you can cut that edge, often eliminating a large section of the graph. This is the main strategy used to reduce the search space for checkers: you can show, for many moves, that making that move is non-optimal. Since the checkers player can decide not to make non-optimal moves, you prune the edge corresponding to the non-optimal move from the graph. This eliminates a significant number of states - for checkers, the final search graph was cut from 5×10²⁰ to something around 10¹⁸ states, with a complete graph only for the end-game - which was a set of roughly 3×10¹⁴ states.
• Limiting: Often, you can approximate the results of a full search by looking ahead through a limited-depth subset of the graph. This is commonly used in computer chess games: by looking ahead no more than 9 edges in the chess game-tree, you can determine a good enough approximation of outcomes to beat most human chess players.
• Edge Heuristics: You can often exploit knowledge of the game to recognize that certain kinds of moves are more likely to lead to a good outcome (win or draw). By preferring to go to the edges corresponding to those moves, you can improve a pruning process to reduce the graph. This is, however, error-prone: sometimes, you'll prune out the best path to winning the game.
• Vertex Heuristics: Another form of exploiting game knowledge. For many games (including Chess), you can assigna "quality value" to a given board position. In combination with limiting, you can often use vertex heuristics to make good guesses at what moves to make. Again, as with most heuristic processes, this will work well most of the time, but there are cases where you'll prune out the best solution.

State spaces and searches like this don't only come up in games - you can find state spaces in all sorts of models - economics, physics, knowledge representation, linguistic dialogue modeling, AI planning, resource allocation, and more. The basic ideas above - the ideas of the state-space graph and graph search - apply to all of these, and more.