Lecture "Backtracking algorithms", exercise 1

[essepuntato]

Propose some variation to the implementation of the peg solitaire exercise in order to make it more efficient – in particular, avoiding unsuccessful configurations if they have been already encountered previously while looking for a solution.

[delfimpandiani]

I am not quite sure if my solution solves the efficiency problem in the way the prompt asks, but it does bring efficiency to the algorithm. I tried to implement various ideas but only ended up with one working one.

First, I thought it might be nice to apply dynamic programming, by creating a "bad moves" list or dictionary that would be appended every time a leaf-lose case was encountered, and which would be checked every time a new move was to be executed. But then I realized that this was unhelpful, as the same exact move (with the board in the same exact state) would not be executed more than once in one specific run of the game.

So then I developed a different idea, based on the previous tree exercises, and specifically on the recursive breadth_first_visit. Basically, with the execution as it is provided by Silvio, the algorithm is a depth_first_visit (i.e., enters each branch deeply until its last descendant with no children -- a leaf-lose case --is found, and then backtracks one generation, and so on successively). This means that the algorithm has to spend a lot of resources not only by going deeply into each branch, but also by only checking one descendant per generation (to see if it is a leaf-win). The point is that the leaf-win case might be in a higher up in a generation of the tree already created, but that simply has not been checked yet. So, my idea is to do a breadth-first visit through all siblings of each of the built generations, so as to not waste time going too deeply before checking if the leaf-win already exists in the tree.

For this, I only edited the solve() code (and recycled the recursive breadth_visit_first algorithm from last exercise):

def solve(pegs, holes, last_move=Node("start")):

    result = None
    breadth_search = breadth_first_visit(last_move)
    for move in breadth_search:
        if len(pegs) == 1 and (3, 2) in pegs:  # leaf-win base case
            result = move
        else:
            move.children = valid_moves(pegs, holes)
            if len(move.children) == 0:  # leaf-lose base case
                undo_move(move, pegs, holes)  # backtracking
            else:  # recursive step
                possible_moves = deque(move.children)
                while result is None and len(possible_moves) > 0:
                    current_move = possible_moves.pop()
                    apply_move(current_move, pegs, holes)
                    result = solve(pegs, holes, current_move)
                if result is None:
                    undo_move(move, pegs, holes)  # backtracking
        return result

def breadth_first_visit(input, queue=[]):
    if queue:
        queue.remove(queue[0])
    breadth_result = [input]
    queue.extend(input.children)
    if queue:
        breadth_result.extend(breadth_first_visit(queue[0]))
    return breadth_result

What this means is that, while the tree is being created in a recursive depth_first way, the checking for the leaf_win case is done recursively in a breadth_first way. This, in turn, means that no time is wasted in building each branch depth all the way to the leaf if a leaf-win case is already present in the tree.

[hizclick]

Here I have proposed a solution, by applying dynamic programming concept. First, I create a list and put all unsuccessful moves in it. So, before searching for the possible moves from the current position the algorithm checks if the last move was successful or not. If it is already in the list it will call undo_move() function if not it will check possible moves from the current position.

def solve(pegs, holes, last_move=Node("start"), unsuccessful_move=list()):
    result = None
    if len(pegs) == 1 and (3, 2) in pegs:  # leaf-win base case
        result = last_move
    else:
        last_move.children = valid_moves(pegs, holes)
        if last_move.children not in unsuccessful_move:
            if len(last_move.children) == 0:  # leaf-lose base case
                unsuccessful_move.append(last_move)
                undo_move(last_move, pegs, holes)  # backtracking
            else:  # recursive step
                possible_moves = deque(last_move.children)

                while result is None and len(possible_moves) > 0:
                    current_move = possible_moves.pop()
                    apply_move(current_move, pegs, holes)
                    result = solve(pegs, holes, current_move, unsuccessful_move)

                if result is None:
                    unsuccessful_move.append(last_move.children)
                    undo_move(last_move, pegs, holes)  # backtracking'
        else:
            undo_move(last_move, pegs, holes)

    return result

[essepuntato]

Hi all,

I'm posting here my take on the exercise - you can find the source of this online as usual. I've reused all the code of the implementation proposed in the lecture notes, except the function solve which has been appropriately extended.

from peg_solitaire import create_6x6_square_board, valid_moves, apply_move, undo_move, test_solve

# Code of the algorithm
def solve(pegs, holes, last_move=Node("start"), no_win=list()):
    result = None

    if pegs not in no_win:
        no_win.append(set(pegs))

        if len(pegs) == 1 and (3, 2) in pegs:  # leaf-win base case
            result = last_move
        else:
            last_move.children = valid_moves(pegs, holes)

            if len(last_move.children) == 0:  # leaf-lose base case
                undo_move(last_move, pegs, holes)  # backtracking
            else:  # recursive step
                possible_moves = deque(last_move.children)

                while result is None and len(possible_moves) > 0:
                    current_move = possible_moves.pop()
                    apply_move(current_move, pegs, holes)
                    result = solve(pegs, holes, current_move, no_win)

                if result is None:
                    undo_move(last_move, pegs, holes)  # backtracking
    else:
        undo_move(last_move, pegs, holes)  # backtracking

    return result

pegs, holes = create_6x6_square_board()
print(test_solve(pegs, holes, (3, 2)))

A comment on @delfimpandiani take:

the same exact move (with the board in the same exact state) would not be executed more than once in one specific run of the game.

It is true that a particular node in the tree of moves will be reached just once. However, each node is actually identified by the sequence of moves that bring to a particular board configuration, and not by the board configuration itself. In fact, it is possible to reach the same board configuration from different branches of the tree of moves. Thus, that "no win" list should not record the bad moves, but rather the bad configurations of the board, that you are sure have no solution. In this way, a depth-first visit of the tree of moves still works quite well, since the dynamic programming check is done on the board configurations (which are reacheable by different branches) and not on the chain of moves (which are unique, indeed).