Foundation of Artificial Intelligence
2AMU10
1 TIME LINE
4th century BCE: Aristotle, calculus
17th century CE: Leibniz, calculus
19th century CE: Babbage, analytical engine | Lovelace, computer programmer
20th century CE:
1910: Whitehead & Russell, Principia Mathematica
1943: McCulloch & Pitts, artificial neuron
1950: Turing, Turing test | Shannon, chess
1956: Newell and Simon, Logic Theorist | Samuel, Checkers | Dartmouth Workshop
1958: McCartly develops Lisp
1961: Rosenblatt’s comprehensive work on Perceptrons
1966: Dendral is developed at Stanford
1969: Minsky & Papert’s critique in their book Perceptrons
1972: Colmereuer develops Prolog
1974: Mycin developed at Stanford | Werbos’s PhD thesis applying backpropagation to ANNs
1982: Expert system R1 gets deployed commercially | Hopfield networks | Fifth generation
computer systems project
1986: Rumelhart et al. reinvent/popularise backpropagation for ANNs
1988: Nearly every major US corporation uses or investigates expert systems.
1
,2 INTRODUCTION, MICROWORLDS, MINIMAX SEARCH
AI can be thought of to be part of a combination of two sections:
• Thinking or Acting
• Human / Anthropomorphic or Rationality
In this course, we lean towards the acting side, mostly rationality and a little human.
• “A field of study that seeks to explain and emulate intelligent behaviour in terms of
computational processes” – (Schalkoff, 1990)
• “The art of creating machines that perform functions that require intelligence when
performed by people” – (Kurzweil, 1990)
2.1. PREHISTORICAL DEVELOPMENTS
AI starts in 1956. However, it is thought of a lot earlier.
4th century BCE: Aristotle, calculus
17th century CE: Leibniz, calculus
19th century CE: Babbage, analytical engine | Lovelace, computer programmer
20th century CE: Turing, Turing test (1950) | Shannon, chess (1950) | Newell and Simon, Logic
Theorist (1955) | Samuel, Checkers (1955)
2.2. GAMES & MICROWORLDS
Games: structured, goals, tractable, complex. This makes it a useful testbed for AI algorithms.
Microworld: bounded domain, unambiguous, simplified structure, clear and measurable goals, not
necessarily a competition.
2.3. MINIMAX SEARCH
Game setup: two players A, B. The players take turns. They
receive perfect information. It is deterministic. The game is
finished if either player wins or it is a draw.
The player takes the move where it would win.
Problems:
• Tree grows exponential 𝑂𝑂�𝑚𝑚𝑑𝑑 � states.
• Intractable for non-trivial games.
Figure 1: Basic tree game
Idea: estimate the “value” of the state without expanding the whole tree → evaluation function.
Minimax: optimize the short-term tactical play using game tree expansion. Score the leaves with an
evaluation function at the non-terminal depth.
• Maximize the score for player A
• Minimize the score for player B
2
, Figure 2: Minimax on a game
3
2AMU10
1 TIME LINE
4th century BCE: Aristotle, calculus
17th century CE: Leibniz, calculus
19th century CE: Babbage, analytical engine | Lovelace, computer programmer
20th century CE:
1910: Whitehead & Russell, Principia Mathematica
1943: McCulloch & Pitts, artificial neuron
1950: Turing, Turing test | Shannon, chess
1956: Newell and Simon, Logic Theorist | Samuel, Checkers | Dartmouth Workshop
1958: McCartly develops Lisp
1961: Rosenblatt’s comprehensive work on Perceptrons
1966: Dendral is developed at Stanford
1969: Minsky & Papert’s critique in their book Perceptrons
1972: Colmereuer develops Prolog
1974: Mycin developed at Stanford | Werbos’s PhD thesis applying backpropagation to ANNs
1982: Expert system R1 gets deployed commercially | Hopfield networks | Fifth generation
computer systems project
1986: Rumelhart et al. reinvent/popularise backpropagation for ANNs
1988: Nearly every major US corporation uses or investigates expert systems.
1
,2 INTRODUCTION, MICROWORLDS, MINIMAX SEARCH
AI can be thought of to be part of a combination of two sections:
• Thinking or Acting
• Human / Anthropomorphic or Rationality
In this course, we lean towards the acting side, mostly rationality and a little human.
• “A field of study that seeks to explain and emulate intelligent behaviour in terms of
computational processes” – (Schalkoff, 1990)
• “The art of creating machines that perform functions that require intelligence when
performed by people” – (Kurzweil, 1990)
2.1. PREHISTORICAL DEVELOPMENTS
AI starts in 1956. However, it is thought of a lot earlier.
4th century BCE: Aristotle, calculus
17th century CE: Leibniz, calculus
19th century CE: Babbage, analytical engine | Lovelace, computer programmer
20th century CE: Turing, Turing test (1950) | Shannon, chess (1950) | Newell and Simon, Logic
Theorist (1955) | Samuel, Checkers (1955)
2.2. GAMES & MICROWORLDS
Games: structured, goals, tractable, complex. This makes it a useful testbed for AI algorithms.
Microworld: bounded domain, unambiguous, simplified structure, clear and measurable goals, not
necessarily a competition.
2.3. MINIMAX SEARCH
Game setup: two players A, B. The players take turns. They
receive perfect information. It is deterministic. The game is
finished if either player wins or it is a draw.
The player takes the move where it would win.
Problems:
• Tree grows exponential 𝑂𝑂�𝑚𝑚𝑑𝑑 � states.
• Intractable for non-trivial games.
Figure 1: Basic tree game
Idea: estimate the “value” of the state without expanding the whole tree → evaluation function.
Minimax: optimize the short-term tactical play using game tree expansion. Score the leaves with an
evaluation function at the non-terminal depth.
• Maximize the score for player A
• Minimize the score for player B
2
, Figure 2: Minimax on a game
3
