Description
Introduction
The eight-puzzle game is a 3 × 3 version of the 15-puzzle in which eight tiles can be moved
around in nine spaces (an amusing game can be played here 8-puzzle
(https://murhafsousli.github.io/8puzzle/#/)). Because the eight-puzzle game generates a smaller state
space than the full 15-puzzle and its graph fits easily on a page, however they follow the same
state space representation and search strategies, therefore we use eight puzzle game as our project
in this course.
There are eight numerical tiles and one blank tile in the eight-puzzle game. We specify a
beginning state and a goal state for the 8-puzzle, it is possible to give a state space accounting of
the problem-solving process, as shown below two figures for the example of beginning and goal
state of the eight-puzzle game.
2 3 6
1 4 8
7 5 0
Fig. 1 An example of the beginning state of the eight-puzzle game (here 0 stands for the blank
tile)
Fig. 2 The goal state of the eight-puzzle game (here 0 stands for the blank tile)
A state is a panel contains the 9 spaces with 9 tile numbers. The blank tile is moved legally in
the 3 × 3 panel until the state reaches the final goal state. Fig. 3 exemplifies partial of a state
generation graph with state space and arcs. A naive implementation of brute force exhaustive
search may successfully find the goal state. But the problem size increases as the puzzle size
increases.
2
Fig. 3 A partial example of a state generation graph of the eight-puzzle game.
The state space of 8-puzzle is represented by a rooted graph such as Fig. 3. The legal moves
are:
a) move the blank up ↑
b) move the blank right →
c) move the blank down ↓
d) move the blank left ←
Each time, the game allows one tile replace. In the provided code implementation, tile labeled
with 0 represents the blank tile. The difference between start state and the goal state is the crux for
solving the game.
Project Requirement
In this project, we need to design and implement different search algorithms that we learned in
the AI class to solve the eight-puzzle game problem automatically. The detailed requirements are:
1. Using uninformed search method to solve the 8-puzzle game problem (30%)
Please select one of the learned uninformed search algorithms (breadth-first search, depth-first
search, or iterative deepening search) to implement to solve the 8-puzzle game problem. More
details about these three algorithms can be found in Chapter 3.2.3 and 3.2.4.
g(0)
g(1)
g(2)
3
2. Informed search (50%)
Please use the best_first_search algorithm along with heuristic search rules to construct the
body of the program to solve the 8-puzzle game problem. Similar to uninformed search method,
best-first search uses lists to maintain states:
an OPEN list is used to store the unexplored states
a CLOSE list is used to store the visited state
OPEN list is a priority queue. The priority is insured through sorting the OPEN list each time
after new states are generated and added into the list. At each iteration, best_first_search removes
the first element from the OPEN list. If it meets the goal conditions, the algorithm returns the
solution path that led to the goal. Note that each state retains ancestor information to determine if
it had previously been reached by a shorter path and to allow the algorithm to return the final
solution path.
The heuristics are used as sorting criteria. In this informed search, reducing the state space
search complexity is the main criterion. We define heuristic evaluations to reduce the states that
need to be checked every iteration. Evaluation function is used to express the quality of
informedness of a heuristic algorithm.
Evaluation function 𝑓(𝑛)
𝑓(𝑛) = 𝑔(𝑛) + ℎ(𝑛)
𝑔(𝑛) measures the actual length of the path from any state n to the start state
ℎ(𝑛) is a heuristic estimate of the distance from state 𝑛 to a goal.
In this 8-puzzle game project, we have
𝑔(𝑛) = actual distance from n to the start state
ℎ(𝑛) = Number of tiles out of place + Sum of distance out of place + Number of direct tile of
reversals
As can be see that three heuristics are adopted in this implementation:
A. Number of tiles out of place
Count the number of tiles that are misplaced through compare the start and goal state.
B. Sum of distance out of place
Count the number of steps needed to move the tile to the correct location. If we treats the
8-puzzle as a 2d array, then this part can be treated as the absolute value of offsets between
the correct location in goal state and deviant location in start state of the same tile.
C. Number of direct tile of reversals
Number of the adjacent tile pair which the location are reversed.
4
3. Comparison analysis. (10%)
Please test the search process of your implemented uninformed search algorithm and informed
search algorithm in terms of computational cost and the length of the path for solving the 8-puzzle
game problem. Write down your detailed analysis and comparison conclusion.
Note that,
(1) to get the computational time of specific program statements or segments you can use the
following to statements
t0 = time.time()
your program statements
t1 = time.time()
ComputationalTime = (t1-t0)
(2) to get fair comparison, you better to use the same experimental platform (the same computer)
4. Bonus points (Optional) (10%)
Employing more informed heuristic estimation. By adding more restrictions into the heuristic
test function. Currently there are three heuristics which elaborated in the informed search section.
There may exist other possible heuristics, for example, recursively check the shortest path, fine
tune the parameter, and so on. Especially, for complicated initial state in some case, it took a long
time to reach the goal by using the informed search algorithm mentioned above. If your newly
added heuristic rule(s) improved the search process compared with the above uninformed and
informed search algorithms, then you will get this bonus points.
5. Project report (10%)
You have to write a project report for this project. You have to complete the template and submit
it together with your project source code. The length of the report must longer than 1 page. The
template of the project report is attached in the project zip file.
5
Result and Discussion
The output is the path from the original state to the goal state. We can use this to verify the
correctness and optimality of our algorithms. Two sample runs are shown below (of course, you
can define the display mode by yourself). Note that these two sample runs, shows the results of
Informed Search Algorithm only:
Sample Run 1:
Sample Run 2:
Hand In Requirements
(1) The starter code is provided in Python language. You must follow the provided starter code to
finish this project. There are two reasons for this:
a. To prevent plagiarism;
b. Reading and understanding other people’s code should be one the ability of CS students.
Note that if your team choose to use Java to implement this project, please contact me for the
information about the starter code.
(2) If you completed this project, you need to hand in the source code been completed by you or
your group. Your source code compressed to a single ZIP file. The name of the code archive
should be EightPuzzle_Teamname.zip.
The code should be well commented, and it should be easy to see the correspondence between
what’s in the code and what’s in the report. You don’t need to include executable or various
supporting files (e.g., utility libraries) whose content is irrelevant to the assignment. If the
6
instructor finds it necessary to run your code in order to evaluate your solution, the instructor
will get in touch with you.
(3) You need to run both your solvers on several input puzzles and included the results in your
project report.
Your output when run the below two initial state:
2 3 6 2 3 1 the goal state is 1 2 3
1 4 8 0 4 6 4 5 6
7 5 0 7 5 8 7 8 0
(4) A project report in PDF format
The report should briefly describe your implemented solution and fully answer all the
questions posed above. Remember: you will not get credit for any solutions you have
obtained, but not included in the report.
All group reports need to include paragraph of individual contribution, i.e., which group
member was responsible for which parts of the solution and submitted material. The
instructor reserves the right to contact group members individually to verify this
information.
Describe the solution and compare the number of attempted search steps and execution
time for your uninformed search method and informed search method implementations.
The name of the report file should be EightPuzzle_Teamname.pdf. Don’t forget to include
the names of all group members and the number of credit units at the top of the report. (You
can find the report template on the provided zip file together with the starter code.)
Finally, which part you think can be improved and if you have better heuristic estimation.
Or the challenges you encountered during this project.
Note that, the instructor reserves the right to give bonus points for any advanced exploration
or especially challenging or creative solutions that you implement. If you submit any work
for bonus points, be sure it is clearly indicated in your report.
WARNING: You will not get credit for any solutions that you have obtained, but not
included in your report!