Propositions in our model - a list of the variables (holes) with either of the possible values - i.e., "in34", "out65" represent occupied hole in (3,4) and empty hole in (6,5) correspondingly.Domain: each hole can be either occupied by a peg, or empty.Ī state of the problem is an assignment of values from the domain to each of the variables.Variables: the holes on the game board (identified by their cartesian coordinates).In our model, the state is defined by the variables and the domain of the values for them: We created a simple model of the problem, that we could use in our algorithms. After each step (expansion), we checked if the two edges have reached one another - we checked if we found a solution in the middle, something that would save most of the running time of single-direction BFIDA* search.įurthermore, we used several heuristics to improve the algorithm, and another method that could forsee dead-ends - and alter the expansion in their direction.
The idea of the bidirectional search is to start simultaneously from the initial and final states, and expand both via BFIDA* search. In out case, in the english version of peg solitaire, both the initial and final state are defined singularly - and we took advantage of that. The main reason to use a more sophisticated algorithm is run-time.Īs we know, breadth-first algorithm's run time increases as the algorithm advances. We tried to implement an improved version of the known IDA* algorith. One of them is Bi-Directional Breadth-First Iterative Deepening A* search algorithm (BD-BFIDA*) with several heuristics, and the other is Constraint Satisfaction Problem (CSP) with backtracking search algorith. We chose to two different methods - algorithms - to solve the problem. The peg that was "jumped over" is taken off the board, and so on - until only one peg remains. The legal moves in the game are simple: a peg can "jump" over a neighbor peg, if there is an empty hole on the other side. The goal of the game is to reverse the initial state: empty all the holes and leave a single peg in the center. Initially, all the holes except the central hole are occupied by pegs. The game, in it's english version, is a board game with 33 holes. In this project, we tried to create an algorithm to solve a game callled "Peg Solitaire" in it's classical ("English") version.