COMPSCI 761 - Advanced Topics in Artificial Intelligence - 22S2 Assignment 1: Game of Fifteen and Search Algorithms
COMPSCI 761 22S2 Assignment 1
- Lecturer: Anna Trofimova
- School of Computer Science, The Univerity of Auckland
- Last update 29th of July at 18:00pm, 2022
Student:
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.
Submit your files using CANVAS upload function.
The submission deadline is 19th of August at 11.59pm, 2022.
Description
This assignment consists of two problems presented in a puzzle game context. For the first problem, you will be implementing a path search problem along with common search algorithms and evaluating their properties. For the second problem, you will be exploring how to define and solve a constraint satisfaction problem. To implement the solutions, you have to use AIPython code that provides you with many implemented classes and examples of their use.
When working with a Jupyter notebook, you can edit the *.py files either in the Jupyter interface (in your browser) or with your favorite editor (e.g., PyCharm). Whenever you save a *.py file, the notebook will reload their content directly.
The libraries that you can use (and need) in this assignment are the following (run the cell below to import the libraries):
In [2]:
import sys
sys.path.insert(0, "./aipython")
import time
import numpy as np
from aipython.searchGeneric import *
from aipython.searchProblem import *
from aipython.cspProblem import *
from aipython.cspSearch import *
import copy
import math
Tip: If you placed the notebook correctly it should not give you any errors.
If you think that there are other libraries you might need then send an email to anna.trofimova@auckland.ac.nz to confirm.
Part 1 - Heuristics [5 marks]
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. To solve the puzzle, the tiles must be moved so that they are ordered 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:
goal = [[1, 2, 3, 4],
[5, 6, 7, 8],
[9, 10, 11, 12],
[13, 14, 15, 0]]
Task 1.1
Edit the code below to implement a search problem class representing the Game of Fifteen that uses heuristic based on Manhattan Distance (h1). The class must be implemented by extending the class Search_problem.
Manhattan Distance between two points p1p1 at (x1,y1)(x1,y1) and p2p2 at (x2,y2)(x2,y2) is dM(p1,p2)=|x1−x2|+|y1−y2|dM(p1,p2)=|x1−x2|+|y1−y2|
Tip: If you have problems understanding how to overwrite methods take a look at the implementation of Search_problem_from_explicit_graph class in searchProblem.py
class GameFifteenProblem(Search_problem):
def __init__(self, start, goal):
self.start = start
self.goals = goal
self.repeat = ()
self.repeatr = ()
self.repeat1 = ()
return
def start_node(self):
"""Returns the start node"""
return self.start
def is_goal(self, node):
"""Returns True if the node is the goal, otherwise False"""
return node == self.goals
def neighbors(self, node):
#print(node)
"""Returns a list of the arcs for the neighbors of node, for example:
return [Arc(node, to_neighbor_node1, cost1), Arc(node, to_neighbor_node2, cost2)]"""
if node not in self.repeat:
for i in range(1,3):
for j in range(1,3):
if node[i][j] == 0:
nei1 = copy.deepcopy(node)
nei1[i][j] = node[i][j-1]
nei1[i][j-1] = 0
nei2 = copy.deepcopy(node)
nei2[i][j] = node[i][j+1]
nei2[i][j+1] = 0
nei3 = copy.deepcopy(node)
nei3[i][j] = node[i-1][j]
nei3[i-1][j] = 0
nei4 = copy.deepcopy(node)
nei4[i][j] = node[i+1][j]
nei4[i+1][j] = 0
result = [Arc(node, nei1,1),Arc(node, nei2,1), Arc(node, nei3,1), Arc(node, nei4,1)]
self.repeatr+=tuple(result)
self.repeat+=tuple(node)
return result
if node[1][0] == 0:
nei1 = copy.deepcopy(node)
nei1[0][0] = node[1][0]
nei1[1][0] = 0
nei2 = copy.deepcopy(node)
nei2[2][0] = node[1][0]
nei2[1][0] = 0
nei3 = copy.deepcopy(node)
nei3[1][1] = node[1][0]
nei3[1][0] = 0
result = [Arc(node, nei1,1),Arc(node, nei2,1), Arc(node, nei3,1)]
self.repeatr+=tuple(result)
self.repeat+=tuple(node)
return result
elif node[2][0] == 0:
nei1 = copy.deepcopy(node)
nei1[1][0] = 0
nei1[2][0] = node[1][0]
return result
else:
print("debug")
print(self.repeat.index(node))
return self.repeatr[self.repeat.index(node)]
def heuristic(self, node):
"""Returns the heuristic value of the node
based on the Manhattan distance"""
#print(tuple(node))
# if tuple(node) not in self.repeat1.keys():
result = 0
for i in range(0, len(node)):
for j in range(0, len(node[i])):
for x in range(0, len(goal)):
for y in range(0, len(goal[x])):
if (goal[x][y] == node[i][j]):
result += abs(x-i)+abs(y-j)
#self.repeat1[tuple(node)] = result
return result
# else:
# return self.repeat1[tuple(node)]
To validate the correctness of the problem class use the A* searcher algorithm (from searchGeneric.py) to find a solution.
Tip: The cost of the solution should be 9.
start = [[1, 2, 3, 4],
[9, 5, 6, 7],
[10, 11, 8, 0],
[13, 14, 15, 12]]
puzzle = GameFifteenProblem(start, goal)
searcher = AStarSearcher(puzzle)
solution = searcher.search()
print('Cost: ', solution.cost)
Task 1.2
Implement search problem classes representing the Game of Fifteen that use heuristics based on Euclidean Distance (h2) and the number of the inversions of the permutation (h3). The classes must be implemented by extending the class GameFifteenProblem.
Euclidean distance between two points p1p1 at (x1,y1)(x1,y1) and p2p2 at (x2,y2)(x2,y2) is dE(p1,p2)=√(x1−x2)2+(y1−y2)2dE(p1,p2)=(x1−x2)2+(y1−y2)2
An inversion of a permutation (t1,t2,...,tn)(t1,t2,...,tn) of the elements in a finite n-element set of positive integers A={1,2,...,n}A={1,2,...,n} is the pair (tj,tk)(tj,tk), where j<kj<k and tj>tktj>tk.
∑Nj=1∑Nk=j{tj>tk:1,otherwise:0}∑j=1N∑k=jN{tj>tk:1,otherwise:0}, where NN is the total number of elements and titi is the value of i-th element.
In [49]:
class GameFifteenProblemEuclidean(GameFifteenProblem):
def __init__(self, start, goal):
(super().__init__(start, goal))
def heuristic(self, node):
"""Returns the heuristic value of the node
based on the Euclidean distance"""
result = 0
for i in range(0, len(node)):
for j in range(0, len(node[i])):
for x in range(0, len(goal)):
for y in range(0, len(goal[x])):
if (goal[x][y] == node[i][j]):
result += math.sqrt((x-i)**2+(y-j)**2)
return result
In [47]:
class GameFifteenProblemInversions(GameFifteenProblem):
def __init__(self, start, goal):
(super().__init__(start, goal))
def heuristic(self, node):
"""Returns the heuristic value of the node
based on the sum of the inversion number of a permutation"""
return
Task 1.3
Run A* Search algorithm with every heuristic for the following three start states:
In [53]:
# optimal path cost: 14
start14 = [[1, 2, 8, 3],
[5, 6, 7, 4],
[9, 15, 14, 11],
[13, 10, 12, 0]]
# optimal path cost: 17
start17 = [[1, 3, 6, 4],
[5, 2, 8, 14],
[9, 15, 7, 0],
[13, 10, 12, 11]]
# optimal path cost: 23
start23 = [[1, 3, 6, 4],
[5, 8, 15, 14],
[9, 2, 7, 0],
[13, 10, 12, 11]]
puzzle = GameFifteenProblemEuclidean(start23, goal)
searcher = AStarSearcher(puzzle)
solution = searcher.search()
print('Cost: ', solution.cost)
24761 paths have been expanded and 46180 paths remain in the frontier
Cost: 23
In each case record in the tables below the heuristic values for the start states, the number of the expanded nodes, and the costs of the solutions.
Heuristic | h-value: start14 | h-value: start17 | h-value: start23 |
Manhattan | # | # | # |
Euclidean | # | # | # |
Inversions | # | # | # |
Heuristic | expanded: start14 | expanded: start17 | expanded: start23 |
Manhattan | # | # | # |
Euclidean | # | # | # |
Inversions | # | # | # |
Heuristic | path cost: start14 | path cost: start17 | path cost: start23 |
Manhattan | # | # | # |
Euclidean | # | # | # |
Inversions | # | # | # |
Comment on the performance of the A* search algorithm with each heuristic based on the results in the tables. Explain which heuristic is better/worse and why.
# answer
Part 2: Search algorithms [7 marks]
Tip: If you have problems understanding how to overwrite methods take a look at the implementation of AStarSearcher and Searcher classes in searchGeneric.py
Tip: To initialize the frontier think of the type of structure used by the algorithm to store generated nodes. If it uses a priority queue use FrontierPQ from serachGeneric.py
Task 2.1
Implement a class that performs Breadth First Search by extending class Searcher.
In [ ]:
class BreadthFirstSearcher(Searcher):
def __init__(self, problem):
super().__init__(problem)
""" Initializes the forontier """
def initialize_frontier(self):
return
""" Returns True if there are no more nodes to expand """
def empty_frontier(self):
return
""" Adds the path to the forontier """
def add_to_frontier(self, path):
return
"""returns (next) path from the problem's start node
to a goal node. """
def search(self):
return
Task 2.2
Implement a class that performs Iterative Deepening Search by extending class Searcher.
In [ ]:
class IterativeDeepeningSearcher(Searcher):
def __init__(self, problem):
super().__init__(problem)
""" Initializes the forontier """
def initialize_frontier(self):
return
""" Returns True if there are no more nodes to expand """
def empty_frontier(self):
return
""" Adds the path to the forontier """
def add_to_frontier(self, path):
return
def search(self):
return
Task 2.3
Implement a class that performs Iterative Deepening A* Search by extending class Searcher.
In [ ]:
class IterativeDeepeningAStarSearcher(Searcher):
""" Initializes the forontier """
def initialize_frontier(self):
return
""" Returns True if there are no more nodes to expand """
def empty_frontier(self):
return
""" Adds the path to the forontier """
def add_to_frontier(self, path):
return
def search(self):
return
Task 2.4
Implement a class that performs Uniform Cost Search by extending class Searcher.
In [ ]:
class UniformCostSearcher(Searcher):
""" Initializes the forontier """
def initialize_frontier(self):
return
""" Returns True if there are no more nodes to expand """
def empty_frontier(self):
return
""" Adds the path to the forontier """
def add_to_frontier(self, path):
return
Task 2.5
Run Breadth First Search (BFS), Iterative Deepenining Search (IDS), Iterative Deepening A Search (IDA\S), and Uniform Cost Search (UCS) algorithms on each of the 5 start states:
In [25]:
# optimal path cost: 10
start10 = [[2, 3, 7, 4],
[1, 6, 11, 8],
[5, 10, 0, 12],
[9, 13, 14, 15]]
# optimal path cost: 24
start24 = [[2, 7, 11, 4],
[6, 3, 12, 0],
[1, 5, 15, 8],
[9, 10, 13, 14]]
# optimal path cost: 30
start30 = [[2, 7, 11, 4],
[6, 3, 12, 0],
[1, 5, 15, 14],
[9, 10, 8, 13]]
# optimal path cost: 36
start36 = [[7, 11, 12, 4],
[2, 3, 14, 1],
[6, 5, 13, 8],
[9, 10, 15, 0]]
# optimal path cost: 41
start41 = [[7, 11, 12, 4],
[2, 3, 8, 14],
[10, 0, 5, 1],
[6, 9, 13, 15]]
# your code
In each case, record in the table below the number of nodes generated during the search. If the algorithm runs out of memory or the number of nodes in the frontier exceeds 1 million items, just write “Mem” in your table. If the code runs for five minutes without producing output, terminate the process and write “Time” in your table.
Tip: To edit the table double click the cell below.
Algorithm | 10 | 24 | 30 | 36 | 41 |
BFS | # | # | # | # | # |
A* | # | # | # | # | # |
IDS | # | # | # | # | # |
IDA*S | # | # | # | # | # |
UCS | # | # | # | # | # |
Discuss the time and space efficiency of these four algorithms, comment on the results in the table.
# your answer
Part 3: Deceptive Starting States [3 marks]
Task 3.1
Run IDA* on the starting states below and report the number of the expanded nodes.
In [26]:
start37_1 = [[7, 11, 12, 4],
[2, 3, 14, 1],
[6, 5, 13, 0],
[9, 10, 15, 8]]
start37_2 = [[7, 11, 12, 4],
[2, 3, 8, 14],
[6, 0, 1, 15],
[9, 5, 10, 13]]
# your code
Task 3.2
Explain why there is a difference between the number of the expanded nodes for these starting states if their costs of the optimal paths are the same.
# your answer
Part 4: Constraint Satisfaction Problem [5 marks]
This part of the assignment is based on another puzzle called Sudoku. The game consists of 9x9 grid with a few cells filled in with digits. The objective of the game is to fill the remaining cells so that each column, each row, and each of the nine 3×3 sub-grids contain all of the digits from 1 to 9.
The start state of the puzzle is defined as a multidimensional array of numbers, where 0 represents empty cells, for example:
grid = [[9, 5, 0, 8, 2, 7, 3, 0, 0],
[0, 8, 0, 1, 4, 0, 0, 5, 0],
[0, 1, 0, 5, 9, 0, 0, 0, 0],
[8, 3, 0, 0, 0, 0, 0, 7, 5],
[1, 6, 9, 7, 5, 2, 4, 3, 0],
[0, 7, 0, 0, 8, 0, 0, 6, 0],
[0, 9, 1, 0, 6, 0, 8, 4, 0],
[7, 0, 8, 0, 3, 1, 0, 0, 6],
[6, 2, 0, 4, 7, 8, 0, 9, 0]]
Tip: If you have problems with understanding how to implement constrains take a look at cspExamples.py and cspExamplesQueens.py
Task 4.1
Write the code that defines constraint(s) and a function grid_to_csp that returns a CSP for a Sudoku puzzle:
# define constraint function(s)
# function that returns a csp
def grid_to_csp(grid):
domains = {}
constraints = []
return CSP(domains, constraints)
# csp
csp = grid_to_csp(grid)
Task 4.2
Write the code that solves Sudoku csp using a search algorithms of your choice, print the solution.
Task 4.3
Descibe what do nodes represent in the search tree. Explain your choice of the search algorithm and compare it with any other search algorithm implemented in this assignment.
