Unit II: Problem Solving

Adversarial Search - Games - Optimal Decisions in Games, Alpha–Beta Pruning

Constraint Satisfaction Problems - Defining Constraint Satisfaction Problems, Constraint
Propagation, Backtracking Search for CSPs
Knowledge – Logical Agents – Knowledge-Based Agents, Logic, Propositional Logic,
Propositional Theorem Proving

Optimal Decisions in Games - The Setting

 Games like Chess, Tic-Tac-Toe, Checkers, Go involve two players making moves
alternatively.
 Players are typically:
o MAX → tries to maximize the utility (score).
o MIN → tries to minimize the utility (score, from MAX’s perspective).
 The game is modeled as a search problem:
o Initial state → starting board position.
o Successor function → legal moves.
o Terminal test → game over state.
o Utility function → numerical value for win/loss/draw.

Minimax Decision Rule

The standard way to make optimal decisions in two-player, zero-sum, perfect-information

games is the Minimax Algorithm.

 MAX’s turn: choose the move with the maximum value.

 MIN’s turn: choose the move with the minimum value.

Algorithm

Procedure MINIMAX(node, depth, isMaximizingPlayer):

if node is terminal OR depth = 0 then

return Utility(node)

if isMaximizingPlayer then

bestValue ← -∞

for each child in Expand(node) do

val ← MINIMAX(child, depth-1, false)

bestValue ← max(bestValue, val)

return bestValue

else
 bestValue ← +∞

for each child in Expand(node) do

val ← MINIMAX(child, depth-1, true)

bestValue ← min(bestValue, val)

return bestValue

Alpha-Beta Pruning (Optimization)

 A refinement of Minimax.
 Cuts off parts of the game tree that cannot affect the final decision.
 Uses two bounds:
o α (alpha): best value that MAX can guarantee.
o β (beta): best value that MIN can guarantee.
 Prunes (skips) branches when α ≥ β.
 Greatly reduces the number of nodes explored.

Algorithm

Procedure ALPHA_BETA(node, depth, α, β, isMaximizingPlayer):

if node is terminal OR depth = 0 then

return Utility(node)

if isMaximizingPlayer then

value ← -∞

for each child in Expand(node) do

value ← max(value, ALPHA_BETA(child, depth-1, α, β, false))

α ← max(α, value)

if α ≥ β then

break // β cut-off

return value

else

value ← +∞

for each child in Expand(node) do

 value ← min(value, ALPHA_BETA(child, depth-1, α, β, true))

β ← min(β, value)

if α ≥ β then

break // α cut-off

return value

Properties

 Optimality: Same as Minimax.

 Completeness: Yes (for finite trees).
 Time complexity:
o Worst case: O(bm)O(b^m)O(bm) (same as Minimax).
o Best case: O(bm/2)O(b^{m/2})O(bm/2) with good move ordering.
 Space complexity: O(bm)O(bm)O(bm) (depth-first recursion).

Properties of Optimal Decisions

 Optimality: If both players play optimally, the minimax decision is guaranteed to

give the best achievable outcome for MAX.
 Completeness: Yes (for finite games).
 Time complexity:
o Minimax → O(bm)O(b^m)O(bm), where
 b = branching factor,
 m = maximum depth of the game tree.
o Alpha-Beta → O(bm/2)O(b^{m/2})O(bm/2) in the best case.
 Space complexity: O(bm)O(bm)O(bm) (depth-first recursion).

Examples: Refer to the PPTs

Constraint Satisfaction Problems

Sometimes a problem is not embedded in a long set of action sequences but requires picking
the best option from available choices. A good general-purpose problem solving technique is
to list the constraints of a situation (either negative constraints, like limitations, or positive
elements that you want in the final solution). Then pick the choice that satisfies most of the
constraints.

