74

SSM COLLEGE OF ARTS & SCIENCE

DEPARTMENT OF ARTIFICIAL INTELLIGENCE
II [Link] ARTIFICIAL INTELLIGENCE & DATA SCIENCE FOUNDATION OF ARTIFICIAL INTELLIGENCE

UNIT III

5.1 GAME THEORY

Game theory is the study of strategic decision making. It is often used in artificial
intelligence (AI) to model how rational agents should make decisions. Game theory has its roots
in economics, but it has also been applied to other fields such as political science, psychology,
and biology.

There are at least three stances we can take towards multi-agent environments.

1. The first stance, appropriate when there are a very large number of agents, is to consider
them in the Economy aggregate as an economy, allowing us to do things like predict that
increasing demand will cause prices to rise, without having to predict the action of any
individual agent.

2. Second, we could consider adversarial agents as just a part of the environment—a part
that makes the environment nondeterministic. But if we model the adversaries in the
same way that, say, rain sometimes falls and sometimes doesn’t, we miss the idea that
our adversaries are actively trying to defeat us, whereas the rain supposedly has no such
intention.

3. The third stance is to explicitly model the adversarial agents with the techniques of
adversarial game-tree search.

Game Theory has now become a describing factor for both Machine Learning
algorithms and many daily life situations. Consider the SVM (Support Vector Machine) for
instance. According to Game Theory, the SVM is a game between 2 players where one player
challenges the other to find the best hyper-plane after providing the most difficult points for
classification. The final playoff of this game is a solution that will be a trade-off between the
strategic abilities of both players competing.

PRUNING

In the context of artificial neural networks, pruning is the practice of removing

parameters (which may entail removing individual parameters, or parameters in groups such as
by neurons) from an existing network. The goal of this process is to maintain accuracy of the
network while increasing its efficiency

The goal is to remove unwanted branches, improve the tree's structure, and direct new,
healthy growth.

5.1.1 TWO-PLAYER ZERO-SUM GAMES

The 2-person 0-sum game is a basic model in game theory. There are two players, each
with an associated set of strategies. While one player aims to maximize her payoff, the other
 75
SSM COLLEGE OF ARTS & SCIENCE
DEPARTMENT OF ARTIFICIAL INTELLIGENCE
II [Link] ARTIFICIAL INTELLIGENCE & DATA SCIENCE FOUNDATION OF ARTIFICIAL INTELLIGENCE

player attempts to take an action to minimize this payoff. In fact, the gain of a player is the loss
of another.

The games most commonly studied within AI (such as chess and Go) are what game
theorists call deterministic, two-player, turn-taking, perfect information, zero-sum games.
―Perfect information‖ is a synonym for ―fully observable,‖1 and ―zero-sum‖ means that what is
good for one player is just as bad for the other: there is no ―win-win‖ outcome. For games we
often use the term move as a synonym for ―action‖ and position as a synonym for ―state.‖
We will call our two players MAX and MIN, for reasons that will soon become obvious.
MAX moves first, and then the players take turns moving until the game is over. At the end of
the game, points are awarded to the winning player and penalties are given to the loser. A game
can be formally defined with the following elements:

 S0: The initial state, which specifies how the game is set up at the start.

 TO-MOVE(s): The player whose turn it is to move in state s.

 ACTIONS(s): The set of legal moves in state s.

 RESULT(s, a): The transition model, which defines the state resulting from taking
action a in state s.

 IS-TERMINAL(s): A terminal test, which is true when the game is over and false
otherwise. States where the game has ended are called terminal states.

 UTILITY(s, p): A utility function (also called an objective function or payoff function),
which defines the final numeric value to player p when the game ends in terminal state s.
In chess, the outcome is a win, loss, or draw, with values 1, 0, or 1/2.2 Some games have
a wider range of possible outcomes—for example, the payoffs in backgammon range
from 0 to 192.

The game tree is essentially a directed graph, where the nodes represent the positions in
the game and the edges the moves. Even a simple board game like tic-tac toe (noughts and
crosses) has as many as 255,168 leaf nodes in the game tree.

Figure 5.1 shows part of the game tree for tic-tac-toe (noughts and crosses). From the
initial state, MAX has nine possible moves. Play alternates between MAX’s placing an X and
MIN’s placing an O until we reach leaf nodes corresponding to terminal states such that one
player has three squares in a row or all the squares are filled.

The number on each leaf node indicates the utility value of the terminal state from the
point of view of MAX; high values are good for MAX and bad for MIN (which is how the
players get their names).

For tic-tac-toe the game tree is relatively small—fewer than 9!=362,880 terminal nodes
(with only 5,478 distinct states). But for chess there are over 1040 nodes, so the game tree is best
thought of as a theoretical construct that we cannot realize in the physical world.
 76
SSM COLLEGE OF ARTS & SCIENCE
DEPARTMENT OF ARTIFICIAL INTELLIGENCE
II [Link] ARTIFICIAL INTELLIGENCE & DATA SCIENCE FOUNDATION OF ARTIFICIAL INTELLIGENCE

5.2 OPTIMAL DECISIONS IN GAMES

Optimal decision-making in games involves navigating a complex web of choices to

maximize your outcomes. It's like being a chess grandmaster, anticipating moves, countermoves,
and trying to stay several steps ahead.

GAME TREE

The optimal strategy can be found from the minimax value of each node, which we
express as MINIMAX, given a game tree (n). Assuming that both players play optimally from
there through the finish of the game, the utility (for MAX) of being in the corresponding state is
the node's minimax value
 77
SSM COLLEGE OF ARTS & SCIENCE
DEPARTMENT OF ARTIFICIAL INTELLIGENCE
II [Link] ARTIFICIAL INTELLIGENCE & DATA SCIENCE FOUNDATION OF ARTIFICIAL INTELLIGENCE

5.2.1 The minimax search 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.

• Mini-Max algorithm uses recursion to search through the game-tree.

• Min-Max algorithm is 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.

• The minimax algorithm performs a depth-first search algorithm for the exploration of the
complete game tree.

• The minimax algorithm proceeds all the way down to the terminal node of the tree, then
backtrack the tree as the recursion.

Working of Min-Max Algorithm:

• The working of the minimax algorithm can be easily described using an example. Below
we have taken an example of game-tree which is representing the two-player game.

• In this example, there are two players one is called Maximizer and other is called
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. Following are the main steps involved in
solving the two-player game tree:

Step-1: In the first step, the algorithm generates the entire game-tree and apply the utility
function to get the utility values for the terminal states. In the below tree diagram, let's take A is
 78
SSM COLLEGE OF ARTS & SCIENCE
DEPARTMENT OF ARTIFICIAL INTELLIGENCE
II [Link] ARTIFICIAL INTELLIGENCE & DATA SCIENCE FOUNDATION OF ARTIFICIAL INTELLIGENCE

the initial state of the tree. Suppose maximizer takes first turn which has worst-case initial value
=- infinity, and minimizer will take next turn which has worst-case initial value = +infinity.

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
 79
SSM COLLEGE OF ARTS & SCIENCE
DEPARTMENT OF ARTIFICIAL INTELLIGENCE
II [Link] ARTIFICIAL INTELLIGENCE & DATA SCIENCE FOUNDATION OF ARTIFICIAL INTELLIGENCE

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.
o For node B= min(4,6) = 4

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

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.
o For node A max(4, -3)= 4
 80
SSM COLLEGE OF ARTS & SCIENCE
DEPARTMENT OF ARTIFICIAL INTELLIGENCE
II [Link] ARTIFICIAL INTELLIGENCE & DATA SCIENCE FOUNDATION OF ARTIFICIAL INTELLIGENCE

Properties of Mini-Max algorithm

 Complete- Min-Max algorithm is Complete. It will definitely find a solution (if exist), in
the finite search tree.

 Optimal- Min-Max algorithm is optimal if both opponents are playing optimally.

 Time complexity- As it performs DFS for the game-tree, so the time complexity of Min-
Max algorithm is O(bm), where b is branching factor of the game-tree, and m is the
maximum depth of the tree.

 Space Complexity- Space complexity of Mini-max algorithm is also similar to DFS which
is O(bm).

The main drawback of the minimax algorithm is that it gets 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. This limitation of the minimax algorithm can be improved from alpha-beta
pruning
 81
SSM COLLEGE OF ARTS & SCIENCE
DEPARTMENT OF ARTIFICIAL INTELLIGENCE
II [Link] ARTIFICIAL INTELLIGENCE & DATA SCIENCE FOUNDATION OF ARTIFICIAL INTELLIGENCE

5.2.2 Optimal decisions in multiplayer games

Making the greatest decision feasible in a circumstance while considering a variety of
variables, including the game mechanics, the resources at your disposal, potential risks and
rewards, and the activities of other players, is known as optimal decision making in a player
game.

Many popular games allow more than two players. Let us examine how to extend the
minimax idea to multiplayer games. This is straightforward from the technical viewpoint, but
raises some interesting new conceptual issues.

