Week 4 (Chapter 5) - Adversarial Search

Question 1

In game playing, when “perfection” is unobtainable, what must we do?

Answer 1

Must approximate and make trade-offs

Question 2

Explain what it means by “deterministic” in game playing.

Answer 2

No chance involved.

e.g. Chess, checkers, go, othello

Question 3

How to represent a game as a search problem?

Answer 3

Minimax where there are states (nodes) which have a utility function (i.e. a numeric reward for outcome)

Question 4

What is the pseudo code for Minimax algorithm?

Answer 4

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)

Question 5

Properties of minimax?

Answer 5

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

Question 6

How to impose resource limits for Minimax?

Answer 6

• Cutoff (depth limit)

- Evaluation function (estimate the desirability of a position)

Question 7

a-b pruning example

Answer 7

Page 14 - 18 Lecture 4

Question 8

Properties of a-b?

Answer 8

Pruning does not affect final result

Good move ordering improves effectiveness of pruning
- order better moves to be considered first

Question 9

What is the time complexity of a-b pruning with “perfect ordering”

Answer 9

O(b^(m/2))

- Doubles depth of search

Question 10

Give an example of a method of metareasoning

Answer 10

a-b pruning

Question 11

What is the pseudocode of a-b pruning

Answer 11

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 β

Question 12

Examples of non-deterministic games

Answer 12

• Backgammon
• Monopoly

In Backgammon and Monopoly the dice rolls determine the legal moves

Question 13

Is it possible to apply a-b pruning in nondeterministic games?

[Follow-up]

Answer 13

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

Question 14

When representing games as a search function, when do exact values matter and don’t matter?

Answer 14

Deterministic = Don’t matter (chess)

Non-deterministic = Matter (backgammon/monopoly)

Question 15

Does minimax give perfect play?

Answer 15

Yes for deterministic games, perfect-information games.

Question 16

Does expectiminimax give perfect play

Answer 16

Yes

Question 17

What’s the benefit of iterative deepening with minimax?

Answer 17

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