Ai Asignmnt 2

ASSIGNMENT-2
NAME : KARAN SURYAWANSHI

REG NO. : 201070064
COURSE : AI
AIM : Write the domain functions for the Eight puzzle problem. Devise two
heuristic functions h1 and h2. Randomly generate 100 start states and goal
states and run the algorithm with two heuristic functions. Compute and
compare the effective branching factor for the two versions.
Given a 3×3 board with 8 tiles (every tile has one number from 1 to 8) and one empty
space. The objective is to place the numbers on tiles to match the final configuration
using the empty space. We can slide four adjacent (left, right, above and below) tiles
into the empty space.
c(X) = g(X) + h(X)
where g(X) = cost of reaching the current node from the root
h(X) = cost of reaching an answer node from X.
We assume that moving one tile in any direction will have 1 unit cost. Keeping that in
mind, we define a cost function for the 8-puzzle algorithm as below.
c(x) = f(x) + h(x)
where f(x) is the length of the path from root to x (the number of moves so far) and
h(x) is the number of non-blank tiles not in their goal position (the number of
misplaced tiles). There are at least h(x) moves to transform state x to a goal state.
Code:
class Node:
def __init__(self,data,level,fval):
""" Initialize the node with the data, level of the node and the calculated fvalue """
self.data = data
self.level = level
self.fval = fval
def generate_child(self):
""" Generate child nodes from the given node by moving the
blank space either in the four directions {up,down,left,right} """
x,y = self.find(self.data,'_')
""" val_list contains position values for moving the blank space
in either of the 4 directions [up,down,left,right] respectively. """
val_list = [[x,y-1],[x,y+1],[x-1,y],[x+1,y]]
children = []
for i in val_list:
child = self.shuffle(self.data,x,y,i[0],i[1])
if child is not None
child_node = Node(child,self.level+1,0)
children.append(child_node)
return children
def shuffle(self,puz,x1,y1,x2,y2):
if x2 >= 0 and x2 < len(self.data) and y2 >= 0 and y2 < len(self.data):
temp_puz = []
temp_puz = self.copy(puz)
temp = temp_puz[x2][y2]
temp_puz[x2][y2] = temp_puz[x1][y1]
temp_puz[x1][y1] = temp
return temp_puz
else:
return None
def copy(self,root):
""" Copy function to create a similar matrix of the given
node""" temp = []
for i in root:
t = [] for j
in i:
t.append(j)
temp.append(t)
return temp
def find(self,puz,x):
""" Specifically used to find the position of the blank space """
for i in range(0,len(self.data)):
for j in range(0,len(self.data)):
if puz[i][j] == x:
return i,j
class Puzzle:
def __init__(self,size):
""" Initialize the puzzle size by the specified size,open and closed lists to empty """
self.n = size
self.open = []
self.closed = []
def accept(self):
""" Accepts the puzzle from the user """
puz = []
for i in range(0,self.n):
temp = input().split(" ")
puz.append(temp)
return puz
def f(self,start,goal):
""" Heuristic Function to calculate hueristic value f(x) = h(x) + g(x) """
return self.h(start.data,goal)+start.level
def h(self,start,goal):
""" Calculates the different between the given puzzles """
temp = 0
for i in range(0,self.n):
for j in range(0,self.n):
if start[i][j] != goal[i][j] and start[i][j] != '_':
temp += 1
return temp
def process(self):
""" Accept Start and Goal Puzzle
state""" print("Enter the start state
matrix \n") start = self.accept()
print("Enter the goal state matrix
\n") goal = self.accept()
start = Node(start,0,0)
start.fval = self.f(start,goal)
""" Put the start node in the
open list""" self.open.append(start)
print("\n\n")
while True:
cur =
self.open[0]
print("") print(" |
") print(" | ")
print(" \\\'/ \n")
for i in cur.data:
for j in i:
print(j,end=" ")
print("")
""" If the difference between current and goal node is 0 we have reached the
goal node""" if(self.h(cur.data,goal) == 0):
break
for i in cur.generate_child():
i.fval = self.f(i,goal)
self.open.append(i)
self.closed.append(cur)
del self.open[0]
self.open.sort(key = lambda x:x.fval,reverse=False)
puz = Puzzle(3)
puz.process()
OUTPUT:
Different heuristic functions and comparison between effective branching
Factor:
72 4 *12
5* 6 345
83 1 678
Start state Goal state
h1 : Number of misplaced tiles

In the above figure, all the tiles are out of position, hence for this state h1 = 8. h1: is an
admissible heuristic, since it is clear that every tile that is out of position must be
moved at least once.
h2 : Sum of Manhattan distances of the tiles from their goal positions

In the given figure, all the tiles are out of position, hence for this state, h2 = 3 + 1 + 2 + 2 + 2
+ 3 + 3 + 2 = 18. h2 is an admissible heuristic, since in every move, one tile can
only move closer to its goal by one step.
Comparison of Heuristics
The quality of heuristics can be characterized on the basis of the effective branching factor b*. If
the total number of nodes generated by A* for a problem is N, and the solution depth is d, then:
N = b* + (b*)2 + (b*)3 + (b*)4 + ….. + (b*)d Experimental measurements of b* on a
a small set of problems can provide a good guide to the heuristic’s overall usefulness.
A well designed heuristic would have a value of b* close to 1. To compare the
admissible heuristics mentioned earlier, one can generate a large number of initial
states for the 8-puzzle and solve each one using both heuristics. If a(n) > b(n) for all n,
then we can say that a is a better heuristic than b, since it generates fewer nodes in
the search tree. Another way to see this is that a(n) is a closer lower-bound to the
actual path cost to reach the goal, i.e., it is more accurate. Among the admissible
heuristics mentioned earlier (h1 to h4), we can see by the definition of the heuristics
that : h2 > h1.Thus, theoretically, the number of nodes generated or the effective
branching factor in an A* search using these heuristics should be in the same order.
Thus, among the admissible heuristics, Manhattan Distance is the most efficient.
Conclusion:
Heuristic function with manhattan distance is more efficient than
heuristic function with number of misplaced tiles.

Ai Asignmnt 2

Uploaded by

Copyright:

Available Formats

Ai Asignmnt 2

Uploaded by

Document Information

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Ai Asignmnt 2

Uploaded by

Copyright:

Available Formats

ASSIGNMENT-2

NAME : KARAN SURYAWANSHI

h1 : Number of misplaced tiles

h2 : Sum of Manhattan distances of the tiles from their goal positions

You might also like