CSE3013 - "Artificial Intelligence"

Problem Solving(Heuristic) - Adversarial Search

Dr. Pradeep K V
Assistant Professor (Sr.)
School of Computer Science and Engineering
VIT - Chennai

Dr. Pradeep K V CSE3013 - "Artificial Intelligence" 1/ 30

Introduction...!

In the game-playing approach known as adversarial search, the agents are

surrounded by other agents/players. The agents are given a competing goal
(multiagent).

To win the game, these agents engage in competition and attempt to defeat
one another. The adversarial search is a result of such opposing objectives.

Here, game-playing means discussing those games where human intelligence

and logic factor is used, excluding other factors such as luck factor.

Tic-tac-toe, chess, checkers, etc., are such type of games where no luck
factor works, only mind works.

This search is based on the concept of ‘Game Theory’. Where, a game is

played between two players. To complete the game, one has to win the game
and the other looses automatically.

Note : Games are modeled as a Search problem and heuristic evaluation

function, and these are the two main factors which help to model and solve
games in AI.

Dr. Pradeep K V CSE3013 - "Artificial Intelligence" 2/ 30

Importance of Adversarial Search

This algorithm is one of the most favorites in AI arena, and it provides

solutions in Multiple Player Environment with complex situations like:
Each player will have to consider the movements of other players,
formulate strategy dynamically and reach the end goals.
Players introduce unforeseen turns to upset the opponent and win the
game.
Some games are co-operative in nature, and most of them are in
competition.
Each player has conflicting goals, and the opponent is unpredictable.
A quick reaction is required to counter strategize and win the game.
Handling all types of games with predictable, unpredictable outcomes and
following transparent and blind rules and regulations.

Dr. Pradeep K V CSE3013 - "Artificial Intelligence" 3/ 30

Advantages/Uses of Adversarial Search

Adversarial search is used in many fields to find optimal solutions in a

competitive environment and few of the applications are:
In the legal system where two advocates argue their stand representing
their party’s cases and Judges or Jury takes cues from the above-explained
techniques, analyze and deliver judgment.
These techniques are used in the business environment in sourcing
suppliers and buyers for Products/services in a competitive manner.
Wherever hard negotiations are required, these concepts help to maximize
the gain who can negotiate intelligently and prudently.
This concept is the base for further development of new technologies like
Alpha-Beta pruning,

Dr. Pradeep K V CSE3013 - "Artificial Intelligence" 4/ 30

Different Game Scenarios using Adversarial search I

1 Games with Perfect information :

These are open and transparent games where each player has all complete
information on the status of the game, and the move of the opponent is
quite visible to the players. Chess, Checkers, Ethello and Go are some of
such games.

Dr. Pradeep K V CSE3013 - "Artificial Intelligence" 5/ 30

Different Game Scenarios using Adversarial search II

2 Games with Imperfect information :

In these games, players will not have any information on the status of the
game, and it will have blind moves by the players assuming certain
conditions and predicting the outcomes. Tic-Tac Toe, Battleship, Blind
and Bridge are some examples of this type of game.
3 Deterministic Games :
These games follow pre-defined rules and pattern, and it is played in a
transparent manner. Each player can see the moves of the opponents
clearly. Chess, Checkers, Tic-tac-toe, Go are some of the games played
in this manner.
4 Non-Deterministic Games :
Luck, Chance, Probability plays a major role in these types of game. The
outcome of these games is highly unpredictable, and players will have to
take random shots relying on luck. Poker, Monopoly, Backgammon are
few of the games played in this method.

Dr. Pradeep K V CSE3013 - "Artificial Intelligence" 6/ 30

Different Game Scenarios using Adversarial search III

5 Zero-Sum Games :
These games are purely competitive in nature, and one player’s gain is
compensated by other player’s loss.
The net value of gain and loss is zero, and each player will have different
conflicting strategies in these games.
Depending on the game environment and game situation, each player will
either try to maximize the gain or minimize the loss.
The move or strategy depends not only on the game situation and
environment but also on the opponent’s likely strategy and game plan.
This is known as embedded thinking in problem resolution in AI.
Each player backtracks and changes his strategy depends on the progress
of the game, and hence it is also known as backward reasoning in AI.
Chess, Tic-tac-toe is a few of the games played under this rule.

