Marble Solitaire - The Game Solver

Marble Solitaire

Marble solitaire (also called peg solitaire) is a board game that dates back to at least 17th century France. The earliest documentation is the 1687 illustration (shown here) of Anne de Rohan-Chabot, Princess of Soubise, playing the game.

If you’ve ever eaten at a Cracker Barrel restaurant, you may have seen that their dining tables often have a simplified triangle-layout version that uses pegs instead of marbles.

The game is played by moving a marble into an empty hole (traditionally, there is just one empty space in the center to start), “hopping” over exactly one other marble in the process, and the hopped-over marble is removed from the board. The hops can only be up/down/left/right (no diagonal). The game is won when only one marble remains. (In some versions, there is a requirement that the last remaining marble end up in the center hole, but for our version, it can end up anywhere.) Finding a solution can be very difficult for new players. In fact, the origin of this assignment is that over winter break one year, my family spent time at a cabin with this game, and I was so aggravated by not being able to solve it that I decided to code up a solution instead! I realized it was a nice example of a backtracking recursion code solution that 106B students could write too, and here we are!

Here is what the board looks like to start:

As soon as you download the assignment, you will be able to play the marble solitaire game yourself in “human mode” (so a way to procrastinate working on this assignment is built into the assignment!). Take a moment to play the game to learn the rules for valid moves. (Briefly: no diagonal moves; jumps are only one marble wide; no jumping over an already empty space.) You will soon discover that it is challenging to solve. After a few failed attempts, you might say to yourself in frustration, just like I did, “I should just write a program to solve this!”

Here is an animation of human play mode:

Here is an example of a puzzle that a human played for a while, but then reached a state where it is no longer possible to win. There are several marbles remaining, but none is able to make a valid “hop” over another marble.

Example board with no solution remaining:

You’ll notice that there is a “solve” button that asks the computer to pick up where the human leaves off and find a sequence of moves to complete the game, if one exists. But the “solve” button won’t work until you complete the backtracking code!

Here is an animation of computer solve after pressing the solve button:

Now let’s talk about how to write your computer solver!

C++ classes

This is your first time working inside a C++ class! Here’s a quick guide to the files in the project:

• MarbleBoard.h and MarbleBoard.cpp: these are a classic C++ class definition pair, just like we talked about in class in Lecture 13. This is also where much of the code you write will be located.
• marbles.cpp: this is where you will write the solver function that uses the MarbleBoard class.
• marbletypes.h contains two type definitins that you will need to know about, Marble and Move, but you do not really need to look at this file because we have fully described those types below. You must not edit this file.
• MarbleGUI.h, MarbleGUI.cpp, marbletypes.cpp: you do not need to look at these files and must not edit them. You can just ignore them. They run the GUI and the human part of the game, and you should not re-use human game components in your code.

Pay attention to the comments in MarbleBoard.h and MarbleBoard.cpp about what you can and cannot change! Basically, you should keep the public interface as-is (the GUI relies on it!), but you will need to add bodies to some of the functions in the cpp file. And if your function bodies need helper functions, you may add them to the private section of the MarbleBoard.h file, but that is the only change you should be making to that file.

Board representation

A board configuration is represented in code using our Grid ADT. Here is a representation of how that would look when there are just two marbles left:

  XX---XX
  XX---XX
  -------
  -OO----
  -------
  XX---XX
  XX---XX

As you can see in the above visual, we need to distinguish a Grid cell that currently has no marble, but could have a marble, from one that is not actually a valid board position. The invalid board positions are the four corners of the board. Thus each cell of the grid has three possible conditions: empty, occupied, and invalid. If you look in MarbleBoard.h in the private member variables section at the bottom, you will see that the exact type for our board representation is Grid<Marble>. The variable type Marble is a new type of C++ variable, the enum type. An enum type variable can only take on one of a short list of enumerated values (in this case, one of three different values), each of which acts like a defined constant. If you look in the marbletypes.h file, you will see that Marble enum is defined as follows:

