Constraint Satisfaction and Adversarial Search

Introduction

Many artificial intelligence problems are not solved by predicting a single answer from data. Instead, they require an agent to construct a solution that satisfies a collection of restrictions, or to choose an action while another intelligent agent is actively attempting to prevent success. Timetabling, map coloring, resource allocation, diagnosis, planning, chess, checkers, and automated negotiation all illustrate these two broad problem types.

A constraint satisfaction problem (CSP) represents a problem through variables, possible values, and restrictions on which combinations of values are acceptable. CSP algorithms exploit the structure of these restrictions to reduce search. An adversarial search problem represents decision-making in an environment containing competing agents, usually with opposing objectives. Game-tree search, minimax, and alpha-beta pruning are central methods for such settings.

These topics are important because they demonstrate a central principle of AI: intelligent behavior often depends less on blindly exploring possibilities than on representing a problem appropriately and eliminating impossible or inferior alternatives early.

Learning Objectives

By the end of this chapter, you should be able to:

• Define a constraint satisfaction problem using variables, domains, and constraints.
• Distinguish unary, binary, and global constraints.
• Apply consistency techniques, including node, arc, and path consistency.
• Use backtracking search with variable-ordering and value-ordering heuristics.
• Explain the role of constraint propagation and conflict-directed backjumping.
• Model deterministic, turn-taking games as adversarial search problems.
• Construct and evaluate game trees using minimax.
• Explain alpha-beta pruning and identify conditions that improve its performance.
• Analyze practical, ethical, and computational limitations of CSP and adversarial-search systems.

1. Constraint Satisfaction Problems

1.1 Formal model

A constraint satisfaction problem is commonly represented as a triple:

\[

CSP = (X, D, C)

\]

where:

• \(X = \{X_1, X_2, \ldots, X_n\}\) is a set of variables;
• \(D = \{D_1, D_2, \ldots, D_n\}\) gives each variable \(X_i\) a domain \(D_i\) of permitted values;
• \(C\) is a set of constraints restricting allowable combinations of values.

A solution is a complete assignment of values to all variables such that every constraint is satisfied. A partial assignment may be consistent with the constraints considered so far without being a complete solution.

For example, in a university examination timetable, variables may represent examinations, domains may represent available time rooms or periods, and constraints may prohibit two examinations taken by the same student from occurring simultaneously. A solution assigns every examination a valid slot while respecting capacity, availability, and conflict restrictions.

CSPs differ from ordinary state-space search because the order in which variables are assigned is usually irrelevant. The important question is whether the final combination of assignments satisfies the constraints. This permits specialized algorithms that exploit relationships among variables.

1.2 Types of constraints

A unary constraint restricts one variable, such as \(X \neq \text{Monday}\). A binary constraint relates two variables, such as \(X \neq Y\). A higher-order constraint relates three or more variables. For example, a capacity restriction may require the sum of selected resource demands to remain below a limit.

A global constraint is a compact constraint with a recognized structure. The `AllDifferent` constraint requires a group of variables to take pairwise distinct values. Global constraints can be more informative and computationally efficient than representing the same requirement through many separate binary constraints.

Constraints may also be:

• Hard constraints, which must never be violated;
• Soft constraints, which express preferences and may be violated at a cost;
• Extensional constraints, specified by explicitly listing permitted or forbidden tuples;
• Intensional constraints, specified by a rule or predicate.

When soft constraints are present, the task may be optimization rather than simple feasibility. A solution can be evaluated using a cost function, and the objective becomes finding a feasible assignment with minimum cost or maximum utility.

1.3 Constraint graphs

A binary CSP can be represented by a constraint graph. Each variable is a node, and an edge connects two variables when a constraint relates them. The graph helps identify independent subproblems and guides variable ordering.

A graph with few edges may be easier than a densely connected graph, even if both contain the same number of variables. If the graph separates into disconnected components, each component can be solved independently. If a graph has a tree structure, specialized algorithms can solve it substantially more efficiently than unrestricted backtracking.

The graph representation also supports structural reasoning. A variable connected to many others is highly constrained in its relationships and is often a good candidate for early assignment. This observation motivates the degree heuristic discussed later.

