Adversarial Search

Question 1

How can a game be defined?

Answer 1

S: State space
N: A set of players
A: A set of actions
An initial state and terminal state
Players
R(s, a): a function that updates the game state
payoffs: Payoff to player i in terminal state

Question 2

What is a zero-sum game?

Answer 2

When all payoffs equal zero for every state.

Question 3

What is an optimal strategy?

Answer 3

One that leads to outcomes at least as good as any other strategy when player i is playing an infallible opponent.

Question 4

What is a game tree?

Answer 4

A representation of possible plays of the game.
Every node is labeled the initial state
Every edge is labeled an action
The path from root to any node is a history of play.

Question 5

What are the properties of minimax algorithm?

Answer 5

Time complexity - O(b^m)
Space - O(bm)

Question 6

What are the properties of alpha-beta pruning?

Answer 6

Best case time - O(b^k/2)
Average case time - O(b^3k/4)