Instructions
• This Midterm 2 review guide covers multi-agent search, CSPs, and Bayesian network.
• You could use this review guide together with lecture notes (textbook if helpful), recitation
notes, homework, practice problems, and programming assignments.
• Midterm exam: * denotes an optional concept that will not be included in the midterm exam.
5 Games: Adversarial Search (Lectures 8 & 9)
1. Adversarial game search setting
• Adversarial Search deals with decision-making problems where multiple agents are in-
volved, and their goals are often in direct conflict.
• In adversarial games, the optimal strategy depends not only on your actions but also on
the actions of your opponent(s).
• Goal: Compute strategies that maximize utility in a competitive setting.
2. Adversarial game tree
• Game tree structure: The tree represents all possible moves in a game from the start
state to terminal states.
• Max player: Attempts to maximize its utility.
• Min player: Attempts to minimize (max player’s) utility.
• Terminal states: These are the leaf nodes of the game tree, representing end-game
conditions where the utility is known (e.g., win, lose, or draw).
3. Adversarial search (aka Minimax search)
• A strategy used for decision-making in zero-sum games.
• Maximizing player: Chooses actions that maximize the minimum possible utility.
• Minimizing player: Chooses actions that minimize the maximum possible utility.
• Recursion: Each player assumes the opponent will play optimally, and the values are
computed recursively.
• Minimax Value of a State: The best achievable utility against a rational, optimal oppo-
nent.
• Computational e!ciency: Like exhaustive DFS; Time complexity O(bm ), where m is
the depth (i.e., number of movements) of the adversarial search tree; Space complexity:
O(bm).
4. Speed up minimax search
(a) Alpha-beta pruning: An optimization technique for minimax that skips branches that
do not influence the final decision.
• Alpha: The best option for the maximizing player so far.
9
, • Beta: The best option for the minimizing player so far.
• E”ectiveness: Pruning reduces the number of nodes that need to be evaluated, im-
proving search e!ciency without a”ecting the final result. The approach is domain-
general, and gives the exact solution.
• Properties: Values of intermediate nodes might be wrong; Good child ordering
improves e”ectiveness of pruning
(b) Evaluation function: Used in depth-limited searches (or ordering nodes for alpha-beta
pruning) to estimate the value of non-terminal nodes.
• These are domain-specific and help approximate the utility of game positions.
• Ideal function: Returns the exact minimax value.
• Practical functions: Typically, weighted linear sums of relevant features (e.g., num-
ber of pieces in chess).
• Example: Pacman evaluation functions might include factors like distance to food
and the number of ghosts nearby.
(c) Know the di”erent purposes served by alpha-beta pruning and evaluation functions
5. Expectimax search
• Outcomes involve randomness, such as dice rolls or uncertain opponent actions.
• Max (or min) nodes: As in minimax, these represent decisions by the maximizing (min-
imizing) player.
• Chance nodes: Represent random events where outcomes are calculated using expected
utilities (weighted averages based on probabilities).
• Know that in many real-world scenarios, minimax search and expectimax search are
combined together.
• Alpha-beta pruning does not apply to expectimax search, where as evaluation functions
may be helpful.
6 Constraint Satisfaction Problems (Lectures 11 & 12)
6.1 Formulation of CSPs
• Variables: The elements or entities we are assigning values to.
• Domains: The set of possible values that each variable can take.
• Constraints: The rules or restrictions that must be satisfied. These can be unary, binary, or
n-ary.
• Objective: The goal of a CSP is to find an assignment of values to variables such that all the
constraints are satisfied.
10
• This Midterm 2 review guide covers multi-agent search, CSPs, and Bayesian network.
• You could use this review guide together with lecture notes (textbook if helpful), recitation
notes, homework, practice problems, and programming assignments.
• Midterm exam: * denotes an optional concept that will not be included in the midterm exam.
5 Games: Adversarial Search (Lectures 8 & 9)
1. Adversarial game search setting
• Adversarial Search deals with decision-making problems where multiple agents are in-
volved, and their goals are often in direct conflict.
• In adversarial games, the optimal strategy depends not only on your actions but also on
the actions of your opponent(s).
• Goal: Compute strategies that maximize utility in a competitive setting.
2. Adversarial game tree
• Game tree structure: The tree represents all possible moves in a game from the start
state to terminal states.
• Max player: Attempts to maximize its utility.
• Min player: Attempts to minimize (max player’s) utility.
• Terminal states: These are the leaf nodes of the game tree, representing end-game
conditions where the utility is known (e.g., win, lose, or draw).
3. Adversarial search (aka Minimax search)
• A strategy used for decision-making in zero-sum games.
• Maximizing player: Chooses actions that maximize the minimum possible utility.
• Minimizing player: Chooses actions that minimize the maximum possible utility.
• Recursion: Each player assumes the opponent will play optimally, and the values are
computed recursively.
• Minimax Value of a State: The best achievable utility against a rational, optimal oppo-
nent.
• Computational e!ciency: Like exhaustive DFS; Time complexity O(bm ), where m is
the depth (i.e., number of movements) of the adversarial search tree; Space complexity:
O(bm).
4. Speed up minimax search
(a) Alpha-beta pruning: An optimization technique for minimax that skips branches that
do not influence the final decision.
• Alpha: The best option for the maximizing player so far.
9
, • Beta: The best option for the minimizing player so far.
• E”ectiveness: Pruning reduces the number of nodes that need to be evaluated, im-
proving search e!ciency without a”ecting the final result. The approach is domain-
general, and gives the exact solution.
• Properties: Values of intermediate nodes might be wrong; Good child ordering
improves e”ectiveness of pruning
(b) Evaluation function: Used in depth-limited searches (or ordering nodes for alpha-beta
pruning) to estimate the value of non-terminal nodes.
• These are domain-specific and help approximate the utility of game positions.
• Ideal function: Returns the exact minimax value.
• Practical functions: Typically, weighted linear sums of relevant features (e.g., num-
ber of pieces in chess).
• Example: Pacman evaluation functions might include factors like distance to food
and the number of ghosts nearby.
(c) Know the di”erent purposes served by alpha-beta pruning and evaluation functions
5. Expectimax search
• Outcomes involve randomness, such as dice rolls or uncertain opponent actions.
• Max (or min) nodes: As in minimax, these represent decisions by the maximizing (min-
imizing) player.
• Chance nodes: Represent random events where outcomes are calculated using expected
utilities (weighted averages based on probabilities).
• Know that in many real-world scenarios, minimax search and expectimax search are
combined together.
• Alpha-beta pruning does not apply to expectimax search, where as evaluation functions
may be helpful.
6 Constraint Satisfaction Problems (Lectures 11 & 12)
6.1 Formulation of CSPs
• Variables: The elements or entities we are assigning values to.
• Domains: The set of possible values that each variable can take.
• Constraints: The rules or restrictions that must be satisfied. These can be unary, binary, or
n-ary.
• Objective: The goal of a CSP is to find an assignment of values to variables such that all the
constraints are satisfied.
10