2. Constraint Propagation and Consistency

Blindly assigning values and waiting until the end to discover a contradiction is inefficient. Constraint propagation removes values that cannot participate in any valid solution. Propagation can occur before search or after every assignment during search.

2.1 Node consistency

A variable is node-consistent if every value in its domain satisfies all unary constraints on that variable. If a scheduling variable has domain `{Monday, Tuesday, Wednesday}` and a unary constraint forbids Monday, propagation removes Monday immediately.

2.2 Arc consistency

For a binary constraint between variables \(X\) and \(Y\), an arc from \(X\) to \(Y\) is consistent if every value in the current domain of \(X\) has at least one supporting value in the domain of \(Y\) satisfying the constraint.

A value with no support is called a domain value without a support and can be deleted. For example, suppose:

\[

D(X)=\{1,2,3\}, \quad D(Y)=\{2,3\}, \quad X<Y.

\]

The value 3 for \(X\) has no supporting value in \(D(Y)\), so it is removed. The value 1 has support 2 or 3, and value 2 has support 3. The revised domain is therefore \(D(X)=\{1,2\}\).

Arc consistency does not necessarily produce a complete solution. It only guarantees that each remaining value has local support. A value may have support in each neighboring domain while no globally consistent combination exists.

The AC-3 algorithm establishes arc consistency by maintaining a queue of arcs. When an arc is revised and a domain changes, arcs involving the affected variable are reconsidered. In a common implementation, the worst-case time complexity is expressed as \(O(ed^3)\), where \(e\) is the number of directed arcs and \(d\) is the maximum domain size. Actual performance depends on data structures and the number of revisions.

2.3 Higher levels of consistency

Path consistency considers whether pairs of values for two variables can be extended consistently through a third variable. It is stronger than arc consistency but generally more expensive.

k-consistency states that any consistent assignment to \(k-1\) variables can be extended to a kth variable. Stronger consistency can reduce search, but enforcing it costs computational time. Effective CSP solvers balance propagation strength against propagation expense.

Worked Example: Map Coloring

Consider three regions \(A\), \(B\), and \(C\), each with domain \(\{Red, Green, Blue\}\). Suppose adjacent regions must have different colors, and all three regions are mutually adjacent.

The constraints are:

\[

A \neq B, \quad B \neq C, \quad A \neq C.

\]

Assigning \(A=Red\) causes propagation to remove Red from the domains of \(B\) and \(C\). If we next assign \(B=Green\), propagation removes Green from \(C\), leaving \(C=Blue\). The assignment is complete and valid. If a fourth mutually adjacent region were added while only three colors remained, propagation would eventually produce an empty domain, proving that no solution exists under those conditions.

An empty domain is an immediate indication of failure. It is not merely a poor partial assignment; it proves that the current branch cannot lead to a solution.

3. Backtracking Search and Heuristics

3.1 Basic backtracking

Backtracking is a depth-first search procedure specialized for CSPs. It selects an unassigned variable, assigns a value, checks consistency, and recursively continues. When a contradiction occurs, it undoes the most recent assignment and tries another value.

Conceptually:

```text

Backtrack(assignment):

if assignment is complete:

return assignment

X := select an unassigned variable

for value in ordered values of X:

if value is consistent with assignment:

add X = value

propagate constraints

result := Backtrack(assignment)

if result succeeds:

return result

undo assignment and propagation

return failure

```

In the worst case, if there are \(n\) variables and each has at most \(d\) values, exhaustive search may examine up to \(d^n\) complete assignments. This is an upper bound, not a prediction of actual performance. Propagation and heuristics can reduce the explored search tree dramatically.

3.2 Variable-ordering heuristics

The minimum remaining values (MRV) heuristic selects the unassigned variable with the smallest current domain. It is also called the fail-first heuristic: a variable likely to fail is examined early, avoiding wasted work on unrelated variables.

The degree heuristic selects the variable involved in the largest number of constraints with other unassigned variables. It is especially useful as a tie-breaker for MRV because assigning a highly connected variable can produce more propagation.

3.3 Value-ordering heuristics

