If you want to work alone do:
setup63-Lisa labs/01 noneIf you want to work with a partner, then one of you needs to run the following command while the other one waits until it finishes:
setup63-Lisa labs/01 partnerUsernameOnce the script finishes, the other partner should run it on their account.
cd ~/cs63/labs/01 cp -r /home/meeden/public/cs63/labs/01/* .
git add * git commit -m "lab1 start" git push
cd ~/cs63/labs/01 git pull
The objectives of this lab are to:
For this lab you will modify the following files:
We will be using a text-based version of the Traffic Jam game in this lab. Complete the following steps to familiarize yourself with the game.
./TrafficJam.py puzzles/biggerA.txtYou will see a picture of the board and a list of valid moves you may make (as shown below). The board is always a square grid. In this case the gird is 6x6, but the grid size can change between puzzles. The exit is marked by two vertical bars. 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.
[['1', '1', '2', '2', '3', '-'], ['0', '-', '-', '-', '3', '-'], ['0', '-', '-', '-', '3', '-'], ['-', '-', '4', '-', '5', '-'], ['-', '-', '4', '-', '5', '-'], ['-', '-', '4', '-', '6', '6']]
In this lab you will re-implement BFS, this time using a Node class to create a graph-based search.
The states for this problem are game boards, which are represented as lists of lists. However, lists are not hashable. Therefore, you should use the getKey method to create a hashable version of the the state to store in the visited set.
create a node to store the initial game board add this node to the FIFO frontier while frontier not empty get currNode from frontier if currNode's state is goal show the path return increment the expanded node counter if key of currNode's state is not in visited add key to visited find all possible moves from currNode's state for each move determine the nextBoard if key of nextBoard is not in visited create a node for nextBoard add this node to the frontier report that the game has no solution
| | 1 2 2 - - 1 3 3 - - 1 - 0 - - - - 0 - - - - 0 - - car1 down | | - 2 2 - - 1 3 3 - - 1 - 0 - - 1 - 0 - - - - 0 - - car1 down | | - 2 2 - - - 3 3 - - 1 - 0 - - 1 - 0 - - 1 - 0 - - car2 left | | 2 2 - - - - 3 3 - - 1 - 0 - - 1 - 0 - - 1 - 0 - - car3 left | | 2 2 - - - 3 3 - - - 1 - 0 - - 1 - 0 - - 1 - 0 - - car0 up | | 2 2 - - - 3 3 0 - - 1 - 0 - - 1 - 0 - - 1 - - - - car0 up | | 2 2 0 - - 3 3 0 - - 1 - 0 - - 1 - - - - 1 - - - - Solution found in 6 moves Explanded 91 nodes
This puzzle has no solution | | 1 1 2 2 2 3 - - - - 3 - 0 4 - - - 0 4 - - 5 5 - -
Next you will implement 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 Traffic Jam Game 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:
For example in the starting board for puzA.txt there are two cars blocking the exit and car0 needs to move up 2 rows to reach the exit, so the heuristic should return 4. While in the starting board for puzB.txt there are three cars blocking the exit and car0 needs to move up 3 rows to reach the exit, thus the heuristic should return 6.
Test that your heuristic returns the correct values for all the game boards given in the puzzles directory.
create a node to store the initial game board add this node to the PQ frontier with a priority of 0 while frontier not empty get currNode from frontier if currNode's state is goal show the path return increment the expanded node counter if key of currNode's state is not in visited add key to visited find all possible moves from currNode's state for each move determine the nextBoard if key of nextBoard is not in visited create a node for nextBoard set priority based on depth and the heuristic add this node to the frontier with priority report that the game has no solution
Complete the table provided in the experiments file and reflect on when A* shows the largest gains over BFS.
This is not required, and should only be attempted once you have completed the required portions of this lab.
First, can you come up with a better heuristic for the Traffic Jam Game? Remember that a valid heuristic must never overestimate the distance to the goal. Prove that your heuristic is better by showing that it outperforms the blockingHeuristic in terms of number of nodes expanded.
Next, try implementing greedy search (only considering the heuristic value, and ignoring the cost so far). How does this affect path length? Number of nodes expanded?
cd ~/cs63/labs/01 git add UninformedSearch.py InformedSearch.py experiments git add puzzles/mypuz.txt git commit git push