From now on, you will be working with a partner to complete each lab. Log on to github.swarthmore.edu to see your partner assignment for this lab.
First change into your directory for this class. Then clone the GitHub repository for lab1, replacing USER1 and USER2 with the appropriate usernames:
cd cs63 git clone email@example.com:cs63-f19/lab1-USER1-USER2.git
The objectives of this lab are to:
For this lab you will modify the following files:
We will be using text-based versions of the Traffic Jam and Fifteen Puzzle games in this lab. Complete the following steps to familiarize yourself with the games.
python3 TrafficJam.py puzzles/traffic00.txt
You will see a picture of the board and a list of valid moves you may make (as shown below). In the case of traffic00, the gird is 6x6, but the grid size can change between puzzles. The exit is marked by two vertical bars. In a traffic jam puzzle, each car is represented by a unique number. In this example, cars 1, 2, and 6 are positioned horizontally and can only move left or right, while cars 0, 3, 4, and 5 are positioned vertically and can only move up or down. Cars may be different lengths but are always only one grid square wide. Empty locations are marked by a dash. The goal of the game is to move the car labeled 0 to the exit.
| | 1 1 2 2 3 - 0 - - - 3 - 0 - - - 3 - - - 4 - 5 - - - 4 - 5 - - - 4 6 6 - a: car0 down b: car4 up c: car6 right Select move (or q to quit):
You should be able to solve this particular puzzle in 7 moves.
python3 FifteenPuzzle.py puzzles/fifteen00.jsonThe file fifteen00.json contains a 2x2 puzzle. In a fifteen puzzle, each block is represented by a natural number, and the blank space is represented by a 0. The goal is to put the blocks in increasing order from the top left to the bottom right (with the blank at the bottom right), which for a 2x2 puzzle is the following state:
1 2 3 0Below is the initial state for fifteen00.json. The possible moves describe how the space should move. You should be able to solve his puzzle in four moves:
2 3 1 0 moves: U, L
[['1', '1', '2', '2', '3', '-'], ['0', '-', '-', '-', '3', '-'], ['0', '-', '-', '-', '3', '-'], ['-', '-', '4', '-', '5', '-'], ['-', '-', '4', '-', '5', '-'], ['-', '-', '4', '-', '6', '6']]
You will be implementing A* search. The key difference between informed searches, like A*, and uninformed searches, like BFS, is that they estimate the cost associated with each node. For A* this cost is the sum of how much work it took to get to a node and an estimate of how far it is to the goal from a node.
For the both games, the cost of getting to a node will simply be the number of actions taken, which is stored in the depth of the node. To estimate the distance to the goal you will use a heuristic function.
Complete the implementation of informed search as follows:
create a node to store the initial game board add this node to the PQ frontier with a priority of 0 + h(n) while frontier not empty get currNode from frontier if currNode's state is goal return goal node end if increment the expanded node counter if currNode's state is not in visited add state to visited find all possible moves from currNode's state for each move determine the nextState if nextState is not in visited create a node for nextState set priority based on depth and the heuristic add this node to the frontier with priority end if end for end if end while return None
Now it's time to add some heuristic information. This will allow the informed search to expand less nodes to more efficiently find solutions.
Implement each heuristic described below. We have provided some
starting point unit tests for the heuristics in the
file HeuristicTests.py. For each heuristic, you should
include four tests using the game boards given in
the puzzles directory. To execute the tests do:
Once you've completed informed search you are ready to do some performance testing.
Complete the tables provided in the experiments file, and answer the questions that follow. Note that for the fifteen puzzle problems, uninformed search will become excruciatingly slow for any of the larger board sizes. Feel free to try it for yourself, though I won't ask you to record these results for the fifteen puzzle problems.