The least-constraining-value (LCV) heuristic tries first the value that eliminates the fewest options from neighboring variables. If a solution exists, this ordering tends to preserve flexibility.

MRV and LCV have different purposes. MRV chooses which variable to consider; LCV chooses which value to try for that variable. They should not be confused.

3.4 Forward checking and maintaining arc consistency

Forward checking removes from each unassigned neighbor any value inconsistent with a new assignment. If a neighbor's domain becomes empty, the algorithm backtracks immediately.

Maintaining arc consistency (MAC) applies a stronger propagation procedure, often AC-3, after each assignment. MAC usually detects failures earlier than forward checking but incurs more propagation cost. The preferred method depends on problem size, constraint density, and the cost of consistency checks.

3.5 Backjumping and learning

Chronological backtracking returns to the most recently assigned variable. Backjumping analyzes the cause of failure and returns directly to a relevant earlier variable, skipping assignments that could not have caused the contradiction.

Modern solvers may also record nogoods: combinations of assignments known to be impossible. A learned nogood prevents the solver from repeating the same unsuccessful reasoning in another branch. This connects CSP solving with techniques used in satisfiability and constraint programming.

4. A Detailed Application: University Examination Scheduling

Background

A university must schedule examinations for a semester. Each examination requires a room and a time period. Students enrolled in multiple courses must not face simultaneous examinations. Rooms have capacities, equipment requirements, and availability restrictions.

Problem formulation

Let each examination be a variable. Its domain consists of feasible pairs such as `(Tuesday 10:00, Room 204)`. Constraints include:

• examinations sharing students cannot use the same time period;
• room capacity must meet enrollment;
• a room cannot host two examinations simultaneously;
• laboratories must be assigned rooms with appropriate equipment;
• certain courses may be unavailable during specified periods.

A hard-constraint model can determine whether a valid timetable exists. Soft constraints can represent preferences, such as avoiding consecutive examinations for a student or distributing examinations evenly across the week.

Analysis and approach

The university can first apply unary filtering to remove unavailable periods and rooms. It can then use `AllDifferent`-style reasoning for room-time combinations and binary conflict constraints for student overlaps. Examinations with many enrolled students or many conflicts should receive priority through degree-based ordering. An examination with only two feasible slots should be selected by MRV.

After each tentative assignment, forward checking removes incompatible room-time pairs from neighboring examinations. MAC may be appropriate when the timetable is dense and failures need to be detected early. LCV can try the slot that interferes with the fewest remaining examinations.

Outcome

The resulting schedule is not merely a list generated by arbitrary trial and error. It is a certificate: every examination has a domain value, and every hard constraint has been checked. If soft constraints are included, the system can compare multiple feasible schedules using a weighted objective function.

Learning points

This application illustrates the distinction between feasibility and optimization. It also shows why representation matters. Modeling a domain as room-time pairs may simplify some constraints, while separate time and room variables may support different propagation techniques. Real systems often use hybrid models, global constraints, and optimization solvers rather than a simple hand-coded backtracking routine.

5. Adversarial Search

5.1 From problem solving to competition

In ordinary search, the environment may be passive: an agent selects a path and evaluates its result. In adversarial search, another agent selects actions too. The value of an action depends not only on what the first agent does but also on how the opponent responds.

A game can be modeled using:

• an initial state;
• a player-to-move function;
• legal actions;
• a transition model producing successor states;
• terminal-test conditions;
• a utility function for terminal states.

In a two-player, deterministic, zero-sum game, one player's gain is the other player's loss. Utilities may be represented from the perspective of MAX, the agent attempting to maximize the result. MIN attempts to minimize that same utility.

5.2 Game trees

A game tree contains states as nodes and legal actions as edges. Levels alternate between players. Terminal nodes contain utilities such as win, draw, and loss. The tree may be enormous: even a modest branching factor becomes infeasible at substantial depth.

A ply is one move by one player. A depth of four plies represents two moves by each player in a two-player alternating game. This terminology is useful when reporting search depth.

5.3 Minimax

The minimax principle assumes rational players and computes the value of a state recursively:

