EXPERIMENT NO : 7

Aim : Write a program using Python for solving A* search algorithm

Theory:
A* Algorithm :
The A* (A-star) algorithm is a widely used pathfinding algorithm in the field of
artificial intelligence and computer science. It is an informed search algorithm that
finds the shortest path between a given start node and a target node (or goal) in a
weighted graph. A* uses a heuristic to guide its search, making it more efficient than
uninformed search algorithms like Dijkstra's algorithm, especially in scenarios with
large search spaces.
1. Graph Representation: A* operates on a graph composed of nodes connected
by edges. Each node represents a state or a point in the search space, and
each edge represents a transition or a path between states. Each edge has a
non-negative cost associated with it.
2. Cost Function: A* uses a cost function f(n) to evaluate the cost of reaching a
particular node in the graph. It is defined as the sum of two components:
g(n) the cost of the path from the start node to node (n). h(n) the heuristic estimate
of the cost from node n to the goal node.
3. Heuristic Function: A* relies on a heuristic function h(n) to estimate the cost of
reaching the goal from a given node n . This heuristic function should be admissible,
meaning it should never overestimate the cost to reach the goal. In other words, h(n)
should always be less than or equal to the actual cost to reach the goal from node
(n).
4. Termination: The algorithm terminates when the goal node is reached or when the
open list becomes empty, indicating that there is no path from the start node to the
goal node.
5. Optimality: A* is optimal if the heuristic function is admissible, meaning it never
overestimates the true cost to reach the goal. In this case, A* will always find the
shortest path from the start node to the goal node.

ALGORITHM:
- Initialize two lists: an open list and a closed list.
- Add the start node to the open list.
- While the open list is not empty:
- Select the node with the lowest f(n) value from the open list. Let's call this node
( current ).
- If (current) is the goal node, then a solution has been found. Terminate.
- Move (current) from the open list to the closed list.
- Expand (current) by considering all its neighbouring nodes.
- For each neighbouring node (neighbour):
- If (neighbour) is not in the closed list and not blocked:
 - Calculate g(neighbour) as (g(current) + cost(current, neighbour)).
- If (neighbour) is not in the open list:
- Add (neighbour) to the open list.
- Set g(neighbour) and h(neighbour).
- If ( neighbour) is already in the open list and the new g(neighbour) is lower than the
previous one:
- Update g(neighbour) and h(neighbour).

SOLVED EXAMPLE :

The numbers written on edges represent the distance between the nodes. The numbers
written on nodes represent the heuristic value. Find the most cost-effective path to reach
from start state A to final state I using A* Algorithm.

Solution:

● Step 1:
We start with node A. Node B and Node F can be reached from node A.
A* Algorithm calculates f(B) and f(F).
f(B) = 6 + 8 = 14
f(F) = 3 + 6 = 9
Since f(F) < f(B), it decides to go to node F.
Path- A → F

● Step 2:
Node G and Node H can be reached from node F.
A* Algorithm calculates f(G) and f(H).
f(G) = (3+1) + 5 = 9
f(H) = (3+7) + 3 = 13
Since f(G) < f(H), it decides to go to node G.
Path- A → F → G

● Step 3:
 Node I can be reached from node G. A* Algorithm calculates f(I).
f(I) = (3+1+3) + 1 = 8
Path- A → F → G → I

This is the required shortest path from node A to node J.

FEATURES:

Sure, here are the key features of the A* algorithm summarized in very short points
for practical application:
1. Completeness: A* guarantees finding a solution if one exists, assuming a finite
graph without infinite loops.
2. Optimality: It finds the shortest path with an admissible heuristic function.
3. Heuristic Guidance: A* prioritizes promising paths using heuristic estimates.
4. Efficiency: It's more efficient than uninformed algorithms, particularly in large
search spaces.
5.Adaptability: A* can be tailored to different domains by choosing appropriate
heuristics.
6. Memory Usage: It maintains open and closed lists for exploration, with
manageable memory requirements.
7.Complexity: Time complexity varies but is generally efficient, especially with
consistent heuristics.

