Chapter 2 : Decision TreesTrees are one of the most frequently occuring data structures used in programming. In fact, the HTML document you are reading now contains tags nested within one another in a tree structure. We will not concern ourselves with data structures in this chapter however; what we will be looking at are decision trees, sometimes known as game trees.
Solving a maze
Fig 1 : Sample Maze
function CheckRoom(RoomNumber) begin if RoomNumber has been visited, return. for each room connected to this room if ConnectedRoomNumber == B, the maze has been solved else CheckRoom(ConnectedRoomNumber) end for end functionThat's all! The algorithm takes care of rooms with Dead Ends, rooms with multiple corridors, and anything you care to throw at it. It has the elegant simplicity characteristic of all recursive procedures, but it differs slightly from the functions we have studied previously. It is a backtracking algorithm.
How Backtracking works
Fig 2 : The maze as a tree
Backtracking procedures are characterized by multiple recursive calls, typically within a loop (see the CheckRoom function above). Unlike the simple recursion examples we had encountered in the previous chapter, a backtracking procedure goes through multiple winding and unwinding stages as it loops through the choices it has to make at every node. One of the most common applications of backtracking is in the evaluation of moves for strategy games like chess. We will look at a much simpler game, tic-tac-toe, and see how a backtracking strategy can be used to ensure that we can never lose the game.
Game TreesTic-tac-toe is played on a 3x3 grid, so there are 9 possible starting moves. Each of these can be followed by 8 possible countering moves, which can each be further be followed by 7 moves, and so on. These moves can be viewed as branches of a tree, with the resulting state of the playing grid as the nodes of the tree. It is important to note that the grid itself is not a tree structure, it is the possible grid states after each move that form the decision tree.
The tree will have 3 types of leaf nodes, grid structures representing wins, losses and draws. A typical game playing program will use backtracking to move through this tree, assigning high values to each node which leads to a winning scenario, lower values to the nodes which could conceivably lead to draws, and very low values to nodes that may result in losses. The program then uses the unwinding phase of the algorithm to trickle these values upwards through the tree, so that each of the nodes that represent the next move of the program will have a value. Finally the program chooses the node with the highest value to make it's next move.
This is only a (very) simplistic explanation of how programs evaluate
alternative strategies using backtracking. If you would like to
view the source code
of a tic-tac-toe program which uses a backtracking algorithm, you
can download it from here.
For other games and algorithms, do visit
the awesome X2FTP game programming site.