Formally speaking, a constraint satisfaction problem (or CSP) is defined by a set of variables,
X1;X2; : : : ;Xn, and a set of constraints, C1;C2; : : : ;Cm. Each variable Xi has anonempty
domain Di of possible values. Each constraint Ci involves some subset of tvariables and
specifies the allowable combinations of values for that subset. A state of theproblem is
defined by an assignment of values to some or all of the variables, {Xi = vi;Xj =vj ; : : :} An
assignment that does not violate any constraints is called a consistent or legalassignment. A
complete assignment is one in which every variable is mentioned, and a solution to a CSP is a
complete assignment that satisfies all the constraints. Some CSPs also require a solution that
maximizes an objectivefunction.

CSP can be given an incremental formulation as a standard search problem as follows:

1. Initial state: the empty assignment fg, in which all variables are unassigned.

2. Successor function: a value can be assigned to any unassigned variable, provided that it
does not conflict with previously assigned variables.

3. Goal test: the current assignment is complete.

4. Path cost: a constant cost for every step

Examples:

1. The best-known category of continuous-domain CSPs is that of linear programming

problems, where constraints must be linear inequalities forming a convex region.

2. Crypt arithmetic puzzles.

Example: The map coloring problem.

The task of coloring each region red, green or blue in such a way that no neighboring regions
have the same color.
We are given the task of coloring each region red, green, or blue in such a way that the
neighboring regions must not have the same color.

To formulate this as CSP, we define the variable to be the regions: WA, NT, Q, NSW, V, SA,
and T. The domain of each variable is the set {red, green, blue}. The constraints require
neighboring regions to have distinct colors: for example, the allowable combinations for WA
and NT are the pairs {(red,green),(red,blue),(green,red),(green,blue),(blue,red),(blue,green)}.
(The constraint can also be represented as the inequality WA ≠ NT). There are many possible
solutions, such as {WA = red, NT = green, Q = red, NSW = green, V = red, SA = blue, T =
red}.Map of Australia showing each of its states and territories

Constraint Graph: A CSP is usually represented as an undirected graph, called constraint

graph where the nodes are the variables and the edges are the binary constraints.

The map-coloring problem represented as a constraint graph.

CSP can be viewed as a standard search problem as follows:

> Initial state : the empty assignment {},in which all variables are unassigned.
> Successor function: a value can be assigned to any unassigned variable, provided that it
does not conflict with previously assigned variables.

> Goal test: the current assignment is complete.

> Path cost: a constant cost(E.g.,1) for every step.

Backtracking Search for CSPs

Basic Idea of Backtracking Search

 Assign values to variables one at a time.

 If a partial assignment violates a constraint, backtrack (undo last assignment and try
another value).

 If all variables are assigned without conflict → solution found.

Algorithm

Procedure BACKTRACKING_SEARCH(CSP):

return BACKTRACK({}, CSP)

Procedure BACKTRACK(assignment, CSP):

if assignment is complete then

return assignment

var ← SELECT_UNASSIGNED_VARIABLE(CSP, assignment)

for each value in ORDER_DOMAIN_VALUES(var, assignment, CSP) do

if value is consistent with assignment given CSP then

add {var = value} to assignment

result ← BACKTRACK(assignment, CSP)

if result ≠ failure then

return result

remove {var = value} from assignment

return failure

Key Components

 SELECT_UNASSIGNED_VARIABLE → decides which variable to assign next.

o Heuristics: MRV (Minimum Remaining Values), Degree Heuristic.

  ORDER_DOMAIN_VALUES → decides order of values.

o Heuristic: Least Constraining Value.

 Consistency Check → ensures no constraint is violated.

 Backtracking → if stuck, undo last choice and try another.

Properties

 Completeness: Yes (for finite CSPs).

 Optimality: Finds a solution if one exists, but not necessarily optimal (unless
combined with optimization).
 Time Complexity: Worst case O(dn), where d = domain size, n = number of
variables.
 Space Complexity: O(n) (linear in number of variables, since it stores current
assignment).

In practice, Backtracking Search is made much more efficient with heuristics + inference:

 Forward Checking → eliminates inconsistent values early.

 Arc Consistency (AC-3 algorithm) → enforces local consistency.
 MRV & LCV heuristics → reduce branching factor.