First, we need to replace the single value for each node with a vector of values. For
example, in a three-player game with players A, B, and C, a vector hvA,vB,vCi is associated
with each node.

For terminal states, this vector gives the utility of the state from each player’s viewpoint.
(In two-player, zero-sum games, the two-element vector can be reduced to a single value
because the values are always opposite.) The simplest way to implement this is to have the
UTILITY function return a vector of utilities.

Anyone who plays multiplayer games, such as Diplomacy or Settlers of Catan, quickly
becomes aware that much more is going on than in two-player games. Multiplayer games
usually involve alliances, whether formal or informal, among the players.

Alliances are made and broken as the game proceeds. How are we to understand such
behavior? Are alliances a natural consequence of optimal strategies for each player in a
multiplayer game? It turns out that they can be.

For example, suppose A and B are in weak positions and C is in a stronger position. Then
it is often optimal for both A and B to attack C rather than each other, lest C destroy each of
them individually.

In this way, collaboration emerges from purely selfish behavior. Of course, as soon as C
weakens under the joint onslaught, the alliance loses its value, and either A or B could violate
the agreement. In some cases, explicit alliances merely make concrete what would have
happened anyway.

In other cases, a social stigma attaches to breaking an alliance, so players must balance
the immediate advantage of breaking an alliance against the long-term disadvantage of being
perceived as untrustworthy for more on these complications. If the game is not zero-sum, then
collaboration can also occur with just two players.

Suppose, for example, that there is a terminal state with utilities hvA=1000,vB=1000i
and that 1000 is the highest possible utility for each player. Then the optimal strategy is for both
players to do everything possible to reach this state—that is, the players will automatically
cooperate to achieve a mutually desirable goal
 82
SSM COLLEGE OF ARTS & SCIENCE
DEPARTMENT OF ARTIFICIAL INTELLIGENCE
II [Link] ARTIFICIAL INTELLIGENCE & DATA SCIENCE FOUNDATION OF ARTIFICIAL INTELLIGENCE

5.2.3 ALPHA-BETA PRUNING

Alpha-beta pruning is a modified version of the minimax algorithm. It is an optimization
technique for the minimax algorithm.

As we have seen in the minimax search algorithm that the number of game states it has to
examine are exponential in depth of the tree. Since we cannot eliminate the exponent, but we can
cut it to half. Hence there is a technique by which without checking each node of the game tree
we can compute the correct minimax decision, and this technique is called pruning. This
involves two threshold parameter Alpha and beta for future expansion, so it is called alpha-beta
pruning. It is also called as Alpha-Beta Algorithm.

Alpha-beta pruning can be applied at any depth of a tree, and sometimes it not only prune
the tree leaves but also entire sub-tree.

The two-parameter can be defined as:

1. 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 -∞.

2. 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 Alpha-beta pruning to a standard minimax algorithm returns the same move as the
standard algorithm does, but it removes all the nodes which are not really affecting the final
decision but making algorithm slow. Hence by pruning these nodes, it makes the algorithm fast

Condition for Alpha-beta pruning:

The main condition which required for alpha-beta pruning is:

α>=β
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.

Working of Alpha-Beta Pruning:

Let's take an example of two-player search tree to understand the working of Alpha-beta pruning
 83
SSM COLLEGE OF ARTS & SCIENCE
DEPARTMENT OF ARTIFICIAL INTELLIGENCE
II [Link] ARTIFICIAL INTELLIGENCE & DATA SCIENCE FOUNDATION OF ARTIFICIAL INTELLIGENCE

Step 1: At the first step the, Max player will start first move from node A where α= -∞ and β=
+∞, these value of alpha and beta passed down to node B where again α= -∞ and β= +∞, and
Node B passes the same value to its child D.

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. In the next step, algorithm traverse the next successor of
Node B which is node E, and the values of α= -∞, and β= 3 will also be passed.
 84
SSM COLLEGE OF ARTS & SCIENCE
DEPARTMENT OF ARTIFICIAL INTELLIGENCE
II [Link] ARTIFICIAL INTELLIGENCE & DATA SCIENCE FOUNDATION OF ARTIFICIAL INTELLIGENCE

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.

Step 5: At next step, 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 passed on 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
 85
SSM COLLEGE OF ARTS & SCIENCE
DEPARTMENT OF ARTIFICIAL INTELLIGENCE
II [Link] ARTIFICIAL INTELLIGENCE & DATA SCIENCE FOUNDATION OF ARTIFICIAL INTELLIGENCE

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.

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.
 86
SSM COLLEGE OF ARTS & SCIENCE
DEPARTMENT OF ARTIFICIAL INTELLIGENCE
II [Link] ARTIFICIAL INTELLIGENCE & DATA SCIENCE FOUNDATION OF ARTIFICIAL INTELLIGENCE

5.2.4 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:

1. 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(bm).

2. 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(bm/2).
 87
SSM COLLEGE OF ARTS & SCIENCE
DEPARTMENT OF ARTIFICIAL INTELLIGENCE
II [Link] ARTIFICIAL INTELLIGENCE & DATA SCIENCE FOUNDATION OF ARTIFICIAL INTELLIGENCE

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.

 We can bookkeep the states, as there is a possibility that states may repeat

5.3 HEURISTIC ALPHA–BETA TREE SEARCH

The Heuristic Alpha-Beta Tree Search algorithm is a recursive algorithm that explores
the game tree to find the best move for the AI agent. It uses alpha-beta pruning to discard
branches that are guaranteed to be worse than previously explored branches.6

Another example of a heuristic method in AI is alpha beta purring , a heuristic often

used in two-player games that runs through many different possible next moves until a move is
determined to be worse than a previously-considered move. At that point, the previous move is
chosen as the optimal one. That gives us the formula

H-MINIMAX(s, d) for the heuristic minimax value of state s at search depth d:

5.3.1 Evaluation functions

Most evaluation functions work by calculating various features of the state—for
example, in chess, we would have features for the number of white pawns, black pawns, white
queens, black queens, and so on. The features, taken together, define various categories or
equivalence classes of states: the states in each category have the same values for all the
features.

For example, one category might contain all twopawn versus one-pawn endgames. Any
given category will contain some states that lead (with perfect play) to wins, some that lead to
draws, and some that lead to losses
 88
SSM COLLEGE OF ARTS & SCIENCE
DEPARTMENT OF ARTIFICIAL INTELLIGENCE
II [Link] ARTIFICIAL INTELLIGENCE & DATA SCIENCE FOUNDATION OF ARTIFICIAL INTELLIGENCE

5.3.2 Cutting off search

The next step is to modify ALPHA-BETA-SEARCH so that it will call the heuristic
EVAL
function when it is appropriate to cut off the search. We replace the two lines in Figure 5.7
that mention IS-TERMINAL with the following line:

if [Link]-CUTOFF(state, depth) then return [Link](state, player), null

We also must arrange for some bookkeeping so that the current depth is incremented on
each recursive call. The most straightforward approach to controlling the amount of search is to
set a fixed depth limit so that IS-CUTOFF(state, depth) returns true for all depth greater than
some fixed depth d (as well as for all terminal states).

The depth d is chosen so that a move is selected within the allocated time. A more robust
approach is to apply iterative deepening. When time runs out, the program returns the move
selected by the deepest completed search. As a bonus, if in each round of iterative deepening we
keep entries in the transposition table, subsequent rounds will be faster, and we can use the
evaluations to improve move ordering.

5.3.3 Forward pruning

Forward pruning, or selectively searching a subset of moves, is now commonly used in
game-playing programs to reduce the number of nodes searched with manageable risk. Forward
pruning techniques should consider how pruning errors in a game-tree search propagate to the
root to minimize the risk of making errors.

5.4 MONTE CARLO TREE SEARCH

In computer science, Monte Carlo tree search (MCTS) is a heuristic search algorithm for
some kinds of decision processes, most notably those employed in software that plays board
games. In that context MCTS is used to solve the game tree.

The game of Go illustrates two major weaknesses of heuristic alpha–beta tree search:
First, Go has a branching factor that starts at 361, which means alpha–beta search would be
limited to only 4 or 5 ply. Second, it is difficult to define a good evaluation function for Go
because material value is not a strong indicator and most positions are in flux until the endgame.
In response to these two challenges, modern Go programs have abandoned alpha–beta search
and instead use a strategy called Monte Carlo tree search (MCTS).

The basic MCTS strategy does not use a heuristic evaluation function. Instead, the value
of a state is estimated as the average utility over a number of simulations of complete games n
starting from the state. A simulation (also called a playout or rollout) chooses moves first for t
one player, than for the other, repeating until a terminal position is reached. At that point the t
rules of the game (not fallible heuristics) determine who has won or lost, and by what score. For
games in which the only outcomes are a win or a loss, ―average utility‖ is the same as ―win
percentage.‖
 89
