RAJ KUMAR GOEL INSTITUTE OF TECHNOLOGY &

MANAGEMENT GHAZIABAD
5thKM Stone Delhi, Meerut Road, Near Raj Nagar Extension Road, Ghaziabad, UP-201003 Approved
by AICTE. N. Delhi &Affiliated to Dr. A.P.J. Abdul Kalam Technical University, Lucknow NBA
Accredited Program (B. Tech. ECE, IT) & B. Pharma

Artificial Intelligence Lab(BCS-751)

Submitted to: Mr. Kuldeep Kushwaha
Session: 2025-2026

Name Aditya Rauniyar

Roll No. 2203330130003

Section B

Department of Information Technology

 INDEX

S. No. Experiment Name Date of Date of

Conduction Submission

1. Implement Breadth First Search (BFS) for a

given graph or maze.

2. Implement Breadth First Search (BFS) for a

given graph or maze.

3. Solve the 8-Puzzle Problem using A*

Search Algorithm.

4. Implement Hill Climbing Algorithm for

numerical optimization or pathfinding.

5. Solve Water Jug Problem using state-

space search (BFS or DFS).

6. Build a simple text classifier using NLTK

(e.g., classify messages as spam/ham).

7. Study of PROLOG.

8. Write simple fact for following.

9. Write a program to solve the Monkey

Banana problem.

10. Implement 4-Queens Problem in Prolog.

11. Implement Min-Max (Minimax)

Algorithm for decision making in turn-
based games.

12. Implement Tic-Tac-Toe game with a basic

AI opponent

2
 EXPERIMENT NO. 1

Program Name: Implement Breadth First Search (BFS) for a given graph or maze.

Implementation:
# Function to find BFS of Graph from given source s def
bfs(adj):

# get number of vertices

V= len(adj)

# create an array to store the traversal

res = [] s = 0
# Create a queue for BFS
from collections import
deque q = deque()

# Initially mark all the vertices as not visited

visited = [False] * V

# Mark source node as visited and enqueue it

visited[s] = True
[Link](s)

# Iterate over the queue

while q:

# Dequeue a vertex from queue and store it

curr = [Link]()
[Link](curr)

# Get all adjacent vertices of the dequeued

# vertex curr If an adjacent has not been
# visited, mark it visited and enqueue it
for x in adj[curr]:
if not visited[x]:
visited[x] = True
[Link](x)

return res

if name == " main ":

# create the adjacency list # [ [2, 3, 1],

[0], [0, 4], [0], [2] ]

3
 adj = [[1,2], [0,2,3], [0,4], [1,4],
[2,3]]
ans = bfs(adj)
for i in ans:
print(i, end=" ")

4
 EXPERIMENT NO. 2

Program Name: Implement Breadth First Search (BFS) for a given graph or maze.

Implementation:
def dfsRec(adj, visited, s, res):
visited[s] = True
[Link](s)

# Recursively visit all adjacent vertices that are not visited yet
for i in range(len(adj)):
if adj[s][i] == 1 and not visited[i]:
dfsRec(adj, visited, i, res)

def DFS(adj):
visited = [False] * len(adj)
res = []
dfsRec(adj, visited, 0, res) # Start DFS from vertex 0
return res

def add_edge(adj, s, t):

adj[s][t] = 1
adj[t][s] = 1 # Since it's an undirected graph

# Driver code
V=5
adj = [[0] * V for _ in range(V)] # Adjacency matrix

# Define the edges of the graph edges =

[(1, 2), (1, 0), (2, 0), (2, 3), (2, 4)]

# Populate the adjacency matrix with edges

for s, t in edges:
add_edge(adj, s, t)

res = DFS(adj) # Perform DFS

print(" ".join(map(str, res)))

5
6
 EXPERIMENT NO. 3

Program Name: Solve the 8-Puzzle Problem using A* Search Algorithm.

Implementation:
import heapq
from termcolor import colored