\[

V(s)=

\begin{cases}

Utility(s), & \text{if } s \text{ is terminal}\\

\max_{a\in Actions(s)} V(Result(s,a)), & \text{if MAX moves}\\

\min_{a\in Actions(s)} V(Result(s,a)), & \text{if MIN moves.}

\end{cases}

\]

The assumptions are important: the game is modeled accurately, both players choose legal actions, utilities are comparable, and each player acts optimally according to the zero-sum model. If these assumptions fail, minimax may need modification.

Worked Minimax Example

Suppose MAX has two possible actions, Left and Right. After Left, MIN can choose outcomes with utilities 3 and 5. After Right, MIN can choose outcomes with utilities 2 and 9.

MIN selects the smaller utility in each branch:

\[

V(Left)=\min(3,5)=3,

\]

\[

V(Right)=\min(2,9)=2.

\]

MAX therefore selects Left because:

\[

\max(3,2)=3.

\]

The result is not based on the most favorable leaf overall, which is 9. It is based on the best guaranteed result against an opponent who chooses the response most damaging to MAX.

A full minimax search has time complexity \(O(b^m)\), where \(b\) is the average branching factor and \(m\) is the maximum search depth. Its space complexity for depth-first implementation is commonly \(O(bm)\), excluding storage for the full tree. These are asymptotic bounds and depend on implementation details.

6. Alpha-Beta Pruning

Minimax may evaluate branches that cannot affect the final decision. Alpha-beta pruning avoids such branches while returning exactly the same minimax result as exhaustive minimax, provided the same tree and utility assumptions are used.

• \(\alpha\) is the best value MAX can guarantee along the current path.
• \(\beta\) is the best value MIN can guarantee along the current path.

When \(\alpha \geq \beta\), the remaining successors of the current node need not be explored. A MAX node already has an option at least as good as \(\beta\), so MIN would avoid allowing that branch; alternatively, a MIN node already has an option no greater than \(\alpha\), so MAX would avoid relying on it.

In the worst case, alpha-beta pruning has the same asymptotic time complexity as minimax, \(O(b^m)\). With highly favorable move ordering, its effective complexity can approach \(O(b^{m/2})\), allowing roughly twice the search depth for the same branching factor and computational budget. This best-case interpretation depends strongly on ordering; it is not guaranteed.

Good move ordering is therefore crucial. Strong candidate moves should be examined first at MAX nodes, and strong minimizing moves first at MIN nodes. Practical systems use transposition tables, iterative deepening, killer-move heuristics, and domain-specific move ordering. A transposition table stores evaluations of previously encountered states, which is valuable when different move sequences reach the same state.

7. Depth-Limited Search and Evaluation Functions

Games such as chess have trees too large to search to terminal states. Depth-limited minimax stops at a chosen depth and applies a heuristic evaluation function to nonterminal states.

An evaluation function estimates position quality from MAX's perspective. In a simplified board game, it might combine material advantage, positional control, and mobility:

\[

Eval(s)=w_1 f_1(s)+w_2 f_2(s)+\cdots+w_k f_k(s),

\]

where each \(f_i\) is a measurable feature and \(w_i\) is its weight. The formula is meaningful only when feature scales and perspective are defined consistently. A positive value should favor MAX, and the same evaluation convention must be used throughout the search.

Evaluation functions are approximations and can suffer from the horizon effect: an important consequence lies just beyond the search depth, so the system evaluates a position incorrectly. Quiescence search extends analysis in tactically unstable positions until a more stable position is reached. Iterative deepening searches depth one, then depth two, and so on, allowing a time-limited system to retain the best move from the last completed iteration.

8. Beyond Two-Player Zero-Sum Games

Not every competitive environment satisfies minimax assumptions. In games with more than two players, max-n assigns a utility vector and each player maximizes their own component. Cooperation may be temporary, utilities may not be strictly opposed, and strategic behavior becomes more complex.

In stochastic games, chance events are represented by chance nodes and expected utility is required. In partially observable games, an agent must reason over information states rather than fully known states. In real-world multi-agent systems, agents may have different information, bounded rationality, communication policies, and incentives.

These extensions demonstrate that adversarial search is a modeling framework, not a universal description of competition. The choice of algorithm must reflect the number of agents, uncertainty, observability, and relationship among objectives.

