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 S1 and S2 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.

i-4c76ab16b0a7b14c79135582c9506807-tic-tac.png

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×1020 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×1020 to something around 1018 states, with a complete graph only for the end-game - which was a set of roughly 3×1014 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.

More like this

Random Q ---

How did you generate that great looking tic tac toe graphic?

By Andrew Lacey (not verified) on 16 Sep 2007 #permalink

Yeah, they look great. And those graphs...

By Toni Petrina (not verified) on 16 Sep 2007 #permalink

As usual - I do all of my images in OmniGraffle. I swear, I should be charging them a commission :-). I get so many
people asking how I draw my diagrams :-)

Can you get OmniGraffle for free? Some people have recommended it to me in the past, but I never really looked into it.

Omnigraffle has a free trial, but then you
have to pay for it. It's worth the price- it's a
really brilliant piece of software.

Mark, I do not understand when you say "a state space is a set of equivalence classes over all possible board positions"

An equivalence class is defined only by an equivalence relation. The relation that you have given I think is this: "connected by a directed edge if and only if there is a legal move from one position to the other."

But if this is the relation, then by transitivity etc we will have the whole state space making just one equivalence class. Yes of course one set is still a set of equivalence classes, but I am just wondering if I am missing something. Is that statement deeper than what I am making out of it?

(Okay, I just realized that if the graph is not connected then we will have a set of more than one class. But since all board games that I could think of always had one same starting configuration - this is the root node from which all the other states appear, so all those games will always lead to a connected graph. Now I am thinking what boardgames, rules will lead to disconnected graphs? I couldn't think of any, and of course if you are saying the eq relation is different from what I assumed, then its a different story)

Senthil:

What I meant about equivalence classes is illustrated in the
tic-tac-toe example. The equivalence is an equivalence under the rules of the game. So, for example, in tic-tac-toe, a first-move X in the upper left corner results in a board position that is completely equivalent to a first-move X in the lower right corner. Similarly, for Go, boards are equivalent under rotation and reflection. In Chess, each board position is unique; so the equivalence classes each have one member.

Okay, I understand. This is like the definition of a rigid body. (Where the relative position/configuration of the particles inside are unaffected by rotation or translation of any of the particles)

Other common examples of heuristics that comes to mind are:
- Opening games (from chess), increased depth complete graphs (opening libraries), or at least optimized heuristics.
- End games (from chess), increased depth complete graphs, or at least optimized heuristics.
- Strategies, overall game plans with focus on vertex heuristics.
- Tactics, localized game plans with focus on edge heuristics and variation of search depth.

Typically, in chess at least, strategies and tactics switch focus when they aren't complementary. (Ie, if your opponent are threatening your position you may switch from prioritizing strategy to prioritizing tactic.)

each board position is unique

Is that true? The parity which bishops and castling gives (which we can recognize by noting white and black squares) combined with pawn unidirectionality means each position is unique in the start.

But in end games without pawns and castling don't you have at least 4 symmetry positions from rotation? Also, if you have castled both sides, shouldn't you have symmetry under color change of pieces (ie by switching sides)?

By Torbjörn Lars… (not verified) on 16 Sep 2007 #permalink

I think that one of my earliest introductions to computing was through a game graph. I had a book full of kids "science" projects. One of the projects was to build a Tic-Tac-Toe computer using paper cups and slips of paper. I don't recall the exact layout but you filled the cups with slips of paper showing the various states. You then played the game, pulling a random slip (representing a transition.) If the game ended with the computer losing, you tossed all of the slips that you had pulled during that pass. You ended up with a state machine that would always win or draw.