3.
Games and Constraint satisfaction problems:
Games - Optimal Decisions in Games - Minimax
Algorithm, Alpha-Beta Pruning Algorithm.
Constraint satisfaction problems – constraint
propagation – backtracking search for CSP – local
search for CSP – structure of CSP.
Games in AI
• Games ,fascinating domain in Artificial Intelligence (AI)
• It provide a well-defined environment where different strategies,
decision-making algorithms, and learning processes can be tested and
applied.
• AI techniques can be used to simulate intelligent behavior in games,
from simple board games to complex real-time simulations.
• The study of AI in games provides practical applications and
theoretical insights into areas such as problem-solving, optimization,
and strategic thinking.
• Goal of Ai agents is to make decision that maximize of winning,
Achieving objective, solving problems
• Adversarial search is a search, where we examine the
problem which Searches in which two or more players with
conflicting goals are trying to explore the same search space
for the solution, are called adversarial searches, often known
as Games.
• Note: Adversarial -two or more agents actively compete
against each other
• A zero-sum game is defined as one where the total payoff to
all players is the same for every instance of the game
Games in AI
zero sum game
Board games: Chess, Go, Tic-
Tac-Toe
Card games: Poker, Bridge
Video games: Strategy games
like StarCraft or real-time
multiplayer games
Puzzle games: Sudoku,
Crossword puzzles
Non-Zero sum Game
Components - To formulate Problem
• A game can be defined as a type of search in AI which can
be formalized of the following steps
• Initial state: It specifies how the game is set up at the start.
• Player(s): It specifies which player has moved in the state space.
• Action(s): It returns the set of legal moves in state space.
• Result(s, a): It is the transition model, which specifies the result
of moves in the state space.
• Terminal-Test(s): Terminal test is true if the game is over, else it
is false at any case. The state where the game ends is called
terminal states.
• Utility(s, p): A utility function gives the final numeric value for a
game that ends in terminal states s for player p. It is also called
payoff function. For Chess, the outcomes are a win, loss, or draw
and its payoff values are +1, 0, ½. And for tic-tac-toe, utility values
are +1, -1, and 0
AI Techniques in Games
Minimax Algorithm
Alpha-Beta Pruning
Monte Carlo Tree Search (MCTS)
Reinforcement Learning (RL)
• Neural Networks and Deep Learning
• Game tree:
• A game tree is a tree where nodes of the tree are the game
states and Edges of the tree are the moves by players.
• Game tree involves initial state, actions function, and result
Function.
• Example: Tic-Tac-Toe game tree:
Following are some key points of the game:
• There are two players MAX and MIN.
• Players have an alternate turn and start with MAX.
• MAX maximizes the result of the game tree
• MIN minimizes the result.
Minimax 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.
• Optimal decision-making in games is a fundamental challenge in the field of Artificial
Intelligence (AI).
• Minimax is a decision-making algorithm commonly used in two-player, zero-sum games
(e.g., chess, tic-tac-toe).
• It involves creating a game tree that represents all possible moves and counter-moves for
both players.
• The algorithm seeks to minimize the maximum possible loss (hence the name "minimax")
by selecting the best move at each turn.
Alpha-Beta Pruning:
• Alpha-beta pruning is an optimization technique used in conjunction with the
minimax algorithm.
• It reduces the number of nodes evaluated in the game tree by eliminating branches
that are guaranteed to be suboptimal.
• Note: Pruning makes the search more efficient by ignoring portions of the search
tree that make no difference to the optimal move
Game tree
• Game tree is a graph that shows all possible moves in a
game. It's a useful tool for AI to determine the best
move in a game.
• Game tree is a search tree that follows every sequence
of moves all the way to terminal state.
• Game tree may be infinite ,if the rules of the game
allows for Infinite Repeating position
Game Trees
• The root of the tree is the initial state
– Next level is all of MAX’s moves
– Next level is all of MIN’s moves
–…
Minimax value of a node (backed up
• Example: Tic-Tac-Toe value): –
– Root has 9 blank squares (MAX) If N is terminal, use the utility value
– Level 1 has 8 blank squares (MIN) –
– Level 2 has 7 blank squares (MAX) If N is a Max move, take max of
successors
–…
If N is a Min move, take min of
• Utility function: successors
– win for X is +1
– win for O is -1
Problem formulation-tic tac toe
[Link] State:- Initial board position.
[Link] Test:- Determines whether the game is over.
[Link] State:- State where the game has ended.
[Link] Function:- Numeric value given to terminal states. For example, in
tic-tac-toe, win = +1, loss = -1 and draw = 0.
[Link]:- Turn of a player.
[Link] Tree:- Initial states and the possible states obtained after legal
moves whose depth is measured in terms of plies.
[Link] strategy:- A strategy that can give outcomes atleast as good as
any other strategy when playing against an unerring player.
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).
Limitation of the minimax Algorithm:
• The main drawback of the minimax
algorithm is that it gets really slow for
complex games such as Chess.
• 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
Pseudo-code for MinMax Algorithm
function minimax(node, depth, maximizingPlayer):
if depth = 0 or node is a terminal node:
return the heuristic value of the node
if maximizingPlayer:
bestValue = -infinity
for each child node of node:
v = minimax(child, depth - 1, FALSE)
bestValue = max(bestValue, v)
return bestValue
else:
bestValue = +infinity
for each child node of node:
v = minimax(child, depth - 1, TRUE)
bestValue = min(bestValue, v)
return bestValue
Alpha-Beta Pruning
• Alpha-beta pruning is a modified version of the minimax
algorithm. It is an optimization technique for the
minimax algorithm.
• 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.
• this involves two threshold parameter Alpha and beta
for future expansion, so it is called alpha-beta
pruning.
Key points about alpha-beta
pruning:
• The Max player will only update the value of alpha.
• The Min player will only update the value of beta.
• We will only pass the alpha, beta values to the child
nodes.
• While backtracking the tree, the node values will
be copied to upper nodes instead of values of alpha and
beta.
Alpha-Beta Pruning
[Link] finds the correct minimax decision without looking at the
each and every node by pruning certain subtrees.
[Link] subtrees can be pruned by just keeping track of the two parameters.
Highest value along the path of MAX
Lowest value along the path of MIN
Two play Game tree
Pruning- when to prune branches
• Maximizing Node (Max's Turn):If, during the evaluation of a node, the algorithm
finds that the current node's value is greater than or equal to β (i.e., value ≥ β), it
means the minimizing player has a better option elsewhere, and this branch cannot
influence the final decision. Therefore, the algorithm prunes this branch.
• Minimizing Node (Min's Turn):If, during the evaluation of a node, the algorithm
finds that the current node's value is less than or equal to α (i.e., value ≤ α), it
means the maximizing player has a better option elsewhere, and this branch
cannot influence the final decision. Therefore, the algorithm prunes this branch.
code
Example
Constraint Satisfaction
Problems
Constraint Satisfaction Problem (CSP) is a mathematical
model where a set of variables must be assigned values that
satisfy a number of constraints or limitations
Objective: To eliminate the large portion of search
space at once by identify the variable combination
that violate constraints
Constraint Satisfaction Problems (CSPs) form a backbone
of many AI applications by providing efficient ways to
solve decision-making tasks with constraints.
Refer to Lab experiments
• N queens
• Suduko
• Graph coloring
Key Components of CSP:
[Link]: Elements that need to be assigned values x=.(x1,x2,
…xn)
[Link]: The possible values that each variable can take,D
=[D1,D2,….Dk]
[Link]: Restrictions that specify allowable combinations of
values among variables.C=[C1,C2….Cm]
• Backtracking Search
• Constraint Propagation
• Local Search
1. Variables:
• Each cell in the 9x9 Sudoku grid represents a variable, totaling 81 variables.
2. Domains:
• The domain for each variable (cell) consists of the integers 1 through 9, representing
the possible values that can be assigned to each cell.
3. Constraints:
• Row Constraints: Each number from 1 to 9 must appear exactly once in each row.
• Column Constraints: Each number from 1 to 9 must appear exactly once in each
column.
• Subgrid Constraints: Each number from 1 to 9 must appear exactly once in each of
the nine 3x3 subgrids.
Solving Sudoku as a CSP:
To solve Sudoku puzzles using the CSP framework, various techniques are
employed:
• Backtracking Search: This algorithm incrementally assigns values to
variables, backtracking when a constraint violation occurs.
• Constraint Propagation: Techniques like Arc Consistency (AC-3) are used to
reduce the search space by eliminating values that cannot participate in any
valid solution.
• Heuristics: Strategies such as the Minimum Remaining Value (MRV) heuristic
prioritize assigning values to variables with the fewest legal options remaining,
enhancing efficiency.
Constraint satisfaction problems (CSPs)
Standard search problem: state is a "black box“ – any data structure that
supports successor function and goal test
• CSP:
• state is defined by variables Xi with values from domain Di
• goal test is a set of constraints specifying allowable combinations of values
for subsets of variables
• Simple example of a formal representation language
• Allows useful general-purpose algorithms with more power than
standard search algorithms
Example: Map-Coloring
• Variables WA, NT, Q, NSW, V, SA, T
• Domains Di = {red,green,blue}
• Constraints: adjacent regions must have different colors
• e.g., WA ≠ NT, or (WA,NT) in {(red,green),(red,blue),
(green,red), (green,blue),(blue,red),(blue,green)}
Example: Map-Coloring
• Solutions are complete and consistent
assignments
• e.g., WA = red, NT = green, Q = red, NSW =
green,V = red,SA = blue,T = green
•
Constraint graph
• Binary CSP: each constraint relates two variables
• Constraint graph: nodes are variables, arcs are constraints
Varieties of CSPs
• Discrete variables
• finite domains:
• n variables, domain size d O(dn) complete assignments
• e.g., Boolean CSPs, incl. Boolean satisfiability (NP-complete)
• infinite domains:
• integers, strings, etc.
• e.g., job scheduling, variables are start/end days for each job
• need a constraint language, e.g., StartJob1 + 5 ≤ StartJob3
• Continuous variables
• e.g., start/end times for Hubble Space Telescope observations
• linear constraints solvable in polynomial time by LP
Varieties of constraints
• Unary constraints involve a single variable,
• e.g., SA ≠ green
• Binary constraints involve pairs of variables,
• e.g., SA ≠ WA
• Higher-order constraints involve 3 or more variables,
• e.g., cryptarithmetic column constraints