The symmetry check helps prune the search tree of duplicate branches that are merely a rotation of another a branch. I also implemented another form of graph search that checks for symmetrical board configurations, and adds those to the visited list too. The fact that this heuristic isn't admissable has allowed the search to be more descerning in the boards that it picked and actually reach the goal faster than it would have using an admissble heuristic. That being said, for previously discussed reasons, this actually isn't an issue for this particular puzzle: there are no 'optimal' solutions because they all take an equal number of moves to reach. Regarding admissability, this heuristic is actually not admissable in the traditional sense that it will never overestimate the cost of reaching the goal. The heuristic performed quite well on boards under 8x8, but past this point the heuristic slowed down the search considerably.

My manhattan distance heuristic takes O(N^4) operations, where N is the length or width of the board. One downside of this heuristic is the abysmal computational overhead.

Overall, the heuristic performed quite well! It was the only one of the heuristics to beat the simple DFS implementation, and performed consistently better by several factors of magnitude on every board I could find than anything else. I chose this heuristic because it favored board configurations that were more clumped together (the average distance being smaller) and punished boards that were too spread out or left too many isolated pegs, either of which could indicate a dead-end. Extra Credit Manhattan Distanceįor my extra credit, I implemented a manhattan distance function that calculated the manhattan distance from every peg to every other peg on the board, and then divided that score by the number of pegs on the board times two. Regarding optimality, the peg puzzle does not really have an ‘optimal’ solution, in that all solutions will always occur after the same number of moves and therefore all paths are in fact optimal. In the peg puzzle, this is not the case: although there are duplicate states, no move will ever lead to itself again and so there is not risk of falling into loops. Regarding completeness, naive DFS in most search spaces can easily end up getting trapped in loops around the same states. Upon more careful inspection this is due to the fact that the heuristics that are being used are extremely poor predictors of performance.Īpplying DFS to the peg puzzle is especially effective due to the fact the nature of the puzzle solves most of the ‘problems’ that typically emerge in dealing with DFS: namely completeness and optimality.

In actuality though, the opposite it true: A* found a solution only marginally faster than BFS, and was several factors of magnitude slower than uninformed DFS. It occurred to me that the heuristics that we were testing with were not ideal, but I had presumed that they would manage to find a solution at least as quickly as DFS. What I had not anticipated was how poorly A* and IDA* performed. I had anticipated that it would perform far better than breadth first search (BFS): all the available solutions occur at depth 13, and they are fairly numerous. Of all the search strategies, depth first search (DFS) performed the best by far. Written using Python3.4 with numpy 1.9.2 Analysis of Search Strategies

Peg solitaire solutions