# Class to represent the state of the 8-puzzle class

PuzzleState:
def init (self, board, parent, move, depth, cost):
[Link] = board # The puzzle board configuration
[Link] = parent # Parent state
[Link] = move # Move to reach this state
[Link] = depth # Depth in the search tree
[Link] = cost # Cost (depth + heuristic)

def lt (self, other):

return [Link] < [Link]

# Function to display the board in a visually appealing format

def print_board(board):
print("+---+---+---+") for row in range(0, 9, 3):
row_visual = "|"
for tile in board[row:row + 3]:
if tile == 0: # Blank tile row_visual += f"
{colored(' ', 'cyan')} |"
else:
row_visual += f" {colored(str(tile), 'yellow')} |"
print(row_visual)
print("+---+---+---+")

# Goal state for the puzzle

goal_state = [1, 2, 3, 4, 5, 6, 7, 8, 0]

# Possible moves for the blank tile (up, down, left, right)
moves = {
'U': -3, # Move up
'D': 3, # Move down
'L': -1, # Move left
'R': 1 # Move right
}

# Function to calculate the heuristic (Manhattan distance)

def heuristic(board): distance = 0
for i in range (9):
if board[i] != 0:
x1, y1 = divmod(i, 3)

7
 x2, y2 = divmod(board[i] - 1, 3)
distance += abs(x1 - x2) + abs(y1 - y2)
return distance

# Function to get the new state after a move

def move_tile(board, move, blank_pos):
new_board = board[:]
new_blank_pos = blank_pos + moves[move]
new_board[blank_pos], new_board[new_blank_pos] = new_board[new_blank_pos], new_board[blank_pos]
return new_board

# A* search algorithm
def
a_star(start_state):
open_list = []
closed_list = set()
[Link](open_list, PuzzleState(start_state, None, None, 0, heuristic(start_state)))

while open_list:
current_state = [Link](open_list)

if current_state.board == goal_state:

return current_state

closed_list.add(tuple(current_state.board

)) blank_pos =

current_state.[Link](0)

for move in moves: if move == 'U' and blank_pos < 3: #

Invalid move up continue
if move == 'D' and blank_pos > 5: # Invalid move down continue
if move == 'L' and blank_pos % 3 == 0: # Invalid move left continue
if move == 'R' and blank_pos % 3 == 2: # Invalid move right
continue new_board = move_tile(current_state.board, move,
blank_pos)

if tuple(new_board) in closed_list:
continue

new_state = PuzzleState(new_board, current_state, move, current_state.depth + 1, current_state.depth + 1 +

heuristic(new_board)) [Link](open_list, new_state) return None

# Function to print the solution path

def print_solution(solution):
path = [] current
= solution while
current:

8
 [Link](current)
current = [Link]
[Link]()

for step in path:

print(f"Move: {[Link]}")
print_board([Link])

# Initial state of the puzzle initial_state

= [1, 2, 3, 4, 0, 5, 6, 7, 8]

# Solve the puzzle using A* algorithm solution

= a_star(initial_state)

# Print the solution if

solution:
print(colored("Solution found:", "green"))
print_solution(solution)
else:
print(colored("No solution exists.", "red"))

Output:
Solution found:
Move: None
+---+---+---+
| 1 | 2 | 3 |
+---+---+---+
| 4 | | 5 |
+---+---+---+
| 6 | 7 | 8 |
+---+---+---+
Move: R
+---+---+---+
| 1 | 2 | 3 |
+---+---+---+
| 4 | 5 | |
+---+---+---+
| 6 | 7 | 8 |
+---+---+---+
Move: R
9
+---+---+---+
| 1 | 2 | 3 |
+---+---+---+
| 4 | 5 | 6 |
+---+---+---+
| 7 | | 8 |
+---+---+---+
Move: R
+---+---+---+
| 1 | 2 | 3 |
+---+---+---+
| 4 | 5 | 6 |
+---+---+---+
| 7 | 8 | |
+---+---+---+

