{"id":511,"date":"2007-09-16T11:58:23","date_gmt":"2007-09-16T11:58:23","guid":{"rendered":"http:\/\/scientopia.org\/blogs\/goodmath\/2007\/09\/16\/games-and-graphs-searching-for-victory\/"},"modified":"2007-09-16T11:58:23","modified_gmt":"2007-09-16T11:58:23","slug":"games-and-graphs-searching-for-victory","status":"publish","type":"post","link":"http:\/\/www.goodmath.org\/blog\/2007\/09\/16\/games-and-graphs-searching-for-victory\/","title":{"rendered":"Games and Graphs: Searching for Victory"},"content":{"rendered":"

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

<\/p>\n

In terms of a game, a state space is a set of equivalence classes<\/em> 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
\nof tic-tac-toe consists of all marked boards, partitioned into equivalence classes of marked boards equivalent modulo rotation or reflection.<\/p>\n

Given a state space, two states S1<\/sub> and S2<\/sub> 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<\/em> of the game.<\/p>\n

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<\/em>.<\/p>\n

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
\ncorner, 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.<\/p>\n

\"tic-tac.png\"<\/p>\n

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<\/em> in graph theoretic terms when we have the complete graph of the game, and we know every possible path through it. <\/p>\n

Given a game in its graph form, for anything but the most trivial of games, it’s not
\nfeasible to use a real, complete graph search. For example, the game tree for checkers, which was recently solved<\/a>, has 5×1020<\/sup> nodes. Solving checkers took 18 years of computation – and that was not<\/em> actually a complete search of the state space!<\/p>\n

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:<\/p>\n