Dr. Pradeep K V CSE3013 - "Artificial Intelligence" 7/ 30

Zero-Sum Games : Embedded Thinking

How do it works?
A game can be equated to a type of search in AI, and it will have the
following constituents:
Start of the game: This deals with the initial state of the game and
configurations.
Players: Participants in the game space.
Action: Indicates the moves made by the players in the space.
Result: Outcome of the moves of the players.
Terminal Test: It indicates whether the game is over or not.
Utility: It expresses the final outcome of the game in terms of Loss or
wins or the values.

Dr. Pradeep K V CSE3013 - "Artificial Intelligence" 8/ 30

Game Tree I

It is a tree where nodes of the tree are the game states and Edges of the tree
are the moves by players.

Game tree involves initial state, actions function, and result Function.

Each layer in the tree has the turns for Maximizer and Minimizer alternatively.

Maximizer maximizes the minimum gain and

Minimizer contains the loss and minimizes the maximum loss.

A player takes a maximizer role or minimizer role depending on the game

environment and the opponent’s strategy.

Example: Tic-Tac-Toe game tree:

There are two players MAX and MIN.
Players have an alternate turn and start with MAX.
MAX maximizes the result of the game tree
MIN minimizes the result.

Dr. Pradeep K V CSE3013 - "Artificial Intelligence" 9/ 30

Game Tree II

Dr. Pradeep K V CSE3013 - "Artificial Intelligence" 10/ 30

Game Tree III

From the initial state, MAX has 9 possible moves as he starts first. MAX
place ’x’ and MIN place ’o’, and both player plays alternatively until we
reach a leaf node where one player has three in a row or all squares are
filled.
Both players will compute each node, minimax, the minimax value which
is the best achievable utility against an optimal adversary.
Suppose both the players are well aware of the tic-tac-toe and playing the
best play. Each player is doing his best to prevent another one from
winning. MIN is acting against Max in the game.
So in the game tree, we have a layer of Max, a layer of MIN, and each
layer is called as Ply. Max place ’x’, then MIN puts ’o’ to prevent Max
from winning, and this game continues until the terminal node.
In this either MIN wins, MAX wins, or it’s a draw.
This game-tree is the whole search space of possibilities that MIN and
MAX are playing tic-tac-toe and taking turns alternately.

Dr. Pradeep K V CSE3013 - "Artificial Intelligence" 11/ 30

1. Mini-Max Algorithm

Mini-max algorithm is a recursive or backtracking algorithm which is used

in decision-making and game theory. It provides an optimal move for the
player assuming that opponent is also playing optimally.
It uses recursion to search through the game-tree and mostly used for
game playing in AI. Such as Chess, Checkers, tic-tac-toe, go, and
various tow-players game. This Algorithm computes the minimax decision
for the current state.
In this algorithm two players play the game, one is called MAX and other
is called MIN.
Both the players fight it as the opponent player gets the minimum benefit
while they get the maximum benefit.
Both Players of the game are opponent of each other, where MAX will
select the maximized value and MIN will select the minimized value.
It performs a depth-first search (DFS) algorithm for the exploration of
the complete game tree.
It proceeds all the way down to the terminal node of the tree, then
backtrack the tree as the recursion.

Dr. Pradeep K V CSE3013 - "Artificial Intelligence" 12/ 30

Working of Mini-Max Algorithm I
It is simple. There are two players in the below scenario; one is referred to
as Maximizer, and the other as Minimizer.
Maximizer will try to get the Maximum possible score, and Minimizer
will try to get the minimum possible score.
This algorithm applies DFS, so in this game-tree, we have to go all the
way through the leaves to reach the terminal nodes.
At the terminal node, the terminal values are given so we will compare
those value and backtrack the tree until the initial state occurs.

Dr. Pradeep K V CSE3013 - "Artificial Intelligence" 13/ 30

Working of Mini-Max Algorithm II

1 Step-1: The algorithm generates the entire game-tree and apply the utility
function to get the utility values for the terminal states.

