Module-3

Local Search and Adversarial

Search
[Link],
Asst Prof, SCOPE, VIT-Chennai.

[Link], AsstProf/SCOPE, VIT-Chennai.

[Link], AsstProf/SCOPE, VIT-Chennai.
Local Search and optimization

[Link], AsstProf/SCOPE, VIT-Chennai.

[Link], AsstProf/SCOPE, VIT-Chennai.
Example: n-Queens

[Link], AsstProf/SCOPE, VIT-Chennai.

[Link], AsstProf/SCOPE, VIT-Chennai.
[Link], AsstProf/SCOPE, VIT-Chennai.
[Link], AsstProf/SCOPE, VIT-Chennai.
Hill Climbing Search Algorithm

[Link], AsstProf/SCOPE, VIT-Chennai.

[Link], AsstProf/SCOPE, VIT-Chennai.
Algorithm(max version)

[Link], AsstProf/SCOPE, VIT-Chennai.

Regions in the search space:

[Link], AsstProf/SCOPE, VIT-Chennai.

[Link], AsstProf/SCOPE, VIT-Chennai.
Sideway Moves

[Link], AsstProf/SCOPE, VIT-Chennai.

[Link], AsstProf/SCOPE, VIT-Chennai.
Enforced Hill Climbing: Escaping Shoulders/Local
Optima

[Link], AsstProf/SCOPE, VIT-Chennai.

[Link], AsstProf/SCOPE, VIT-Chennai.
Hill Climing: Stochastic Variations

• Combines hill climbing with random walk or random sampling to get a

hybrid approach which has both the greedy approach of searching
the optimal state along with the algorithm being asymptotically
complete.

[Link], AsstProf/SCOPE, VIT-Chennai.

[Link], AsstProf/SCOPE, VIT-Chennai.
[Link], AsstProf/SCOPE, VIT-Chennai.
[Link], AsstProf/SCOPE, VIT-Chennai.
Simulated Annealing

[Link], AsstProf/SCOPE, VIT-Chennai.

[Link], AsstProf/SCOPE, VIT-Chennai.
[Link], AsstProf/SCOPE, VIT-Chennai.
[Link], AsstProf/SCOPE, VIT-Chennai.
[Link], AsstProf/SCOPE, VIT-Chennai.
Example

[Link], AsstProf/SCOPE, VIT-Chennai.

Required:

1. Initial Point:

2. Number of iteration at one Temperature (or the inner loop terminating

condition):

3. Algorithm termination condition:

4. Initial temperature:

[Link], AsstProf/SCOPE, VIT-Chennai.

 Initial state- 10011, ‘E’ value= f(19)= 2399

ΔE
Temperature Inner Current E ΔE 𝑒𝑇 Random Move Next
loop State ‘r’ value State
iteration

500 1 00011 2287 -112 0.8 0.5 Yes 00111

450 1 00111 3803 1516 - - Yes 00110
405 1 00110 3556 -247 0.543 0.5 Yes 01110
364.5 1 01110 3684 118 - - Yes 01100
328 1 01100 3998 314 - - Yes 01000
295.2 1 01000 3972 -26 0.915 0.7 Yes 01010
265.7 1 01010 4100 128 - - Yes 01011
239.1 1 01011 4071 -29 0.88 0.7 Yes 11011
215.2 1 11011 343 -3728 0
[Link], AsstProf/SCOPE, VIT-Chennai.
0.5 No -
Local Beam Search

[Link], AsstProf/SCOPE, VIT-Chennai.

[Link], AsstProf/SCOPE, VIT-Chennai.
Genetic Algorithm

[Link], AsstProf/SCOPE, VIT-Chennai.

8-Queen String representation

[Link], AsstProf/SCOPE, VIT-Chennai.

[Link], AsstProf/SCOPE, VIT-Chennai.
[Link], AsstProf/SCOPE, VIT-Chennai.
Summary of Genetic Algorithm

[Link], AsstProf/SCOPE, VIT-Chennai.

Steps involved in Genetic Algorithms

[Link], AsstProf/SCOPE, VIT-Chennai.

Example

[Link], AsstProf/SCOPE, VIT-Chennai.

[Link], AsstProf/SCOPE, VIT-Chennai.
[Link], AsstProf/SCOPE, VIT-Chennai.
[Link], AsstProf/SCOPE, VIT-Chennai.
[Link], AsstProf/SCOPE, VIT-Chennai.
[Link], AsstProf/SCOPE, VIT-Chennai.
[Link], AsstProf/SCOPE, VIT-Chennai.
Adversarial Search
• Relaxation of Single Agent assumption.
• Game Playing

[Link], AsstProf/SCOPE, VIT-Chennai.

Game Characteristics

[Link], AsstProf/SCOPE, VIT-Chennai.

[Link], AsstProf/SCOPE, VIT-Chennai.
[Link], AsstProf/SCOPE, VIT-Chennai.
[Link], AsstProf/SCOPE, VIT-Chennai.
[Link], AsstProf/SCOPE, VIT-Chennai.
[Link], AsstProf/SCOPE, VIT-Chennai.
[Link], AsstProf/SCOPE, VIT-Chennai.
[Link], AsstProf/SCOPE, VIT-Chennai.
[Link], AsstProf/SCOPE, VIT-Chennai.
[Link], AsstProf/SCOPE, VIT-Chennai.
[Link], AsstProf/SCOPE, VIT-Chennai.
[Link], AsstProf/SCOPE, VIT-Chennai.
[Link], AsstProf/SCOPE, VIT-Chennai.
Alpha-Beta Pruning-
•Alpha-beta pruning is a modified version of the minimax algorithm. It is an
optimization technique for the minimax algorithm.

[Link], AsstProf/SCOPE, VIT-Chennai.

• This involves two threshold parameter Alpha and beta for future expansion.
• The two-parameter can be defined as:
• Alpha: The best (highest-value) choice we have found so far at any point along
the path of Maximizer. The initial value of alpha is -∞.
• Beta: The best (lowest-value) choice we have found so far at any point along the
path of Minimizer. The initial value of beta is +∞.
• The condition for Alpha-beta Pruning is that α >= β.
• The alpha and beta values of each node must be kept track of. Alpha can only be
updated when it’s MAX’s time, and beta can only be updated when it’s MIN’s turn.
• MAX will update only alpha values and the MIN player will update only beta values.
• The node values will be passed to upper nodes instead of alpha and beta values
during going into the tree’s reverse.
• Alpha and Beta values only are passed to child nodes.

[Link], AsstProf/SCOPE, VIT-Chennai.

Working of Alpha-Beta pruning

[Link], AsstProf/SCOPE, VIT-Chennai.

[Link], AsstProf/SCOPE, VIT-Chennai.
[Link], AsstProf/SCOPE, VIT-Chennai.
[Link], AsstProf/SCOPE, VIT-Chennai.
[Link], AsstProf/SCOPE, VIT-Chennai.
[Link], AsstProf/SCOPE, VIT-Chennai.
Time Complexity
• Worst ordering:
• Does not prune any of the leaves of the tree, and works exactly as
minimax algorithm.
• It consumes more time. as the best move occurs on the right side of the
tree.
• The time complexity for such an order is O(bm).
• Ideal ordering:
• The best moves occur at the left side of the tree.
• We apply DFS hence it first search left of the tree and go deep twice as
minimax algorithm in the same amount of time.
• Complexity in ideal ordering is O(bm/2).
[Link], AsstProf/SCOPE, VIT-Chennai.