Artificial Intelligent Lab

LAB EXPERIMENTS

Dept. Of Computer Applications, VBSPU

 Artificial Intelligent Lab

# PROGRAM 1: Introduction of various python libraries used for machine learning.

Dept. Of Computer Applications, VBSPU

 Artificial Intelligent Lab

Dept. Of Computer Applications, VBSPU

 Artificial Intelligent Lab

# PROGRAM 2: Program to implement Uninformed Search Technique: Breadth First Search

Source Code:

graph = {

'5' : ['3','7'],

'3' : ['2', '4'],

'7' : ['8'],

'2' : [],

'4' : ['8'],

'8' : []

visited = [] # List for visited nodes.

queue = [] #Initialize a queue

def bfs(visited, graph, node): #function for BFS

[Link](node)

[Link](node)

while queue: # Creating loop to visit each node

m = [Link](0)

print (m, end = " ")

for neighbour in graph[m]:

if neighbour not in visited:

[Link](neighbour

[Link](neighbour)

# Driver Code

print("Following is the Breadth-First Search")

bfs(visited, graph, '5')

Dept. Of Computer Applications, VBSPU

 Artificial Intelligent Lab

Dept. Of Computer Applications, VBSPU

 Artificial Intelligent Lab

Step-by-step algorithm for Breadth-First Search:

Initialize a queue to keep track of nodes to visit.

Enqueue the starting node into the queue.
Initialize a set to keep track of visited nodes, and add the starting node to the set.
While the queue is not empty, repeat steps 5-7.
Dequeue the first node from the queue.
For each neighbor of the dequeued node that has not been visited yet, add it to the
visited set and enqueue it into the queue.
If the goal node is found, return it. Otherwise, continue to step 4.

Dept. Of Computer Applications, VBSPU

 Artificial Intelligent Lab

# PROGRAM 3: Program to implement Uninformed Search Technique: Depth First Search

Source Code:

graph = {

'5' : ['3','7'],

'3' : ['2', '4'],

'7' : ['8'],

'2' : [],

'4' : ['8'],

'8' : []

visited = set() # Set to keep track of visited nodes of graph.

def dfs(visited, graph, node): #function for dfs

if node not in visited:

print (node)

[Link](node)

for neighbour in graph[node]:

dfs(visited, graph, neighbour)

# Driver Code

print("Following is the Depth-First Search")

dfs(visited, graph, '5')

Dept. Of Computer Applications, VBSPU

 Artificial Intelligent Lab

Step-by-step algorithm for Depth-First Search:

Initialize a stack to keep track of nodes to visit.

Push the starting node into the stack.
Initialize a set to keep track of visited nodes, and add the starting node to the set.
While the stack is not empty, repeat steps 5-7.
Pop the top node from the stack.
For each neighbor of the popped node that has not been visited yet, add it to the visited
set and push it onto the stack.
If the goal node is found, return it. Otherwise, continue to step 4.

Dept. Of Computer Applications, VBSPU

 Artificial Intelligent Lab

# PROGRAM 4: Program to implement Informed Search Technique: A* Algorithm

Source Code:
class Node():

def __init__(self, parent=None, position=None):

[Link] = parent
[Link] = position

self.g = 0
self.h = 0
self.f = 0

def __eq__(self, other):

return [Link] == [Link]

def astar(maze, start, end):

"""Returns a list of tuples as a path from the given start to the given end in the given
maze"""

# Create start and end node

start_node = Node(None, start)
start_node.g = start_node.h = start_node.f = 0
end_node = Node(None, end)
end_node.g = end_node.h = end_node.f = 0

# Initialize both open and closed list

open_list = []
closed_list = []

# Add the start node

open_list.append(start_node)

# Loop until you find the end

while len(open_list) > 0:

# Get the current node

current_node = open_list[0]
current_index = 0
for index, item in enumerate(open_list):
if item.f < current_node.f:
current_node = item
current_index = index

Dept. Of Computer Applications, VBSPU

 Artificial Intelligent Lab

# Pop current off open list, add to closed list

open_list.pop(current_index)
closed_list.append(current_node)

# Found the goal

if current_node == end_node:
path = []
current = current_node
while current is not None:
[Link]([Link])
current = [Link]
return path[::-1] # Return reversed path

# Generate children
children = []
for new_position in [(0, -1), (0, 1), (-1, 0), (1, 0), (-1, -1), (-1, 1), (1, -1), (1, 1)]: #
Adjacent squares

# Get node position

node_position = (current_node.position[0] + new_position[0],
current_node.position[1] + new_position[1])

# Make sure within range

if node_position[0] > (len(maze) - 1) or node_position[0] < 0 or
node_position[1] > (len(maze[len(maze)-1]) -1) or node_position[1] < 0:
continue

# Make sure walkable terrain

if maze[node_position[0]][node_position[1]] != 0:
continue

# Create new node

new_node = Node(current_node, node_position)

# Append
[Link](new_node)

# Loop through children

for child in children:

# Child is on the closed list

Dept. Of Computer Applications, VBSPU

 Artificial Intelligent Lab

for closed_child in closed_list:

if child == closed_child:
continue

# Create the f, g, and h values

child.g = current_node.g + 1
child.h = (([Link][0] - end_node.position[0]) ** 2) + (([Link][1] -
end_node.position[1]) ** 2)
child.f = child.g + child.h

# Child is already in the open list

for open_node in open_list:
if child == open_node and child.g > open_node.g:
continue

# Add the child to the open list

open_list.append(child)

def main():

maze = [[0, 0, 0, 0, 1, 0, 0, 0, 0, 0],

[0, 0, 0, 0, 1, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 1, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 1, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 1, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 1, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 1, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 1, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]]

start = (0, 0)
end = (7, 6)

path = astar(maze, start, end)

print(path)

if name == '__main__':
main()

Dept. Of Computer Applications, VBSPU

 Artificial Intelligent Lab

// A* Search Algorithm

1. Initialize the open list

2. Initialize the closed list put the starting node on the open list (you can leave its f at zero)

3. while the open list is not empty

a) find the node with the least f on the open list, call it "q"
b) pop q of the open list
c) generate q's 8 successors and set their parents to q
d) for each successor
i) if successor is the goal, stop search
ii) else, compute both g and h for successor successor.g = q.g + distance between
successor and q successor.h = distance from goal to successor (This can be done
using many ways, we wil discuss three heuristics- Manhattan, Diagonal and
Euclidean Heuristics) successor.f = successor.g + successor.h ii )if a node with
the same position as successor is in the OPEN list which has a lower f than
successor, skip this successor
iv) if a node with the same position as successor is in the CLOSED list which
has a lower f than successor, skip this successor otherwise, add the node to the
open list end (for loop)
e) push q on the closed list end (while loop)