Forward Checking in CSPs

 Forward Checking is an inference technique used during Backtracking Search.

 When a variable is assigned, Forward Checking looks ahead and eliminates
inconsistent values from the domains of unassigned variables.
 This reduces search space and helps detect failure early, before exploring deeper.

How it Works

1. Choose a variable X and assign it a value v.

2. For every unassigned variable Y that shares a constraint with X:
o Remove from Domain(Y) all values that are inconsistent with X = v.
3. If any domain becomes empty, backtrack immediately.

Algorithm

Procedure FORWARD_CHECKING(CSP, assignment, var, value):

for each neighbor Y of var not yet assigned do

for each val in Domain(Y) do

if (var=value, Y=val) violates a constraint then

remove val from Domain(Y)

 if Domain(Y) is empty then

return false // failure (inconsistent)

return true

Advantages

 Detects failure earlier than plain backtracking.

 Reduces branching factor by pruning domains.

Limitations

 Only looks one step ahead (local consistency).

 Cannot detect deeper inconsistencies (needs stronger inference like Arc Consistency /
AC-3).

So, Forward Checking = Backtracking + Early domain filtering.

It’s often combined with MRV (Minimum Remaining Values) heuristic for maximum
efficiency.

Arc Consistency in CSPs

What is Arc Consistency?

 An arc is a directed constraint between two variables: (X→Y)(X \rightarrow

Y)(X→Y).

 A CSP is arc-consistent if:

For every value x in Domain(X), there exists some value y in Domain(Y) such that the
constraint between X and Y is satisfied.

In other words: every value of X must be supported by at least one compatible value of Y.
If not, remove x from Domain(X).

Why Use Arc Consistency?

 It prunes inconsistent values before or during search.

 Stronger than Forward Checking (which only looks ahead after an assignment).

 Helps detect failure early by shrinking domains.

Algorithm

Procedure AC-3(CSP):

queue ← set of all arcs (Xi, Xj) in CSP

 while queue is not empty do

(Xi, Xj) ← remove an arc from queue

if REVISE(Xi, Xj) then

if Domain(Xi) is empty then

return false // inconsistency found

for each Xk in Neighbors(Xi) - {Xj} do

add (Xk, Xi) to queue

return true

Procedure REVISE(Xi, Xj):

revised ← false

for each value x in Domain(Xi) do

if no value y in Domain(Xj) satisfies constraint(Xi, Xj) then

remove x from Domain(Xi)

revised ← true

return revised

Properties

 Completeness: Ensures local consistency (not full solution, but prunes search).

 Time Complexity: O(cd3), where

o c = number of constraints,

o d = domain size.

 When used: Before backtracking search (preprocessing), or during search to prune

domains dynamically.

Minimum Remaining Values (MRV) — Variable Ordering

Definition:

 Also called the ―most constrained variable‖ heuristic.

 When selecting the next variable to assign:

Choose the variable with the fewest legal values left in its domain.

Why?

 If a variable has very few options, it is more likely to fail.

 Assigning it early detects failure sooner, reducing wasted search.

Least Constraining Value (LCV) — Value Ordering

Definition:

 When choosing a value for a variable:

Choose the value that rules out the fewest options for neighboring variables.

Why?

 Keeps future flexibility high.

 Reduces chance of dead-ends later in the search.

Properties

 MRV reduces the branching factor by choosing the most critical variable.
 LCV reduces chances of backtracking by preserving options.
 Both are heuristics (don’t guarantee optimality, but improve efficiency).
Knowledge Based Agents

A knowledge-based agent needs a KB and an inference mechanism. It operates by storing

sentences in its knowledge base, inferring new sentences with the inference mechanism, and
using them to deduce which actions to take. ... The interpretation of a sentence is the fact to
which it refers.

Knowledge base = set of sentences in a formal language Declarative approach to building an