SSM COLLEGE OF ARTS & SCIENCE
DEPARTMENT OF ARTIFICIAL INTELLIGENCE
II [Link] ARTIFICIAL INTELLIGENCE & DATA SCIENCE FOUNDATION OF ARTIFICIAL INTELLIGENCE

Monte Carlo tree search (MCTS) algorithm consists of four phases: Selection,
Expansion, Rollout/Simulation, Backpropagation. Algorithm starts at root node R, then moves
down the tree by selecting optimal child node until a leaf node L(no known children so far) is
reached.

Selection:
In this process, the MCTS algorithm traverses the current tree from the root node using a
specific strategy. The strategy uses an evaluation function to optimally select nodes with the
highest estimated value

 The parameters are characterized by the formula that is typically used for this purpose is
given below.

where;
Si = value of a node i
xi = empirical mean of a node i
C = a constant
t = total number of simulations
When traversing a tree during the selection process, the child node that returns the
greatest value from the above equation will be one that will get selected. During
 90
SSM COLLEGE OF ARTS & SCIENCE
DEPARTMENT OF ARTIFICIAL INTELLIGENCE
II [Link] ARTIFICIAL INTELLIGENCE & DATA SCIENCE FOUNDATION OF ARTIFICIAL INTELLIGENCE

traversal, once a child node is found which is also a leaf node, the MCTS jumps into
the expansion step.

Expansion
In this phase, we expand from one node and start looking one level deeper. The node we
expanded from becomes the parent (current state), and its children become the possible next
moves.

Simulation
In this phase, we simulate the game from the selected child node in phase one and continue the
game by making random choices until we reach an end state, i.e. a win, lose or draw. Let’s
assign following values to these results/outcomes:

 WIN = +1

 LOOSE = -1

 DRAW = 0

Backpropagation
In this phase, we backpropagate and update the result we found in the simulation phase to
all the nodes in the random path we traversed and up till the root node. This sets the
value v(i) which is then used in the selection phase of the formula.

These types of algorithms are particularly useful in turn based games where there is no
element of chance in the game mechanics, such as Tic Tac Toe, Connect 4, Checkers, Chess,
Go, etc. This has recently been used by Artificial Intelligence Programs like lphaGo, to play
against the world’s top Go players. But, its application is not limited to games only. It can be
used in any situation which is described by state-action pairs and simulations used to forecast
outcomes.

Monte Carlo Tree Search (MCTS) is a popular algorithm for decision-making and game-
playing tasks. Some of the advantages of using MCTS include the following:

 Strong performance: MCTS performs well in various game-playing tasks, including

chess, go, and poker.

 Minimal domain knowledge: MCTS requires only minimal knowledge of its working
domain. With minimal expertise, it can solve many tasks without needing external task-
specific heuristics.

 Adaptable: MCTS can adapt to environmental changes using simulations. These

simulations can be used to explore new states of the environment.
 91
SSM COLLEGE OF ARTS & SCIENCE
DEPARTMENT OF ARTIFICIAL INTELLIGENCE
II [Link] ARTIFICIAL INTELLIGENCE & DATA SCIENCE FOUNDATION OF ARTIFICIAL INTELLIGENCE

 Robustness: Because it takes a probabilistic approach to decision-making and can deal

with environmental uncertainty, MCTS is resilient to noisy or incomplete information.

 Scalability: MCTS can carefully explore the most promising regions of the search space,
allowing it to scale to vast and complex decision-making tasks.

 Exploration-exploitation balance: MCTS balances the trade-off between exploration

and exploitation, enabling it to discover new and optimal strategies while exploiting
promising options.

MCTS is a sophisticated algorithm that can be used for various gaming and decision-making
tasks, offering outstanding performance and flexibility with little domain expertise.

Disadvantages of MCTS

Monte Carlo Tree Search (MCTS), while its benefits, has a few drawbacks as well that should be
taken into account:

 Computationally Intensive: The time and space complexity of the MCTS algorithm
depend on various factors, such as the size of the game tree, the number of simulations
per move, and the branching factor of the tree.
,
 The time complexity of MCTS is exponential in the depth of the game tree and linear in
the number of simulations per move.

 The space complexity is also proportional to the size of the game tree. Thus, simulating
a large number of game states using MCTS can be computationally intensive. Therefore,
it makes it challenging to apply MCTS to tasks that require fast decision-making.

 Requires a Large Number of Simulations: MCTS algorithm can be time-consuming

and computationally expensive. This is because it requires many simulations to achieve a
stable performance state.

 Bias Towards Early Moves: MCTS may be biased in favor of early moves in the search
tree as these states are investigated more frequently and have more information available
about them.

 Can Be Vulnerable to Specific Strategies: In certain games, MCTS can be exposed to

particular strategies or techniques that are challenging to foresee or resist.

 Lack of Human Intuition: Human intuition and knowledge can be useful in some
decision-making tasks. But MCTS lacks the incorporation of human intelligence.

 Difficult to Tune: Because the algorithm's performance can be susceptible to selecting

parameters and heuristics, MCTS can be challenging to tweak and optimize.
 92
SSM COLLEGE OF ARTS & SCIENCE
DEPARTMENT OF ARTIFICIAL INTELLIGENCE
II [Link] ARTIFICIAL INTELLIGENCE & DATA SCIENCE FOUNDATION OF ARTIFICIAL INTELLIGENCE

Overall, MCTS is a strong algorithm with many benefits. Still, it has several drawbacks and
difficulties that must be carefully considered for particular tasks or domains.

5.5 STOCHASTIC GAMES

A stochastic game was introduced by Lloyd Shapley in the early 1950s. It is a dynamic
game with probabilistic transitions played by one or more players. The game is played in a
sequence of stages. At the beginning of each stage, the game is in a certain state.

Stochastic Games. Stochastic games model dynamic interactions in which the

environment changes in response to players' behavior. In Shapley's words, ―In a stochastic game
the play proceeds by steps from position to position, according to transition probabilities
controlled jointly by the two players‖ (4).

Many unforeseeable external occurrences can place us in unforeseen circumstances in

real life. Many games, such as dice tossing, have a random element to reflect this
 93
SSM COLLEGE OF ARTS & SCIENCE
DEPARTMENT OF ARTIFICIAL INTELLIGENCE
II [Link] ARTIFICIAL INTELLIGENCE & DATA SCIENCE FOUNDATION OF ARTIFICIAL INTELLIGENCE

unpredictability. These are known as stochastic games. Backgammon is a classic game that
mixes skill and luck. The legal moves are determined by rolling dice at the start of each
player’s turn white, for example, has rolled a 6–5 and has four alternative moves in the
backgammon scenario shown in the figure below

This is a standard backgammon position. The object of the game is to get all of
one’s pieces off the board as quickly as possible. White moves in a clockwise direction
toward 25, while Black moves in a counterclockwise direction toward 0.

Unless there are many opponent pieces, a piece can advance to any position; if
there is only one opponent, it is caught and must start over. White has rolled a 6–5 and must
pick between four valid moves: (5–10,5–11), (5–11,19–24), (5–10,10–16), and (5–11,11–16),
where the notation (5–11,11–16) denotes moving one piece from position 5 to 11 and then
another from 11 to 16.
 94
SSM COLLEGE OF ARTS & SCIENCE
DEPARTMENT OF ARTIFICIAL INTELLIGENCE
II [Link] ARTIFICIAL INTELLIGENCE & DATA SCIENCE FOUNDATION OF ARTIFICIAL INTELLIGENCE

compute the expected value, which is the sum of the value over all outcomes, weighted by
the probability of each chance action

where r represents a possible dice roll (or other chance event) and RESULT(s, r) is the same
state as s, with the additional fact that the result of the dice roll is r

5.6 PARTIALLY OBSERVABLE GAMES

Bobby Fischer declared that ―chess is war,‖ but chess lacks at least one major
characteristic of real wars, namely, partial observability. In the ―fog of war,‖ the whereabouts of
enemy units is often unknown until revealed by direct contact. As a result, warfare includes the
use of scouts and spies to gather information and the use of concealment and bluff to confuse the
enemy.

In a partially observable environment, The agent is not familiar with the complete
environment at a given time. Real-life Example: Playing card games is a perfect example of a
partially-observable environment where a player is not aware of the card in the opponent's hand

5.6.2 Card games

An example of a partially observable system would be a card game in which some of the cards
are discarded into a pile face down. In this case the observer is only able to view their own cards
and potentially those of the dealer.

Characteristics of Partially Observable Games (POMDPs):

Partial Observability: In POMDPs, the agent's observations are incomplete and do not directly
reveal the true state of the environment. This introduces uncertainty, as the agent must reason
about the possible states given its observations.

Hidden States: The environment's true state, also known as the hidden state, evolves according
to a probabilistic process. The agent's observations provide noisy or incomplete information
about this hidden state.