Dept. Of Computer Applications, VBSPU

 Artificial Intelligent Lab

Program 4 :Write a Program to Implement Tic-Tac-Toe

game using Python.
# Tic-Tac-Toe Program using #
random number in Python

# importing all necessary libraries import

numpy as np
import random
from time import sleep
# Creates an empty board def create_board():
return([Link]([[0, 0, 0],

[0, 0, 0],
[0, 0, 0]]))
# Check for empty places on board def
possibilities(board):
l = []

for i in range(len(board)):
for j in range(len(board)):

if board[i][j] == 0:
[Link]((i, j))
return(l)

# Select a random place for the player def

random_place(board, player):
selection = possibilities(board) current_loc =
[Link](selection) board[current_loc] =
player return(board)

# Checks whether the player has three # of their

marks in a horizontal row def row_win(board,
player):
for x in range(len(board)): win =
True

for y in range(len(board)):
if board[x, y] != player: win =
False continue

if win == True:

Dept. Of Computer Applications, VBSPU

 Artificial Intelligent Lab

return(win)
return(win)

# Checks whether the player has three # of their

marks in a vertical row
def col_win(board, player):
for x in range(len(board)): win =
True

for y in range(len(board)):
if board[y][x] != player: win =
False continue

if win == True:
return(win)
return(win)

# Checks whether the player has three # of their

marks in a diagonal row
def diag_win(board, player): win =
True
y=0
for x in range(len(board)):
if board[x, x] != player: win =
False
if win:
return win
win = True if
win:
for x in range(len(board)): y =
len(board) - 1 - x
if board[x, y] != player: win =
False
return win

# Evaluates whether there is # a

winner or a tie
def evaluate(board):
winner = 0

for player in [1, 2]:

if (row_win(board, player) or

Dept. Of Computer Applications, VBSPU

 Artificial Intelligent Lab
col_win(board,player) or
diag_win(board,player)):

winner = player

if [Link](board != 0) and winner == 0: winner

= -1
return winner

# Main function to start the game def

play_game():
board, winner, counter = create_board(), 0, 1
print(board)
sleep(2)

