AI 3

Lecture 3

What is game theory?

A field that studies strategic interactions, focusing on how agents should play, how people do play, and how to design games with desired properties

What components define a game?

1. initial state

2. player(s)

3. Action(s)

4. Results(s,a)

5. Terminal(s)

6. Utility(s,p)

what is Result(s,a)?

Transition/successor function

What is Terminal(s)?

Whether the game has ended

What is Utility(s,p)?

Payoff for player p in terminal state s

Why is game theory important in AI?

1. AI is about making good decisions

2. Many AI problems can be modelled as games

3. Multi-agent decision making naturally fits game theory

What are the main types of games?

1. Sequential vs Simultaneous

2. Constant-sum(zero-sum) vs Variable-sum

What does classic game theory focus on?

Two-player, one-turn, simultaneous-move games

What is a strategy?

A complete specification of what to do in every non-terminal state of a game

What are pure and mixed strategies?

Pure: always choose the same action

Mixed:choose actions probabilistically

What is a best response?

A strategy that gives the highest payoff against a specific opponent strategy

Why is best response difficult in practice?

Because the opponent’s strategy is usually unknown

What is a dominated strategy?

A strategy that always gives a worse payoff than another strategy, regardless of what the opponent does.

What is Iterated Elimination of Dominated Strategies(IEDS)?

Repeatedly removing dominated strategies from the game

Does IEDS always give a unique solution?

No

What assumption underlies IEDS?

Common Knowledge of Rationality(CKR)

What is the maximin strategy?

Choose the strategy that maximises the worst-case payoff

Why use maximin?

It guarantees the best possible outcome in the worst case

What is a strategy profile?

A specification of strategies for all players

What is a Nash equilibrium?

A strategy profile where no player can improve their payoff by unilaterally changing strategy

Does a Nash equilibrium always exist?

Yes, at least one(possibly mixed) Nash Equilibrium always exists

What is the relationship between IEDS and NE

If IEDS yields a unique solution, it is a Nash equilibrium

Why are many games computationally hard?

The number of possible game states grows exponentially

What is a zero-sum game?

A game where the sum of all players’ utilities is constant (one player’s gain is another’s loss)

Who are the players in zero-sum games:

1. MAX: tries to maximise utility

2. MIN: tries to minimise utility

What is V(s)?

The utility (value) of state s assuming optimal play

What is minimax used for?

Computing optimal play in deterministic, zero-sum, perfect-information games

How is V(s) computed?

1. Terminal state: use utility

2. MAX node: max of children

3. MIN node: min of children

How are Stochastic games handled?

By introducing chance nodes that model randomness

What is expectimax?

A variant of minimax that handles chance nodes by taking expected values instead of min/max.

What is the time complexity of minimax?

O(b^m), where b = branching factor and m = depth.

Why is minimax impractical for large games?

The search tree grows exponentially and leaf utilities are far away.

What is alpha-beta pruning?

An optimisation that avoids exploring branches that cannot affect the final decision.

What are α and β?

• α: best value MAX can guarantee

• β: best value MIN can guarantee

When can pruning occur?

When β < α.

How much can alpha-beta pruning reduce complexity?

In the best case, it halves the effective search depth: O(b^(m/2)).

Why use depth-limited search?

Full search is infeasible in real games.

What replaces utility at cutoff depth?

An evaluation function.

What is an evaluation function?

An estimate of the utility of a non-terminal state.

What is the trade-off in evaluation functions?

Accuracy vs computation time (depth vs complexity).

What techniques improve game-playing agents?

• Alpha-beta pruning

• Iterative deepening search (IDS)

• Transposition tables

• Move ordering

• Aspiration windows

• Learned evaluation functions

What is the standard approach in modern game-playing AI?

Alpha-beta pruning + iterative deepening + evaluation functions + optimisations.