Belief State: To handle partial observability, the agent maintains a belief state, which is a
probability distribution over possible hidden states. The belief state captures the agent's
uncertainty about the true state of the environment.
 95
SSM COLLEGE OF ARTS & SCIENCE
DEPARTMENT OF ARTIFICIAL INTELLIGENCE
II [Link] ARTIFICIAL INTELLIGENCE & DATA SCIENCE FOUNDATION OF ARTIFICIAL INTELLIGENCE

Action and Observation: The agent takes actions based on its belief state, and it receives
observations that depend on the hidden state. These observations help the agent update its belief
state and make decisions.

Objective and Policy: The agent's goal is to find a policy—a mapping from belief states to
actions—that maximizes a specific objective, such as cumulative rewards or long-term expected
utility.

Solving Partially Observable Games (POMDPs):

Solving POMDPs is challenging due to the added complexity of partial observability. traditional
techniques used for MDPs, such as dynamic programming and value iteration, are not directly
applicable to POMDPs. Instead, specialized algorithms and techniques are developed to address
the partial observability:

Belief Space Methods: These methods work directly in the space of belief states and involve
updating beliefs based on observations and actions. Techniques like the POMDP forward
algorithm and backward induction are used to compute optimal policies.

Particle Filtering: Particle filters are used to maintain an approximation of the belief state using
a set of particles, each representing a possible state hypothesis.

Point-Based Methods: These methods focus on selecting a subset of belief states (points) that
are critical for decision-making. Techniques like PBVI (Point-Based Value Iteration) and
POMCP (Partially Observable Monte Carlo Planning) fall under this category.

Approximate Solutions: Due to the complexity of exact solutions, approximate methods such
as online planning, heuristic-based policies, and reinforcement learning techniques are often
employed to find near-optimal solutions.
 96
SSM COLLEGE OF ARTS & SCIENCE
DEPARTMENT OF ARTIFICIAL INTELLIGENCE
II [Link] ARTIFICIAL INTELLIGENCE & DATA SCIENCE FOUNDATION OF ARTIFICIAL INTELLIGENCE

CHAPTER 6

CONSTRAINT SATISFACTION PROBLEMS

Finding a solution that meets a set of constraints is the goal of constraint satisfaction
problems (CSPs), a type of AI issue. Finding values for a group of variables that fulfill a set
of restrictions or rules is the aim of constraint satisfaction problems. For tasks including
resource allocation, planning, scheduling, and decision-making, CSPs are frequently
employed in AI.

There are mainly three basic components in the constraint satisfaction problem:

Variables: The things that need to be determined are variables. Variables in a CSP are the
objects that must have values assigned to them in order to satisfy a particular set of
constraints. Boolean, integer, and categorical variables are just a few examples of the various
types of variables, for instance, could stand in for the many puzzle cells that need to be filled
with numbers in a sudoku puzzle.

Domains: The range of potential values that a variable can have is represented by domains.
Depending on the issue, a domain may be finite or limitless. For instance, in Sudoku, the set
of numbers from 1 to 9 can serve as the domain of a variable representing a problem cell.

Constraints: The guidelines that control how variables relate to one another are known as
constraints. Constraints in a CSP define the ranges of possible values for variables. Unary
constraints, binary constraints, and higher-order constraints are only a few examples of the
various sorts of constraints. For instance, in a sudoku problem, the restrictions might be that
each row, column, and 3×3 box can only have one instance of each number from 1 to 9.

6.1 DEFINING CONSTRAINT SATISFACTION PROBLEMS

 A constraint satisfaction problem consists of three components, X,D, and C:

 X is a set of variables, {X1, . . . ,Xn}.

 D is a set of domains, {D1, . . . ,Dn}, one for each variable.

 C is a set of constraints that specify allowable combinations of values.

A domain, Di, consists of a set of allowable values, {v1, . . . ,vk}, for variable Xi. For
example, a Boolean variable would have the domain {true, false}. Different variables can have
different domains of different sizes.

Each constraint Cj consists of a pair hscope, reli, where scope is a tuple of variables that
participate in the constraint and rel Relation is a relation that defines the values that those
variables can take on.
 97
SSM COLLEGE OF ARTS & SCIENCE
DEPARTMENT OF ARTIFICIAL INTELLIGENCE
II [Link] ARTIFICIAL INTELLIGENCE & DATA SCIENCE FOUNDATION OF ARTIFICIAL INTELLIGENCE

A relation can be represented as an explicit set of all tuples of values that satisfy the
constraint, or as a function that can compute whether a tuple is a member of the relation. For
example, if X1 and X2 both have the domain {1,2,3}, then the constraint saying that X1 must be
greater than X2 can be written as

h(X1,X2),{(3,1), (3,2), (2,1)}i or as h(X1,X2),X1 > X2i.

CSPs deal with assignments of values to variables, {Xi =vi,Xj =vj, . . .}. An assignment
that does not violate any constraints is called a consistent or legal assignment. A complete
assignment is one in which every variable is assigned a value, and a solution to a CSP is
a consistent, complete assignment.

A partial assignment is one that leaves some variables unassigned, and a partial solution
is a partial assignment that is consistent. Solving a CSP is an NP-complete problem in general,
although there are important subclasses of CSPs that can be solved very efficiently.

6.1.1 Example problem: Map coloring

Map colouring problem states that given a graph G {V, E} where V and E are the set of
vertices and edges of the graph, all vertices in V need to be coloured in such a way that no two
adjacent vertices must have the same colour. To formulate this as a CSP, we define the variables
to be the regions:

X = {WA,NT,Q,NSW,V,SA,T}.

The domain of every variable is the set Di ={red,green,blue}.

The constraints require neighboring regions to have distinct colors. Since there are nine places
where regions border, there are nine constraints:

C = {SA 6= WA,SA 6= NT,SA 6= Q,SA 6= NSW,SA 6=V, WA 6= NT,NT 6= Q,Q 6=

NSW,NSW 6=V}.

Here we are using abbreviations; SA 6= WA is a shortcut for h(SA,WA),SA 6= WAi, where

SA 6= WA can be fully enumerated in turn as

{(red,green), (red,blue), (green, red), (green,blue), (blue, red), (blue,green)}.

There are many possible solutions to this problem, such as

{WA=red,NT=green,Q=red,NSW=green,V =red,SA=blue,T =red }.

It can be helpful to visualize a CSP as a constraint graph, as shown in Figure 6.1(b). The
nodes of the graph correspond to variables of the problem, and an edge connects any two
variables that participate in a constraint.
 98
SSM COLLEGE OF ARTS & SCIENCE
DEPARTMENT OF ARTIFICIAL INTELLIGENCE
II [Link] ARTIFICIAL INTELLIGENCE & DATA SCIENCE FOUNDATION OF ARTIFICIAL INTELLIGENCE

Why formulate a problem as a CSP? One reason is that the CSPs yield a natural
representation for a wide variety of problems; it is often easy to formulate a problem as a CSP.
Another is that years of development work have gone into making CSP solvers fast and
efficient.A third is that a CSP solver can quickly prune large swathes of the search space that an
atomic state-space searcher cannot.

For example, once we have chosen {SA=blue} in the Australia problem, we can
conclude that none of the five neighboring variables can take on the value blue. A search
procedure that does not use constraints would have to consider 35=243 assignments for the five
neighboring variables; with constraints we have only 25=32 assignments to consider, a reduction
of 87%.

In atomic state-space search we can only ask: is this specific state a goal? No? What
about this one? With CSPs, once we find out that a partial assignment violates a constraint, we
can immediately discard further refinements of the partial assignment.

Furthermore, we can see why the assignment is not a solution—we see which variables
violate a constraint— so we can focus attention on the variables that matter. As a result, many
problems that are intractable for atomic state-space search can be solved quickly when
formulated as a CSP.

6.1.2 Example problem: Job-shop scheduling

Job Shop Scheduling is a combinatorial optimization problem in the field of operational
research and management science. It involves scheduling a series of operations on multiple
machines in a predefined technological sequence to minimize the maximum completing time of
all jobs, known as the makespan.
 99
SSM COLLEGE OF ARTS & SCIENCE
DEPARTMENT OF ARTIFICIAL INTELLIGENCE
II [Link] ARTIFICIAL INTELLIGENCE & DATA SCIENCE FOUNDATION OF ARTIFICIAL INTELLIGENCE

Factories have the problem of scheduling a day’s worth of jobs, subject to various
constraints. In practice, many of these problems are solved with CSP techniques. Consider the
problem of scheduling the assembly of a car. The whole job is composed of tasks, and we can
model each task as a variable, where the value of each variable is the time that the task starts,
expressed as an integer number of minutes. Constraints can assert that one task must occur
before another—for example, a wheel must be installed before the hubcap is put on—and that
only so many tasks can go on at once. Constraints can also specify that a task takes a certain

JOB SCHEDULING ALGORITHM

