ACADEMIC HONESTY
As usual, the standard honor code and academic honesty policy applies. We will be using automatedplagiarism detectionsoftware to ensure that only original work is given credit. Submissions isomorphic to (1) those that exist anywhere online, (2) those submitted byyour classmates, or (3) those submitted by students in prior semesters, will be detected and considered plagiarism.
INSTRUCTIONS
In thisassignmentyou will create an agent to solve the 8-puzzlegame. You may visit
mypuzzle.org/sliding
for a refresher of the rules of the game. You will implement and compare several search algorithms and collect some statistics related to their performances. Please read all sections oftheinstructions carefully:
I.Introduction
II.AlgorithmReview
III.What You Need To Submit
IV.What Your Program Outputs
V.Important Information
VI.Before YouFinish
NOTE: This project incorporates material learned from bothWeek 2(uninformed search) andWeek 3(informed search). Since this project involves a fair amount of programming and design, we are releasingit now to let you get started earlier. In particular, do not worry ifcertain concepts (e.g. heuristics, A-Star, etc.) are not familiar at this point; you will understand everything you need to know by Week 3.
Alsonote that there isskeleton code available for use(see the third tab of this assignment). This iscompletely optional to use, and you may alter it as much as you'd like. Youmay also complete the assignment withoutreferring to the skeleton code at all.
I.Introduction
An instance of the N-puzzle game consists of aboardholding N = m^2 − 1 (m = 3, 4, 5, ...) distinct movable tiles, plus an empty space. The tiles are numbers from the set {1, …, m^2 − 1}. For any such board, the empty space may be legally swapped with any tile horizontally or vertically adjacent to it. In this assignment, we will represent the blank space with the number 0 and focus on the m = 3 case (8-puzzle).
Given an initialstateof the board, the combinatorial search problem is to find a sequence of moves that transitions this state to the goal state; that is, the configuration with all tiles arranged in ascending order ⟨0, 1, …, m^2 − 1⟩. The search space is the set of all possible states reachable from the initial state.
The blank space may be swapped with a component in one of the four directions {‘Up’, ‘Down’, ‘Left’, ‘Right’}, one move at a time. The cost of moving from one configuration of the board to another is the same and equal to one. Thus, the total cost of path is equal to the number of moves made from the initial state to the goal state.
II.Algorithm Review
Recall from the lectures that searches begin by visiting the root node of the search tree, given by the initial state. Among other book-keeping details,three majorthings happen in sequence in order tovisit a node:
- First, weremovea node from the frontier set.
- Second, wecheckthe state against the goal state to determine if a solution has been found.
- Finally, if the result of the check is negative, we thenexpandthe node. To expand a given node, we generate successor nodes adjacent to the current node, and add them to the frontier set. Note that if these successor nodes are already in the frontier, or have already been visited, then they shouldnotbe added to thefrontier again.
This describes the life-cycle of a visit, and is the basic order of operations for search agents in this assignment—(1) remove, (2) check, and (3) expand.In this assignment, we will implement algorithms as described here. Please refer to lecture notes for further details, and review the lecture pseudocode before you begin the assignment.
IMPORTANT:Note that you may encounter implementations elsewhere that attempt to short-circuit this order by performing the goal-check on successor nodes immediately upon expansion of a parent node. For example, Russell & Norvig's implementation of breadth-first searchdoes precisely this. Doing so may lead to edge-case gains in efficiency, but do not alter the general characteristics of complexity and optimality for each method. For simplicity and grading purposesin this assignment,donot make such modifications to algorithms learned in lecture.
III.What You Need To Submit
Your job in this assignment is to writedriver.py, which solves any 8-puzzle board when given an arbitrary starting configuration. The program will be executed as follows:
$ python3 driver.py
The method argument will be one of the following. You need to implement all three of them:
bfs(Breadth-First Search)
dfs(Depth-First Search)
ast(A-Star Search)
The board argument will be a comma-separated list of integers containing no spaces. For example, to use the bread-first search strategy to solve the input board given by the starting configuration {0,8,7,6,5,4,3,2,1}, the program will be executed like so (with no spaces between commas):
$ python3 driver.py bfs 0,8,7,6,5,4,3,2,1
IMPORTANT: The version of the python that we are using isPython 3.6.4.
IV.What Your Program Outputs
When executed, your program will create / write to a file calledoutput.txt, containing the following statistics:
path_to_goal: the sequence of moves taken to reach the goal
cost_of_path: the number of moves taken to reach the goal
nodes_expanded: the number of nodes that have been expanded
search_depth: the depth within the search treewhen the goal node isfound
max_search_depth: the maximum depthof the search tree in the lifetime of the algorithm
running_time: the total running time of the search instance, reported in seconds
max_ram_usage: the maximum RAM usage in the lifetime of the process as measured by theru_maxrssattribute in theresourcemodule, reported in megabytes
Example #1:Breadth-First Search
Supposethe program is executed for breadth-first search as follows:
$ python3 driver.py bfs 1,2,5,3,4,0,6,7,8
Whichshould lead to the following solutionto the input board:
.
The output file (example) will containexactlythe following lines:
path_to_goal: ['Up', 'Left', 'Left']
cost_of_path: 3
nodes_expanded: 10
search_depth: 3
max_search_depth: 4
running_time: 0.00188088
max_ram_usage: 0.07812500
.
Example #2: Depth-First Search
.
Suppose the program is executed for depth-first search as follows:
$ python3 driver.py dfs 1,2,5,3,4,0,6,7,8
Whichshould lead to the following solutionto the input board:
.
The output file (example) will containexactlythe following lines:
path_to_goal: ['Up', 'Left', 'Left']
cost_of_path: 3
nodes_expanded: 181437
search_depth: 3
max_search_depth: 66125
running_time: 5.01608433
max_ram_usage: 4.23940217
.
Other test cases are available onWeek 2 Project: Implementation FAQspage.
Note on Correctness
.
Of course, the specific values forrunning_timeandmax_ram_usagevariableswillvary greatly depending on the machineused and the specific implementation details; there is no "correct" value to look for. They are intended to enable you to check the time and space complexity characteristics of your code, and you should spend time to do so. All theother variables, however, will haveone and only onecorrect answer foreach algorithm and initial board specified in the sampletest cases.*A good way to check the correctness of yourprogram is to walk through smallexamples by hand, like the ones above.
.
*In general,for any initial board whatsoever, for BFS and DFS there is one and only one correct answer. For A*, however, youroutput ofnodes_expandedmay vary a little, depending on specific implementation details. You will be fine as long as your algorithm conforms to allspecificationslisted in these instructions.
V.Important Information
Please read the following information carefully. Since this is the first programming project, we are providing many hints and explicit instructions.Before you posta clarifying question on the discussion board, make sure that your question is not already answered in the following sections.
1.Implementation
You will implement the following threealgorithms as demonstrated in lecture. In particular:
Breadth-First Search. Use an explicit queue, as shown in lecture.
Depth-First Search. Use an explicit stack, as shown in lecture.
A-Star Search. Use a priority queue, as shown in lecture. Forthe choice of heuristic, use theManhattanpriority function; that is, the sum of the distances of the tiles from their goal positions. Note that the blanks space is not considered an actual tile here.
2. Order of Visits
In this assignment, where an arbitrary choice must be made, we alwaysvisitchild nodes in the "UDLR" order; that is, [‘Up’, ‘Down’, ‘Left’, ‘Right’] in that exact order. Specifically:
Breadth-First Search. Enqueue in UDLR order; dequeuing results inUDLR order.
Depth-First Search.Push onto the stack in reverse-UDLR order; popping off results in UDLR order.
A-Star
Search.Since you are using a priority queue, what happens when there are duplicate keys? What do you need to do to ensure that nodes are retrieved from the priority queue in the desired order?
3. SubmissionTest Cases
You cansubmityourproject any number of times before the deadline. Only the final submission will be graded. Following each submission, all threeofyour algorithmswill be automaticallyrun ontwo sample test cases each, for a total of6distinct tests:
Test Case #1
python3 driver.py bfs 3,1,2,0,4,5,6,7,8
python3 driver.py dfs 3,1,2,0,4,5,6,7,8
python3 driver.py ast 3,1,2,0,4,5,6,7,8
Test Case #2
python3 driver.py bfs 1,2,5,3,4,0,6,7,8
python3 driver.py dfs 1,2,5,3,4,0,6,7,8
python3 driver.py ast 1,2,5,3,4,0,6,7,8
Thisis provided as a sanity check for your code and the required output format. In particular, this is intendedto ensure that you do not lose credit for incorrect output formatting.Make sure your code passes at leastthese two test cases. You will see that the results of each test areassessed by8items: 7 items are listed inSectionIV. What Your Program Outputs. The last point isfor code that executes and produces any output at all. Each item is worth 0.75 point.
4. Grading and Stress Tests
We will grade yourproject by runningadditional test caseson your code. In particular, there will be fivetest cases in total, each tested on all threeof your algorithms, for a total of15distinct tests. Similar to the submission test cases, each test will be graded by 8items, for a total of 90points.Plus, we give 10 points for code completing all 15 test cases within 10 minutes. If you implement your code with reasonabledesigns of data structures, your code will solve all 15 test cases within a minute in total.We will be using a wide variety of inputs to stress-test your algorithms to check for correctness of implementation. So, we recommend that you test your own code extensively.
Do not worry about checking formalformed inputboards, including boards of non-square dimensions, or unsolvable boards.
You will not be graded on the absolute values of your running-time or RAM usage statistics.The values of these statistics can vary widely depending on the machine.However, we recommend that you take advantage of them in testing your code.Try batch-running your algorithms on various inputs, and plotting your results on a graphto learn more about thespace and time complexity characteristics of your code. Just because an algorithm provides the correct path to goal does not mean it has been implemented correctly.
5. Tips on Getting Started
Begin by writing a class to represent thestateof the game at a given turn, including parent and child nodes. We suggest writing a separatesolverclass to work with the state class. Feel free to experiment with your design, for example including aboardclass to represent the low-level physical configuration of the tiles, delegating the high-level functionality to the state class. When comparing your code with pseudocode, you might come up with another class for organising specific aspects of your search algorithm elegantly.
You will not be graded on your design, so you are at a liberty to choose among your favorite programming paradigms. Students have successfully completed this project using an entirely object-oriented approach, and others have done so with a purely functional approach. Your submission will receive full credit as long as your driver program outputs the correct information.
VI.Before YouFinish
Make sureyour code passes at least thetwo submission test cases.
Make sureyour algorithms generate the correct solution for an arbitrary solvable problem instance of 8-puzzle.
Make sureyour program always terminates without error, and in a reasonable amount of time.You will receive zero points from the grader if your program fails to terminate. Running times of more than a minute or two may indicate a problem with your implementation.If your implementation exceeds the timelimit allocated (20 minutes for all test cases), your grade may be incomplete.
Make sureyour program output follows the specified format exactly. In particular, for the path to goal, use square brackets to surround the list of items, use single quotes aroundeach item, and capitalize the first letter of each item. Round floating point numbers to 8places after the decimal. You will not receive proper credit from the grader if your format differs from the provided examples above.
USE OF VOCAREUM
This assignment uses Vocareum for submission and grading. Vocareum comes equipped with an editing environment that you may use to do your development work. You areNOTrequired to use the editor. In particular, you are free to choose your favorite editor / IDE to do your development work on. When you are done with your work, you can simply upload your files onto Vocareum forsubmission and grading.
However, your assignments will be graded on the platform, so youMUSTmake sure that your code passes at least the submission test cases. In particular, do not use third-party libraries and packages. We do not guarantee that they will work on the platform, even if they work on your personal computer. For the purposes of this project,everything that comes with the standard Python library should be more than sufficient.
other test cases?
A.The following two test cases mighthelp for your stat validation. Note that long path_to_goals are truncated and running_time/max_ram_usage are removed:
python3 driver.py dfs6,1,8,4,0,2,7,3,5
path_to_goal: ['Up', 'Left', 'Down', ... , 'Up', 'Left', 'Up', 'Left']
cost_of_path: 46142
nodes_expanded: 51015
search_depth: 46142
max_search_depth: 46142
python3 driver.py bfs6,1,8,4,0,2,7,3,5
path_to_goal: ['Down', 'Right', 'Up', 'Up', 'Left', 'Down', 'Right', 'Down', 'Left', 'Up', 'Left', 'Up', 'Right', 'Right', 'Down', 'Down', 'Left', 'Left', 'Up', 'Up']
cost_of_path: 20
nodes_expanded: 54094
search_depth: 20
max_search_depth: 21
python3 driver.py ast6,1,8,4,0,2,7,3,5
path_to_goal: ['Down', 'Right', 'Up', 'Up', 'Left', 'Down', 'Right', 'Down', 'Left', 'Up', 'Left', 'Up', 'Right', 'Right', 'Down', 'Down', 'Left', 'Left', 'Up', 'Up']
cost_of_path: 20
nodes_expanded: 696
search_depth: 20
max_search_depth: 20
python3 driver.py dfs8,6,4,2,1,3,5,7,0
path_to_goal: ['Up', 'Up', 'Left', ...,, 'Up', 'Up', 'Left']
cost_of_path: 9612
nodes_expanded: 9869
search_depth: 9612
max_search_depth: 9612
python3 driver.py bfs8,6,4,2,1,3,5,7,0
path_to_goal: ['Left', 'Up', 'Up', 'Left', 'Down', 'Right', 'Down', 'Left', 'Up', 'Right', 'Right', 'Up', 'Left', 'Left', 'Down', 'Right', 'Right', 'Up', 'Left', 'Down', 'Down', 'Right', 'Up', 'Left', 'Up', 'Left']
cost_of_path: 26
nodes_expanded: 166786
search_depth: 26
max_search_depth: 27
python3 driver.py ast8,6,4,2,1,3,5,7,0
path_to_goal: ['Left', 'Up', 'Up', 'Left', 'Down', 'Right', 'Down', 'Left', 'Up', 'Right', 'Right', 'Up', 'Left', 'Left', 'Down', 'Right', 'Right', 'Up', 'Left', 'Down', 'Down', 'Right', 'Up', 'Left', 'Up', 'Left']
cost_of_path: 26
nodes_expanded: 1585
search_depth: 26
max_search_depth: 26