agent (or other system): Tell it what it needs toknow – Then it can Ask itself what to do—
answers should follow from the KB Agents can be viewed at the knowledge level i.e., what
they know, regardless of how implemented or at the implementation level i.e., data structures
in KB and algorithms that manipulate them. The Wumpus World:

A variety of "worlds" are being used as examples for Knowledge Representation, Reasoning,
and Planning. Among them the Vacuum World, the Block World, and the Wumpus World.
The Wumpus World was introduced by Genesereth, and is discussed in Russell-Norvig. The
Wumpus World is a simple world (as is the Block World) for which to represent knowledge
and to reason. It is a cave with a number of rooms, represented as a 4x4 square
Rules of the Wumpus World: The neighborhood of a node consists of the four squares
north, south, east, and west of the given square. In a square the agent gets a vector of
percepts, with components Stench, Breeze, Glitter, Bump, Scream For example [Stench,
None, Glitter, None, None]

 Stench is perceived at a square iff the wumpus is at this square or in its neighborhood.
 Breeze is perceived at a square iff a pit is in the neighborhood of this square.
 Glitter is perceived at a square iff gold is in this square
 Bump is perceived at a square iff the agent goes Forward into a wall
 Scream is perceived at a square iff the wumpus is killed anywhere in the cave An
agent can do the following actions (one at a time): Turn (Right), Turn (Left), Forward,
Shoot, Grab, Release, Climb

The agent can go forward in the direction it is currently facing, or Turn Right, or Turn Left.
Going forward into a wall will generate a Bump percept.

The agent has a single arrow that it can shoot. It will go straight in the direction faced by the
agent until it hits (and kills) the wumpus, or hits (and is absorbed by) a wall.

The agent can grab a portable object at the current square or it can Release an object that it is
holding.

The agent can climb out of the cave if at the Start square. The Start square is (1,1) and
initially the agent is facing east. The agent dies if it is in the same square as the wumpus. The
objective of the game is to kill the wumpus, to pick up the gold, and to climb out with it.
Representing our Knowledge about the Wumpus World Percept(x, y) Where x must be a
percept vector and y must be a situation. It means that at situation y the agent perceives x. For
convenience we introduce the following definitions:

 Percept([Stench,y,z,w,v],t) = > Stench(t)

 Percept([x,Breeze,z,w,v],t) = > Breeze(t)
 Percept([x,y,Glitter,w,v],t) = > AtGold(t) Holding(x, y)

Where x is an object and y is a situation. It means that the agent is holding the object x in
situation y. Action(x, y) Where x must be an action (i.e. Turn (Right), Turn (Left), Forward,)
and y must be a situation. It means that at situation y the agent takes action x. At(x,y,z)
Where x is an object, y is a Location, i.e. a pair [u,v] with u and v in {1, 2, 3, 4}, and z is a
situation. It means that the agent x in situation z is at location y. Present(x,s) Means that
object x is in the current room in the situation s. Result(x, y) It means that the result of
applying action x to the situation y is the situation Result(x,y).Notethat Result(x,y) is a term,
not a statement.

For example we can say

 Result(Forward, S0) = S1
 Result(Turn(Right),S1) = S2
These definitions could be made more general. Since in the Wumpus World there is a single
agent, there is no reason for us to make predicates and functions relative to a specific agent.
In other "worlds" we should change things appropriately.

Logic in AI

 Logic is the mathematical language of reasoning.

 It allows AI systems to represent knowledge and perform inference to make
intelligent decisions.

What is Logic?

 A formal system for representing statements about the world.

 Provides rules to determine whether statements are true or false.
 Used to infer new facts from existing ones.

In AI: Logic = Knowledge Representation + Reasoning.

Components of Logic

Every logical system has:

1. Syntax (form)
o Defines how valid sentences (formulas) are constructed.
o Example: In propositional logic, (P ∧ Q) → R is valid, but P ∨ ∧ Q is invalid.
2. Semantics (meaning)
o Assigns truth values to logical sentences with respect to the world.
o Example: If P = "It is raining" is true, then ¬P ("It is not raining") is false.
3. Pragmatics (use)
o How logic is applied for reasoning in AI systems.

