10.3 BACKTRACKING
INTRODUCTION |
In the development of computer games, it only gets really interesting when the computer itself becomes an intelligent game partner. Such a program must not only comply with the rules of the game, but it must also pursue a winning strategy. In order to implement a game strategy, the game should be understood as a sequence of game situations that can be clearly identified with a suitable variable s. These are known as game states and is therefore s is called a state variable. The goal of the strategy is to move from an initial state to a winning state where the game is usually over. The game states can be neatly shown as nodes in a game graph. For each turn, there is a transition from one node to one of its successors. The rules of the game specify what the possible successor nodes or neighbors of a particular game state are. You can draw the transition as a directional connecting line, also called an edge [more... Game theory is based essentially on Graf theory, an important part of mathematics.].In this section you will learn important techniques that have a general validity and help you to write computer games that can win even against very intelligent human players. However, in addition to these general techniques there is still plenty of room for your own ideas, to write more efficient, simpler, and better adapted game strategies that possibly have a better chance of winning or consumes less computing time. It is a fact that many political, economical, and social systems can be understood as a game, and so you can apply your acquired knowledge on a wide array of practically relevant fields. |
SEARCHING FOR A SOLUTION FOR A SOLO GAME |
As previously mentioned, you represent the game states as nodes in a graph that is run through step by step. You have to first uniquely determine the game states by certain criteria, such as the arrangement of the tokens on a game board. The rules of the game specify which are the possible successor nodes or neighbors for a specific game state. These are connected with the node by lines (edges). Since they are successor node, the edges have a direction from the node to its neighbors. Sometimes a node is also called a "mother" and its neighbors "daughters", and there is also the possibility that there is an edge from a daughter back to her mother. Here you begin from a simple game graph for a game that is played either by a single person or by the computer alone. The single person game, or solo game, should be constructed so that there are no paths that lead back again. This ensures that you do not fall into a cycle that runs endlessly when moving through the graph. Such a special graph is called a tree [more... Tree is a graph without cycles]. You can identify the nodes in any order with numbers between 0 and 17. The graph has the following structure:
The tree should be saved as a whole in a suitable data structure. A list is well suited for this, in which the numbers of neighboring nodes are included as sublists where at the index 0 we find the list of neighbors of node 0, at index 1 is the list of neighbors of node 1, etc. If a node does not have a neighbor, its neighbor list is empty [more... Such a node is called a leaf of the tree]. As you can easily see, the following list represents the given tree
Identifying a node by a number is a trick that allows you to determine the neighbors of a node with a list index. The algorithm for finding the path from a certain node to one in the deeper tree structure is defined recursively in the function search(node). Formulated in pseudo code it reads: search(node): Additionally, the "visited" nodes are entered in the back of the list visited. If the goal is not reached earlier, the node is removed again from visited after all nodes were traversed, in order to go back to the original state [more... visited has the structure of a stack (last-in-first-out) ]. The start and target node number can be entered at the beginning of the program. neighbours = [[4, 1, 16], [2, 5, 7], [], [], [9, 13], [11, 14], [], [],
[17, 6, 3], [], [], [], [], [10, 12], [], [], [15, 8], []]
def search(node):
visited.append(node) # put (push) to stack
# Check for solution
if node == targetNode:
print "Target ", targetNode, "achieved. Path:", visited
targetFound = True
return
for neighbour in neighbours[node]:
search(neighbour) # recursive call
visited.pop() # redraw (pop) from stack
startNode = -1
while startNode < 0 or startNode > 17:
startNode = inputInt("Start node (0..17):")
targetNode = -1
while targetNode < 0 or targetNode > 17:
targetNode = inputInt("Target node (0..17):")
visited = []
search(startNode)
|
MEMO |
|
The correct path [0, 1, 5, 14] is written out for the start node 0 and the target node 14. If you add the node 0 as a neighbor at node 13, you create a cycle and this results in a disastrous situation and the program is aborted with a runtime error that says that the maximum recursion depth is reached. |
THE TRAVERSING OF AN ALIEN |
It is neat to be able to visibly follow the algorithm by representing the game tree graphically and gradually traversing it (by pressing a key). For this you best use a GameGrid window in which nodes are made visible as cycles in certain cell coordinates (locations). In the current cell you see a semi-transparent alien waving at you.
You draw the tree with the graphical methods of GGBackground. You can attach a small circle mark to the edges, instead of an arrow tip, using getMarkerPoint() to show the direction of the edge. Make sure that you refresh the screen using refresh(). You can view important information in the status bar. from gamegrid import * neighbours = [[4, 1, 16], [2, 5, 7], [], [], [9, 13], [11, 14], [], [], [17, 6, 3], [], [], [], [], [10, 12], [], [], [15, 8], []] locations = [Location(6, 0), Location(6, 1), Location(4, 2), Location(13, 3), Location(1, 1), Location(6, 2), Location(12, 3), Location(8, 2), Location(12, 2), Location(0, 2), Location(1, 3), Location(5, 3), Location(3, 3), Location(2, 2), Location(7, 3), Location(10, 2), Location(11, 1), Location(11, 3)] def drawGraph(): getBg().clear() for i in range(len(locations)): getBg().setPaintColor(Color.lightGray) getBg().fillCircle(toPoint(locations[i]), 6) getBg().setPaintColor(Color.black) getBg().drawText(str(i), toPoint(locations[i])) for k in neighbours[i]: drawConnection(i, k) refresh() def drawConnection(i, k): getBg().setPaintColor(Color.gray) startPoint = toPoint(locations[i]) endPoint = toPoint(locations[k]) getBg().drawLine(startPoint, endPoint) getBg().fillCircle(getMarkerPoint(endPoint, startPoint, 10), 3) def search(node): global targetFound if targetFound: return visited.append(node) # put (push) to stack alien.setLocation(locations[node]) refresh() if node == targetNode: setStatusText("Target " + str(targetNode) + "achieved. Path: " + str(visited)) targetFound = True return else: setStatusText("Current node " + str(node) + " . Visited: " + str(visited)) getKeyCodeWait(True) # exit if GameGrid is disposed for neighbour in neighbours[node]: search(neighbour) # Recursive call visited.pop() makeGameGrid(14, 4, 50, Color.red, False) setTitle("Tree-traversal (depth-first search). Press a key...") addStatusBar(30) show() setBgColor(Color.white) drawGraph() startNode = -1 while startNode < 0 or startNode > 17: startNode = inputInt("Start node (0..17):") targetNode = -1 while targetNode < 0 or targetNode > 17: targetNode = inputInt("Target node (0..17):") visited = [] targetFound = False alien = Actor("sprites/alieng_trans.png") addActor(alien, locations[startNode]) search(startNode) setTitle("Tree-traversal (depth-first search). Target achieved")
|
MEMO |
|
As you can see, the alien moves to the daughter nodes "in the depth of the tree" and then jumps back to the last mother node. For this reason, this principle is called depth-first search with backtracking. |
THE ALIEN ON THE WAY BACK |
If you want to make visible the path that the alien moves while moving back, you need to save the sequence of nodes while moving forward in a list steps. There is a new list at each recursion depth and you save these in stepsList. After moving back, you have to remove the last entry with stepList.pop().. from gamegrid import * neighbours = [[4, 1, 16], [2, 5, 7], [], [], [9, 13], [11, 14], [], [], [17, 6, 3], [], [], [], [], [10, 12], [], [], [15, 8], []] locations = [Location(6, 0), Location(6, 1), Location(4, 2), Location(13, 3), Location(1, 1), Location(6, 2), Location(12, 3), Location(8, 2), Location(12, 2), Location(0, 2), Location(1, 3), Location(5, 3), Location(3, 3), Location(2, 2), Location(7, 3), Location(10, 2), Location(11, 1), Location(11, 3)] def drawGraph(): getBg().clear() for i in range(len(locations)): getBg().setPaintColor(Color.lightGray) getBg().fillCircle(toPoint(locations[i]), 6) getBg().setPaintColor(Color.black) getBg().drawText(str(i), toPoint(locations[i])) for k in neighbours[i]: drawConnection(i, k) refresh() def drawConnection(i, k): getBg().setPaintColor(Color.gray) startPoint = toPoint(locations[i]) endPoint = toPoint(locations[k]) getBg().drawLine(startPoint, endPoint) getBg().fillCircle(getMarkerPoint(endPoint, startPoint, 10), 3) def search(node): global targetFound if targetFound: return visited.append(node) # put (push) to stack alien.setLocation(locations[node]) refresh() if node == targetNode: setStatusText("Target " + str(targetNode) + "achieved. Path: " + str(visited)) targetFound = True return else: setStatusText("Current nodes " + str(node) + " . Visited: " + str(visited)) getKeyCodeWait(True) # exit if GameGrid is disposed for neighbour in neighbours[node]: steps = [node] stepsList.append(steps) steps.append(neighbour) search(neighbour) # Recursive call steps.reverse() if not targetFound: for loc in steps[1:]: setStatusText("Go back") alien.setLocation(locations[loc]) refresh() getKeyCodeWait() stepsList.pop() visited.pop() makeGameGrid(14, 4, 50, Color.red, False) setTitle("Tree-traversal (depth-first search). Press a key...") addStatusBar(30) show() setBgColor(Color.white) drawGraph() startNode = -1 while startNode < 0 or startNode > 17: startNode = inputInt("Start node (0..17):") targetNode = -1 while targetNode < 0 or targetNode > 17: targetNode = inputInt("Target node (0..17):") visited = [] stepsList = [] targetFound = False alien = Actor("sprites/alieng_trans.png") addActor(alien, locations[startNode]) search(startNode) setTitle("Tree-traversal (depth-first search). Target achieved")
|
MEMO |
|
The alien now really moves back up in the tree, which makes it particularly clear why the algorithm is called backtracking. Recursive backtracking plays an important role in many algorithms and is sometimes also referred to as the “Swiss army knife of computer scientists”. |
STRATEGY IN A MAZE |
Sometimes it is difficult, or even just frightening, to find your way out of a maze. However, now you can write a program with your knowledge about backtracking that can find its way out of a maze with certainty. It is quite obvious that you can model a maze that has no cycles as a tree. Finding the exit in such a maze therefore corresponds a tree traversal. Here you use only a small random maze with 11x11 cells. The alien moves one step when you press the button, but if you hit the Enter key it searches for the exit completely autonomously. You generate the maze with the class Maze. You pass it the desired number of rows and columns as odd numbers. Each time, a different random maze is created with an entry at the top left side and an exit at the bottom right. You can test whether there is a wall cell at the location loc using isWall(loc).
from gamegrid import * def createMaze(): global maze maze = GGMaze(11, 11) for x in range(11): for y in range(11): loc = Location(x, y) if maze.isWall(loc): getBg().fillCell(loc, Color(0, 50, 0)) else: getBg().fillCell(loc, Color(255, 228, 196)) refresh() def getNeighbours(node): neighbours = [] for loc in node.getNeighbourLocations(0.5): if isInGrid(loc) and not maze.isWall(loc): neighbours.append(loc) return neighbours def search(node): global targetFound, manual if targetFound: return visited.append(node) # push alien.setLocation(node) refresh() delay(500) if manual: if getKeyCodeWait(True) == 10: #Enter setTitle("Finding target...") manual = False # Check for termination if node == exitLocation: targetFound = True for neighbour in getNeighbours(node): if neighbour not in visited: backSteps = [node] backStepsList.append(backSteps) backSteps.append(neighbour) search(neighbour) # recursive call backSteps.reverse() if not targetFound: for loc in backSteps[1:]: setTitle("Must go back...") alien.setLocation(loc) refresh() delay(500) if manual: setTitle("Went back. Press key...") else: setTitle("Went back. Find target...") backStepsList.pop() visited.pop() # pop manual = True targetFound = False visited = [] backStepsList = [] makeGameGrid(11, 11, 40, False) setTitle("Press a key. (<Enter> for automatic") show() createMaze() startLocation = maze.getStartLocation() exitLocation = maze.getExitLocation() alien = Actor("sprites/alieng.png") addActor(alien, startLocation) search(startLocation) setTitle("Target found")
|
MEMO |
|
It is interesting to compare the solution strategy of a human with that of the computers. A human player can recognize the overall situation with a simple glance and derive a strategy of how to reach the exit as quickly as possible. They act with a characteristically human global overview that your computer program lacks. Your program only detects the current situation locally, but it "remembers" the already passed routes very precisely and then systematically searches for new routes leading to the target destination. However, the situation changes in favor of the computer when the human is withheld a global overview, e.g. if they themselves were actually located inside of the maze and walls are too hight to see over.. |
EXERCISES |
|
ADDITIONAL MATERIAL |
THE N-QUEENS PROBLEM |
The following is a chess problem that has already been discussed since the mid-19th century. Place n queens on a chessboard with nxn fields so that they can not beat each other in accordance with the rules of chess. (The rules of chess state that a queen can move both horizontally and vertically, as well as diagonally.) There are two issues with varying degrees of difficulty: On the one hand, you would like to specify a solution, and on the other hand, you would like to find out how many solutions there are in total. Already in 1874 the mathematician Glaisher proved that there are a total of 92 solutions for the classic checkerboard with n = 8. The queens problem is considered to be a classic example of backtracking. You place the queens one after another onto the board always making sure that an added queen does not come into conflict with the queens already present. If you proceed aimlessly, there is usually a moment where it is no longer possible to place a queen. The applied strategy in backtracking is that it undoes the last step and tries an alternative. If there is still no solution from the alternative step, you must undo this step as well, etc. With this procedure, a person can easily loose the overview of which positions have already been tested, but a computer on the other hand, does not have this problem, since it procedes purely systematically.
You can determine the neighboring nodes of the current nodes (node) in the backtracking algorithm using the function getNeighbours(node). Thereby you switch from the one-dimensional data structure to Locations, which uses x and y coordinates of the fields. You gather the already occupied fields in the list squares and you put those which cannot be filled due to the rules of the game in the list forbidden. (In this case it is convenient to use the method getDiagonalLocations().) Finally, you create the list allowed for fields that can still be filled. You now need to replace the -1 in the neighboring nodes list with the column index on which the new queen is placed. You implement the already known backtracking algorithm in search(). Once a solution is found, you stop the search (recursion stop). from gamegrid import * n = 8 # number of queens def getNeighbours(node): squares = [] # list of occupied squares for i in range(n): if node[i] != -1: squares.append(Location(node[i], i)) forbidden = [] # list of forbidden squares for location in squares: a = location.x b = location.y for x in range(n): forbidden.append(Location(x, b)) # same row for y in range(n): forbidden.append(Location(a, y)) # same column for loc in getDiagonalLocations(location, True): #diagonal up forbidden.append(loc) for loc in getDiagonalLocations(location, False): #diagonal down forbidden.append(loc) allowed = [] # list of all allowed squares = all - forbidden for i in range(n): for k in range(n): loc = Location(i, k) if not loc in forbidden: allowed.append(loc) neighbourNodes = [] for loc in allowed: neighbourNode = node[:] i = loc.y # row k = loc.x # col neighbourNode[i] = k neighbourNodes.append(neighbourNode) return neighbourNodes def search(node): global found if found or isDisposed(): return visited.append(node) # node marked as visited # Check for solution if not -1 in node: found = True drawNode(node) for s in getNeighbours(node): search(s) visited.pop() def drawBoard(): for i in range(n): for k in range(n): if (i + k) % 2 == 0: getBg().fillCell(Location(i, k), Color.white) def drawNode(node): removeAllActors() for i in range(n): addActorNoRefresh(Actor("sprites/chesswhite_1.png"),Location(node[i],i)) refresh() makeGameGrid(n, n, 600 // n, False) setBgColor(Color.darkGray) drawBoard() show() setTitle("Searching. Please wait..." ) visited = [] found = False startNode = [-1] * n # all squares empty search(startNode) setTitle("Search complete. ")
|
MEMO |
|
Depending on the performance of your computer, you may have to wait anywhere from a few seconds to a few minutes until a solution is found. If it takes too long, you can set n = 6. |
EXERCISES |
|