Game Playing and Search in Games

Question 1

How does the MINIMAX algorithm work?

Describe its properties in terms of completeness, time complexity, space complexity, and optimality.

Answer 1

A tree is created - first layer represents computer’s move (MAX), next layer opponent’s move (MIN), etc. The MAX nodes try to pick the next move with the highest calculated outcome at the end, and the MIN nodes pick the node with the lowest calculated outcome. Assumes the opponent will always move in their best interest.

Completeness: yes if tree is finite
Time complexity: O(b^m)
Space complexity: O(bm) (depth-first exploration)
Optimality: yes if against an optimal opponent

Question 2

How does alpha-beta pruning work?

Answer 2

No need to explore optional already worse than the current best option (in MINIMAX).
Alpha - lower bound on the value of a MAX node.
Beta - upper bound on the value of a MIN node.

Question 3

Describe shallow search techniques.

Answer 3

1. Limited search for a few levels.
2. Reorder the level-1 successors.
3. Proceed with alpha-beta minimax search.

Question 4

Name and describe 3 additional refinements for the MINIMAX search.

Answer 4

1. Waiting for quiescence: continue the search until no drastic change occurs from one level to the next.
2. Secondary search: after choosing a move, search a few more levels beneath it to make sure it still looks good.
3. Book moves: for some parts of the game (especially initial and end moves), keep a catalogue of best moves to make.

Question 5

How do you do MINIMAX for games of chance?

Answer 5

Use 3 kinds of nodes - MIN, MAX, CHANCE.

Question 6

How are imperfect decisions used in terms of MINIMAX?

Answer 6

Using a heuristic to estimate end result as opposed to completing the tree.