game search problems Flashcards
formalise a game problem
States : π (Start State π 0)
β Actions: π΄ (may depend on player/state)
β Transition function: π Γ π΄ β π
β Terminal test: π β (π‘π’ππ, ππππ π)
β Players: π = (1, β¦ , π) (usually take turns)
β Utilities: ππ‘πππππππ Γ π β π
(values on outcomes)
what is a utility function
utility function is the function that defines the final numeric value of a game that ends in a terminal state S for player P
(also known as objective function or payoff function)
what is a transition function in a game problem
s ->. state
a -> action
tf : s * a β> s
what is the terminal test in a game problem
s β> (true,false)
what is the uility in a game problem
p -> players
R β> results
can usually be 1β¦ n
U: S terminal * p β> R (values on outcome)
what are other names the utitlity function can be called
objective function
payoff function
what is minimax
Minimax value of a node is the utility of the terminal state to
which both players play optimally from that node.
So the process of a two-player game is that one player (called
player Max) is to maximise its utility whereas its opponent
(called player Min) is to minimise the utility of Max
how would minimax affect a two player game
find a node where thea player can maxmise the utiltiy whereas the opponent can minimse the other playerβs utiltity
write the code for the minimax function
function minimax_value (state) return its minimax value
if state is a terminal state
return its utility
if state is for agent Max to take an action
return max_value(state)
if state is for agent Min to take an action
return min_value(state)
write the code for function max_value in the minimax function
function max_value (state) return its minimax value π£
initialise π£ = ββ
for each successor of state
π£ = max(π£, πππππππ₯ _π£πππ’π(π π’ππππ π ππ))
return π£
write the code for function min_value in the minimax function
function min_value (state) return its minimax value π£
initialise π£ = +β
for each successor of state
π£ = min(π£, πππππππ₯ _π£πππ’π(π π’ππππ π ππ))
return π£
what type of games is minimax used for
deterministic
zero sum games
how efficient is minimax
it uses depth first search which is exhaustive
time complexity is O(b^m)
b -> branching factor
m -> maximum depth of the tree
space : O(bm)
Solving them is completely infeasible in most cases
what is the time complexity for minimax algorithm
O(b^m)
b -> branching factor
m -> maximum depth of node
what is the space complexity for minimax algorithm
O(bm)
b -> branching factor
m -> maximum depth of node
what is the general configuration for alpha - beta pruning
Let π be the value that Max can currently get at least.
β We are now computing the min_value at some node π
β When we explore πβs children, if we find that the value
of π will never be better than π (for agent Max), then
we can stop considering πβs other children