enum Marble {
    MARBLE_EMPTY,       // a hole with no marble in it
    MARBLE_OCCUPIED,    // a hole with a marble in it
    MARBLE_INVALID      // not part of the board (the four corners of the grid)
};

In other words, you could make a variable of type Marble and assign it a value like this: Marble marble1 = MARBLE_EMPTY; or test the value of a Marble variable like this: if (marble1 == MARBLE_OCCUPIED). Here is a longer example code passage that accomplishes a pretty silly goal (print “Found a marble!” once for each marble on a board), but should help give you an idea of how it looks to use this new enum in your own code:

void foo(Grid<Marble>& board) {
    for (int row = 0; row < board.numRows(); row++) {
        for (int col = 0; col < board.numCols(); col++) {
            if (board[row][col] == MARBLE_OCCUPIED) {
                cout << "Found a marble!" << endl;
            }
        }
    }
}

The solvePuzzle function

The core of your work is to implement this function in the marbles.cpp file:

bool solvePuzzle(MarbleBoard& board, Vector<Move>& moveHistory)

The function should return true if you found a way to win the game, given the current board state stored in board, and false otherwise. The input vector moveHistory is initially empty, and you should fill it with the sequence of winning moves, if there is one, starting with the first move in index 0 and continuing from there (it doesn’t matter what is stored in the vector if you return false saying there is no solution). By providing the winning sequence by pass-by-reference, the GUI code will be able to animate the winning gameplay.

The solvePuzzle function will be implemented using a recursive backtracking approach, using a recursive helper function. The recursive helper function must also appear in marbles.cpp, alongside the primary solvePuzzle() function.

Recursive search of all possible sequences of legal moves

Your code should run a backtracking recursion search of all possible sequences of legal moves. Pull out the Lecture 11 slides, and go to Slide 27 to remind yourself of our backtracking function template. Then ask yourself the usual questions we ask when adapting this template to a new problem:

• For success base case: what does “success” mean for this problem? (Hint: what did we say above is the criteria for winning the game? More on this below!)
• For failure base case: what does “failure” mean for this problem? (Hint: we will talk about this more below!)
• For recursive case:
  • What constitutes one “step” of work for this problem? (Hint: making one marble move)
  • What set of options should we loop over for our choose-explore-unchoose loop? (Hint: we need to make a Vector that holds all possible legal moves, given the current board state, so we can loop over that vector. More on this below!)

After the choose-explore-unchoose loop completely finishes, with no successful solution found, it means that there is no possible next move that can eventually win. Return accordingly.

Success base case

The test for success is that only one marble remains. (It can be in any valid grid location.) We made it even easier for you to check by putting this test in a MarbleBoard member function called isSolved(), and the implementation is already provided for you in MarbleBoard.cpp. You should take a look at the implementation to verify your understanding, but use this member function, do not re-implement the logic yourself in your solvePuzzle base case.

Keeping track of sequence of moves so far

The function header already provides moveHistory structure that you should use to store the sequence of moves that you build up one-by-one during your choose-explore-unchoose recursive call loop.

bool solvePuzzle(MarbleBoard& board, Vector<Move>& moveHistory)

Keeping track of boards visited so far

The total number of different sequences of moves is enormous, so we want to be smart about how we manage so many options. An important observation is that there are often multiple different sequences of moves that arrive at the same board state. But we only really care that there is at least one way to arrive at that board state, we don’t really care about second and third and fourth ways to reach that same board state.

So we will borrow a trick from the Maze recursive backtracking code that we looked at in class (Lecture 12, Slide 19), and keep track of already-“visited” board states. That way, if we come across one we already generated by a different sequence of moves, we can just stop our exploration, knowing it was already handled. That means this will be your failure base case: the board has already been seen.

