A program that uses various search algorithms to solve pegboard games
Pegboard Solver
This program was an assignment for CS 580 – Introduction to Artificial Intelligence at
Old Dominion University during the Fall 2020 semester.
Pegboards of various dimensions (4×4 thru 8×8) are solved by search algorithms
including:
- Breadth First Search
- Depth First Search
- Greedy Best First Search
- A* Search
Execution
This program was originally written in Python and is re-done in Dart; its SDK can be
installed here. Additionally, the program is run in the command-line
by executing the following command:
Executables are located in the bin directory.
# Unix-based
./solver [argument]
# Windows
solver.exe [argument]
The following arguments are valid and not case-sensitive:
| Argument | Search Algorithm |
|---|---|
breadth |
Breadth First Search |
depth |
Depth First Search |
greedy |
Greedy Best First Search |
a_star |
A* Search |
Additionally, the --help flag can be used as an argument to bring up the list of search
algorithms.
Report
Note: Times for larger pegboards varies greatly. For time’s sake, I went for
quick-to-get solutions; generally it will take much longer. The 4×4 pegboards are
consistant with the results however.
Breadth First Search
Of all the search algorithms, Breadth First took the longest as it works down the fringe
generation by generation.
Source: https://en.wikipedia.org/wiki/Breadth-first_search
This as a result makes it take a considerable amount of time to find a solution when used
on pegboards with dimensions above 4×4. When running the algorithm on 4×4 pegboards,
solutions were found after 1869 unique states and either 1686 or 2114 if there
were none.
4×4 Solution
0 0 1 0
0 0 0 0
0 0 0 0
0 0 0 0
-- Goal State found --
Unique states explored: 1869
Total search time: 0:00:00.308898
Depth First Search
Depth First search works its way down the fringe, going from left to right. This has the
chance to make the search mroe memory efficient when compared to Breadth First. However,
if the solution is not found or is farther right in the fringe, the benefits are lost.
When running this search algorithm against the pegboards, I found that solutions were
found much faster than Breadth First search. When a solution was found, usually under
100 unique states were visited. Another finding to note is that solutions for larger
pegboards were more realistic to achieve.
4×4 Solution
0 0 1 0
0 0 0 0
0 0 0 0
0 0 0 0
-- Goal State found --
Unique states explored: 37
Total search time: 0:00:00.018837
5×5 Solution
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 1 0 0
-- Goal State found --
Unique states explored: 45711
Total search time: 0:00:46.585281
6×6 Solution
0 1 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
-- Goal State found --
Unique states explored: 575
Total search time: 0:00:00.171659
Greedy Best First Search
Greedy Best First search is Depth First search with an admissible heuristic. The heuristic
allows for pegboards that appear more “promising” to be selected over others, resulting in
a solution being found quicker in some cases. Heuristics do not guarentee an optimal path
is being taken.
For this program, Manhatten Distance is
used as a heuristic. This heuristic was selected as it is more likely for a solution to be
obtained when pegs are more towards the center.
4×4 Solution
0 0 0 0
0 0 0 1
0 0 0 0
0 0 0 0
-- Goal State found --
Unique states explored: 21
Total search time: 0:00:00.019271
4×4 Solution
0 0 0 0
0 0 0 0
0 0 0 0
0 1 0 0
-- Goal State found --
Unique states explored: 15
Total search time: 0:00:00.018762
5×5 Solution
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 1 0 0
-- Goal State found --
Unique states explored: 711
Total search time: 0:00:00.167668
6×6 Solution
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 1
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
-- Goal State found --
Unique states explored: 3257
Total search time: 0:00:00.857798
A* Search
A* search extends Greedy Best First
search by applying path cost alongside the heuristic, Manhatten Distance. In the case
of pegboards, states with less moves are generally favored, allowing for the optimal path
to be much more likely be found. In smaller boards, such as 4×4, the effects of the
algorithm were not really noticable; however, it becomes effective in the other dimensions.
4×4 Solution
0 0 0 0
0 0 0 0
0 0 0 0
0 1 0 0
-- Goal State found --
Unique states explored: 18
Total search time: 0:00:00.053961
4×4 Solution
0 0 0 0
0 0 0 0
0 0 0 0
0 1 0 0
-- Goal State found --
Unique states explored: 15
Total search time: 0:00:00.016254
5×5 Solution
0 0 0 0 0
0 0 0 0 0
1 0 0 0 0
0 0 0 0 0
0 0 0 0 0
-- Goal State found --
Unique states explored: 1116
Total search time: 0:00:00.088612
6×6 Solution
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 1 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
-- Goal State found --
Unique states explored: 46367
Total search time: 0:00:49.095035