![peg solitaire solving algorithm peg solitaire solving algorithm](https://www.codeproject.com/script/Membership/ProfileImages/%7B606ffc8a-b6ed-49d0-8717-4ebe8375cc8a%7D.jpg)
In our project we implemented the methods that create the files needed for the algorithm (the domain files and problems files) - all they need is a list of the holes (in cartesian coordinates) participating in the game, and the rest of the work will be done by our program, so with little work - many interesting, similar problems can be solved - the search method is general-purposed.Satisfiability and Peg Solitaire Satisfiability and Peg Solitaire The other solution - using CSP - did work, and has a important benefit: it is very easy to apply to boards in any shape - not just the english version. We used several other methods that we hoped that would help searching - by trying to eliminate dead-ends as early as possible - but unfortunately they were effective only in advanced stages, and did not help as much as we have hoped they would.The heuristic functions that we used were not good enough, and did not improve significantly the search.When we analyzed our results (or lack of results), we have proposed two possible reasons why our BFIDA* algorithm did not work as expected: Our CSP model, though, did work (with the mentioned search method), and easily converged to a solution within a very short time (less than a second). Sadly, our BD-BFIDA* algorithm did not yield the result we expected - it would not converge in an acceptable time. The Search algorithm that we used is the search method given to us in exercise 3.Goal State in the english version is the exact opposite of the initial state.Initial State in the english version is a list of "inXY" for all of the holes in the game (that are initially occupied) and "outXY" for the central hole - which is empty.Actions in out model are the possible moves in the game (jumping with a peg over another peg), with the corresponding restrictions according to the rules.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.
![peg solitaire solving algorithm peg solitaire solving algorithm](https://www.beyondthealgorithm.ca/wp-content/uploads/2020/05/1404314432.png)
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.