In diagram, let’s take ’A’ is the initial state of the tree. Suppose
Maximizer takes first turn which has worst-case initial value = -∞, and
Minimizer will take next turn which has worst-case initial value = +∞.

Dr. Pradeep K V CSE3013 - "Artificial Intelligence" 14/ 30

Working of Mini-Max Algorithm III

2 Step-2: Now, first we find the utilities value for the Maximizer, its initial
value is -∞, so we will compare each value in terminal state with initial
value of Maximizer and determines the higher nodes values. It will find
the maximum among the all.

For node D :
max(-1,-∞) =>
max(-1,4)= 4
For Node E :
max(2, -∞) =>
max(2, 6)= 6
For Node F :
max(-3, -∞) =>
max(-3,-5) = -3
For node G :
max(0, -∞) =>
max(0, 7) = 7

Dr. Pradeep K V CSE3013 - "Artificial Intelligence" 15/ 30

Working of Mini-Max Algorithm IV

3 Step-3: In the next step, it’s a turn for minimizer, so it will compare all
nodes value with +∞, and will find the 3rd layer node values.

For node B :
min(4,6) = 4

For node C :
min (-3, 7) = -3

Dr. Pradeep K V CSE3013 - "Artificial Intelligence" 16/ 30

Working of Mini-Max Algorithm V

4 Step-4: Now it’s a turn for Maximizer, and it will again choose the
maximum of all nodes value and find the maximum value for the root
node. In this game tree, there are only 4 layers, hence we reach
immediately to the root node, but in real games, there will be more than 4
layers.

For node A :
max(4, -3) = 4

Dr. Pradeep K V CSE3013 - "Artificial Intelligence" 17/ 30

Working of Mini-Max Algorithm VI

Properties of Mini-Max algorithm

Complete : It is Complete. It will definitely find a solution (if exist), in the
finite search tree.
Optimal : It is optimal if both opponents are playing optimally.
Time Complexity : As it performs DFS for the game-tree, so the time
complexity of is O(bm ), where b is branching factor of the game-tree, and m
is the maximum depth of the tree.
Space Complexity : It is also similar to DFS which is O(bm).

Drawback of Mini-Max algorithm

It is really slow for complex games such as Chess, go, etc.
This type of games has a huge branching factor, and the player has lots of
choices to decide

Dr. Pradeep K V CSE3013 - "Artificial Intelligence" 18/ 30

Alpha-Beta Pruning I

It is an optimization technique for the MiniMax algorithm.

The word ‘pruning’ means cutting down branches and leaves.
The amount of game states that must be examined in the MiniMax is
exponentially correlated with the depth of the tree. Since the exponent
cannot be removed, we can reduce it by half. Thus, there is a method
known as "pruning" that allows us to compute the optimal MiniMax
choice without having to examine each node of the game tree.
Alpha-beta pruning can be applied at any depth of a tree. In rare cases,
the entire sub-tree is pruned in addition to the tree leaves.
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 +∞.
It does the same move as in MiniMax, but it eliminates all the nodes that
are merely slowing down the algorithm without having any significant
bearing on the final result. Thus, by cutting these nodes, the algorithm
becomes quick.

Dr. Pradeep K V CSE3013 - "Artificial Intelligence" 19/ 30

Conditions and Keypoints of Alpha-Beta pruning

Condition for Alpha-beta pruning :

α >= β

Key points about alpha-beta pruning :

The Max player will only update the value of alpha(α).

The Min player will only update the value of beta(β).
While backtracking the tree, the node values will be passed to upper
nodes instead of values of alpha(α) and beta(β).
We will only pass the alpha(α), beta(β) values to the child nodes.

Dr. Pradeep K V CSE3013 - "Artificial Intelligence" 20/ 30

Working of Alpha-Beta Pruning I

Given the two-player search(Game)

tree

Step-1 : The first move for the

maximum player will begin at node A,
where alpha and beta values are equal
to α = −∞ and β = +∞. These
values are then given to node B,
where alpha and beta values are equal
to α = −∞ and β = +∞ again.
Node B then passes the same value
to its descendant(child) D.