9. Practical, Ethical, and Governance Considerations

CSP systems can produce schedules, allocations, or decisions that are formally valid but socially undesirable. A hospital allocation model, for example, may satisfy capacity constraints while unfairly disadvantaging a patient group. Soft constraints and objective functions encode values; they are not neutral technical details.

Organizations should document:

• which constraints are mandatory and who authorized them;
• how priorities and weights were selected;
• what data and assumptions define feasibility;
• how exceptions and human overrides are handled;
• whether outcomes are equitable across affected groups;
• how decisions can be audited and appealed.

Adversarial systems also create governance issues. Game-playing methods can transfer to cybersecurity, negotiation, and strategic planning, where an opponent may exploit predictable behavior. Systems should be tested against adversarial inputs, monitored for unsafe strategies, and constrained by domain-specific rules. In high-impact applications, human oversight and transparent logging are essential.

10. Best Practices and Contemporary Developments

Effective CSP modeling begins with a precise representation rather than immediate algorithm selection. Variables should reflect meaningful decisions, domains should exclude impossible values early, and constraints should be expressed at an appropriate level of granularity. Global constraints can improve both clarity and propagation.

A practical workflow is to:

1. define variables and domains;

2. separate hard constraints from preferences;

3. identify structure in the constraint graph;

4. apply preprocessing and propagation;

5. choose search heuristics suited to the problem;

6. validate solutions independently;

7. measure runtime, failure causes, solution quality, and fairness.

For adversarial search, systems should combine iterative deepening, reliable evaluation functions, transposition tables, and careful move ordering where appropriate. Testing should include unusual positions, ties, repeated states, and time-limit behavior.

Contemporary AI systems often combine symbolic search with machine learning. Learned models may estimate values, rank moves, or guide branching, while symbolic constraints preserve legality and provide verifiable guarantees. This hybrid approach is powerful but introduces new risks: learned guidance can be biased, difficult to explain, or vulnerable to distribution shift. A robust design keeps the distinction between a heuristic preference and a hard validity condition.

Chapter Summary

Constraint satisfaction problems represent decisions using variables, domains, and constraints. Their solutions are complete assignments satisfying all hard restrictions. Constraint graphs expose structural relationships, while node consistency, arc consistency, path consistency, forward checking, and maintaining arc consistency eliminate impossible values before or during search.

Backtracking provides a systematic search method. MRV selects the most restricted variable, the degree heuristic favors highly connected variables, and LCV preserves flexibility by trying less restrictive values first. Backjumping, nogood learning, and global constraints can further improve performance. CSP methods support practical applications such as scheduling, allocation, configuration, and diagnosis, but their objectives and constraints must be reviewed for fairness and governance.

Adversarial search models environments in which agents compete. Minimax selects the best guaranteed action under optimal opposition. Alpha-beta pruning produces the same result as minimax while avoiding branches that cannot influence the decision; its efficiency depends heavily on move ordering. Depth limits, evaluation functions, iterative deepening, quiescence search, and transposition tables make game search practical. More complex settings require extensions for chance, multiple players, partial observability, and non-zero-sum objectives.

Key Terms

Constraint satisfaction problem: A problem defined by variables, domains, and constraints.

Variable: An entity whose value must be selected.

Domain: The set of values currently available to a variable.

Constraint: A rule restricting allowable assignments.

Hard constraint: A restriction that must be satisfied.

Soft constraint: A preference that may be violated at a cost.

Constraint graph: A graph showing variables and their relationships.

Constraint propagation: Removing values that cannot occur in a valid solution.

Arc consistency: A condition in which every domain value has support in a neighboring domain.

Backtracking: Depth-first search that reverses assignments after failure.

MRV heuristic: Selecting the variable with the smallest remaining domain.

Degree heuristic: Selecting the variable connected to the most unassigned variables.

Least-constraining value: A value that eliminates the fewest neighboring options.

Minimax: Adversarial search assuming optimal alternating players.

Game tree: A tree of states and legal actions in a game.

Alpha-beta pruning: Eliminating game-tree branches that cannot affect minimax value.

