Week 2 - Adversarial search and constraint satisfaction Flashcards
(17 cards)
What is an adversarial search
Search where there are 2 agents with conflicting goals
what is minimax
Minimax is used in two-player adversarial games where one agent (Max) tries to maximize the score, and the other (Min) tries to minimize it. Each player assumes the opponent will always make the most punishing move possible. Therefore, Minimax chooses the best possible outcome assuming the worst-case scenario from the opponent, i.e., Max selects the move that gives the maximum of the minimum scores resulting from Min’s optimal response, and vice versa.
what does minimax algorithm do
the minimax algorithm selects the best outcome of the worst case scenarios as opposing player plays optimally to hurt you
properties of minimax algorithm
MINIMAX EXPLORES GAMETREE IN DFS
time complexity - O (b^d)
space complexity - O(b * d)
complete - IF TREE IS FINITE
optimal - IF OPPOSING PLAYER IS PLAYING OPTIMALLY
NOT EFFICIENT - WE CAN USE ALPHABETA PRUNING TO SKIP PATHS WE KNOW WONT LEAD TO ANSWER
what are the 3 main components of CSP
. finite set of variables
. set of domains ( set of values that can be assigned to each variable)
. constraints
why are csp solvers different from searches
so reason csp solving is different from searches
is that we dont care about the sequence of actions that take us to the goal state
we only care about finding a goal state given that constrainst are satisfied under the solution (assigment of variables to values in domain)
why faster to use csp solvers than somehtign like an informed search
so reason csp solving is different from searches
is that we dont care about the sequence of actions that take us to the goal state
we only care about finding a goal state given that constrainst are satisfied under the solution (assigment of variables to values in domain)
what is a csp solution
an instantion of ALL variables to values in the domain such that ALL constrainsts are satisfied
READ
csp solvers explore PARTIAL ASSIGNENTS that have to be consistent ( follow constrainsts)
solving a csp ( how it works)
States: assignments of variables to values within domains
Initial state: no variables
Action: assign a value to an unassigned variable if it doesn’t violate a constraint, if no legal assignments then failure
goal test: all variables assigned (value in domain) and constraints satisfied
why is complete search tree so ineffiecnt
searches all possible assignments of n from domain size m
n ! x m^n
We can make this more effeicent by backtracking
Why does incorporating backtracking in a complete search tree make it more effient
backtracking:
each level is assigning a specific variable :
we assign a variable a value
if failure we backtrack to next assignment
if all assignments ( im assuming for that variable ) fail then failure
reduce now to m ^n
( before was n! x m^n with complete search tree)
How can we make a search tree that incoporates backtracking even more efficient know
. choose how we select the next variable to assign carefully
. choose value to select in smarter order
. Detect failures early ( through forward checking or constraint propogation
choosing how we select the next variable to assign carefully
. Most constrained variable
- choose variable with the fewest legal
moves [MRV heuristic ] - minimum
remaining values
. most constraining variable
-choose variable that imposes the most
constraints on the remaining variables
choosing the value we select ( in a smart order)
choose the least constraining value
- value that leaves remaining variable
with the most legal moves
(rules out fewest)
Detecting failure early (forward checking)
Propoogate information from a variable we assigned to an unassigned variable
keep track of legal moves for remaining variables at each iteration we assign a variable
TERMINATES EARLY WHEN an unassigned variable has no remaining legal values
Detecting failure early (constraint propogation)
Constraint propagation enforces constraints and detects failure even earlier than forward checking
Uses the arc consistency algorithm which makes sure pairs of variables that affect each other are consistent
X → Y is consistent if for each value of X there are allowed values of Y
When checking X → Y throw out any values of X where there wouldn’t be an allowed value for Y
If X loses a value then we must check every pair again
Can be run before or after a variable assigment