while winner == 0:
for player in [1, 2]:
board = random_place(board, player) print("Board after
" + str(counter) + " move") print(board)
sleep(2)
counter +=
1
winner = evaluate(board)
if winner != 0:
break
return(winner)

# Driver Code
print("Winner is: " + str(play_game()))

Output:-

[ 0 0
[ ]
0
[ 0 0
0 ]
[ 0 0
0 ]
]
Board after 1 move

[ 0 0
[ ]
0
[ 0 0
0 ]

Dept. Of Computer Applications, VBSPU

 Artificial Intelligent Lab
[ 0 0
1 ]
]
Board after 2 move

[ 0 0
[ ]
0
[ 2 0
0 ]
[ 0 0
1 ]
]
Board after 3 move

[ 1 0
[ ]
0
[ 2 0
0 ]
[ 0 0
1 ]
]
Board after 4 move

[ 1 0
[ ]
0
[ 2 0
2 ]
[ 0 0
1 ]
]
Board after 5 move

[ 1 0
[ ]
1
[ 2 0
2 ]
[ 0 0
1 ]
]
Board after 6 move

Dept. Of Computer Applications, VBSPU

 Artificial Intelligent Lab
[ 1 0
[ ]
1
[ 2 0
2 ]
[ 2 0
1 ]
]
Board after 7 move

[ 1 0
[ ]
1
[ 2 0
2 ]
[ 2 1
1 ]
]
Board after 8
move [[1 1 0]
[2 2 2]
[1 2 1]]
Winner is: 2

Dept. Of Computer Applications, VBSPU

 Artificial Intelligent Lab

# PROGRAM 5 : Program to implement Local Search Technique: Hill Climbing Algorithm

Source Code:

import random

def randomSolution(tsp):
cities = list(range(len(tsp)))
solution = []

for i in range(len(tsp)):
randomCity = cities[[Link](0, len(cities) - 1)]
[Link](randomCity)
[Link](randomCity)

return solution

def routeLength(tsp, solution):

routeLength = 0
for i in range(len(solution)):
routeLength += tsp[solution[i - 1]][solution[i]]
return routeLength

def getNeighbours(solution):
neighbours = []
for i in range(len(solution)):
for j in range(i + 1, len(solution)):
neighbour = [Link]()
neighbour[i] = solution[j]
neighbour[j] = solution[i]
[Link](neighbour)
return neighbours

def getBestNeighbour(tsp, neighbours):

bestRouteLength = routeLength(tsp, neighbours[0])
bestNeighbour = neighbours[0]
for neighbour in neighbours:
currentRouteLength = routeLength(tsp, neighbour)
if currentRouteLength < bestRouteLength:
bestRouteLength = currentRouteLength
bestNeighbour = neighbour
return bestNeighbour, bestRouteLength

Dept. Of Computer Applications, VBSPU

 Artificial Intelligent Lab

def hillClimbing(tsp):
currentSolution = randomSolution(tsp)
currentRouteLength = routeLength(tsp, currentSolution)
neighbours = getNeighbours(currentSolution)
bestNeighbour, bestNeighbourRouteLength = getBestNeighbour(tsp, neighbours)

while bestNeighbourRouteLength < currentRouteLength:

currentSolution = bestNeighbour
currentRouteLength = bestNeighbourRouteLength
neighbours = getNeighbours(currentSolution)
bestNeighbour, bestNeighbourRouteLength = getBestNeighbour(tsp, neighbours)
return currentSolution, currentRouteLength
def main():
tsp = [
[0, 400, 500, 300],
[400, 0, 300, 500],
[500, 300, 0, 400],
[300, 500, 400, 0]
]

print(hillClimbing(tsp))

if name == " main ":

main()

Dept. Of Computer Applications, VBSPU

 Artificial Intelligent Lab

Algorithm for Simple Hil Climbing:

Step 1: Evaluate the initial state, if it is goal state then return success and Stop.
Step 2: Loop Until a solution is found or there is no new operator left to apply.
Step 3: Select and apply an operator to the current state.
Step 4: Check new state:
If it is goal state, then return success and quit.
Else if it is better than the current state then assign new state as a current state.
Else if not better than the current state, then return to step2.
Step 5: Exit.

Dept. Of Computer Applications, VBSPU

 Artificial Intelligent Lab

# PROGRAM 6: Program to implement Game Playing Algorithms: Minimax and Alpha

Beta
Pruning

Source Code

a) MiniMAx

Algorithm import math

def minimax (curDepth, nodeIndex,

maxTurn, scores,
targetDepth):

# base case : targetDepth reached

if (curDepth == targetDepth):
return scores[nodeIndex]

if (maxTurn):
return max(minimax(curDepth + 1, nodeIndex * 2,
False, scores, targetDepth),
minimax(curDepth + 1, nodeIndex * 2 + 1,
False, scores, targetDepth))
else:
return min(minimax(curDepth + 1, nodeIndex * 2,
T
rue,
scores,
targetD
epth),
minima
x(curDe
pth + 1,
nodeInd
ex * 2 +
1,
True, scores, targetDepth))

# Driver code
scores = [3, 5, 2, 9, 12, 5, 23, 23]

treeDepth = [Link](len(scores), 2)

print("The optimal value is : ", end = "")

print(minimax(0, 0, True, scores, treeDepth))

Dept. Of Computer Applications, VBSPU

 Artificial Intelligent Lab

Dept. Of Computer Applications, VBSPU

 Artificial Intelligent Lab

Algorithm:

1. Construct the complete game tree

