I.

AO* (And-Or Star) Algorithm in Artificial Intelligence

 The AO* algorithm is a search algorithm used to find an optimal solution
in AND-OR graphs.

 It is an extension of the A* algorithm designed for problem-solving in

hierarchical or decomposable tasks, where problems can be divided
into subproblems.
(Problem Reduction in AI)
 The divide and conquer strategy,

a solution to a problem  decomposing it into

smaller sub-problems.

sub-problem  to find get its sub-solution.

  Finally recombined to get a solution.

 That is called Problem Reduction. This method generates arc which is

called as AND arcs.

 One AND arc may point to any number of successor nodes, all of which

must be solved for an arc to point to a solution.

Example: Sorting a large list of numbers can be done by dividing the list,

sorting smaller parts, and then merging them.

Example: To clean a room, AI might set subgoals like “pick up toys,” “dust

surfaces,” and “vacuum floor.”

Problem Reduction algorithm

1. Initialize the graph to the starting node.

2. Loop until the starting node is labelled SOLVED or until its cost goes

above FUTILITY:

Benefits:

1. Faster problem-solving

2. Better handling of complex issues

3. More efficient use of resources

4. Improved AI learning and adaptation

II. Game Playing in AI- Adversarial Search

Adversarial search algorithms are the backbone of strategic decision-making in

artificial intelligence; it enables the agents to navigate competitive scenarios

effectively.

Role of Adversarial Search in AI

 Game-playing: The Adversarial search finds a significant application

in game-playing scenarios, including renowned games like chess, Go, and

poker.
  The adversarial search offers the simplified nature of these games that

represents the state of a game in a straightforward approach and the

agents are limited to a small number of actions whose effects are

governed by precise rules.

 Decision-making:

 Decision-making plays a central role in adversarial search

algorithms, where the goal is to find the best possible move or

strategy for a player in a competitive environment against one or

more components.

 This requires strategic thinking, evaluation of potential

outcomes, and adaptive decision-making throughout the game.

III. Minimax algorithm

The Minimax algorithm is claimed to be a recursive or backtracking

algorithm that is responsible for choosing the best optimal move in the

conflicting environment.

Back Tracking Algorithm

Key terminologies in the Minimax algorithm

 Minimax Tree: A tree structure  all possible moves

used by Minimax to find the best move.

 Max Winning

 MAX (Maximizer) - Maximizer seeks favorable outcomes in games by

maximizing chances of winning for themselves as players.

 Min effort

 MIN (Minimizer) - Minimizer reduces winning chances, making

moves leading to least favorable outcome for the Maximizer in games.

 Initial state - Starting state of game board, representing the configuration

at the beginning of the game.

  Terminal state -Terminal states are the final outcomes of a game board,

resulting in either a win, loss, or draw.

 Heuristic Evaluation Function: Function evaluates game states for

maximizer, assigning numerical values to each game state based on piece

positions, material advantage, and board control.

IV. Problems in game playing

1. Limited scope: The techniques and algorithms developed for game

playing may not be well-suited for other types of applications and may

need to be adapted or modified for different domains.

 2. Computational cost: Game playing can be computationally expensive,

especially for complex games such as chess or Go, and may require

powerful computers to achieve real-time performance.

V. Alpha-Beta Pruning

 Alpha-beta pruning is an optimization technique for the minimax

algorithm.
  Alpha-Beta Pruning is an optimization technique for the

Minimax algorithm used in game-playing AI (like chess, tic-tac-

toe, etc.).

 It reduces the number of nodes evaluated in the search tree by

eliminating branches that cannot possibly affect the final

decision.

🧠 Key Idea

While exploring the game tree:

 Alpha (α) → the best (highest) value that the maximizer can guarantee

so far.

 Beta (β) → the best (lowest) value that the minimizer can guarantee so

far.

If at any point α ≥ β, we can prune (cut off) that branch — no need to explore

it further because it won’t affect the final decision.

Algorithm Steps

1. Start with the root node and initialize α = -∞, β = +∞.

2. Apply the Minimax algorithm recursively.

3. For each node:

o If it’s a Max node, update α = max(α, value).

 o If it’s a Min node, update β = min(β, value).

4. If at any time α ≥ β, stop exploring that branch (prune).

A (MAX)

/ \

B(MIN) C (MIN)

/ \ / \

3 5 2 9

Step-by-step:

 Start at A (MAX), α = -∞, β = +∞

 Go to B (MIN):

o Explore 3 → β = 3

o Explore 5 → β = min(3, 5) = 3

→ B returns 3 to A

 Update α = max(-∞, 3) = 3

Now go to C (MIN):

 First child = 2 → β = 2

Since 2 < α (3) → prune the rest of C’s children!

(No need to check 9 because MAX would never choose this branch)
✅ Final result: Best value for MAX = 3

 Reduces computation time.

 Doesn’t affect the correctness of the Minimax result.

 Makes AI decisions faster.

Applications

 Chess

 Checkers

 Tic-tac-toe

 Any two-player zero-sum game