Ply: One move by one player.

Evaluation function: A heuristic estimate of a nonterminal game state's value.

Horizon effect: Error caused by consequences occurring beyond the search depth.

Transposition table: A cache of previously evaluated game states.

Review Questions

Short Answer Questions

1. What are the three components of a constraint satisfaction problem?

2. How does arc consistency remove values from a variable's domain?

3. What is the purpose of the minimum remaining values heuristic?

4. State the assumptions underlying minimax in a two-player zero-sum game.

5. What does alpha-beta pruning preserve, and what does it avoid?

Long Answer Questions

1. Explain constraint propagation, forward checking, and maintaining arc consistency, comparing their benefits and computational costs.

2. Describe how MRV, the degree heuristic, and least-constraining value work together in backtracking search.

3. Formulate a university examination timetable as a CSP, identifying variables, domains, hard constraints, and soft constraints.

4. Explain minimax using a game tree and discuss why choosing the maximum leaf utility is not generally correct.

5. Discuss depth-limited adversarial search, evaluation functions, the horizon effect, and quiescence search.

Analytical / Application Questions

1. A scheduling CSP has variables with domains of sizes 1, 2, and 4. Which variable should MRV select, and why might the degree heuristic be used afterward?

2. At a MAX node, the current alpha value is 7. A descendant MIN node has already obtained beta value 5. Should the remaining children of that MIN node be explored? Explain.

3. Design a CSP model for assigning hospital operating rooms to surgeries. Identify at least four hard constraints, two soft constraints, and two propagation or ordering techniques suitable for the problem.

Multiple Choice Questions with Answers

Question 1

Which element of a CSP specifies the possible values an individual variable may take?

A. Utility function

B. Domain

C. Game tree

D. Transposition table

Correct Answer: B. Domain

Question 2

What does arc consistency require for each value in a variable's domain?

A. It must be the smallest value available

B. It must support every neighboring value

C. It must have at least one supporting value in the neighboring domain

D. It must satisfy only unary constraints

Correct Answer: C. It must have at least one supporting value in the neighboring domain

Question 3

Which heuristic selects the variable with the fewest remaining legal values?

A. Least-constraining value

B. Degree heuristic

C. Minimum remaining values

D. Random restart

Correct Answer: C. Minimum remaining values

Question 4

What is the main purpose of forward checking?

A. To remove inconsistent values from neighboring unassigned variables

B. To evaluate terminal game utilities

C. To maximize the branching factor

D. To convert a CSP into a game tree

Correct Answer: A. To remove inconsistent values from neighboring unassigned variables

Question 5

In minimax, what does MIN do at its decision nodes?

A. Selects the action with the greatest utility for MAX

B. Selects the action with the smallest backed-up utility

C. Selects a random legal action

D. Always selects the action with the shortest path

Correct Answer: B. Selects the action with the smallest backed-up utility

Question 6

In a zero-sum game, a terminal utility of +10 from MAX's perspective means what?

A. MIN receives +10 as well

B. The state is neutral for both players

C. The outcome favors MAX according to the utility scale

D. The game must continue for ten more plies

Correct Answer: C. The outcome favors MAX according to the utility scale

Question 7

When can alpha-beta pruning stop exploring remaining children at a node?

A. When alpha is greater than or equal to beta

B. When beta is zero only

C. When the node has exactly two children

D. When the search reaches the root

Correct Answer: A. When alpha is greater than or equal to beta

Question 8

What is the best-case time complexity commonly associated with alpha-beta pruning under excellent move ordering?

A. O(1)

B. O(b)

C. O(b^(m/2))

D. O(m^b) regardless of ordering

Correct Answer: C. O(b^(m/2))

Question 9

What problem occurs when an important consequence lies just beyond a depth limit?

A. Arc inconsistency

B. Horizon effect

C. Domain splitting

D. Node consistency

Correct Answer: B. Horizon effect

Question 10

What is the primary role of a transposition table?

A. To store previously evaluated game states

B. To delete all repeated legal moves

C. To enforce unary CSP constraints

D. To replace the utility function with random values

Correct Answer: A. To store previously evaluated game states