deutsch     english    français     Print

 

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.

PROGRAMMING CONCEPTS: Game state, game graph, depth-first search, backtracking

 

 

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

neighbours = [[4, 1, 16], [2, 5, 7], [], [], [9, 13],[11, 14], [], [], [17, 6, 3], [], [], [], [], [10, 12], [], [], [15, 8], []]

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):
     if node == targetnode:
          print "Target achieved"
          return
      determine list of neighbors
      run through this list and execute:
          search(neighbors)

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)
Highlight program code (Ctrl+C copy, Ctrl+V paste)

 

 

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")
Highlight program code (Ctrl+C copy, Ctrl+V paste)

 

 

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")
Highlight program code (Ctrl+C copy, Ctrl+V paste)

 

 

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).

It is often not suitable to determine the full game graph before the game. In many cases this is simply impossible, since there are so many game situations that you are not able to determine them in a reasonable time and there would also not be enough space for the data. Due to this, it is usually better to determine the neighboring nodes of the current node only during backtracking.

You detect the neighboring nodes in your program by selecting the 4 adjacent cells that are not a wall or outside of the grid.

 

 
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")
Highlight program code (Ctrl+C copy, Ctrl+V paste)

 

 

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

 

1.


A binary tree has two neighboring nodes for every node, namely a left and a right one. Choose a list with two numbers [m, n] as a node identifier, where m indicates the depth in the tree and n indicates the width.

The program should write out the path after entering the start and target nodes.

2.

It is amazing that you can always find the way out of a maze using the right-hand rule, even if it has cycles in it. Following it, you always walk with your right hand along the wall and stick to the following rules:

  • If the right is free, then go to the right
  • If you can not go to the right, but going straight is an option, then go straight
  • If you can not go to the right or straight ahead, then turn to the left

Implement this rule for a GameGrid maze with a rotatable beetle Actor lady = Actor(True, "sprites/ladybug.gif"). Instructions: Place the beetle in the next cell according to the rule using move(). If it is a wall cell, undo the step.

Compare this solution algorithm with the solution you get by backtracking.

 

   

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.

As with all tasks in backtracking, you can regard the game states as nodes in a game graph. Selecting a suitable data structure is very important. Proceeding in accordance with the "brute force" principle, where you set n queens on the board in all possible ways and after sort out those cases which can not be beat, is not suitable because with n = 8 there are around 422 million possible positions.

It is much better if from the beginning you only consider positions where the placed queens are located on different rows and columns. For n = 8 you can specify the game state with a list of 8 numbers, where the first number is the column index of the queen in the first row, the second number is the column index of the queen in the second row, etc. For rows without queens, write -1 as an index.

If you take row and column indices from 0 to n-1, you identify the adjacent position with node = [1, 4, -1, 3, 0, 6, -1, 7].

 

 

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. ")
Highlight program code (Ctrl+C copy, Ctrl+V paste)

 

 

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

 

1.


Solve the same task without using the GameGrid library. Substitute Location with cell lists [i, k]. You can write out the solution as a node list.

2.

Generalize the program declared above for n = 6 or your own program from exercise 1 so that all solutions are found. Take into account that, because of symmetries of the gameboard, a solution node is found several times and avoid duplicates with a list of already found solutions.