Set of jobs with deadlines and profits are taken as an input with the job scheduling algorithm and
scheduled subset of jobs with maximum profit are obtained as the final output.

Algorithm

Examples

Consider the following tasks with their deadlines and profits. Schedule the tasks in such a way
that they produce maximum profit after being executed −

S. No. 1 2 3 4 5
Jobs J1 J2 J3 J4 J5
Deadlines 2 2 1 3 4
Profits 20 60 40 100 80

Step 1
Find the maximum deadline value, dm, from the deadlines given. Dm = 4

Step 2
Arrange the jobs in descending order of their profits.

S. No. 1 2 3 4 5
Jobs J4 J5 J2 J3 J1
Deadlines 3 4 2 1 2
Profits 100 80 60 40 20

The maximum deadline, dm, is 4. Therefore, all the tasks must end before 4. Choose the job with
highest profit, J4. It takes up 3 parts of the maximum deadline. Therefore, the next job must have
the time period 1. Total Profit = 100.

Step 3

The next job with highest profit is J5. But the time taken by J5 is 4, which xceeds the deadline
by 3. Therefore, it cannot be added to the output set.
 100
SSM COLLEGE OF ARTS & SCIENCE
DEPARTMENT OF ARTIFICIAL INTELLIGENCE
II [Link] ARTIFICIAL INTELLIGENCE & DATA SCIENCE FOUNDATION OF ARTIFICIAL INTELLIGENCE

Step 4

The next job with highest profit is J2. The time taken by J5 is 2, which also exceeds the deadline
by 1. Therefore, it cannot be added to the output set.

Step 5

The next job with higher profit is J3. The time taken by J3 is 1, which does not exceed the given
deadline. Therefore, J3 is added to the output set.
Total Profit 100 + 40 = 140

Step 6

Since, the maximum deadline is met, the algorithm comes to an end. The output set of jobs
scheduled within the deadline are {J4, J3} with the maximum profit of 140.

6.1.3 Variations on the CSP formalism

The simplest kind of CSP involves variables that have discrete, finite domains. E.g. Map-
coloring problems, scheduling with time limits, the 8-queens problem. A discrete domain can be
infinite. e.g. The set of integers or strings.

The simplest kind of CSP involves variables that have discrete, finite domains. Map-
coloring problems and scheduling with time limits are both of this kind. The 8-queens problem
can also be viewed as a finite-domain CSP, where the variables Q1, . . . ,Q8 correspond to the
queens in columns 1 to 8, and the domain of each variable specifies the possible row numbers
for the queen in that column, Di = {1,2,3,4,5,6,7,8}. The constraints say that no two queens can
be in the same row or diagonal.

A discrete domain can be infinite, such as the set of integers or strings. (If we didn’t put a
deadline on the job-scheduling problem, there would be an infinite number of start times for
each variable.) With infinite domains, wemust use implicit constraints like T1+d1 ≤T2 rather
than explicit tuples of values.

Special solution algorithms (which we do not discuss here) exist for linear constraints on
integer variables—that is, constraints, such as the one just given, in which each variable appears
only in linear form. It can be shown that no algorithm exists for solving general nonlinear
constraints on integer variables—the problem is undecidable.

