Scribd
Upload
160 views4 pages

Adversarial Search Notes

Adversarial Search is a technique used in AI for multi-agent environments, particularly in two-player games, where opponents aim to maximize their gain while minimizing their opponent's. The Minimax algorithm is a key decision-making tool in these scenarios, assuming optimal play from both players, while Alpha-Beta Pruning optimizes the Minimax process by eliminating branches that won't affect the final decision. The document includes examples illustrating the application of these algorithms in game trees.

Uploaded by

prashant kumar
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
160 views4 pages

Adversarial Search Notes

Adversarial Search is a technique used in AI for multi-agent environments, particularly in two-player games, where opponents aim to maximize their gain while minimizing their opponent's. The Minimax algorithm is a key decision-making tool in these scenarios, assuming optimal play from both players, while Alpha-Beta Pruning optimizes the Minimax process by eliminating branches that won't affect the final decision. The document includes examples illustrating the application of these algorithms in game trees.

Uploaded by

prashant kumar
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 4

Adversarial Search in AI - Detailed Notes

1. Introduction to Adversarial Search

Adversarial Search is used in multi-agent environments, particularly in two-player games like chess or

tic-tac-toe.

It models situations where opponents work against each other to maximize their gain while minimizing their

opponent's.

2. Game Formalization

A game in AI is defined by:

- Initial State

- Player(s)

- Actions(s)

- Result(s, a)

- Terminal Test(s)

- Utility(s, p)

Games can be zero-sum (one player's gain is another's loss), deterministic, and have perfect or imperfect

information.

3. Minimax Algorithm

The Minimax algorithm is a decision-making algorithm used in two-player zero-sum games. It assumes that

both players play optimally.

- MAX: Tries to maximize the score.

- MIN: Tries to minimize the score.

The algorithm performs a depth-first search of the game tree.


Adversarial Search in AI - Detailed Notes

Example 1 (3-layer Tree):

[A]

/ \

[B] [C]

/ \ / \

[D] [E] [F] [G]

/\ /\ /\ /\

3 5 6 9 1 2 0 -1

- B returns min(3,5)=3; E returns min(6,9)=6 => B=min(3,6)=3

- C returns min(1,2)=1; G returns min(0,-1)=-1 => C=min(1,-1)=-1

- A = max(3, -1) = 3 => MAX chooses move B

Example 2 (5-layer Tree):

[A]

/ \

[B] [C]

/ \ / \

[D] [E] [F] [G]

/\ /\ /\ /\

2 5 6 9 1 4 0 -1

- D = min(2,5) = 2, E = min(6,9) = 6 => B = max(2,6) = 6

- F = min(1,4) = 1, G = min(0,-1) = -1 => C = max(1,-1) = 1

- A = min(6,1) = 1 => MIN would prefer the state leading to C

4. Alpha-Beta Pruning

Alpha-Beta Pruning is an optimization over Minimax. It avoids exploring parts of the tree that won't affect the
Adversarial Search in AI - Detailed Notes

final decision.

- Alpha: Best value for MAX along the path.

- Beta: Best value for MIN along the path.

Prune if beta <= alpha.

Example 1 (Same as above):

[A]

/ \

[B] [C]

/ \ / \

[D] [E] [F] [G]

/\ /\ /\ /\

3 5 6 9 1 2 0 -1

- B = min(3,5)=3, E= min(6,9)=6 => B = max(3,6)=6 => alpha=6

- F = min(1,2)=1 => beta = 1 < alpha (6), so prune G

- A = min(6,1) => MIN chooses path to C = value 1

Example 2 (5-layer tree with pruning):

[A]

/ \

[B] [C]

/ \ / \

[D] [E] [F] [G]

/\ /\ /\ /\

10 8 6 9 1 4 0 -1

- D = min(10,8)=8, E = min(6,9)=6 => B = max(8,6)=8

- F = min(1,4)=1, G = min(0,-1)=-1 => C = max(1,-1)=1


Adversarial Search in AI - Detailed Notes

- A = min(8,1)=1 => MIN chooses C

Pruning: Once F returns 1 and alpha from B=8, no need to check G since beta=1 < alpha=8

You might also like