CODE AND OUTPUT: Attached behind

CONCLUSION:Thus, we have implemented a program to solve the A* search

algorithm in Python.In conclusion, implementing the A* algorithm for an AI lab
practical offers valuable hands-on experience with a versatile and efficient
pathfinding technique. Through this practical, students gain insight into essential AI
concepts such as heuristic search, optimality, and adaptability. The A* algorithm's
completeness and efficiency make it a valuable tool for solving real-world problems
in various domains, including robotics, gaming, and navigation systems. This
practical provides students with a solid foundation for understanding and applying
advanced AI algorithms in diverse scenarios.
 EXPERIMENT NO : 8

AIM: Write a program using Python for Tic Tac Toe problem

THEORY :
1. Objective: The goal is to create an AI player that competes against a human player in a
game of Tic Tac Toe.
2. Game Overview: Tic Tac Toe is a two-player game played on a 3x3 grid. Players take
turns marking Xs and Os in empty cells with the aim of getting three of their symbols in a
row, column, or diagonal.
3. Game State Representation: The game state can be represented using a 3x3 grid where
empty cells are represented by ' ', Xs by 'X', and Os by 'O'. Alternatively, it can be
represented using a numerical board where each cell is numbered from 1 to 9.
4. Game Tree: The game tree represents all possible moves and outcomes starting from the
initial state. For Tic Tac Toe, the branching factor reduces with each move due to the limited
grid size.
5. Minimax Algorithm: Minimax is a decision-making algorithm used to determine the best
move for the AI player. It alternates between maximising its own score and minimising the
opponent's score, assuming the opponent plays optimally.
6. Evaluation Function: An evaluation function assigns a score to each game state,
indicating the desirability of that state for the AI player. In Tic Tac Toe, the evaluation function
can be simple, assigning scores based on winning, losing, or drawing.
7. Alpha-Beta Pruning: Alpha-Beta pruning is an optimization technique used to reduce the
number of nodes evaluated by the Minimax algorithm. It eliminates branches that are
guaranteed to be worse than previously examined branches.
8. Heuristic: In addition to Minimax, heuristics can be employed to improve AI performance.
Heuristics provide rules or strategies to guide the AI's decision-making process, such as
prioritising winning moves or blocking the opponent from winning.
9.Game Loop: The game loop manages player turns, allowing the AI player to make
decisions based on the current game state and the chosen strategy.
10.Testing and Iteration: After implementation, the AI player should be tested against human
players to evaluate its performance and identify areas for improvement. Iterative refinement
may involve adjusting the evaluation function, heuristics, or optimization techniques to
enhance AI gameplay.
By understanding these key points, students can implement a functional AI player for Tic Tac
Toe, gaining practical experience in AI algorithms and game development.

MINIMAX ALGORITHM WITH ALPHA-BETA PRUNING FOR TIC TAC TOE:

● To develop a program for Tic Tac Toe, the Minimax algorithm, enhanced with
Alpha-Beta pruning, is employed.
● This algorithm aims to determine the optimal move for the AI player by recursively
exploring the game tree while efficiently pruning branches that are unlikely to lead to
the best outcome.
● The steps involved in the process are:
1. Initialization of alpha as negative infinity and beta as positive infinity.
 2. Minimax Function evaluates each possible move by exploring the game tree
to a certain depth and returns the best score found.
3. Integrate Alpha-Beta pruning into the Minimax function to reduce
unnecessary exploration of branches in the game tree.
4. In Tic Tac Toe, evaluation is done based on scores. Positive scores could
indicate positions favorable to the AI, negative scores positions favorable to
the opponent, and zero scores represent draws.
5. After exploring the game tree to a certain depth, select the move that leads to
the highest evaluated score for the AI. This move represents the optimal
choice based on the Minimax algorithm's evaluation of possible outcomes.

