1. Homepage
2. Programming
3. COMPSCI 761 - Advanced Topics in Artificial Intelligence - 22S2 Assignment 1: Game of Fifteen and Search Algorithms

# COMPSCI 761 - Advanced Topics in Artificial Intelligence - 22S2 Assignment 1: Game of Fifteen and Search Algorithms

AunklandCOMPSCI 761Advanced Topics in Artificial IntelligencePythonArtificial IntelligenceGame of FifteenEuclidean DistanceSearch algorithmsAStarSearcher

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.

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 :

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]]

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 == 0:

nei1 = copy.deepcopy(node)

nei1 = node

nei1 = 0

nei2 = copy.deepcopy(node)

nei2 = node

nei2 = 0

nei3 = copy.deepcopy(node)

nei3 = node

nei3 = 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 == 0:

nei1 = copy.deepcopy(node)

nei1 = 0

nei1 = node

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)

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=1Nk=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 :

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 :

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

Run A* Search algorithm with every heuristic for the following three start states:

In :

# 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.

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

Implement a class that performs Breadth First Search by extending class Searcher.

In [ ]:

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 """

return

"""returns (next) path from the problem's start node

to a goal node. """

def search(self):

return

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 """

return

def search(self):

return

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 """

return

def search(self):

return

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 """

return

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 :

# 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]]

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.

Part 3: Deceptive Starting States [3 marks]

Run IDA* on the starting states below and report the number of the expanded nodes.

In :

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]]

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.

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

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)

Write the code that solves Sudoku csp using a search algorithms of your choice, print the solution. QQ WeChat Whatsapp