Artificial Intelligence

PDF version

[Rough notes]

Traditional roles of machines vs humans —

Humans: creativity, determine goals, construct algorithms, using natural language, speech, vision.

Machine: fast and accurate arithmetic, execute precise procedures

AI is (partly) about blurring the distinction between these roles.

Can machines simulate or behave in more intelligent ways? Can they be creative? Can they come up with their own algorithms?

Alan Turing: 1950, “On Computing Machinery and Intelligence”

The Turing Test: operational definition of intelligence. Can machines think?

Planning ← early success of AI (1950s-60s)

Given a particular goal, determine the steps necessary to reach the goal.

Many problems can be specified as a search through a state space graph.

A graph is a connected structure with nodes (circles) and edges (connections).

  • The physical positioning (locations) of the nodes are irrelevant for most purposes. What matters in a graph is just which nodes are connected to which other nodes.

Maps are graphs, and route-finding on a map is an example of this problem.

But many other problems can be treated as graph problems and we’d apply the same route-finding techniques.

eight-puzzle-sample.png

Figure 1: A start and goal state for the 8-puzzle

Game playing AIs & NPCs

  • We’ll consider two-player zero-sum game w/no randomness & no hidden state
  • An example game tree for an unspecified two-player game