10
 EXPERIMENT NO. 4

Program Name: Implement Hill Climbing Algorithm for numerical optimization or pathfinding.

Implementation
: import random
import math

def hill_climbing(objective_function, bounds, step_size, max_iterations):

# Initialize a random solution within the bounds
solution = [[Link](bounds[i][0], bounds[i][1]) for i in range(len(bounds))] best_solution
= solution[:]
best_fitness = objective_function(best_solution)

for _ in range(max_iterations):
# Generate a new solution by applying a small change to the current solution new_solution
= [x for x in solution]
dimension_to_change = [Link](0, len(bounds) - 1)
new_solution[dimension_to_change]+=[Link](-step_size,step_size)
new_solution[dimension_to_change] = max(bounds[dimension_to_change][0],
min(bounds[dimension_to_change][1], new_solution[dimension_to_change]))

# Evaluate the new solution

new_fitness = objective_function(new_solution)

# If the new solution is better, accept it

if new_fitness < best_fitness:
solution = new_solution
best_solution=new_solution[:]
best_fitness = new_fitness
else:
# Accept the new solution with some probability to avoid local optima if
[Link]() < [Link]((best_fitness - new_fitness) / (abs(best_fitness) + 1e-9)):
solution = new_solution

return best_solution, best_fitness

# Example objective function: minimize x^2 + y^2

def objective_function(solution): return
solution[0]**2 + solution[1]**2

bounds = [(-5, 5), (-5, 5)] # bounds for x and y

step_size = 0.1 max_iterations = 1000
best_solution, best_fitness = hill_climbing(objective_function, bounds, step_size, max_iterations)
print(f"Best solution: x = {best_solution[0]}, y = {best_solution[1]}")
print(f"Best fitness: {best_fitness}")

11
Output:
Best solution: x = -3.633010903595869, y = 0.5620945535042986
Best fitness: 13.514718512725668

12
 EXPERIMENT NO. 5

Program Name: Solve Water Jug Problem using state-space search (BFS or DFS).

Implementation: # Function to perform DFS to solve the water jug problem def
water_jug_dfs(capacity1, capacity2, target):
visited = set() # To track visited states path
= [] # To store the solution path

def dfs(jug1, jug2):

# If we have already visited this state, return False (avoid cycles)
if (jug1, jug2) in visited: return False

# Mark the state as visited

[Link]((jug1, jug2))

# Append the current state to the path

[Link]((jug1, jug2))

# If the target is achieved in either jug, return True

if jug1 == target or jug2 == target: return True

# Explore all possible transitions (DFS recursive calls)

# Fill 3-liter jug if
dfs(3, jug2):
return True #
Fill 5-liter jug if
dfs(jug1, 5):
return True #
Empty 3-liter jug if
dfs(0, jug2):
return True #
Empty 5-liter jug if
dfs(jug1, 0):
return True
# Pour water from 3-liter jug into 5-liter jug if
dfs(max(0, jug1 - (5 - jug2)), min(5, jug1 + jug2)):
return True
# Pour water from 5-liter jug into 3-liter jug if
dfs(min(3, jug1 + jug2), max(0, jug2 - (3 - jug1))):
return True

# If none of the transitions lead to the goal, backtrack [Link]()

return False

13
 # Start DFS from the initial state (0, 0) dfs(0,
0)

# If we found a solution, return the path

return path

# Example Usage
capacity1 = 3 # Capacity of the 3-liter jug capacity2 =
5 # Capacity of the 5-liter jug target = 4 # Target
amount to measure solution =
water_jug_dfs(capacity1, capacity2, target)

if solution:
print("Solution steps:") for
step in solution:
print(step)
else:
print("No solution found.")

import [Link] as plt import

networkx as nx