To keep track of all the visited boards as a collection of thousands or millions of Grid<Marble>s would be too costly, so instead we will store a compressed version of the board state. We have provided a pre-written MarbleBoard member function called encode() for you to use, which returns type BoardEncoding. You will need to choose an ADT to store your collection of already-visited BoardEncodings, and, since you will need to pass this ADT around in your recursive function calls, you will need to make a recursive helper function for the primary solvePuzzle function.

Finding all possible legal moves

As mentioned above, for the choose-explore-unchoose loop, you will need to make a Vector containing all possible legal moves, given the current board state. To do this, you will need to implement one of the MarbleBoard member functions that you will see already set up for you in MarbleBoard.h and MarbleBoard.cpp:

Vector<Move> findPossibleMoves();

The Move type is a struct defined in the marbletypes.h file as follows:

struct Move {
    GridLocation start;
    GridLocation end;
};

So a Move gives where the hopping marble is starting, and where it should end up.

Hint: The foo example code above is actually a pretty good start to implementing this function, since you’ll want to loop over all cells in the Grid, and for each one that contains a marble (i.e., for each Grid cell that is MARBLE_OCCUPIED), check each of the four directions it could hop (up, down, left, right).

You need to be careful that you only add a Move to the Vector if it meets all the criteria for a legal move! This includes things like: the end space is currently empty, the distance of the “hop” is exactly one marble, the hopped location has a marble, neither the start nor the end is out of bounds of the Grid or MARBLE_INVALID, etc.

Choose and unchoose

For your choose-explore-unchoose, you will use two more helper functions, which you will also implement:

void makeMove(Move move);
void undoMove(Move move);

These functions should update the board state for making and undoing moves. You may assume that the Move is a legal move and, for undoMove(), you may assume that it was indeed the most recent move made. To get you started, the first action I would take for makeMove would be to change the ending location to MARBLE_OCCUPIED. The order of changes doesn’t really matter, but that is one of the three changes you need to make, plus you need to update the MarbleBoard member variable that tracks the current number of marbles.

Development Strategy

• I would recommend going in reverse of how we’ve listed the functions here!

• First, implement makeMove and undoMove. Use test cases to make sure they work perfectly. For testing, notice that there are a number of test board configurations provided for you in the starter code in the boards folder.

• Next, implement findValidMoves. Testing this on boards with a huge number of valid moves will be tricky, so I would recommend starting with a board with only two marbles, side-by-side (like one-jump.txt). Then slowly work up to more complex board configurations.

• Finally, it’s time to tackle the big deal: the backtrackig recursion in solvePuzzle()! First, design the parameter list for your recursive helper function, and then get started on its implementation. If you hold tight to the backtracking template from Lecture 11 Slide 27, you should find it a very satisfying example of that format! Again, when testing this function, you should start out with a board that is just two or three moves away from winning, at most. Do NOT start testing with a full board. The number of board states to explore is too huge and it will be too hard to figure out where things went off track. If things are not going right, set a breakpoint in your solvePuzzle function right after the call to findPossibleMoves() and make sure you agree with the list it returned. Then step through making sure that one move is selected and the “choose” step does all the updates that are needed. Step over the recursive call, and check whether it returned the true/false outcome that you expect for the chosen board state. Then step through the “unchoose” and make sure that does all the updates you expect.

Extending Your Understanding

Once you have a working Marbles solver, head over to short_answer.txt and answer the following two questions which take your understanding of the underlying backtracking principles one step further!

Extensions

• Even with our compressed board “visited” list, the search space is large and the time to find a solution can drag on. See if there are “heuristic” improvements you can make to the search algorithm, such as some rules that would recognize early on if a board is hopeless even though a few more next moves may be possible. Do some timings with different start boards to see how much your heuristics help. (Heuristic improvements are those that do not change the fundamental underlying algorithm and are not guaranteed to be successful in improving performance, but may make some worthwhile performance improvements nonetheless.)

• This solver is deterministic, meaning that given the same input board, the same sequence of winning moves will be given every time, even though there may be many many different possible solutions. Change this behavior so that each time it runs, the order of trying next moves is random, giving the user more variety.