ARTIFICIAL INTELIGENCE(3170716) 200490131056

Practical : 1
Aim : Write a program to implement Tic-Tac-Toe game problem.

import numpy as np
import random
from time import sleep
# Creates an empty board
def create_board():
return(np.array([[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:
l.append((i, j))
return(l)
# Select a random place for the player
def random_place(board, player):
selection = possibilities(board)
current_loc = random.choice(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)

1|Page
ARTIFICIAL INTELIGENCE(3170716) 200490131056

# 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
col_win(board,player) or
diag_win(board,player)):
winner = player
if np.all(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()))

2|Page
ARTIFICIAL INTELIGENCE(3170716) 200490131056

Output :

3|Page
ARTIFICIAL INTELIGENCE(3170716) 200490131056

Practical : 2
Aim : Write a program to implement BFS (for 8 puzzle problem or Water
Jug problem or Any AI search problem).

from collections import deque

def BFS(a, b, target):
# Map is used to store the states, every
# state is hashed to binary value to
# indicate either that state is visited
# before or not
m = {}
isSolvable = False
path = []
# Queue to maintain states
q = deque()
# Initialing with initial state
q.append((0, 0))
while (len(q) > 0):
# Current state
u = q.popleft()
# q.pop() #pop off used state
# If this state is already visited
if ((u[0], u[1]) in m):
continue
# Doesn't met jug constraints
if ((u[0] > a or u[1] > b or
u[0] < 0 or u[1] < 0)):
continue
# Filling the vector for constructing
# the solution path
path.append([u[0], u[1]])
# Marking current state as visited
m[(u[0], u[1])] = 1
# If we reach solution state, put ans=1
if (u[0] == target or u[1] == target):
isSolvable = True
if (u[0] == target):
if (u[1] != 0):
# Fill final state
path.append([u[0], 0])
else:
if (u[0] != 0):
# Fill final state
path.append([0, u[1]])
# Print the solution path
sz = len(path)
for i in range(sz):
print("(", path[i][0], ",",
path[i][1], ")")

4|Page
ARTIFICIAL INTELIGENCE(3170716) 200490131056

break
# If we have not reached final state
# then, start developing intermediate
# states to reach solution state
q.append([u[0], b]) # Fill Jug2
q.append([a, u[1]]) # Fill Jug1
for ap in range(max(a, b) + 1):
# Pour amount ap from Jug2 to Jug1
c = u[0] + ap
d = u[1] - ap
# Check if this state is possible or not
if (c == a or (d == 0 and d >= 0)):
q.append([c, d])
# Pour amount ap from Jug 1 to Jug2
c = u[0] - ap
d = u[1] + ap
# Check if this state is possible or not
if ((c == 0 and c >= 0) or d == b):
q.append([c, d])
# Empty Jug2
q.append([a, 0])
# Empty Jug1
q.append([0, b])
# No, solution exists if ans=0
if (not isSolvable):
print("No solution")
# Driver code
if __name__ == '__main__':
Jug1, Jug2, target = 4, 3, 2
print("Path from initial state "
"to solution state ::")
BFS(Jug1, Jug2, target)

Output :

5|Page
ARTIFICIAL INTELIGENCE(3170716) 200490131056

Practical : 3
Aim : Write a program to implement DFS (for 8 puzzle problem or Water
Jug problem or Any AI search problem).
#include <cstdio>
#include <stack>
#include <map>
#include <algorithm>
using namespace std;
struct state {
int x, y;
bool operator < (const state& that) const {
if (x != that.x) return x < that.x;
return y < that.y;
}
};
int capacity_x, capacity_y, target;
void dfs(state start, stack <pair <state, int> >& path) {
stack <state> s;
state goal = (state) {-1, -1};
map <state, pair <state, int> > parentOf;
s.push(start);
parentOf[start] = make_pair(start, 0);
while (!s.empty()) {
state top = s.top();
s.pop();
if (top.x == target || top.y == target) {
goal = top;
break;
}
// Rule 1: (x, y) -> (capacity_x, y) if x < capacity_x
// Fill the first jug
if (top.x < capacity_x) {
state child = (state) {capacity_x, top.y};
// Consider this state for visiting only if it has not been visited before
if (parentOf.find(child) == parentOf.end()) {
s.push(child);
parentOf[child] = make_pair(top, 1);
}
}
// Rule 2: (x, y) -> (x, capacity_y) if y < capacity_y
// Fill the second jug
if (top.y < capacity_y) {
state child = (state) {top.x, capacity_y};
if (parentOf.find(child) == parentOf.end()) {
s.push(child);
parentOf[child] = make_pair(top, 2);
}
}
// Rule 3: (x, y) -> (0, y) if x > 0

6|Page
ARTIFICIAL INTELIGENCE(3170716) 200490131056

// Empty the first jug

if (top.x > 0) {
state child = (state) {0, top.y};
if (parentOf.find(child) == parentOf.end()) {
s.push(child);
parentOf[child] = make_pair(top, 3);
}
}
// Rule 4: (x, y) -> (x, 0) if y > 0
// Empty the second jug
if (top.y > 0) {
state child = (state) {top.x, 0};
if (parentOf.find(child) == parentOf.end()) {
s.push(child);
parentOf[child] = make_pair(top, 4);
}
}
// Rule 5: (x, y) -> (min(x + y, capacity_x), max(0, x + y - capacity_x)) if y > 0
// Pour water from the second jug into the first jug until the first jug is full
// or the second jug is empty
if (top.y > 0) {
state child = (state) {min(top.x + top.y, capacity_x), max(0, top.x + top.y -
capacity_x)};
if (parentOf.find(child) == parentOf.end()) {
s.push(child);
parentOf[child] = make_pair(top, 5);
}
}
// Rule 6: (x, y) -> (max(0, x + y - capacity_y), min(x + y, capacity_y)) if x > 0
// Pour water from the first jug into the second jug until the second jug is full
// or the first jug is empty
if (top.x > 0) {
state child = (state) {max(0, top.x + top.y - capacity_y), min(top.x + top.y,
capacity_y)};
if (parentOf.find(child) == parentOf.end()) {
s.push(child);
parentOf[child] = make_pair(top, 6);
}
}
}
// Target state was not found
if (goal.x == -1 || goal.y == -1)
return;
// backtrack to generate the path through the state space
path.push(make_pair(goal, 0));
// remember parentOf[start] = (start, 0)
while (parentOf[path.top().first].second != 0)
path.push(parentOf[path.top().first]);
}
int main() {

7|Page
ARTIFICIAL INTELIGENCE(3170716) 200490131056

stack <pair <state, int> > path;

printf("Enter the capacities of the two jugs : ");
scanf("%d %d", &capacity_x, &capacity_y);
printf("Enter the target amount : ");
scanf("%d", &target);
dfs((state) {0, 0}, path);
if (path.empty())
printf("\nTarget cannot be reached.\n");
else {
printf("\nNumber of moves to reach the target : %d\nOne path to the target is as
follows :\n", path.size() - 1);
while (!path.empty()) {
state top = path.top().first;
int rule = path.top().second;
path.pop();
switch (rule) {
case 0: printf("State : (%d, %d)\n#\n", top.x, top.y);
break;
case 1: printf("State : (%d, %d)\nAction : Fill the first jug\n", top.x, top.y);
break;
case 2: printf("State : (%d, %d)\nAction : Fill the second jug\n", top.x, top.y);
break;
case 3: printf("State : (%d, %d)\nAction : Empty the first jug\n", top.x, top.y);
break;
case 4: printf("State : (%d, %d)\nAction : Empty the second jug\n", top.x, top.y);
break;
case 5: printf("State : (%d, %d)\nAction : Pour from second jug into first jug\n",
top.x, top.y);
break;
case 6: printf("State : (%d, %d)\nAction : Pour from first jug into second jug\n",
top.x, top.y);
break;
}
}
}
return 0;
}

8|Page
ARTIFICIAL INTELIGENCE(3170716) 200490131056

Output :

9|Page
ARTIFICIAL INTELIGENCE(3170716) 200490131056

Practical : 4
Aim : Write a program to implement Single Player Game (Using any
Heuristic Function)

Import random
print("#------------------#")
print("| GUESS THE NUMBER |")
print("#------------------#") print('\
n')

print('Range of Random Numbers.')

start = int(input('Enter Starting Index:
')) end = int(input('Enter Ending Index:
')) number = random.randint(start, end)
print('\n')

while True:
guess = int(input('Guess the number: '))
if guess > number:
print('\nHmmm, try a lower number...\n')

elif guess < number:

print('\nGo a little higher\n')

else:
print("Right on! Well done!")
break

10 | P a g e
ARTIFICIAL INTELIGENCE(3170716) 200490131056

Output :

11 | P a g e
ARTIFICIAL INTELIGENCE(3170716) 200490131056

Practical : 5
Aim : Write a program to Implement A* Algorithm.

Class node()
"""A node class for A* Pathfinding"""
def __init__(self, parent=None, position=None):
self.parent = parent
self.position = position
self.g = 0
self.h = 0
self.f = 0
def __eq__(self, other):
return self.position == other.position
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:

12 | P a g e
ARTIFICIAL INTELIGENCE(3170716) 200490131056

path.append(current.position)
current = current.parent
return path[::-1] # Return reversed path

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

# 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
children.append(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 = ((child.position[0] - end_node.position[0]) **
2) + ((child.position[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)

13 | P a g e
ARTIFICIAL INTELIGENCE(3170716) 200490131056

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 :

14 | P a g e
ARTIFICIAL INTELIGENCE(3170716) 200490131056

Practical : 6
Aim : Write a program to implement mini-max algorithm for any game
development.
# A simple Python3 program to find
# maximum score that
# maximizing player can get
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,
True, scores, targetDepth),
minimax(curDepth + 1, nodeIndex * 2 + 1,
True, scores, targetDepth))

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

treeDepth = math.log(len(scores), 2)

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

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

Output :

15 | P a g e
ARTIFICIAL INTELIGENCE(3170716) 200490131056

Practical : 7
Aim : Assume given a set of facts of the form father(name1,name2) (name1
is the father of name2).

female(pam).
female(liz).
female(pat).
female(ann).

male(jim).
male(bob).
male(tom).
male(peter).

parent(pam,bob).
parent(tom,bob).
parent(tom,liz).
parent(bob,ann).

parent(bob,pat).
parent(pat,jim).
parent(bob,peter).
parent(peter,jim).

mother(X,Y):- parent(X,Y),female(X).
father(X,Y):-parent(X,Y),male(X).
sister(X,Y):-parent(Z,X),parent(Z,Y),female(X),X\==Y.
brother(X,Y):-parent(Z,X),parent(Z,Y),male(X),X\==Y.
grandparent(X,Y):-parent(X,Z),parent(Z,Y).
grandmother(X,Z):-mother(X,Y),parent(Y,Z).
grandfather(X,Z):-father(X,Y),parent(Y,Z).
wife(X,Y):-parent(X,Z),parent(Y,Z),female(X),male(Y).
uncle(X,Z):-brother(X,Y),parent(Y,Z).

16 | P a g e
ARTIFICIAL INTELIGENCE(3170716) 200490131056

Output :

17 | P a g e
ARTIFICIAL INTELIGENCE(3170716) 200490131056

Practical : 8
Aim : Define a predicate brother(X,Y) which holds iff X and Y are
brothers.
Define a predicate cousin(X,Y) which holds iff X and Y are cousins.
Define a predicate grandson(X,Y) which holds iff X is a grandson of Y.
Define a predicate descendent(X,Y) which holds iff X is a descendent of Y.
Consider the following genealogical tree: father(a,b).
father(a,c). father(b,d). father(b,e). father(c,f).
Say which answers, and in which order, are generated by your
definitions for the following queries in Prolog:
?- brother(X,Y).
?- cousin(X,Y).
?- grandson(X,Y).
?- descendent(X,Y).

father(anil,harshvardhan).
father(anil,arjun).
father(bonny,sonam).
father(bonny,jhanvi).
father(arjun,ridham).
grandson(X,Y):-father(X,K),father(K,Y)
cousin(A,B):-father(K,X),father(K,Y),father(X,A),father(Y,B) brother(X,Y):-
father(K,X),father(K,Y) descendent(X,Y):-father(K,X),father(K,Y)
descendent(X,Y):-father(K,X),father(K,Y),father(X,A),father(Y,B)
descendent(X,Y):-father(X,K),father(K,Y)
Output :

18 | P a g e
ARTIFICIAL INTELIGENCE(3170716) 200490131056

Practical : 9
Aim : Write a program to solve Tower of Hanoi problem using Prolog.

move(1,X,Y,_) :-
write('Move top disk from '), write(X), write(' to '),write(Y), nl.
move(N,X,Y,Z) :-
N>1,
M is N-1,
move(M,X,Z,Y),
move(1,X,Y,_),
move(M,Z,Y,X).

Output :

19 | P a g e
ARTIFICIAL INTELIGENCE(3170716) 200490131056

Practical : 10
Aim : Write a program to solve N-Queens problem using Prolog.
% render solutions nicely. use_rendering(chess).

queens(N, Queens) :-
length(Queens, N),
board(Queens, Board, 0, N, _, _),
queens(Board, 0, Queens).

board([], [], N, N, _, _).

board([_|Queens],
[Col-Vars|Board],
Col0, N, [_|VR], VC) :- Col is Col0+1,
functor(Vars, f, N),
constraints(N, Vars, VR, VC),

board(Queens, Board, Col, N, VR, [_|VC]).

constraints(0, _, _, _) :- !.
constraints(N, Row, [R|Rs], [C|Cs]) :-
arg(N, Row, R-C),
M is N-1,
constraints(M, Row, Rs, Cs).

queens([], _, []).
queens([C|Cs], Row0, [Col|Solution]) :-
Row is Row0+1,
select(Col-Vars, [C|Cs], Board),
arg(Row, Vars, Row-Row),
queens(Board, Row, Solution).

Output:-

20 | P a g e
ARTIFICIAL INTELIGENCE(3170716) 200490131056

Practical : 11
Aim : Write a program to solve 8 puzzle problem using Prolog.

21 | P a g e
ARTIFICIAL INTELIGENCE(3170716) 200490131056

goal([1,2,3, 4,0,5, 6,7,8]).

move([X1,0,X3, X4,X5,X6, X7,X8,X9],
[0,X1,X3, X4,X5,X6, X7,X8,X9]).
move([X1,X2,0, X4,X5,X6, X7,X8,X9],
[X1,0,X2, X4,X5,X6, X7,X8,X9]).
move([X1,X2,X3, X4,0,X6,X7,X8,X9],
[X1,X2,X3, 0,X4,X6,X7,X8,X9]).
move([X1,X2,X3, X4,X5,0,X7,X8,X9],
[X1,X2,X3, X4,0,X5,X7,X8,X9]).
move([X1,X2,X3, X4,X5,X6, X7,0,X9],
[X1,X2,X3, X4,X5,X6, 0,X7,X9]).
move([X1,X2,X3, X4,X5,X6, X7,X8,0],
[X1,X2,X3, X4,X5,X6, X7,0,X8]).
move([0,X2,X3, X4,X5,X6, X7,X8,X9],
[X2,0,X3, X4,X5,X6, X7,X8,X9]).
move([X1,0,X3, X4,X5,X6, X7,X8,X9],
[X1,X3,0, X4,X5,X6, X7,X8,X9]).
move([X1,X2,X3, 0,X5,X6, X7,X8,X9],
[X1,X2,X3, X5,0,X6, X7,X8,X9]).
move([X1,X2,X3, X4,0,X6, X7,X8,X9],
[X1,X2,X3, X4,X6,0, X7,X8,X9]).
move([X1,X2,X3, X4,X5,X6,0,X8,X9],
[X1,X2,X3, X4,X5,X6,X8,0,X9]).
move([X1,X2,X3, X4,X5,X6,X7,0,X9],
[X1,X2,X3, X4,X5,X6,X7,X9,0]).
move([X1,X2,X3, 0,X5,X6, X7,X8,X9],
[0,X2,X3, X1,X5,X6, X7,X8,X9]).
move([X1,X2,X3, X4,0,X6, X7,X8,X9],
[X1,0,X3, X4,X2,X6, X7,X8,X9]).
move([X1,X2,X3, X4,X5,0, X7,X8,X9],
[X1,X2,0, X4,X5,X3, X7,X8,X9]).
move([X1,X2,X3, X4,X5,X6, X7,0,X9],
[X1,X2,X3, X4,0,X6, X7,X5,X9]).
move([X1,X2,X3, X4,X5,X6, X7,X8,0],
[X1,X2,X3, X4,X5,0, X7,X8,X6]).
move([X1,X2,X3, X4,X5,X6, 0,X8,X9],
[X1,X2,X3, 0,X5,X6, X4,X8,X9]).
move([0,X2,X3, X4,X5,X6, X7,X8,X9],
[X4,X2,X3, 0,X5,X6, X7,X8,X9]).
move([X1,0,X3, X4,X5,X6, X7,X8,X9],
[X1,X5,X3, X4,0,X6, X7,X8,X9]).
move([X1,X2,0, X4,X5,X6, X7,X8,X9],
[X1,X2,X6, X4,X5,0, X7,X8,X9]).
move([X1,X2,X3, 0,X5,X6, X7,X8,X9],
[X1,X2,X3, X7,X5,X6, 0,X8,X9]).

22 | P a g e
ARTIFICIAL INTELIGENCE(3170716) 200490131056

move([X1,X2,X3, X4,0,X6, X7,X8,X9],

[X1,X2,X3, X4,X8,X6, X7,0,X9]).
move([X1,X2,X3, X4,X5,0, X7,X8,X9],
[X1,X2,X3, X4,X5,X9, X7,X8,0]). dfsSimplest(S,
[S]) :- goal(S).
dfsSimplest(S, [S|Rest]) :- move(S, S2), dfsSimplest(S2, Rest).
dfs(S, Path, Path) :- goal(S). dfs(S, Checked, Path) :- move(S,
S2), \+member(S2, Checked), dfs(S2, [S2|Checked], Path).

Output :

Practical : 12
Aim : Write a program to solve travelling salesman problem using Prolog.

edge(a, b, 3).

23 | P a g e
ARTIFICIAL INTELIGENCE(3170716) 200490131056

edge(a, c, 4).
edge(a, d, 2).
edge(a, e, 7).
edge(b, c, 4).
edge(b, d, 6).
edge(b, e, 3).
edge(c, d, 5).
edge(c, e, 8).
edge(d, e, 6).
edge(b, a, 3).
edge(c, a, 4).
edge(d, a, 2).
edge(e, a, 7).
edge(c, b, 4).
edge(d, b, 6).
edge(e, b, 3).
edge(d, c, 5).
edge(e, c, 8).
edge(e, d, 6).
edge(a, h, 2).
edge(h, d, 1).
len([], 0).
len([H|T], N):- len(T, X), N is X+1 .
best_path(Visited, Total):- path(a, a, Visited, Total).

path(Start, Fin, Visited, Total) :- path(Start, Fin, [Start], Visited, 0, Total).

path(Start, Fin, CurrentLoc, Visited, Costn, Total) :-

edge(Start, StopLoc, Distance), NewCostn is Costn + Distance, \+ member(StopLoc,
CurrentLoc),
path(StopLoc, Fin, [StopLoc|CurrentLoc], Visited, NewCostn, Total).

path(Start, Fin, CurrentLoc, Visited, Costn, Total) :-

edge(Start, Fin, Distance), reverse([Fin|CurrentLoc], Visited), len(Visited, Q),
(Q\=7 -> Total is 100000; Total is Costn + Distance).

shortest_path(Path):-setof(Cost-Path, best_path(Path,Cost), Holder),pick(Holder,Path).

best(Cost-Holder,Bcost-_,Cost-Holder):- Cost<Bcost,!.
best(_,X,X).

pick([Cost-Holder|R],X):- pick(R,Bcost-Bholder),best(Cost-Holder,Bcost-Bholder,X),!.
pick([X],X).

Output :

24 | P a g e
ARTIFICIAL INTELIGENCE(3170716) 200490131056

25 | P a g e