23S2 Assignment 1
$$ % macros \newcommand{\indep}{\perp \!\!\!\perp} $$
Student:
Name Surname, UPI
Submission
This interactive notebook contains the instructions to complete assignment 1; You should submit this notebook with the code and answers in one single file in .ipybn format with name assignment1.ipybn. Write your name and UPI in the cell above (to edit the markdown text double-click the cell).
There is a maximum file size cap of 5MB, so make sure your submission does not exceed this size. The submitted notebook should contain all your source code and answers. You can add new cells and use markdown text to organise and explain your implementation/answer.
Late submission policy: for each day past the deadline, there's a 20% deduction from the maximum possible score. By the fifth day post-deadline, the highest score attainable is 0. Example: if your submission received an 80% grade, but it was turned in 2 days late, then your final score is capped at 60%.
Submit this notebook using CANVAS upload function.
Description
This assignment consist of 5 parts with the following distribution of the mark:
part 1 is worth 5% of the total mark
part 2 is worth 25% of the total mark
part 3 is worth 35% of the total mark
part 4 is worth 25% of the total mark
part 5 is worth 15% of the total mark
For solving the problems in this assignment, please utilize the aipython package. This package offers a variety of pre-implemented classes and usage examples. To download the most recent version of the package, follow this link: https://artint.info/AIPython/aipython.zip
Place this notebook in a folder next to aipyton folder (not inside it).
When working with a Jupyter notebook, you can edit the *.ipynb files either in the Jupyter interface (in your browser) or with your favorite editor (e.g. PyCharm). Whenever you save a *.ipynb file, the notebook will reload its content directly. Whenever you execute a cell, the output is displayed below that cell and remains saved within the notebook - do not clear the output.
The libraries that you can use (and need) in this assignment are the following (run the cell below to import the libraries):
In [1]:
import syssys.path.insert(0, "./aipython")import timeimport numpy as npfrom aipython.searchGeneric import *from aipython.searchProblem import *from aipython.cspProblem import *import randomimport copyimport math
If you want to use a library which is not in this list, you need to get an explicit permission from the lecturer (anna.trofimova@auckland.ac.nz)
Part 1 - State Space Problem & Search [5%]
This part of the assignment is based on a popular puzzle, Game of Fifteen, also known as 15-puzzle. The game consists of 15 numbered tiles on a four by four grid where one tile is missing. The objective is to rearrange the tiles by moving the empty space to order them from 1 to 15. The goal state of the puzzle is defined as a multidimensional array of digits, where 0 represents the missing tile, as follow:
In [ ]:
goal = [[1, 2, 3, 4], [5, 6, 7, 8], [9, 10, 11, 12], [13, 14, 15, 0]]
Task 1.1 Creating a FifteenPuzzleGame class
Edit the code below to implement a search problem class representing the Game of Fifteen. The class should be an extension of Search_problem class and the heuristic function should be implemented as a Manhattan distance.
In [ ]:
class GameFifteenProblem(Search_problem): """A class that represents 15 Puzzle Game problem (with Manhattan heuristic) start - 2D array of numbers representing the initial state of the game goal - 2D array of numbers representing the goal stay of the game """ def __init__(self, start, goal): return def start_node(self): return def is_goal(self, node): return def heuristic(self, node): return def neighbors(self, node): return
To validate the correctness of the problem class you cab use the A* searcher algorithm (from searchGeneric.py) to find a solution.
The cost of the solution should be 7.
In [ ]:
start_test = [[1, 2, 3, 4], [9, 5, 6, 7], [10, 0, 11, 8], [13, 14, 15, 12]]puzzle = GameFifteenProblem(start_test, goal)searcher = AStarSearcher(puzzle)solution = searcher.search()print('Cost: ', solution.cost)
Part 2 - Performance Evaluation [25%]
Task 2.1 Implement IDA*
Edit the code below to implement a class representing Iterative Deepening A* Search. The class should be an extension of Searcher class and the search should terminate when the solution is found or when the limit - the boundary for the evaluation value, cannot be updated any further.
In [ ]:
class IterativeDeepeningAStarSearcher(Searcher): """returns a searcher for a problem. Paths can be found by repeatedly calling search(). """ def __init__(self, problem): super().__init__(problem) def add_to_frontier(self, path): return @visualize def search(self): return
Task 2.2 Record Search Performance
In this task you will compare the properties of different search algorithms. You will need to run Uniform Cost Search, Greedy Search, A* Search and Iterative Deepening A* Search on each of the start states below:
In [ ]:
start6 = [[1, 2, 7, 3], [5, 6, 11, 4], [9, 10, 0, 8], [13, 14, 15, 12]]start12 = [[1, 3, 4, 0], [5, 2, 6, 7], [9, 10, 15, 8], [13, 14, 12, 11]]start25 = [[10, 11, 6, 3], [2, 1, 0, 4], [5, 8, 15, 7], [9, 13, 14, 12]]start33 = [[2, 7, 0, 4], [6, 3, 11, 12], [1, 5, 15, 14], [9, 10, 8, 13]]start41 = [[7, 11, 12, 4], [2, 5, 3, 14], [10, 0, 8, 1], [6, 9, 13, 15]]
Use the implementation of A* Search from aipython package and the implementation of Uniform-Cost Search and Greedy Search from the cell below.
In [ ]:
class UniformCostSearcher(AStarSearcher): """returns a greedy searcher for a problem. Paths can be found by repeatedly calling search(). """ def __init__(self, problem): super().__init__(problem) def add_to_frontier(self, path): """add path to the frontier with the appropriate cost""" value = path.cost self.frontier.add(path, value) returnclass GreedyBestSearcher(AStarSearcher): """returns a greedy searcher for a problem. Paths can be found by repeatedly calling search(). """ def __init__(self, problem): super().__init__(problem) def add_to_frontier(self, path): """add path to the frontier with the appropriate cost""" value = self.problem.heuristic(path.end()) self.frontier.add(path, value) return
In each case, record in the table below the number of nodes generated during the search. If the number of generated states exceeds 800000 items, just write “Mem” in your table. If the code runs for 1 minute without producing output, terminate the process and write “Time” in your table.
Tip: To edit the table double click the cell below.
Algorithm 6 12 25 33 41
UCS
GBS
A*
IDA*S
Task 2.3 Performance Evaluation
In the cell below briefly evaluate the time and space performance of each algorithm using the data from the table. Identify the most efficient algorithm and mention any results that differ from your expectations. Limit your answer to 100 words.
Tip: To edit the answer double click the cell below.
Answer: Insert your answer here.
Part 3 - Game State Generation [35%]
Task 3.1 Implement Game Generator
Edit the code in the cell below to implement a class 'GameGenerator' which generates a Game of Fifteen with a specified cost of the optimal solution. The method 'generate' should return a 2D array representing the game state with the specified path cost. Please limit the scope of your implementation to the approaches/algorithms covered in the course.
Your implementation will be evaluated based on the correctness of the output, the runtime, and the extent of code reuse.
In [ ]:
class GameGenerator(): def __init__(self, path_cost): return def generate(self): return
Task 3.2 Game Generator Intuition
In the cell below describe the algorithm or method you employed to develop the GameGenerator class. Detail how you ensured the correctness of the output and optimized the generation speed. Limit your answer to 100 words.
Tip: To edit the answer double click the cell below.
Answer: Insert your answer here.
Part 4 - Graph Search [25%]
The cell below specifies a state space problem as a graph, where the start state is the node S and the goal state is the node G. The arc cost and the heuristic values for each state are also provided.
In [ ]:
problem = Search_problem_from_explicit_graph( {'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'J', 'K', 'L', 'M', 'N', 'O', 'P', 'Q', 'R', 'S'}, [Arc('A', 'H', 1), Arc('A', 'K', 1), Arc('A', 'R', 7), Arc('B', 'O', 7), Arc('B', 'R', 2), Arc('B', 'S', 3), Arc('C', 'E', 1), Arc('C', 'N', 1), Arc('C', 'R', 6), Arc('D', 'B', 5), Arc('D', 'L', 6), Arc('E', 'B', 1), Arc('E', 'K', 1), Arc('E', 'M', 6), Arc('F', 'G', 5), Arc('F', 'J', 3), Arc('G', 'C', 2), Arc('G', 'F', 2), Arc('G', 'J', 2), Arc('H', 'D', 5), Arc('H', 'E', 5), Arc('H', 'J', 7), Arc('H', 'M', 6), Arc('J', 'C', 1), Arc('J', 'D', 2), Arc('J', 'G', 7), Arc('J', 'H', 3), Arc('J', 'Q', 2), Arc('J', 'S', 5), Arc('K', 'C', 6), Arc('K', 'L', 5), Arc('K', 'N', 5), Arc('K', 'S', 2), Arc('M', 'E', 6), Arc('M', 'O', 7), Arc('N', 'C', 1), Arc('N', 'E', 1), Arc('N', 'M', 5), Arc('O', 'C', 2), Arc('O', 'R', 1), Arc('P', 'B', 4), Arc('P', 'E', 5), Arc('P', 'F', 1), Arc('P', 'H', 7), Arc('P', 'J', 4), Arc('P', 'K', 2), Arc('P', 'M', 2), Arc('P', 'R', 3), Arc('P', 'S', 1), Arc('Q', 'J', 7), Arc('Q', 'K', 1), Arc('Q', 'N', 6), Arc('Q', 'P', 2), Arc('R', 'E', 2), Arc('R', 'O', 1), Arc('R', 'Q', 6), Arc('R', 'S', 7), Arc('S', 'E', 1), Arc('S', 'M', 2), Arc('S', 'N', 3)], start='S', goals={'G'}, hmap={'A': 15, 'B': 19, 'C': 18, 'D': 21, 'E': 20, 'F': 10, 'G': 0, 'H': 10, 'J': 7, 'K': 17, 'L': 19, 'M': 22, 'N': 18, 'O': 15, 'P': 12, 'Q': 12, 'R': 18, 'S': 18})
Task 4.1 Graph Search
In the cell below write the code that finds an optimal solution to the problem above. Please limit the scope of your implementation to the approaches/algorithms covered in the course. Print the solution in the format: S --> A --> B --> C --> G.
Your implementation will be evaluated based on the correctness of the output, the runtime, and the extent of code reuse.
In [ ]:
# insert you code here
Task 4.2 Graph Search Intuition
In the cell below describe the algorithm or method you employed to find an optimal solution in the previous task. Explain your choice. Limit your answer to 100 words.
Tip: To edit the answer double click the cell below.
Answer: Insert your answer here.
Part 5 - Queens Conflicts [15%]
The goal of 8-Queens problem is to place 8 queens on an 8x8 chessboard so that no two queens threaten each other. This means that no two queens can be in the same row, column, or diagonal.
Consider the following state of the problem where 0 represents empty square and 1 represents a square with a queen:
In [ ]:
board_start = [[0, 1, 0, 0, 0, 0, 0, 0], [0, 1, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 1], [0, 0, 0, 0, 0, 0, 0, 1], [0, 0, 1, 0, 0, 0, 0, 0], [0, 0, 1, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 1, 0, 0], [0, 0, 0, 0, 1, 0, 0, 0]]
Task 5.1 Count conflicts
In the cell below implement the function conflicts which take a state of the chessboard as an argument and returns the number of conflicts for it.
In [ ]:
def conflicts(board): return
Task 5.2 Local Search
In the cell below develop the function queens_with_conflicts which implements a local search approach to finding a state of 8-queens that has specified number of conflicts. The function should take a 2D array representing the initial board and the number of conflicts as input, and then return a 2D array representing the solution.
Your implementation will be evaluated based on the correctness of the output, the runtime, and the extent of code reuse.
In [ ]:
def queens_with_conflicts(board, c): return
Task 5.3 Queens with Conflicts Intuition
In the cell below explain the choice of your local search algorithm and intuition behind the function queens_with_conflicts.Limit your answer to 100 words.
Tip: To edit the answer double click the cell below.
Answer: Insert your answer here.