READ BEFORE YOU START:

You will need to use Python to do this assignment. The code is using Python 3.7, but it should work with later versions. It will not run with Python 2.

Advice to run the assignment code on your personal computer:

1.   Download the S22022_A1.zip file.

2.   Extract all the contents in a folder dedicated to your assignment.

3.   Create a virtual environment to run the assignment code, in the previous folder (about using virtual environments with Python, seelink).

4.   Activate the virtual env. and run “pip install -r A1 \requirements.txt” to install all the packages needed in the virtual env.

5.   Run search.py to see if you get any error (should not output anything as there are no function/class calls in it).

6.   You can then work in the virtual env. without “contaminating” your global python setup.

You should only make changes to the search.py file. Do not change any other file. You can add code in the existing functions, and also at the end of the file (for new classes and functions, as well as a main() function to run your experiments).

For better readability (the markers will appreciate it), we ask you to add comments where you add code, referring to the task you are solving by making those changes/additions.

There is quite a bit of code in the search.py file as it can be used for other tasks. The instructions for each task in this assignment will guide you about which part you should focus on. However, you should start by spending some time understanding how the code is structured to be able to add your own parts.

Make sure you read the last section “What you need to turn in” before you submit your assignment.

Topic: Greedy Best-First Search versus A* ( 10 marks)

Task1: (1 mark) – Instrument A* search and implement greedy search

Instrument the astar_search function code (you actually need to put your code in the best_first_graph_search function called in astar_search) in search.py so that it retrieves and prints out (without display argument being True):

1.   the number of expanded nodes (when a node is removed from the open list and added to the close list),

2.   the number of generated nodes (when a node is created from its parent),

3.   the number of duplicate nodes (when the state is already in the open list or the closed list),

4.   the solution path, and

5.   the solution path length.

In addition, add a function greedy_search to implement a greedy search algorithm (there is a comment above astar_search in the search.py file saying how to do this). You should be able to call it as you would call astar_search, e.g.:                                                             astar_search(EightPuzzle((1,2,3,4,0,6,7,5,8)))

greedy_search(EightPuzzle((1,2,3,4,0,6,7,5,8)))

Task 2: (1 mark) – Implementing heuristics for the Eight Puzzle problem

Find the “misplaced tile” heuristic that is already in the EightPuzzle class code, and rename it h_mt.

Implement the Manhattan distance heuristic for the EightPuzzle class (call it h_man).

Task3: (1 mark) – Compare A* search and greedy search

Run the following 5 problems with both the “misplaced tiles h” (this is given in the code) and your Manhattan heuristics for A* search and greedy search.  For each run, retrieve the

number of expanded nodes and the solution path length.

The five problems you should run are:

Fill the following table with your results to compare the results you get with A* and greedy:

Task 4: (2 marks) – Implement the Bubble Puzzle game

Make a new class BubblePuzzle to solve the following type ofpuzzle/game (you can inspire yourself from the EightPuzzle class):

https://www.crazygames.com/game/bubble-sorting

We advise you to first play a few stages of the game to better understand how it works, and then formulate the problem (state representation, successor function, initial state, goal test), to guide your implementation.

The class should be called as follows:

astar_search(BubblePuzzle([[ORANGE, PURPLE], [], [], [ORANGE, PURPLE]]))

This is an initial state with 4 “bottles” . The first bottle has purple at the bottom and orange at the top, the two next bottles are empty, and the last bottle has purple at the bottom and orange at the top.

Task 5: (2 marks) – Implement heuristics for the Bubble Puzzle game

Make two heuristics, h1 and h2, for the Bubble Puzzle game. h1 should be stronger than h2 and neither should be the 0-heuristic. Implement them in your BubblePuzzle class.

Since you are running A*, you should make sure your heuristics are admissible and consistent.  If your heuristic is not admissible or not consistent you might notice that you are getting solutions longer than optimal.  If you see solutions shorter than optimal, you have a bug in your actions or your goal test.

To help you out, here are 4 problems and their optimal solution path length:

Task6: (3 marks) – Report about how A* search compares with Greedy search

Write a report discussing how A* compares to greedy search when you have a weak heuristic and a stronger one.  Use the table from task 3 and include a similar table for the BubblePuzzle.

Task7: (Extra for Experts - 1 bonus mark – a bonus mark can be used to offset any lost marks in any assignment – but you cannot get more than 30 marks in the practical section)

1.   Make your code handle inconsistent heuristics.

2.   Make an admissible and inconsistent heuristic for the Eight Puzzle.

3.   Prove that your heuristic is admissible and inconsistent.

4.   Instrument your code to print out reopened nodes (a duplicate node whose g-value is lower than the node with the same state in the open list or the closed list)