Week 4 (Chapter 5) - Adversarial Search Flashcards
In game playing, when “perfection” is unobtainable, what must we do?
Must approximate and make trade-offs
Explain what it means by “deterministic” in game playing.
No chance involved.
e.g. Chess, checkers, go, othello
How to represent a game as a search problem?
Minimax where there are states (nodes) which have a utility function (i.e. a numeric reward for outcome)
What is the pseudo code for Minimax algorithm?
function Minimax-Decision(game) returns an operator
__for each op in Operators[game] do
____Value[op] ← Minimax-Value(Apply(op, game), game)
__end
__return the op with the highest Value[op]
====
function Minimax-Value(state, game) returns a utility value
__if Terminal-Testgame then
____return Utilitygame
__else if max is to move in state then
____return the highest Minimax-Value of Successors(state)
__else
____return the lowest Minimax-Value of Successors(state)
Properties of minimax?
Complete - Yes, if tree if finite
Optimal - Yes, against an optimal opponent. Otherwise might result in infinite loop
Time - O(b^m)
Space - O(bm), depth first exploration
How to impose resource limits for Minimax?
- Cutoff (depth limit)
- Evaluation function (estimate the desirability of a position)
a-b pruning example
Page 14 - 18 Lecture 4
Properties of a-b?
Pruning does not affect final result
Good move ordering improves effectiveness of pruning
- order better moves to be considered first
What is the time complexity of a-b pruning with “perfect ordering”
O(b^(m/2))
- Doubles depth of search
Give an example of a method of metareasoning
a-b pruning
What is the pseudocode of a-b pruning
Basically it’s Minimax AND keeping track of alpha, beta AND pruning
function Max-Value(state, game, α, β) returns the minimax value of state
inputs:
- state, current state in game
- game, game description
- α, the best score for max along the path to state
- β, the best score for min along the path to state
\_\_if Cutoff-Test(state) then return Eval(state) \_\_for each s in Successors(state) do \_\_\_\_α ← Max(α, Min-Value(s, game, α, β)) \_\_\_\_if α ≥ β then return β \_\_end \_\_return α
=====
function Min-Value(state, game, α, β) returns the minimax value of state
__if Cutoff-Test(state) then return Eval(state)
__for each s in Successors(state) do
____β ← Min( β, Max-Value(s, game, α, β))
____if β ≤ α then return α
__end
__return β
Examples of non-deterministic games
- Backgammon
- Monopoly
In Backgammon and Monopoly the dice rolls determine the legal moves
Is it possible to apply a-b pruning in nondeterministic games?
[Follow-up]
Yes, a version of expectiminimax is possible for a-b pruning.
HOWEVER, only if the leaf values are bounded.
As depth increases, probability of reaching a given node shrinks
- Value of lookahead is diminished
a-b pruning is much less effective
When representing games as a search function, when do exact values matter and don’t matter?
Deterministic = Don’t matter (chess)
Non-deterministic = Matter (backgammon/monopoly)
Does minimax give perfect play?
Yes for deterministic games, perfect-information games.
Does expectiminimax give perfect play
Yes
What’s the benefit of iterative deepening with minimax?
obviously with minimax for any iteration of minimax with a depth below the max depth, the minimax algo has to pick the best move based only on the eval function, not the final reward
so the idea i have is
minmax gives you an estimate of the best move
which you then explore first, in your next iteration
and the reason that improves pruning is because pruning is optimised when the best moves are selected first
however its not perfect
because your eval function could suck
in which case you would not end up pruning anything
=====
implementing a cutoff depth limit helps with resource limits such as time or space
