L1: Introduction, Microworlds, Minimax Search

Question 1

What are the four different ways of thinking about AI?

Answer 1

acting vs. thinking and human/ anthropomorphic vs. rationality (we focus on rational acting)

Question 2

Properties of games

Answer 2

o Typically clearly structured
o Clear goals/ tasks (i.e. winning)
o Limited enough to be tractable (clear rules)
o Complex enough to be interesting

Question 3

When did AI beat humans in games?

Answer 3

Backgammon- 1980s
Checkers & Chess- 1990s
Shogi, Go, Starcraft II- 2010s

Question 4

Name some microworld examples

Answer 4

o SHRDLU (moving blocks around based on instructions)
o DENDRAL (mass spectrometry- expert system)
o MYCIN (antibiotics- expert system)
o ELIZA (psychotherapy- NLP)
o STUDENT (word algebra- NLP)

Question 5

Characteristics of abstract two person game

Answer 5

o Players take turns
o Perfect information (everyone knows everything need to know to make best choice)- no one makes a mistake
o Deterministic (lack of randomness)
o Game is finished when one player wins or draws (i.e. if draw game tree will not all stop at same level)
o No cycles

Question 6

How many terminal states in game with m moves and d turns?

Answer 6

O(m^d)

Question 7

Basic idea of minimax?

Answer 7

• Optimise short-term tactical play using game tree expansion
• Score leaves with evaluation function at non-terminal depth (evaluation does not need to be zero sum)
• Assume optimal play from both players

Question 8

What are possible extensions to minimax?

Answer 8

 Alpha-beta pruning
 Iterative deepening
 Transposition tables
 Quiescence search