Contents
Recursion
Decision Trees
Maze Generation
Mysterious Maze

Backtracking

Chapter 2 : Decision Trees
Trees 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
Consider a maze, shown in the diagram above, where a player has to decide how to get from room A to room B. The player can move from room to room through the corridors provided, but has no way of telling how many corridors a room is connected to until he reaches that room. We will now see a sample session to understand the approach the player uses to solve the maze.
  1. The player moves from room A to room 2.
  2. From here he can move either to rooms 1 or 3. He chooses 1.
  3. Dead End. He returns to room 2, then goes on to room 3.
  4. He has no choice but to move to room 4.
  5. Given a choice between rooms 5 and 6, he chooses 6.
  6. Another choice between 7 and 8, he chooses 7.
  7. Dead End. He returns to 6 and chooses 8.
  8. Dead End again. He returns to 6 and sees that he has exhausted his choices.
  9. He goes back to room 4, and chooses room 5.
  10. He sees room B, moves to it, and solves the maze.
We will now examine some pseudocode which implements the algorithm described above. 
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 function
That'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
The sample maze, like all mazes, is essentially a tree, with room A at the root of the tree. Consequently, the backtracking algorithm discussed above is a tree-spanning algorithm. When it reaches a node like room 2, where it has more than one path to choose from, it picks one path (to room 1) which is a leaf node, or Dead End. Finding that it can proceed no more, it unwinds to it's previous execution, (back to room 2) and takes the other path, to room 3. Such an algorithm is known as a depth-first spanning algorithm, because it tends to follow a path right down to the bottom of the tree, before it gives up and unwinds to a previous execution in order to choose a different path. Manually apply the CheckRoom function above to the tree to get a feel of how the algorithm works.

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 Trees
Tic-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.

Prev : Recursion Next : Maze Generation