AMITY SCHOOL OF ENGINEERING &
TECHNOLOGY
AMITY UNIVERSITY UTTAR PRADESH
GAUTAM BUDDHA NAGAR
ARTIFICIAL INTELLIGENCE
LAB FILE
(CSE 401)
Submitted To; Submitted By:
Dr Vandana Bhatia Saurabh Singh
A12405216144
7CSE13-X
j
Experiment 1
Write a program to implement A* algorithm in python
Program
class Node():
"""A node class for A* Pathfinding"""
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
# 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
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()
Output
Experiment 2
Write a program to implement Single Player Game
Program
Output
Experiment 3
Write a program to implement Tic-Tac-Toe game problem
Program
# 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:
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
for x in range(len(board)):
if board[x, x] != 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
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
Experiment 4
Implement Brute force solution to the Knapsack problem in Python
Program
class Bounty:
def __init__(self, value, weight, volume):
[Link], [Link], [Link] = value, weight, volume
panacea = Bounty(3000, 0.3, 0.025)
ichor = Bounty(1800, 0.2, 0.015)
gold = Bounty(2500, 2.0, 0.002)
sack = Bounty( 0, 25.0, 0.25)
best = Bounty( 0, 0, 0)
current = Bounty( 0, 0, 0)
best_amounts = (0, 0, 0)
max_panacea = int(min([Link] // [Link], [Link] //
[Link]))
max_ichor = int(min([Link] // [Link], [Link] //
[Link]))
max_gold = int(min([Link] // [Link], [Link] //
[Link]))
for npanacea in xrange(max_panacea):
for nichor in xrange(max_ichor):
for ngold in xrange(max_gold):
[Link] = npanacea * [Link] + nichor * [Link]
+ ngold * [Link]
[Link] = npanacea * [Link] + nichor *
[Link] + ngold * [Link]
[Link] = npanacea * [Link] + nichor *
[Link] + ngold * [Link]
if [Link] > [Link] and [Link] <= [Link]
and \
[Link] <= [Link]:
best = Bounty([Link], [Link],
[Link])
best_amounts = (npanacea, nichor, ngold)
print "Maximum value achievable is", [Link]
print "This is achieved by carrying (one solution) %d panacea,%d ichor and
%d gold" % \(best_amounts[0], best_amounts[1], best_amounts[2])
print "The weight to carry is %4.1f and the volume used is %5.3f" %
([Link], [Link])
Output
Experiment 5
Implement Graph colouring problem using python
Program
def color_nodes(graph):
# Order nodes in descending degree
nodes = sorted(list([Link]()), key=lambda x: len(graph[x]),
reverse=True)
color_map = {}
for node in nodes:
available_colors = [True] * len(nodes)
for neighbor in graph[node]:
if neighbor in color_map:
color = color_map[neighbor]
available_colors[color] = False
for color, available in enumerate(available_colors):
if available:
color_map[node] = color
break
return color_map
if __name__ == '__main__':
graph = {
'a': list('bcd'),
'b': list('ac'),
'c': list('abdef'),
'd': list('ace'),
'e': list('cdf'),
'f': list('ce')
}
print(color_nodes(graph))
# {'c': 0, 'a': 1, 'd': 2, 'e': 1, 'b': 2, 'f': 2}
Output
Experiment 6
Write a program to implement BFS for water jug problem using Python
Program
def pour(jug1, jug2):
max1, max2, fill = 5, 7, 4 #Change maximum capacity and final capacity
print("%d\t%d" % (jug1, jug2))
if jug2 is fill:
return
elif jug2 is max2:
pour(0, jug1)
elif jug1 != 0 and jug2 is 0:
pour(0, jug1)
elif jug1 is fill:
pour(jug1, 0)
elif jug1 < max1:
pour(max1, jug2)
elif jug1 < (max2-jug2):
pour(0, (jug1+jug2))
else:
pour(jug1-(max2-jug2), (max2-jug2)+jug2)
print("JUG1\tJUG2")
pour(0, 0)
Output
Experiment 7
Write a program to implement DFS using Python
Program
# Python3 program to print DFS traversal
# from a given given graph
from collections import defaultdict
# This class represents a directed graph using
# adjacency list representation
class Graph:
# Constructor
def __init__(self):
# default dictionary to store graph
[Link] = defaultdict(list)
# function to add an edge to graph
def addEdge(self, u, v):
[Link][u].append(v)
# A function used by DFS
def DFSUtil(self, v, visited):
# Mark the current node as visited
# and print it
visited[v] = True
print(v, end = ' ')
# Recur for all the vertices
# adjacent to this vertex
for i in [Link][v]:
if visited[i] == False:
[Link](i, visited)
# The function to do DFS traversal. It uses
# recursive DFSUtil()
def DFS(self, v):
# Mark all the vertices as not visited
visited = [False] * (len([Link]))
# Call the recursive helper function
# to print DFS traversal
[Link](v, visited)
# Driver code
# Create a graph given
# in the above diagram
g = Graph()
[Link](0, 1)
[Link](0, 2)
[Link](1, 2)
[Link](2, 0)
[Link](2, 3)
[Link](3, 3)
print("Following is DFS from (starting from vertex 2)")
[Link](2)
Output
Experiment 8
Tokenization of word and Sentences with the help of NLTK package
Program
import nltk
[Link]('punkt')
from [Link] import word_tokenize
text = "God is Great! I won a lottery."
print(word_tokenize(text))
Output
Experiment 9
Design an XOR truth table using Python
Program
# Python3 program to illustrate
# working of Xor gate
def XOR (a, b):
if a != b:
return 1
else:
return 0
# Driver code
if __name__=='__main__':
print(XOR(5, 5))
print("+---------------+----------------+")
print(" | XOR Truth Table | Result |")
print(" A = False, B = False | A AND B =",XOR(False,False)," |
")
print(" A = False, B = True | A AND B =",XOR(False,True)," | ")
print(" A = True, B = False | A AND B =",XOR(True,False)," | ")
print(" A = True, B = True | A AND B =",XOR(True,True)," | ")
Output
Experiment 10
Study of SCIKIT fuzzy
Theory
scikit-fuzzy (a.k.a. skfuzzy): Fuzzy logic toolbox for Python.
This package implements many useful tools for projects involving fuzzy logic, also known as grey
logic.
Scikit-fuzzy is a robust set of foundational tools for problems involving fuzzy logic and fuzzy systems.
This area has been a challenge for the scientific Python community, largely because the common first
exposure to this topic is through the MATLAB® Fuzzy Logic Toolbox™.
The current capabilities of scikit-fuzzy include: fuzzy membership function generation; fuzzy set
operations; lambda-cuts; fuzzy mathematics including Zadeh's extension principle, the vertex
method, and the DSW method; fuzzy implication given an IF THEN system of fuzzy rules (via
Mamdani [min] or Larsen [product] implication); various defuzzification algorithms; fuzzy c-means
clustering; and Fuzzy Inference Ruled by Else-action (FIRE) denoising of 1d or 2d signals.
The goals of scikit-fuzzy are to provide the community with a robust toolkit of independently
developed and implemented fuzzy logic algorithms, filling a void in the capabilities of scientific and
numerical Python, and to increase the attractiveness of scientific Python as a valid alternative to
closed-source options. Scikit-fuzzy is structured similarly to scikit-learn and scikit-image, current
source code is available on GitHub, and pull requests are welcome.