# Function to create and visualize the state space transitions for DFS
def visualize_dfs_solution(solution): G = [Link]()

# Add the nodes and edges based on the DFS solution path for
i in range(len(solution) - 1):
G.add_edge(solution[i], solution[i + 1])

pos = nx.spring_layout(G) # Position the nodes for visualization [Link](figsize=(8,

6))

# Draw the graph with nodes and labels

[Link](G, pos, with_labels=True, node_color='lightgreen', node_size=1500, font_size=12,
font_weight='bold') nx.draw_networkx_edges(G, pos, edgelist=list([Link]()),
edge_color='blue', width=2)

[Link]("Water Jug Problem - DFS Solution Path") [Link]()

# Visualize the DFS solution if
solution:
visualize_dfs_solution(solutio
n)

14
Output:

15
 EXPERIMENT NO. 6
Program Name: Build a simple text classifier using NLTK (e.g., classify messages as spam/ham).

Implementation:
import nltk
from [Link] import names
from [Link] import NaiveBayesClassifier
from [Link] import accuracy import
random

# Download NLTK resources (only first time) [Link]('punkt')

# Sample dataset (spam/ham)

data = [
("Win money now!!!", "spam"),
("Congratulations, you won a free lottery ticket", "spam"),
("Call this number to claim your prize", "spam"),
("Hi, are we still meeting tomorrow?", "ham"), ("Don't
forget to bring the documents", "ham"),
("See you at the office", "ham"),
("Reminder: your bill is due tomorrow", "ham"),
("Exclusive deal just for you!!!", "spam")
]

# Feature extraction function def

extract_features(text):
words = nltk.word_tokenize([Link]()) return
{word: True for word in words}

# Apply feature extraction

featuresets = [(extract_features(msg), label) for (msg, label) in data]

#Train/testsplit
[Link](featuresets) train_size
= int(len(featuresets) * 0.75)
train_set, test_set = featuresets[:train_size], featuresets[train_size:]

# Train Naive Bayes classifier

classifier = [Link](train_set)

# Evaluate
print("Accuracy:", accuracy(classifier, test_set))
print("\nMostinformativefeatures:")
classifier.show_most_informative_features(5)
# Try on new messages tests
=[

16
 "Congratulations, you have won a car!!!",
"Are you coming to the meeting?",
"Reminder: Pay your electricity bill"
]

for msg in tests:

label = [Link](extract_features(msg)) print(f"Message:
{msg} -> {label}")

Output:
Accuracy: 0.75
Most informative features:
!! = True spam : ham = 2.3 : 1.0 free = True
spam : ham = 2.1 : 1.0 congratulations = True
spam : ham = 2.0 : 1.0 bill = True ham : spam
= 1.9 : 1.0

Message: Congratulations, you have won a car!!! -> spam

Message: Are you coming to the meeting? -> ham
Message: Reminder: Pay your electricity bill -> ham

17
 EXPERIMENT NO. 7

Program Name: Study of PROLOG

Implementation:

Facts, Rules and Queries

Symbols
Prolog expressions are comprised of the following truth-functional symbols, which have the same
interpretation as in the predicate calculus.
English Predicate Calculus PROLOG
and ^ ,
or v ;
if --> :-
not ~ not
Variables and Names
Variables begin with an uppercase letter. Predicate names, function names, and the names for objects
must begin with a lowercase letter. Rules for forming names are the same as for the predicate calculus.
mother_of
male female
greater_than
socrates Facts
A fact is a predicate expression that makes a declarative statement about the problem domain. Whenever
a variable occurs in a Prolog expression, it is assumed to be universally quantified. Note that all Prolog
sentences must end with a period.
likes(john, susie). /* John likes Susie */ likes(X, susie).
/* Everyone likes Susie */
likes(john, Y). /* John likes everybody */
likes(john, Y), likes(Y, john). /* John likes everybody and everybody likes John */
likes(john, susie); likes(john,mary). /* John likes Susie or John likes Mary */
not(likes(john,pizza)). /* John does not like pizza */ likes(john,susie) :-
likes(john,mary)./* John likes Susie if John likes Mary.
Rules
A rule is a predicate expression that uses logical implication (:-) to describe a relationship among facts.
Thus a Prolog rule takes the form
left_hand_side :- right_hand_side .
This sentence is interpreted as: left_hand_side if right_hand_side. The left_hand_side is restricted to
a single, positive, literal, which means it must consist of a positive atomic expression. It cannot be
negated and it cannot contain logical connectives.
This notation is known as a Horn clause. In Horn clause logic, the left hand side of the clause is the
conclusion, and must be a single positive literal. The right hand side contains the premises. The Horn
clause calculus is equivalent to the first-order predicate calculus.

Examples of valid rules: friends(X,Y) :- likes(X,Y),likes(Y,X). /* X and Y are friends if

they like each other */
18
hates(X,Y) :- not(likes(X,Y)). /* X hates Y if X does not like Y. */
enemies(X,Y) :- not(likes(X,Y)),not(likes(Y,X)). /* X and Y are enemies if they don't like each other */
parent_of(X,Y) :- father_of(X,Y). /* Rule #1 */ parent_of(X,Y) :- mother_of(X,Y). /* Rule
#2 */

Examples of invalid rules:

left_of(X,Y) :- right_of(Y,X) /* Missing a period */
likes(X,Y),likes(Y,X) :- friends(X,Y). /* LHS is not a single literal */ not(likes(X,Y))
:- hates(X,Y). /* LHS cannot be negated */

Queries
The Prolog interpreter responds to queries about the facts and rules represented in its database. The
database is assumed to represent what is true about a particular problem domain. In making a query
you are asking Prolog whether it can prove that your query is true. If so, it answers "yes" and displays
any variable bindings that it made in coming up with the answer. If it fails to prove the query true, it
answers "No".

Whenever you run the Prolog interpreter, it will prompt you with ?-. For example, suppose our
database consists of the following facts about a fictitious family. father_of(joe,paul).
father_of(joe,mary). mother_of(jane,paul). mother_of(jane,mary).
male(paul).
male(joe).
female(mary).
female(jane).

We get the following results when we make queries about this database.
?- ['[Link]'].

?- listing.

mother_of(jane, paul).
mother_of(jane, mary).

male(paul).
male(joe).

female(mary).
female(jane).

father_of(joe, paul).
father_of(joe, mary).

(10 ms) yes

| ?- father_of(joe,paul).

true ?

yes
| ?- father_of(paul,mary).

19
no
| ?- father_of(X,mary).
X = joe

yes

EXAMPLE of Facts:& Rules:

father_of(joe,paul).
father_of(joe,mary).
father_of(joe,hope).
mother_of(jane,paul).
mother_of(jane,mary).
mother_of(jane,hope).

male(paul).
male(joe).
male(ralph).
male(X) :- father_of(X,Y).

female(mary).
female(jane).
female(hope).

son_of(X,Y) :- father_of(Y,X),male(X). son_of(X,Y)

:- mother_of(Y,X),male(X).

daughter_of(X,Y) :- father_of(Y,X),female(X). daughter_of(X,Y)

:- mother_of(Y,X),female(X).

sibling_of(X,Y) :- !,father_of(Z,X),father_of(Z,Y),X\=Y. sibling_of(X,Y)

:- !,mother_of(Z,X),mother_of(Z,Y),X\=Y.
Sample: Screen Shot:
likes(ryan, britney).
likes(britney, ryan).
likes(don, josh).
dating(X, Y):- likes(X,Y), likes(Y,X).
friendship(X,Y):- likes(X,Y); likes(Y,X).

Query:
?- dating(ryan, britney). True ?-
dating(don, josh). False

20
 EXPERIMENT NO.8
Program Name: Write simple fact for following. a.
Ram likes mango.
b. Seema is a girl.
c. Bill likes Cindy.
d. Rose is red.
e. John owns gold.

Implementation:
Clauses likes(ram
,mango).
girl(seema).
red(rose).
likes(bill ,cindy).
owns(john ,gold).

Output: Goal
queries ?-
likes(ram,What).
What= mango
?-likes(Who,cindy).
Who= cindy
?-red(What).
What= rose
?-owns(Who,What).
Who= john
What= gold.

OR

FACTS/RULES/RELATION

Two person are brothers, if,

They both are male.
They have the same parent.
Now consider we have the below phrases − parent(sudip,
piyus). parent(sudip, raj). male(piyus). male(raj).
brother(X,Y) :- parent(Z,X), parent(Z,Y),male(X), male(Y)

QUERY
?brother(X,Y).
(Piyush,raj).
?parent(X,Y).
?Male(X).

21
 EXPERIMENT NO. 9
Program Name: Write a program to solve the Monkey Banana problem.

Theory:Imagine a room containing a monkey, chair and some bananas. That has been hanged from the
centre of ceiling. If the monkey is clever enough he can reach the bananas by placing the chair directly
below the bananas and climb on the chair .The problem is to prove the monkey can reach the bananas. The
monkey wants it, but cannot jump high enough from the floor. At the window of the room there is a box
that the monkey can use. The monkey can perform the following actions:- 1) Walk on the floor.
2) Climb the box.
3) Push the box around (if it is beside the box).
4) Grasp the banana if it is standing on the box directly under the banana.

