Triangle / Peg Solitaire Solver

[zekish]

Hello, all. I am in the process of writing a peg solitaire solver in Python. It will allow the user to select the shape of the board in the future but for now I'm testing it with a standard 5 row triangle game, like the ones you find in Cracker Barrel. It's the game where you start out with pegs in holes, with one hole empty, then jump pegs (like checkers) and try to get exactly one peg remaining in the end. My solver will solve for all solutions for a given starting hole, whether the game ends with one peg, two, etc.

I chose Python as my language of choice for a few reasons:

• I'm new to Python so I want to learn it.
• I initially thought my data structure would be more involved so I chose Python over C++ to open up the opportunity to use dictionaries.
• Taking user-entered strings and using them as integers is just easier in interpreted languages.

Turns out C++ probably wouldn't have been too bad a choice but I'm enjoying the experience of learning Python.

Below, you'll find the code for the main recursive algorithm for moving along the board and solving it. The background you may need to understand it is as follows:

• There is a Simulation class that instantiates a simulation object, which contains the move() function. It also has as one of its members a list called moves , which stores all the moves for each possible path that can be taken for each game.
• board is a board object and temp_stack is the running stack for a current try at solving the game.
• board.poss_moves is a list of all possible moves the 5 row triangle board contains.

So, when move is called, it checks to see if there are any moves left. If not, the game is over. It appends to the simulation.moves list a snapshot of the game and returns. If the game is not over, it cycles through the list of all possible moves and checks to see which ones that apply to the state of the board that has been passed through as a parameter. If a move can be made, it deep copies a new board and stack (so there can be fresh, new objects being passed into the recursion tree), adjusts the board copy, and updates the temp_stack copy that a new move has been made. Recursion happens as move is called again with the copies as arguments.

The idea is that when the game ends, the program backs out of the recursion tree and picks up where it left off in the main loop. I know Python uses pass by reference so I was a bit unsure as to whether I'd be able to use a recursion tree effectively so this is why I used deep copy, so that there is a previous version of the board and temp_stack to revert to when the back tracking occurs. After all the loops expire, the program should back fully out of recursion and resume. But it doesn't. In fact, it winds up freezing up the computer.

Any thoughts as to what I'm doing wrong? Also, feel free to offer up ideas on how you might do this. I know other people have written peg solitaire solvers. Some have actually explicitly created tree data structures to house each board state but I feel that is not necessary if you use the 'imaginary' recursion tree.

Here's the move function:

def move(self, board, temp_stack):
        if board.game_end():
            self.moves.append({'final_peg_num': board.count_pegs(), 'list': temp_stack})
        else:
            for i in range(len(board.poss_moves)):
                if board.can_move(board.poss_moves[i]):
                new_board = deepcopy(board)
                new_stack = deepcopy(temp_stack)

                # move the peg and adjust the board
                new_board.set_val(board.poss_moves[i])

                # Append the stack
                new_stack.append(board.poss_moves[i])

                self.move(new_board, new_stack)

May the discussions begin!

[TrustyTony]

As I see, you are not getting any use out of your recursion, no modified self variables or using a return value from recursion (and actually no returned value in any case). And you should have one stack to keep saved states not new each time or I do not understand what you are doing. Did you do your algorithm by hand for some simple end game situations to check your algorithm?

Your indention is off for lines 7 onwards.

[Gribouillis]

I don't have the time to study your code now (the whole program could be useful) but I think it could be a use case for this snippet that I wrote some weeks ago http://www.daniweb.com/software-development/python/code/395270 . See if it applies to your problem.

[zekish]

As I see, you are not getting any use out of your recursion, no modified self variables or using a return value from recursion (and actually no returned value in any case).

I had a version where I was popping from the temp stack and undoing board updates but that wasn't working right, either. I was able to get it to run through once but it wouldn't loop right so the sim ended after the first game was over. The idea behind this implementation is that the loop iterator, i, is what is changing and controlling how long the program stays in the function. I'm not a fan of looping in a recursive function, though, but it seemed like a simple way to iterate.

And you should have one stack to keep saved states not new each time or I do not understand what you are doing. Did you do your algorithm by hand for some simple end game situations to check your algorithm?

The purpose of creating new stacks is to use the recursive tree to store unique board and stack structures locally within each recursive call so there would be no need to either create an explicit data structure or "back up" by popping and resetting the board. I've actually played through the game on paper, using quarters for pegs, to research the actual game play. It has helped quite a bit.

Your indention is off for lines 7 onwards.

Yeah, sorry about that. Paste error.

[zekish]

I don't have the time to study your code now (the whole program could be useful) but I think it could be a use case for this snippet that I wrote some weeks ago http://www.daniweb.com/software-development/python/code/395270 . See if it applies to your problem.

It might but it's quite a bit to read right now, between the comments and the code. I like recursion because in instances like this, it would seem even harder to write the code non-recursively. Recursive code can be hard to write but once you figure it out, it's quite elegant and easy to follow. I'm also using this project as a means to help me get the hang of recursion more. It's a challenge but one I'm dealing with. Thanks for the input!

[woooee]

def move(self, board, temp_stack):
            if board.game_end():

What does the function game_end test? Definitely not new_board or new_stack since they are not instance variables and are not passed to the function, so the game_end function is testing some container that does not change. Add a print statement to the function to see what is really happening.

[zekish]

def move(self, board, temp_stack):
            if board.game_end():

What does the function game_end test? Definitely not new_board or new_stack since they are not instance variables and are not passed to the function, so the game_end function is testing some container that does not change. Add a print statement to the function to see what is really happening.

board.game_end() is testing board (the incoming parameter) to see if there are any moves left on the board. Since new_board is being passed to move, game_end() is testing new_board. board is just a reference to new_board.

[woooee]

Is "board" a class instance with a function named "game_end" or some other container, as a class instance can not be tested, but only a container in that class can contain moves. Perhaps you should include the end_game function as well as the code that creates the instance of the class board.

def move(self, board, temp_stack):

If board is a class instance with a game_end function, then you are passing the class to this function twice, i.e. self & board, unless board is an instance of a second, different class.

[zekish]

Is "board" a class instance with a function named "game_end" or some other container, as a class instance can not be tested, but only a container in that class can contain moves. Perhaps you should include the end_game function as well as the code that creates the instance of the class board.

def move(self, board, temp_stack):

If board is a class instance with a game_end function, then you are passing the class to this function twice, i.e. self & board, unless board is an instance of a second, different class.

move is not a member function of the GameBoard class (of which board is an instantiated object). It is a function of another class called Simulation. I'm not quite following what you're saying.