Peg Solitaire
What is the problem?
Our project will be implementing the game of Peg Solitaire in Haskell. During the game, a player is presented with a board that looks like the first figure.
Where each dot represents a peg, and the circle in the middle represents an empty spot. The player can then move pegs according to the following rule: A valid move is to jump a peg orthogonally over an adjacent peg into a hole two positions away and then to remove the jumped peg. For example, the player could perform the following action: d6 to d4, resulting in the second figure.
The goal of the game is to remove all the pegs from the board expect one, which must end up in the center of the board (in position D4).
What is the something extra?
Our game will include a solver that, given the state of a Peg Solitaire game, will produce the steps needed to solve that game. Users can use this as a ‘hint’, to help them get unstuck, or just to complete the game for them.
What did we learn from doing this?
Haskell was suitable for implementing peg solitaire, as we were able to represent the various aspects of the board and play-sequence through user-defined types. Due to the simplicity of the board, we decided to make the game run fully through the terminal (but still incorporating a fun user-experience). We implemented a game of peg solitaire from start to finish, which a user can play with relative ease. While displaying the irregularly-shaped board and computing the and moves was not trivial, most of the hard work during the project was done on creating an AI solver for the game.
While the game initially seems simple, it is incredibly challenging to find a solution by yourself. In fact, there is a large collection of literature that seeks to design algorithms for solving the puzzle. The challenge of the problem mostly stems from the sheer number of possible states (8,589,934,590 distinct boards to be exact)––it has been shown to be NP-Complete in previous studies. For our solver, we adapted a backtracking generic search algorithm, which implements depth-first search (since all of the solutions are deep into the tree). However, due to the size of the search space, this simple algorithm is unable to solve a starting board in less than a few hours. Therefore, we decided to exploit the symmetry of the problem (each board state has 7 “congruent” board states, due to the shape of the board), and hash the board states into numbers such that all congruent board states would be assigned the same number. Then, whenever a board state was found not to lead to a solution, its hashed value would be stored in a memory object that is passed to further recursions. This allowed us to avoid recursing on redundant board states, which saves a lot of compute time.
However, the functional nature of Haskell somewhat limited this memoization. Since the memory had to be threaded through each recursive function, the saved (previously failed) boards were not consistent between different levels of the search tree. If we were able to store the previous failures in a global dictionary, this would not have been an issue. For this reason, our hashing optimization was not as successful as others, but we were still able to significantly reduce the time complexity using this optimization.
Overall, we learned how to implement a search algorithm using a functional programming language, which came with its own strengths and limitations. We then added this solver to the game, so that if at any point a player get frustrated and wants to find a solution from a given board state, they can do so. After solving the problem, the solver then prints out the board during each move in the winning sequence.