Parse Tree

Implementation:
in_room(bananas). in_room(chair).
in_room(monkey). clever(monkey).
can_climb(monkey, chair).
tall(chair). can_move(monkey,
chair, bananas).
can_reach(X, Y):- clever(X),close(X, Y).
get_on(X,Y):- can_climb(X,Y).
under(Y,Z):- in_room(X),in_room(Y),in_room(Z),can_climb(X,Y,Z).
close(X,Z):-get_on(X,Y), under(Y,Z); tall(Y).
Output:
Queries:
?- can_reach(A, B).
A = monkey.
B = banana.
?- can_reach(monkey, banana).
Yes.

22
 EXPERIMENT NO. 10
Program Name: Implement 4-Queens Problem in Prolog

Implementation:

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:

?-[‘[Link]’].
True

?-queens(4,Queens).
Queens=[2,4,1,3]
Queens=[3,1,4,2]

?-queens(8,Queens).
Queens=[4,7,3,8,2,5,1,6]

23
 EXPERIMENT NO. 11
Program Name: Implement Min-Max (Minimax) Algorithm for decision making in turn-based
games.

Implementation:
def minimax(board, depth, is_max):
score = evaluate(board)
if score != 0 or depth == 0: return score

moves = [(i,j) for i in range(3) for j in range(3) if board[i][j] == ' '] if