Propositional Logic (PL)

 Deals with atomic propositions (true/false).

 Operators: ¬ (NOT), ∧ (AND), ∨ (OR), → (IMPLIES), ↔ (IFF).
 Example:
o P: "It is raining."
o Q: "The ground is wet."
o Rule: P → Q.
o If P = True, then Q must be True.

Simple but limited (cannot express relations, objects, quantifiers).

Inference in Logic

Inference = deriving new knowledge from known facts.

Common Inference Rules:

 Modus Ponens:
 P → Q, P

--------

 Modus Tollens:

P → Q, ¬Q

--------

¬P

 Resolution:

A ∨ B, ¬B ∨ C ⇒ A ∨ C

 Generalized Modus Ponens (FOL):

∀x (P(x) → Q(x)), P(a) ⇒ Q(a).

Theorem Proving in Logic

Given: Knowledge Base (KB) and query α.

Check if KB ⊨ α (KB entails α).

Methods:

1. Truth Table Checking (for PL): brute-force evaluation.

2. Inference Rules (Modus Ponens, Resolution, etc.).

3. Resolution Theorem Proving (used in FOL & PL).

4. Refutation Method: add ¬α to KB, try to derive contradiction.

Validity And Satisfiability

A sentence is valid if it is true in all models, e.g.,True, A∨¬A, A⇒A, (A∧(A⇒B)) ⇒B

Validity is connected to inference via the Deduction Theorem:

KB |= α if and only if (KB⇒α) is valid

A sentence is satisfiable if it is true in some model e.g., A∨B, C

A sentence is unsatisfiable if it is true in no models e.g., A ∧¬A

Satisfiability is connected to inference via the following: KB|=α iff (KB∧¬α) is unsatisfiable
i.e., prove α by reduction
Conjunctive Normal Form (CNF)

Definition: A formula is in Conjunctive Normal Form (CNF) if it is a conjunction (AND,

∧) of one or more clauses, where each clause is a disjunction (OR, ∨) of literals.

 Literal = A proposition (P) or its negation (¬P).

 Clause = OR of literals.

 CNF = AND of clauses.

Example CNF form:

(P∨¬Q∨R) ∧ (¬P∨S) ∧ (Q∨R

Here:

 Clause 1 = (P ∨ ¬Q ∨ R)
 Clause 2 = (¬P ∨ S)
 Clause 3 = (Q ∨ R)

Why CNF is Important in AI

 Standard form for automated theorem proving.

 Resolution method (used in inference engines) requires CNF.
 SAT solvers (Boolean satisfiability) take CNF input.

Conversion to CNF (Steps)

To convert any propositional logic formula into CNF:

1. Eliminate bi-conditional (↔) and implication (→):

o P→Q≡(¬P∨Q)
o P↔Q≡(P→Q)∧(Q→P)
2. Move NOT (¬) inward using De Morgan’s laws:
o ¬(P ∧ Q) ≡ (¬P ∨ ¬Q)
o ¬(P ∨ Q) ≡ (¬P ∧ ¬Q)
o Also eliminate double negation (¬¬P ≡ P).
3. Apply distributive law to get AND-of-ORs form:
o (P ∨ (Q ∧ R)) ≡ (P ∨ Q) ∧ (P ∨ R).
4. Flatten nesting if needed.

Example Conversion

Convert:

(P→Q)∧(Q→R)

Step 1: Eliminate implications

  P→Q≡(¬P∨Q)
 Q→R≡(¬Q∨R)

So formula becomes:

(¬P∨Q)∧(¬Q∨R)

Step 2: Already in CNF (AND of ORs).

Final CNF:

(¬P∨Q)∧(¬Q∨R)

Another Example

Convert:

¬(P∨Q)→R

Step 1: Remove implication

¬(¬(P∨Q))∨R

Step 2: Simplify double negation

(P∨Q)∨R

Step 3: Flatten ORs

(P∨Q∨R)

Final CNF: Single clause.