CRYPTARITHMETIC PUZZLES
Cryptarithmetic is a class of constraint satisfaction problems which includes making
mathematical relations between meaningful words using simple arithmetic operators like `plus'
in a way that the result is conceptually true, and assigning digits to the letters of these words and
generating numbers in order to make .
 101
SSM COLLEGE OF ARTS & SCIENCE
DEPARTMENT OF ARTIFICIAL INTELLIGENCE
II [Link] ARTIFICIAL INTELLIGENCE & DATA SCIENCE FOUNDATION OF ARTIFICIAL INTELLIGENCE

The goal here is to assign each letter a digit from 0 to 9 so that the arithmetic works out
correctly. The rules are that all occurrences of a letter must be assigned the same digit, and no
digit can be assigned to more than one letter
 102
SSM COLLEGE OF ARTS & SCIENCE
DEPARTMENT OF ARTIFICIAL INTELLIGENCE
II [Link] ARTIFICIAL INTELLIGENCE & DATA SCIENCE FOUNDATION OF ARTIFICIAL INTELLIGENCE

S 0 1 2 3 4 5 6 7 8 9
E 0 1 2 3 4 5 6 7 8 9
N 0 1 2 3 4 5 6 7 8 9
D 0 1 2 3 4 5 6 7 8 9
M 0 1 2 3 4 5 6 7 8 9
O 0 1 2 3 4 5 6 7 8 9
R 0 1 2 3 4 5 6 7 8 9
Y 0 1 2 3 4 5 6 7 8 9

STEP 1
Condition Satisfied

1. No string has starts with Zero

S 0 1 2 3 4 5 6 7 8 9
E 0 1 2 3 4 5 6 7 8 9
N 0 1 2 3 4 5 6 7 8 9
D 0 1 2 3 4 5 6 7 8 9
M 1 2 3 4 5 6 7 8 9
O 0 1 2 3 4 5 6 7 8 9
R 0 1 2 3 4 5 6 7 8 9
Y 0 1 2 3 4 5 6 7 8 9
 103
SSM COLLEGE OF ARTS & SCIENCE
DEPARTMENT OF ARTIFICIAL INTELLIGENCE
II [Link] ARTIFICIAL INTELLIGENCE & DATA SCIENCE FOUNDATION OF ARTIFICIAL INTELLIGENCE

2. Extra Character in M. So carry will be in this problem. As default we can add two large
number the result is 18 carry will 1 so assign 1 to extra character . So assign
M=1
The result is

S 2 3 4 5 6 7 8 9
E 2 3 4 5 6 7 8 9
N 2 3 4 5 6 7 8 9
D 2 3 4 5 6 7 8 9
M 1
O 2 3 4 5 6 7 8 9
R 2 3 4 5 6 7 8 9
Y 2 3 4 5 6 7 8 9

1
1

STEP 2
We have to find next value.
The next value is S M O. Already the value of M is 1. So we find the values for S and O.
The condition is

1. Definitely need carry

2. So we add the value of M with number having carry
3. Now we substitute

S 9

M 1

O 0

The possible values of S and O is 2 3 4 5 6 7 8 9

Here value of M is 1

The Value of S and O is unknown

So now we substitute the values the S only because O is the reminder of S + M

 104
SSM COLLEGE OF ARTS & SCIENCE
DEPARTMENT OF ARTIFICIAL INTELLIGENCE
II [Link] ARTIFICIAL INTELLIGENCE & DATA SCIENCE FOUNDATION OF ARTIFICIAL INTELLIGENCE

S+M=O
2+1 = 3
3+1 = 4
4+1 = 5
5+ 1 = 6
6+ 1 = 7
7+ 1 = 8
8+ 1 = 9
9+ 1 = 10
The carry will come only 9 + 1 = 10 the result is’

1 1

1 0

S 9
E 2 3 4 5 6 7 8 9
N 2 3 4 5 6 7 8 9
D 2 3 4 5 6 7 8 9
M 1
O 0
R 2 3 4 5 6 7 8 9
Y 2 3 4 5 6 7 8 9

STEP 3
Next we have to find the Values of E and N
The condition is
The carry if either 0 or 1

Now we apply 0 for zero carry

0+ E+ 0 = N
E=N

No two digits have same number . So carry zero condition will fail
Now we apply for One carry
1+ E+ 0 = N
1+ E = N ---------------------> 1
Now we have to find the values of E and N

STEP 4

Next we have to find the Values of N and R

The condition is
 105
SSM COLLEGE OF ARTS & SCIENCE
DEPARTMENT OF ARTIFICIAL INTELLIGENCE
II [Link] ARTIFICIAL INTELLIGENCE & DATA SCIENCE FOUNDATION OF ARTIFICIAL INTELLIGENCE

The carry if either 0 or 1

Now we apply zero carry
0+N+R=E
N+R=E

Add 10 to E because the carry is 1

N + R = E + 10

Substitute 1 + E to N
1+ E + R = E + 10

Cancel both E
1+ R = 10
R = 10 – 1
R=9

The value 9 is 9 is already assign to S

Finally the carry will be 1

Now we apply one carry

1+N+R=E

Substitute 1 + E to N
1+1+ E + R = E + 10
2 + E + R = E + 10
2 + R = 10
R = 10 – 2
R=8

8 Is not assign to any one. So R is 8

S 9
E 2 3 4 5 6 7
N 2 3 4 5 6 7
D 2 3 4 5 6 7
M 1
O 0
R 8
Y 2 3 4 5 6 7

1 1

1 0 8

1 0
 106
SSM COLLEGE OF ARTS & SCIENCE
DEPARTMENT OF ARTIFICIAL INTELLIGENCE
II [Link] ARTIFICIAL INTELLIGENCE & DATA SCIENCE FOUNDATION OF ARTIFICIAL INTELLIGENCE

STEP 5
Next we have to find the Values of D E and Y
D+E=Y
Add 10 to Y
D + E = Y + 10
The condition is

Identify which two number gives carry

5 + 5 = 10 5+6 = 11 5+7 = 12
6+ 5 = 11 6 + 6 = 12 6 + 7 = 13
7 + 5 = 12 7+6 = 13 7 + 7 = 14

5+7 = 12 6 + 7 = 13
7 + 5 = 12 7+6 = 13

5+7 = 12 6 + 7 = 13
Here y value is either 2 or 3
5 + 7 = 12
6 + 7 = 13
D + E = 12 That is 5 + 7 = 12
D + E = 13 That is 6 + 7 = 13

Now the common value is 7. Assign to E. Now we assign 7 to E

1 1

9 7

1 0 8 7

1 0 8

Here add carry one to 7 So N= 8. But already 8 is assign to R

So assign 7 to D

S 9
E 2 3 4 5 6 7
N 2 3 4 5 6 7
D 7
M 1
O 0
R 8
Y 2 3 4 5 6 7
 107
SSM COLLEGE OF ARTS & SCIENCE
DEPARTMENT OF ARTIFICIAL INTELLIGENCE
II [Link] ARTIFICIAL INTELLIGENCE & DATA SCIENCE FOUNDATION OF ARTIFICIAL INTELLIGENCE

1 1

9 7

1 0 8

1 0

STEP 6
Now the value of E is either 5 or 6
Now we substitute 6 to E

1 1

9 6

1 0 8 6

1 0 6

7 is already assign to D . So the value of E is 5

1 1

9 5 6 7

1 0 8 5

1 0 6 5

Here N = 6 and E = 5

S 9
E 5
N 6
D 7
M 1
O 0
R 8
Y 2 3 4 5 6 7

STEP 7
Now we have to find the value of Y is either 2 0r 3
 108
SSM COLLEGE OF ARTS & SCIENCE
DEPARTMENT OF ARTIFICIAL INTELLIGENCE
II [Link] ARTIFICIAL INTELLIGENCE & DATA SCIENCE FOUNDATION OF ARTIFICIAL INTELLIGENCE

S 9
E 5
N 6
D 7
M 1
O 0
R 8
Y 2

1 1

9 5 6 7

1 0 8 5

1 0 6 5 2

6.2 Constraint Propagation: Inference in CSPs

Consistency techniques were first introduced for improving the efficiency of picture
recognition programs, by researchers in artificial intelligence [Waltz]. Picture recognition
involves labelling all the lines in a picture in a consistent way.

Constraint Propagation

Artificial Intelligence (AI) encompasses a variety of methods and techniques to solve

complex problems efficiently. One such technique is constraint propagation, which plays a
crucial role in areas like scheduling, planning, and resource allocation
 109
SSM COLLEGE OF ARTS & SCIENCE
DEPARTMENT OF ARTIFICIAL INTELLIGENCE
II [Link] ARTIFICIAL INTELLIGENCE & DATA SCIENCE FOUNDATION OF ARTIFICIAL INTELLIGENCE

Introduction to Constraint Propagation

Constraint propagation is a fundamental concept in constraint satisfaction problems

(CSPs). A CSP involves variables that must be assigned values from a given domain while
satisfying a set of constraints. Constraint propagation aims to simplify these problems by
reducing the domains of variables, thereby making the search for solutions more efficient.

The idea is that this will leave fewer choices to consider when we make the next choice
of a variable assignment. Constraint propagation may be intertwined with search, or it may be
done as a preprocessing step, before search starts. Sometimes this preprocessing can solve the
whole problem, so no search is required at all.

The key idea is local consistency. If we treat each variable as a node in a graph and each
binary constraint as an edge, then the process of enforcing local consistency in each part of the
graph causes inconsistent values to be eliminated throughout the graph. There are different
types of local consistency, which we now cover in turn.

6.2.1 Node consistency

A single variable (corresponding to a node in the CSP graph) is node-consistent if all the
values in the variable’s domain satisfy the variable’s unary constraints. For example, in the
variant of the Australia map-coloring problem (Figure 6.1) where South Australians dislike
green, the variable SA starts with domain {red,green,blue}, and we can make it node consistent
by eliminating green, leaving SA with the reduced domain {red,blue}.

We say that a graph is node-consistent if every variable in the graph is node-consistent. It

is easy to eliminate all the unary constraints in a CSP by reducing the domain of variables with
unary constraints at the start of the solving process.

As mentioned earlier, it is also possible to transform all n-ary constraints into binary
ones. Because of this, some CSP solvers work with only binary constraints, expecting the user to
eliminate the other constraints ahead of time. We make that assumption for the rest of this
chapter, except where noted.

Arc consistency ensures that for every value of one variable, there is a consistent value
in another variable connected by a constraint. This algorithm is often used as a preprocessing
step to simplify CSPs before applying more complex algorithms.

6.2.2 Arc consistency

Arc Consistency refers to a powerful propagation technique used in computer science to

ensure that all binary constraints between variables in a constraint satisfaction problem are
satisfied.

Arc consistency ensures that for every value of one variable, there is a consistent value in
another variable connected by a constraint. This algorithm is often used as a preprocessing step
to simplify CSPs before applying more complex algorithms.
 110
SSM COLLEGE OF ARTS & SCIENCE
DEPARTMENT OF ARTIFICIAL INTELLIGENCE
II [Link] ARTIFICIAL INTELLIGENCE & DATA SCIENCE FOUNDATION OF ARTIFICIAL INTELLIGENCE

Arc consistency ensures that for every value of one variable, there is a consistent value
in another variable connected by a constraint. This algorithm is often used as a preprocessing
step to simplify CSPs before applying more complex algorithms

Backtracking tree search is a blind search. Forward checking checks constraints between
the current variable and all future ones. Arc consistency then checks constraints between all
pairs of future .variables.

6.2.3 Path consistency

Path consistency extends arc consistency by considering triples of variables. It ensures
that for every pair of variables, there is a consistent value in the third variable. This further
reduces the domains and simplifies the problem

Arc consistency checks the consistency of labels for each couple of nodes linked by a
binary constraint and removes the labels that cannot satisfy this local condition. Path consistency
algorithms ensure that any pair of labelings (î, b)-(j, c) allowed by a direct relation is also
allowed by all paths from i to j.

6.2.4 K-consistency
k-Consistency generalizes the concept of arc and path consistency to k variables. It
ensures that for every subset of k-1 variables, there is a consistent value in the kth variable.
Higher levels of consistency provide more pruning but are computationally more expensive.

A graph is K-consistent if the following is true: Choose values of any K-1 variables that
satisfy all the constraints among these variables and choose any Kth variable. Then there exists a
value for this Kth variable that satisfies all the constraints among these K variables.

A graph is K-consistent if the following is true: Choose values of any K-1 variables that
satisfy all the constraints among these variables and choose any Kth variable. Then there exists a
value for this Kth variable that satisfies all the constraints among these K variables.

6.2.6 Sudoku

The popular Sudoku puzzle has introduced millions of people to constraint satisfaction
problems, although they may not realize it. A Sudoku board consists of 81 squares, some of
which are initially filled with digits from 1 to 9. The puzzle is to fill in all the remaining squares
such that no digit appears twice in any row, column, or 3×3 box (see Figure 6.4). A row,
column, or box is called a unit.

Following are the rules of Sudoku for a player

.
1. In all 9 sub matrices 3×3 the elements should be 1-9, without repetition.
2. In all rows there should be elements between 1-9 , without repetition.
3. In all columns there should be elements between 1-9 , without repetition.
 111
SSM COLLEGE OF ARTS & SCIENCE
DEPARTMENT OF ARTIFICIAL INTELLIGENCE
II [Link] ARTIFICIAL INTELLIGENCE & DATA SCIENCE FOUNDATION OF ARTIFICIAL INTELLIGENCE

Naive Approach:

1. Randomly take any number 1-9.

2. Check if it is safe to put in the cell.(row , column and box)
3. If safe, place it and increment to next location and go to step 1.
4. If not safe, then without incrementing go to step 1.
5. Once matrix is fully filled, remove k no. of elements randomly to complete game.

Using Backtracking ApproachIn this approach, we assign numbers one-by-one to empty

cells. Before assigning any number, we check whether the same is present in the current column,
current row, or the current 3 x 3 sub-grid or not. If the same number is present, then we take
another number and check its safety.

Steps. First, identify empty cells which is defined by 0. If an empty cell is found, check if
it is valid to put a number in that cell by checking whether the number already exists in the same
row, column, or 3x3 sub-grid. If it is valid to place a number in the cell, the number is assigned
to the cell. Otherwise, backtrack and assign 0 again

6.3 BACKTRACKING SEARCH FOR CSPS

Backtracking

Backtracking is a class of algorithms for finding solutions to some computational

problems, notably constraint satisfaction problems, that incrementally builds candidates to the
solutions, and abandons a candidate ("backtracks") as soon as it determines that the candidate
cannot possibly be completed to a valid

Examples where backtracking can be used to solve puzzles or problems include: Puzzles
such as eight queens puzzle, crosswords, verbal arithmetic, Sudoku, and Peg Solitaire.
Combinatorial optimization problems such as parsing and the knapsack problem.
 112
SSM COLLEGE OF ARTS & SCIENCE
DEPARTMENT OF ARTIFICIAL INTELLIGENCE
II [Link] ARTIFICIAL INTELLIGENCE & DATA SCIENCE FOUNDATION OF ARTIFICIAL INTELLIGENCE

Backtracking is like trying different paths, and when you hit a dead end, you backtrack
to the last choice and try a different route. In this article, we’ll explore the basics of
backtracking, how it works, and how it can help solve all sorts of challenging problems. It’s
like a method for finding the right way through a complex choices

Backtracking Search for CSP in Artificial Intelligence: Backtracking is a widely used

technique for solving CSPs. It is a systematic search algorithm that explores possible
assignments for variables, backtracking when it encounters constraints that cannot be satisfied.

Basic Terminologies

 Candidate: A candidate is a potential choice or element that can be added to the current
solution.

 Solution: The solution is a valid and complete configuration that satisfies all problem
constraints.

 Partial Solution: A partial solution is an intermediate or incomplete configuration being

constructed during the backtracking process.

 Decision Space: The decision space is the set of all possible candidates or choices at each
decision point.

 Decision Point: A decision point is a specific step in the algorithm where a candidate is
chosen and added to the partial solution.
 Feasible Solution: A feasible solution is a partial or complete solution that adheres to all
constraints.
 Dead End: A dead end occurs when a partial solution cannot be extended without violating
constraints.

 Backtrack: Backtracking involves undoing previous decisions and returning to a prior

decision point.

 Search Space: The search space includes all possible combinations of candidates and
choices.
 113
SSM COLLEGE OF ARTS & SCIENCE
DEPARTMENT OF ARTIFICIAL INTELLIGENCE
II [Link] ARTIFICIAL INTELLIGENCE & DATA SCIENCE FOUNDATION OF ARTIFICIAL INTELLIGENCE

 Optimal Solution: In optimization problems, the optimal solution is the best possible
solution.

Types of Backtracking Problems

Problems associated with backtracking can be categorized into 3 categories:

 Decision Problems: Here, we search for a feasible solution.

 Optimization Problems: For this type, we search for the best solution.

 Enumeration Problems: We find set of all possible feasible solutions to the problems of
this type.

How does Backtracking works?

As we know backtracking algorithm explores each and every possible path in order to
find a valid solution, this exploration of path can be easily understood via given images:
 114
SSM COLLEGE OF ARTS & SCIENCE
DEPARTMENT OF ARTIFICIAL INTELLIGENCE
II [Link] ARTIFICIAL INTELLIGENCE & DATA SCIENCE FOUNDATION OF ARTIFICIAL INTELLIGENCE

As shown in the image,

 ―IS” represents the Initial State where the recursion call starts to find a valid solution.

C : it represents different Checkpoints for recursive calls

 TN: it represents the Terminal Nodes where no further recursive calls can be made,
these nodes act as base case of recursion and we determine whether the current
solution is valid or not at this state.

 At each Checkpoint, our program makes some decisions and move to other
checkpoints untill it reaches a terminal Node, after determining whether a solution is
valid or not, the program tarts to revert back to the checkpoints and try to explore
other paths.

 For example in the above image TN1…TN5 are the terminal node where the solution
is not acceptable, while TN6 is the state where we found a valid solution.

 The back arrows in the images shows backtracking in actions, where we revert the
changes made by some checkpoint.

Recursion Backtracking
Recursion does not always need backtracking Backtracking always uses recursion to solve
problems
Solving problems by breaking them into Solving problems with multiple choices and
smaller, similar subproblems and solving exploring options systematically,
them recursively. backtracking when needed.

Controlled by function calls and call stack. Managed explicitly with loops and state.
Applications of Recursion: Tree and Graph Application of Backtracking: N Queen
Traversal, Towers of Hanoi, Divide and problem, Rat in a Maze problem, Knight’s
Conquer Algorithms, Merge Sort, Quick Sort, Tour Problem, Sudoku solver, and Graph
and Binary Search. coloring problems.

Applications of Backtracking

 Creating smart bots to play Board Games such as Chess.

 Solving mazes and puzzles such as N-Queen problem.
 Network Routing and Congestion Control.
 Decryption
 Text Justification
 115
SSM COLLEGE OF ARTS & SCIENCE
DEPARTMENT OF ARTIFICIAL INTELLIGENCE
II [Link] ARTIFICIAL INTELLIGENCE & DATA SCIENCE FOUNDATION OF ARTIFICIAL INTELLIGENCE

6.3.1 VARIABLE AND VALUE ORDERING

Variable Ordering
Experiments and analysis of several researchers have shown that the ordering in which
variables are chosen for instantiation can have substantial impact on the complexity of backtrack
search. The ordering may be either
 a static ordering, in which the order of the variables is specified before the search begins,
and it is not changed thereafter, or

 a dynamic ordering, in which the choice of next variable to be considered at any point
depends on the current state of the search.

Dynamic ordering is not feasible for all search algorithms, e.g., with simple backtracking
there is no extra information available during the search that could be used to make a different
choice of ordering from the initial ordering. However, with forward checking, the current state
includes the domains of the variables as they have been pruned by the current set of
instantiations, and so it is possible to base the choice of next variable on this information.

Several heuristics have been developed and analyzed for selecting variable ordering. The
most common one is based on the "first-fail" principle, which can be explained as

"To succeed, try first where you are most likely to fail."

In this method, the variable with the fewest possible remaining alternatives is selected for
instantiation. Thus the order of variable instantiations is, in general, different in different
branches of the tree, and is determined dynamically. This method is based on assumption that
any value is equally likely to participate in a solution, so that the more values there are, the more
likely it is that one of them will be a successful one.

The first-fail principle may seem slightly misleading, after all, we do not want to fail.
The reason is that if the current partial solution does not lead to a complete solution, then the
sooner we discover this the better. Hence encouraging early failure, if failure is inevitable, is
beneficial in the long term.

On the other end, if the current partial solution can be extended to a complete solution,
then every remaining variable must be instantiated and the one with smallest domain is likely to
be the most difficult to find a value for (instantiating other variables first may further reduce its
domain and lead to a failure). Hence the principle could equally well be stated as:

"Deal with hard cases first: they can only get more difficult if you put them off."

This heuristic should reduce the average depth of branches in the search tree by triggering early
failure.

Another heuristic, that is applied when all variables have the same number of values, is
to choose the variable which participates in most constraints (in the absence of more specific
 116
SSM COLLEGE OF ARTS & SCIENCE
DEPARTMENT OF ARTIFICIAL INTELLIGENCE
II [Link] ARTIFICIAL INTELLIGENCE & DATA SCIENCE FOUNDATION OF ARTIFICIAL INTELLIGENCE

information on which constraints are likely to be difficult to satisfy, for instance). This heuristic
follows also the principle of dealing with hard cases first.

There is also a heuristic for static ordering of variables that is suitable for simple
backtracking. This heuristic says: choose the variable which has the largest number of
constraints with the past variables. For instance, during solving graph coloring problem, it is
reasonable to assign color to the vertex which has common arcs with already colored vertices so
the conflict is detected as soon as possible.

Value Ordering

Once the decision is made to instantiate a variable, it may have several values available.
Again, the order in which these values are considered can have substantial impact on the time to
find the first solution. However, if all solutions are required or there are no solutions, then the
value ordering is indifferent.

A different value ordering will rearrange the branches emanating from each node of the
search tree. This is an advantage if it ensures that a branch which leads to a solution is searched
earlier than branches which lead to death ends. For example, if the CSP has a solution, and if a
correct value is chosen for each variable, then a solution can be found without any backtracking.

Suppose we have selected a variable to instantiate: how should we choose which value to
try first? It may be that none of the values will succeed, in that case, every value for the current
variable will eventually have to be considered, and the order does not matter. On the other hand,
if we can find a complete solution based on the past instantiations, we want to choose a value
which is likely to succeed, and unlikely to lead to a conflict. So, we apply the "succeed
first" principle.

One possible heuristic is to prefer those values that maximize the number of options
available. Visibly, the algorithm AC-4 is good for using this heuristic as it counts the supporting
values. It is possible to count "promise" of each value, that is the product of the domain sizes of
the future variables after choosing this value (this is an upper bound on the number of possible
solutions resulting from the assignment).

The value with highest promise should be chosen. Is also possible to calculate the
percentage of values in future domains which will no longer be usable. The best choice would be
the value with lowest cost.

Another heuristic is to prefer the value (from those available) that leads to an easiest to
solve CSP. This requires to estimate the difficulty of solving a CSP. One method [Dechter]
propose to convert a CSP into a tree-structured CSP by deleting a minimum number of arcs and
then to find all solutions of the resulting CSP (higher the solution count, easier the CSP).

For randomly generated problems, and probably in general, the work involved in
assessing each value is not worth the benefit of choosing a value which will on average be more
likely to lead to a solution than the default choice. In particular problems, on the other hand,
 117
SSM COLLEGE OF ARTS & SCIENCE
DEPARTMENT OF ARTIFICIAL INTELLIGENCE
II [Link] ARTIFICIAL INTELLIGENCE & DATA SCIENCE FOUNDATION OF ARTIFICIAL INTELLIGENCE

there may be information available which allows the values to be ordered according to the
principle of choosing first those most likely to succeed.

6.3.3 Intelligent backtracking: Looking backward

Artificial Intelligence: Backtracking is a key technique used in artificial intelligence to
solve problems related to planning, decision-making, and optimization. Examples include
pathfinding, route planning, and constraint satisfaction problems in robotics and other AI
applications.

Chronological backtracking is one way to work on a faulty plan; it begins as soon as a

dead end is detected. The procedure is to withdraw the most recently made choice, and its
consequences, to select an alternative at that choice point, and to move ahead again

An Intelligent Backtracking Algorithm is a Constraint Satisfaction Algorithm based on

informed search that backtracks an unsolvable search problem to a previous solvable search
problem. AKA: Dependency Directed Backtracking. Example(s)

6.4 LOCAL SEARCH FOR CSPS

In constraint satisfaction, local search is an incomplete method for finding a solution to a
problem. It is based on iteratively improving an assignment of the variables until all constraints
are satisfied. In particular, local search algorithms typically modify the value of a variable in an
assignment at each step

Min-Conflicts solves the N-Queens Problem by selecting a column from the chess board
for queen reassignment. The algorithm searches each potential move for the number of conflicts
(number of attacking queens), shown in each square.

6.5 THE STRUCTURE OF PROBLEMS

A problem can be defined by five components: • initial state, actions, transition model,
goal test, path cost. INITIAL STATE: The initial state that the agent starts in. ACTIONS: A
description of the possible actions available to the agent.

Every problem has a goal state that must be attained, a defined set of initial states, and potential
actions or moves.

There are basically three types of problem in artificial intelligence:

1. Ignorable: In which solution steps can be ignored.

2. Recoverable: In which solution steps can be undone.

3. Irrecoverable: Solution steps cannot be undo.

 118
SSM COLLEGE OF ARTS & SCIENCE
DEPARTMENT OF ARTIFICIAL INTELLIGENCE
II [Link] ARTIFICIAL INTELLIGENCE & DATA SCIENCE FOUNDATION OF ARTIFICIAL INTELLIGENCE

Steps problem-solving in AI: The problem of AI is directly associated with the nature of
humans and their activities. So we need a number of finite steps to solve a problem which
makes human easy [Link] are the following steps which require to solve a problem:

 Problem definition: Detailed specification of inputs and acceptable system solutions.

 Problem analysis: Analyse the problem thoroughly.

 Knowledge Representation: collect detailed information about the problem and define
all possible techniques.

 Problem-solving: Selection of best techniques.

Components to formulate the associated problem:

 Initial State: This state requires an initial state for the problem which starts the AI agent
towards a specified goal. In this state new methods also initialize problem domain solving
by a specific class.

 Action: This stage of problem formulation works with function with a specific class taken
from the initial state and all possible actions done in this stage.

 Transition: This stage of problem formulation integrates the actual action done by the
previous action stage and collects the final stage to forward it to their next stage.

 Goal test: This stage determines that the specified goal achieved by the integrated
transition model or not, whenever the goal achieves stop the action and forward into the
next stage to determines the cost to achieve the goal.

 Path costing: This component of problem-solving numerical assigned what will be the
cost to achieve the goal. It requires all hardware software and human working cost .

6.5.1 Cutset conditioning

Cutset Conditioning is a technique for solving nearly-tree-structured CSPs in which some

variables are assigned to separately from the rest, removed from the constraint graph and
leaving a tree-structured CSP for those remaining.

The first way to reduce a constraint graph to a tree involves assigning values to some
variables so that the remaining variables form a tree. Consider the constraint graph for Australia,
shown again in Figure 6.12(a). Without South Australia, the graph would become a tree, as in
(b). Fortunately, we can delete South Australia (in the graph, not the country) by fixing a value
for SA and deleting from the domains of the other variables any values that are inconsistent with
the value chosen for SA.
 119
SSM COLLEGE OF ARTS & SCIENCE
DEPARTMENT OF ARTIFICIAL INTELLIGENCE
II [Link] ARTIFICIAL INTELLIGENCE & DATA SCIENCE FOUNDATION OF ARTIFICIAL INTELLIGENCE

Now, any solution for the CSP after SA and its constraints are removed will be consistent
with the value chosen for SA. (This works for binary CSPs; the situation is more complicated
with higher-order constraints.) Therefore, we can solve the remaining tree with the algorithm
given above and thus solve the whole problem. Of course, in the general case (as opposed to ap
coloring), the value chosen for SA could be the wrong one, so we would need to try each ossible
value. The general algorithm is as follows:

1. Choose a subset S of the CSP’s variables such that the constraint graph becomes a tree after
removal of S. S is called a cycle cutset.

2. For each possible assignment to the variables in S that satisfies all constraints on S,

o remove from the domains of the remaining variables any values that are inconsistent
with the assignment for S, and

o if the remaining CSP has a solution, return it together with the assignment for S.

6.5.2 Tree decomposition

A tree-decomposition of a graph G is a representation of G in a tree-like structure. From

this structure it is possible to deduce certain connectivity properties of G. Such information can
be used to construct efficient algorithms to solve problems on G.

The second way to reduce a constraint graph to a tree is based on constructing a tree
decomposition of the constraint graph: a transformation of the original graph into a tree where
each Tree decomposition node in the tree consists of a set of variables, as in Figure 6.13. A tree
decomposition must satisfy these three requirements:

 Every variable in the original problem appears in at least one of the tree nodes.
 120
SSM COLLEGE OF ARTS & SCIENCE
DEPARTMENT OF ARTIFICIAL INTELLIGENCE
II [Link] ARTIFICIAL INTELLIGENCE & DATA SCIENCE FOUNDATION OF ARTIFICIAL INTELLIGENCE

 If two variables are connected by a constraint in the original problem, they must appear
together (along with the constraint) in at least one of the tree nodes.

 If a variable appears in two nodes in the tree, it must appear in every node along the path
connecting those nodes.

 The first two conditions ensure that all the variables and constraints are represented in the
tree decomposition.

 The third condition seems rather technical, but allows us to say that any variable from the
original problem must have the same value wherever it appears: the constraints in the tree
say that a variable in one node of the tree must have the same value as the corresponding
variable in the adjacent node in the tree.

For example, SA appears in all four of the connected nodes in Figure 6.13, so each edge in
the tree decomposition therefore includes the constraint that the value of SA in one node must be
the same as the value of SA in the next. You can verify from Figure 6.12 that this decomposition
makes sense.

Once we have a tree-structured graph, we can apply TREE-CSP-SOLVER to get a solution

in O(nd2) time, where n is the number of tree nodes and d is the size of the largest domain. But
note that in the tree, a domain is a set of tuples of values, not just individual values.

For example, the top left node represents, at the level of the original problem, a subproblem with

variables {WA,NT,SA}, domain {red,green,blue}, and

constraints WA 6= NT,SA 6= NT,WA 6= SA.

 121
SSM COLLEGE OF ARTS & SCIENCE
DEPARTMENT OF ARTIFICIAL INTELLIGENCE
II [Link] ARTIFICIAL INTELLIGENCE & DATA SCIENCE FOUNDATION OF ARTIFICIAL INTELLIGENCE

At the level of the tree, the node represents a single variable, which we can call
SANTWA, whose value must be a three-tuple of colors, such as (red,green,blue), but not (red,
red,blue), because that would violate the constraint SA 6= NT from the original problem.

We can then move from that node to the adjacent one, with the variable we can call
SANTQ, and find that there is only one tuple, (red,green,blue), that is consistent with the choice
for SANTWA. The exact same process is repeated for the next two nodes, and independently we
can make any choice for T.

The complexity of solving a CSP is strongly related to the structure of its constraint
graph. Tree-structured problems can be solved in linear time. Cutset conditioning can reduce a
general CSP to a tree-structured one and is quite efficient (requiring only linear memory) if a
small cutset can be found.

Tree decomposition techniques transform the CSP into a tree of subproblems and are
efficient if the tree width of the constraint graph is small; however they need memory
exponential in the tree width of the constraint graph. Combining cutset conditioning with tree
decomposition can allow a better t of mem versus time.