not moves: return 0

if is_max:
best = -1000 for i,
j in moves:
board[i][j] = 'X'
best = max(best, minimax(board, depth-1, False)) board[i][j]
=''
return best
else:
best = 1000 for i,
j in moves:
board[i][j] = 'O'
best = min(best, minimax(board, depth-1, True)) board[i][j]
=''
return best

def evaluate(board): #
Check winner
for i in range(3):
if board[i][0] == board[i][1] == board[i][2] == 'X': return 10
if board[i][0] == board[i][1] == board[i][2] == 'O': return -10
if board[0][i] == board[1][i] == board[2][i] == 'X': return 10
if board[0][i] == board[1][i] == board[2][i] == 'O': return -10
if board[0][0] == board[1][1] == board[2][2] == 'X': return 10
if board[0][0] == board[1][1] == board[2][2] == 'O': return -10
if board[0][2] == board[1][1] == board[2][0] == 'X': return 10
if board[0][2] == board[1][1] == board[2][0] == 'O': return -10
return 0

def find_best_move(board):
best_val, best_move = -1000, None
for i in range(3): for j in range(3):
if board[i][j] == ' ': board[i][j]
= 'X'
move_val = minimax(board, 9, False)
board[i][j] = ' ' if move_val >
best_val:
24
 best_val, best_move = move_val, (i, j)