2. Evaluate scores for leaves using the evaluation function
3. Back-up scores from leaves to root, considering the player type:
4. For max player, select the child with the maximum score
5. For min player, select the child with the minimum score
6. At the root node, choose the node with max value and perform the corresponding move

Dept. Of Computer Applications, VBSPU

 Artificial Intelligent Lab

Source Code

b) Alpha Beta Pruning Algorithm

# Initial values of Alpha and Beta

MAX, MIN = 1000, -1000

# Returns optimal value for current player

#(Initially called for root and maximizer)
def minimax(depth, nodeIndex, maximizingPlayer,
values, alpha, beta):

# Terminating condition. i.e

# leaf node is reached
if depth == 3:
return

values[nodeIndex] if

maximizingPlayer:

best = MIN

# Recur for left and right children

for i in range(0, 2):

val = minimax(depth + 1, nodeIndex * 2 + i,

False, values, alpha, beta)
best = max(best, val)
alpha = max(alpha, best)

# Alpha Beta
Pruning if beta <=
alpha:
break

return best
else:
best = MAX

R
e

Dept. Of Computer Applications, VBSPU

 Artificial Intelligent Lab
c #
u
r r
i
f g
o h
r t

l c
e h
f i
t l
d
a r
n e
d n
for i in range(0, 2):

Dept. Of Computer Applications, VBSPU

 Artificial Intelligent Lab

val = minimax(depth + 1, nodeIndex * 2 + i,

True, values, alpha, beta)
best = min(best, val)
beta = min(beta, best)

# Alpha Beta
Pruning if beta <=
alpha:
break

return best

# Driver Code
if name == " main ":

values = [3, 5, 6, 9, 1, 2, 0, -1]

print("The optimal value is :", minimax(0, 0, True, values, MIN, MAX))

Algorithm:

1. Define the initial values for alpha and beta as negative and positive infinit y, respectively.
2. Begin the recursive search through the tree, starting at the root node.
3. If the current node is a leaf node, evaluate its value and return it.
4. If the current node is a maximizing node, then set alpha to the maximum of alpha and the
value returned from its child node.
5. If alpha is greater than or equal to beta, then prune the remaining child nodes and return
alpha.
6. If the current node is a minimizing node, then set beta to the minimum of beta and the
value returned from its child node.
7. If beta is less than or equal to alpha, then prune the remaining child nodes and return beta.
8. Recurse to the next level of the tree, continuing with steps 3 to 7 until the entire tree has
been searched.
9. Return the final value of alpha or beta depending on whether the root node is a
maximizing or minimizing node.

Dept. Of Computer Applications, VBSPU

 Artificial Intelligent Lab

Dept. Of Computer Applications, VBSPU

 Artificial Intelligent Lab

# PROGRAM 7: Program to Implement N-Queens Problem using Python

# Python program to solve N Queen

# Problem using backtracking

global N
N=4
def printSolution(board):
for i in range(N):
for j in range(N):
print board[i]
[j], print
# A utility function to check if a queen can
# be placed on board[row][col]. Note that this
# function is called when "col" queens are
# already placed in columns from 0 to col -1.
# So we need to check only left side for
# attacking queens
def isSafe(board, row, col):
# Check this row on left side
for i in range(col):
if board[row][i] == 1:
return False
# Check upper diagonal on left side
for i, j in zip(range(row, -1, -1), range(col, -1, -1)):
if board[i][j] == 1:
return False
# Check lower diagonal on left side
for i, j in zip(range(row, N, 1), range(col, -1, -1)):
if board[i][j] == 1:
return False
return True
def solveNQUtil(board, col):
# base case: If al queens are placed
# then return true
if col >= N:
return True
# Consider this column and try placing
# this queen in all rows one by one
for i in range(N):
if isSafe(board, i, col):
# Place this queen in board[i][col]

Dept. Of Computer Applications, VBSPU

 Artificial Intelligent Lab

# recur to place rest of the queens

if solveNQUtil(board, col + 1) == True:
return True
# If placing queen in board[i][col
# doesn't lead to a solution, then
# queen from board[i][col]
board[i][col] = 0
# if the queen can not be placed in any row in
# this colum col then return false
return False
# This function solves the N Queen problem using
# Backtracking. It mainly uses solveNQUtil() to #
solve the problem. It returns false if queens
# cannot be placed, otherwise return true and
# placement of queens in the form of 1s.
# note that there may be more than one
# solutions, this function prints one of the
# feasible solutions.
def solveNQ():
board = [ [0, 0, 0, 0],
[0, 0, 0, 0],
[0, 0, 0, 0],
[0, 0, 0, 0]
]
if solveNQUtil(board, 0) == False:
print "Solution does not exist"
return False
printSolution(board)
return True
# driver program to test above function
solveNQ()

Output:
0010
1000
0001
0100

Dept. Of Computer Applications, VBSPU