TIC TAC TOE GAME TREE:

CODE AND OUTPUT: Attached behind

CONCLUSION: Thus, we have implemented a program to solve the Tic Tac Toe
game in Python.In conclusion, implementing the Minimax algorithm with Alpha-Beta
Pruning for Tic Tac Toe in an AI practical provides valuable hands-on experience in
developing an optimal AI player for a classic game. This approach enables the AI to
make intelligent decisions while efficiently exploring the game tree, leading to
improved performance and gameplay. By understanding and implementing this
algorithm, students gain insights into advanced AI techniques and their application
in strategic decision-making scenarios.
 EXPERIMENT NO : 9

Aim : Write A program using Python to solve the N-QUEEN Problem.

THEORY :
1. Objective: The goal is to place N queens on an N×N chessboard in such a way that
no two queens threaten each other.
2. Problem Representation: The problem can be represented as placing N queens on
an N×N chessboard, where each queen occupies a unique row and column.
3. Constraint Satisfaction Problem (CSP): The N-Queen problem is a CSP where each
queen must satisfy the constraint of not being able to attack any other queen
horizontally, vertically, or diagonally.
4. State Space: The state space consists of all possible configurations of queen
placements on the board.
5. Search Algorithms: Various search algorithms can be used to solve the N-Queen
problem, including backtracking, genetic algorithms, and constraint satisfaction
algorithms.
6.Backtracking: Backtracking is a common technique used to systematically search
through the state space by trying different configurations and backtracking when a
constraint is violated.
7.Constraint Satisfaction Algorithms: These algorithms aim to find solutions that
satisfy all constraints. They typically use techniques such as constraint propagation
and backtracking to efficiently search the solution space.
8.Heuristic Search: Heuristic search algorithms can be applied to the N-Queen
problem to guide the search process towards promising solutions. Heuristics can be
based on the number of conflicts or the number of queens placed so far.
9.Optimization: In addition to finding any solution, optimization techniques can be
employed to find the best or optimal solution, such as minimising the number of
conflicts or maximising the number of queens placed.
10. Evaluation and Testing: After implementation, the solution can be evaluated by
testing it against different board sizes and comparing the performance of different
algorithms. The effectiveness of the solution can be measured based on factors
such as runtime, memory usage, and solution quality.

ALGORITHM :
1. Initialize: Start with an empty N×N chessboard.
2. Place Queen: Begin with the first row and try placing a queen in each
column of that row.
3. IsSafe Function: Before placing a queen in a particular position, check if it is
safe from attacks by previously placed queens. Implement a function to check if
there are no queens in the same row, column, or diagonal as the current position.
4. Backtrack: If placing the queen violates any constraints, backtrack to the
previous row and try placing the queen in the next column.
5.Recursion: Recursively repeat steps 2-4 for each row until all queens are
placed on the board.
6.Solution Found: If all N queens are successfully placed on the board without
violating any constraints, a solution is found.
7.Multiple Solutions: Backtrack to find all possible solutions by exploring
different combinations of queen placements.

GAME TREE:

CODE AND OUTPUT: Attached behind

CONCLUSION: Thus, we have implemented a program to solve the N-QUEEN

problem in Python.In conclusion, implementing the N-Queen problem in an AI
practical offers valuable hands-on experience in solving constraint satisfaction
problems using backtracking algorithms. By exploring different strategies to
efficiently place queens on a chessboard without attacking each other, students gain
insight into problem-solving techniques and algorithmic optimization. This practical
exercise enhances understanding of search algorithms, recursion, and constraint
satisfaction, providing a solid foundation for tackling complex real-world problems in
artificial intelligence and computer science. Overall, the N-Queen problem serves as
an engaging and instructive exercise to reinforce key concepts in AI and
computational problem-solving.
 EXPERIMENT NO : 10

Aim: To create a Chatbot

Code : Code is attached behind

Conclusion : Hence we have created the Chatbot in google colab.