return best_move, best_val

# Test board = [[' ']*3 for _ in

range(3)] print("Empty board:")
for row in board: print(row)

move, score = find_best_move(board)

print(f"\nBest move: {move}")
print(f"Score: {score}")

board[move[0]][move[1]] = 'X' print("\nAfter

move:")
for row in board: print(row)

Output:
Empty board:
[' ', ' ', ' ']
[' ', ' ', ' ']
[' ', ' ', ' ']

Best move: (0, 0)

Score: 0

After move:
['X', ' ', ' ']
[' ', ' ', ' ']
[' ', ' ', ' ']

25
 EXPERIMENT NO. 12
Program Name: Implement Tic-Tac-Toe game with a basic AI opponent.

Implementation:
def print_board(board):
for i, row in enumerate(board):
print(f"{' | '.join(row)}") if i
< 2: print(" --------- ")

def check_winner(board): # Check

rows, columns, diagonals for i in
range(3):
if board[i][0] == board[i][1] == board[i][2] != ' ': return board[i][0]
if board[0][i] == board[1][i] == board[2][i] != ' ': return board[0][i]
if board[0][0] == board[1][1] == board[2][2] != ' ': return board[0][0]
if board[0][2] == board[1][1] == board[2][0] != ' ': return board[0][2] return
None

def minimax(board, is_ai_turn): winner =

check_winner(board) if winner == 'O':
return 1 # AI wins if winner == 'X': return
-1 # Human wins
if all(board[i][j] != ' ' for i in range(3) for j in range(3)): return 0 # Draw

if is_ai_turn: best
= -2 for i in
range(3):
for j in range(3):
if board[i][j] == ' ': board[i][j]
= 'O'
best = max(best, minimax(board, False))
board[i][j] = ' '
return best
else:
best = 2 for i in
range(3):
for j in range(3):
if board[i][j] == ' ': board[i][j]
= 'X'
best = min(best, minimax(board, True))
board[i][j] = ' '
return best

def ai_move(board): best_score,

best_move = -2, None for i in
range(3):
for j in range(3):

26
 if board[i][j] == ' ':
board[i][j] = 'O' score =
minimax(board, False)
board[i][j] = ' ' if score >
best_score:
best_score, best_move = score, (i, j)
return best_move

def play_game():
board = [[' ']*3 for _ in range(3)]
print("Tic-Tac-Toe: You=X, AI=O")
print("Enter row,col (0-2): ")

while True:
print_board(board)

# Human move
try:
r, c = map(int, input("Your move: ").split(',')) if
board[r][c] != ' ':
print("Occupied!"); continue
board[r][c] = 'X'
except:
print("Invalid!"); continue

if check_winner(board) or all(board[i][j] != ' ' for i in range(3) for j in range(3)):

break

# AI move move =
ai_move(board) if move:
board[move[0]][move[1]] = 'O'
print(f"AI plays: {move}")

if check_winner(board) or all(board[i][j] != ' ' for i in range(3) for j in range(3)):

break

print_board(board) winner =
check_winner(board) if winner ==
'X': print("You win!") elif winner
== 'O': print("AI wins!") else:
print("Draw!")

# Run game
play_game()

Output:
Tic-Tac-Toe: You=X, AI=O Enter
row,col (0-2):
| |

27
 | |

| |
Your move: 1,1
| |

|X|

| |
AI plays: (0, 0)
O||

|X|

| |
Your move: 0,1
O|X|

|X|

| |
AI plays: (2, 1)
O|X|

|X|

|O|
AI wins!

28