FUNDAMENTALS OF GAME DESIGN, SECOND EDITION

Game Tree Search

In turn-based games such as checkers, chess, or Go, each player has a number of choices—possible moves that he can make—at each turn. You choose your move, then your opponent makes his move from the choices available to him, and then it's back to you with a new set of possible moves, and so on. If you draw a graph of this, showing how the options branch out at every turn, it looks like a tree, so the set of all possible future moves is called the game tree.

With simple games, artificial opponents search through the game tree, looking for the moves that produce the most advantageous result. The fewer choices there are, the easier this is. With tic-tac-toe, the problem is trivial; with checkers, it is comparatively easy; with chess, it is quite difficult; and with Go, no one has yet managed to build a computer game that can play as well as a master human player. In Go, the board is large and the player can play nearly anywhere, so the number of possible future moves is simply astronomical. In addition, unlike in chess, it is very difficult to evaluate whether a potential move is good or bad; it depends too much on other moves.

As a designer, do not expect to use game-tree search in any but the simplest of games. The length of time it will take for the computer to compute a good move increases exponentially with the number of possible moves available.