Games and Search

Question 1

What is a deterministic game?

Answer 1

A game with a finite amount of states and possible moves

Question 2

What are zero-sum games?

Answer 2

Agents have opposite utilities (values on outcomes). One player tries to maximise the other tries to minimise (adversial).

Question 3

What are general games?

Answer 3

Agents have independent utilities. Cooperation, indifference, competition and more possible.

Question 4

What is a game tree (2-player)?

Answer 4

For 2-player deterministic turns, value of a state is the best achievable outcome from that state. Terminal nodes/utility values, determine who has won.

Question 5

What are some examples of terminal nodes/utility values for game trees?

Answer 5

Opponent win = -1
Draw = 0
Player win = 1

Question 6

What is minimax?

Answer 6

Choose move to position with highest minimax value.

Question 7

Is minimax complete?

Answer 7

Yes, if tree is finite

Question 8

Is minimax optimal?

Answer 8

Against an optimal opponent yes.

Question 9

What is the time complexity of minimax?

Answer 9

O(b^m)

Question 10

What is the space complexity of minimax

Answer 10

O(b^m)

Question 11

What is alpha-beta pruning?

Answer 11

Similar to minmax, but avoids branches that will not yield a better result.

Question 12

How does alpha-beta pruning affect the time complexity?

Answer 12

Halves the time complexity (m/2) and doubles to solvable depth.