Dr. Pradeep K V CSE3013 - "Artificial Intelligence" 21/ 30

Working of Alpha-Beta Pruning II

Step-2 : At Node D, the value of α will be calculated as its turn for Max. The
value of α is compared with firstly 2 and then 3, and the max (2, 3) = 3 will be
the value of α at node D and node value will also 3.

Step-3 : Now algorithm backtrack to node B, where the value of β will change as
this is a turn of Min, Now β = +∞, will compare with the available subsequent
nodes value, i.e. min (∞, 3) = 3, hence at node B now α= -∞, and β= 3.

Dr. Pradeep K V CSE3013 - "Artificial Intelligence" 22/ 30

Working of Alpha-Beta Pruning III

Here the algorithm traverse the next successor of Node B which is node E, and
the values of α = −∞, and β = 3 will also be passed.
Step-4 : At node E, Max will take its turn, and the value of alpha will change.
The current value of alpha will be compared with 5, so max(−∞, 5) = 5, hence
at node E, α = 5 and β = 3, where α >= β, so the right successor of E will be
pruned, and algorithm will not traverse it, and the value at node E will be 5.

Dr. Pradeep K V CSE3013 - "Artificial Intelligence" 23/ 30

Working of Alpha-Beta Pruning IV

Step-5 : Here, algorithm again backtrack the tree, from node B to node A. At
node A, the value of alpha will be changed the maximum available value is 3 as
max(-∞, 3) = 3, and β= +∞, these two values now passes to right successor of
A which is Node C.
At node C, α = 3 and β = +∞, and the same values will be given to node F.
Step-6 : At node F, again the value of α will be compared with left child which
is 0, and max(3,0)= 3, and then compared with right child which is 1, and
max(3,1)= 3 still α remains 3, but the node value of F will become 1.

Dr. Pradeep K V CSE3013 - "Artificial Intelligence" 24/ 30

Working of Alpha-Beta Pruning V

Step-7 : Node F returns the node value 1 to node C, at C α = 3 and β=

+∞, here the value of beta will be changed, it will compare with 1 so min
(∞, 1) = 1. Now at C, α = 3 and β = 1, and again it satisfies the
condition α >= β, so the next child of C which is G will be pruned, and
the algorithm will not compute the entire sub-tree G.

Dr. Pradeep K V CSE3013 - "Artificial Intelligence" 25/ 30

Working of Alpha-Beta Pruning VI

Step-8 : C now returns the value of 1 to A here the best value for A is
max (3, 1) = 3. Following is the final game tree which is the showing the
nodes which are computed and nodes which has never computed. Hence
the optimal value for the maximizer is 3 for this example..

Dr. Pradeep K V CSE3013 - "Artificial Intelligence" 26/ 30

Move Ordering in Alpha-Beta pruning

The effectiveness of alpha-beta pruning is highly dependent on the order in

which each node is examined. Move order is an important aspect of alpha-beta
pruning.

It can be of two types:

Worst ordering: In some cases, alpha-beta pruning algorithm does not
prune any of the leaves of the tree, and works exactly as minimax
algorithm. In this case, it also consumes more time because of alpha-beta
factors, such a move of pruning is called worst ordering. In this case, the
best move occurs on the right side of the tree. The time complexity for
such an order is O(b m ).
Ideal ordering: The ideal ordering for alpha-beta pruning occurs when lots
of pruning happens in the tree, and 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(b m/2 ).

Dr. Pradeep K V CSE3013 - "Artificial Intelligence" 27/ 30

Rules to find good ordering

Following are some rules to find good ordering in alpha-beta pruning:

Occur the best move from the shallowest node.
Order the nodes in the tree such that the best nodes are checked first.
Use domain knowledge while finding the best move. Ex: for Chess, try
order: captures first, then threats, then forward moves, backward moves.
As there is a chance that some states will repeat, we can keep a record of
the states.

Dr. Pradeep K V CSE3013 - "Artificial Intelligence" 28/ 30

Try it...

Dr. Pradeep K V CSE3013 - "Artificial Intelligence" 29/ 30

Dr. Pradeep K V CSE3013 - "Artificial Intelligence" 30/ 30