Transcript ppt - Duke Computer Science

Artificial Intelligence
Search and Heuristics
“Can a machine think?”
• Alan Turing asked this question in the 1950 article titled
Computing Machinery and Intelligence
• His answer was “Yes”
• This led to the question
"If a computer could think, how could we tell?"
• Turing's suggestion:
– if the responses from the computer were
indistinguishable from that of a human, the
computer could be said to be thinking.
The Turing test
• Turing proposed the following criterion in 1950 for
deciding whether a computer is intelligent
– A human holds a teletype conversation on any topic
with an
unseen correspondent
– If the human believes he is talking to another human
when he is really talking to a computer then the
computer is deemed to be intelligent
• Turing predicted that by the year 2000 a computer
program would be able to fool the average questioner for
five minutes about 70% of the time
Chatterbots
• A group of programs attempting to cross the language
barrier between humans and computers were developed
in an attempt to pass - or ridicule - Turing's test
• Such programs are now known as Chatterbots
– computer programs which simulate conversation with
a user in a (written) natural language
• The most famous such program, ELIZA, was published
in 1966 by Joseph Weizenbaum from MIT in
Communications of the ACM
• ELIZA attempts to communicate in a natural language by
engaging humans in conversation with a simulated
Rogerian psychotherapist
How ELIZA works
• ELIZA simulates a conversation between psychiatrist
and patient
– stereotypical method: mirror the patient's feelings by
repeating the input statements as questions
• Looks for patterns of words in the input
• Applies a series of pattern matching rules
• Replies with predetermined output
• Uses a very small database of words and phrases
• ELIZA is relatively effective because it exploits the fact
that humans read so much meaning into what is said
– fools users into interpreting nonsense as conversation
http://www.manifestation.com/neurotoys/eliza.php3
http://www.cs.duke.edu/courses/summer04/cps001/chatterbots/eliza.html
The Loebner prize
• The first formal instantiation of a Turing test
• Implemented in 1991 by Dr. Hugh Loebner, a professor
very much interested in seeing AI succeed
– pledged $100,000 to the first computer (programmer)
that could pass the test.
• Each year an annual prize of $2000 and a bronze medal
is awarded to the most human computer.
– winner of the annual contest is best entry relative to
other entries that year
– irrespective of how good it is in an absolute sense.
http://www.loebner.net/Prizef/loebner-prize.html
Loebner prize winners & more bots
• 1991 Loebner Prize winner Joseph Weintraub
– PC Therapist
• 2001 Loebner Prize winner Richard Wallace
http://alicebot.org
• 2003 Loebner Prize winner Juergen Pirner
http://www.abenteuermedien.de/jabberwock
• Sites for all things Chatterbot:
http://www.simonlaven.com
http://www.botspot.com/pages/chatbots.html
Validity of the Turing test?
• Supporters
– human-like interaction is seen as essential to humanlike intelligence
• Opponents
– test is neither necessary nor sufficient for intelligence
– what is important is that the computer demonstrates
cognitive ability regardless of its behavior
– not necessary for program to speak for it to be
intelligent
– there are humans that would fail the Turing test
– there are unintelligent computers that might pass
The origins of AI
• Alan Turing proposed that machines could be
programmed to exhibit intelligent behavior in 1950
• John McCarthy gave the name artificial intelligence to
the field in his 1956 proposal to explore
– “the conjecture that every aspect of learning or any
other feature of intelligence can in principle be so
precisely described that a machine can be made to
simulate it”
What is intelligence?
• Intelligence is the computational part of the ability to
achieve goals in the world
– varying degrees of intelligence occur in people, many
animals and some machines
• The ultimate effort is to make computer programs that
can solve problems and achieve goals in the world as
well as humans
http://www-formal.stanford.edu/jmc/whatisai/
Reasoning
• If we are to build machines that are able to perform
complex tasks without human intervention, we must
make them more humanlike in the sense that they must
possess or at least simulate the ability to reason
• How can machines be programmed to simulate
reasoning? Is it possible?
• Adversary’s argument:
– it is impossible to write down formal rules for every
situation
• Alan Turing says:
– it is scientifically impossible to prove that people are
not driven by rules
Reasoning
• Making a conclusion or logical judgment on the basis of
circumstantial evidence and prior conclusions rather than
on the basis of direct observation
• Program a computer to represent conclusions as states
• The ultimate conclusion or judgment is called the goal
• Process of reasoning can be viewed as searching the
space of all possible states to find path or sequence of
actions from the initial state to the goal
• Based on observation of current state (and possibly prior
states) select some new goal state it wishes to achieve
and devise a strategy for achieving it
Methods for reasoning
• Start at initial state and systematically consider possible
actions and reason forward toward the goal
• Reason backwards from the goal state
• Identify subgoals
– goal cannot be achieved until certain a subgoal is
reached, where that subgoal depends upon some
previous achievement
• Distance measures
– estimate how close moving to a particular state will
bring you to the goal
Search
• Many structures are used to model the abstract nature of
search
– search states, search spaces, search trees
• There are many search algorithms
• Search algorithms are one of two types
– complete or exhaustive
• guaranteed to find solution or prove there is none
– incomplete
• may not find a solution even when it exists
• often more efficient than complete search
– else there would be no reason to use them
Search states
• Search states summarize information about the current
state of the search
• The goal state is a special instance of a search state
– contains complete information
– gives the solution to the problem
• In general, a search state other than the goal
– provides partial information only
– will not solve the problem
– may not even extend to the solution
Search in AI
• Search states allow us to generalize search
• Do not view search is as just a process to reach the goal
• Instead we seek a solution or subgoal to extend our
current search state
– increase distance on path from some other state
– there may be no such solution along the current path,
even if the overall problem is solvable
• Original search problem is to extend the initial state
• Most search in AI performed by structured exploration of
search states
Search space
• Search space is an abstract logical space composed of
nodes and links (edges)
– nodes represent the search states
– edges are all legal connections between search
states
• Search algorithms are well-defined instructions for
navigating the search space
Search trees
•
•
•
•
•
Search trees are an abstraction of one possible search
Root node is the initial state
Leaves represent all possible solutions and failures
All other nodes represent states in between
Edges represent actions
X
– consider two nodes X, Y
E
and edge E between them
– state Y is the consequence
Y
of performing action E while in state X
• Child nodes represent extensions
– children of a node give all possible consequences of
moving forward from that node
Tic-Tac-Toe
• The first player is X and the
second is O
• Object of game: get three of
your symbol in a horizontal,
vertical or diagonal row on a
33 game board
• X always goes first
• Players alternate placing Xs and Os on the game board
• Game ends when a player has three in a row (a wins) or
all nine squares are filled (a draw)
Partial search tree for Tic-Tac-Toe
• Impossible to draw entire tree
• 9! = 362,880 possible states
Frontier
• Search trees are a useful concept in theory
• In practice, search algorithms do not compute and store
the entire search tree
– requires exponential time/space
– we can discard nodes we already explored
– we can discard nodes we will never use
• Search algorithms store frontier of search
– nodes in search tree with unexplored children
• Many search algorithms are easy to understand in terms
of search trees and how they explore the frontier
Classic search algorithms
• Breadth-first search
• Depth-first search
• Best-first search
• Depth-bounded depth-first search
• Iterative deepening search
Breadth-first search
1
• Explore all nodes at one
height in tree before any
other nodes
• Always move to
shallowest and
leftmost node
4
in the frontier
8
16
2
5
9
17
3
10
6
11
18
12
19
21
7
13
14
20
15
Depth-first search
1
• Explore all nodes
in subtree of current
node before any
2
14
other nodes
• Always move to
8
leftmost and
3
15
19
deepest node
in the frontier
4
7
9 10 16 17 20 21
• Tree must be
finite
5
6
11 12
18
13
Complete or incomplete search?
• Breadth-first and depth-first search are complete
– exhaustively search the tree
– guaranteed to find the goal (if it exists)
• Depth-bounded and iterative deepening searches are
incomplete search algorithms based on depth-first
search
– Depth-bounded depth-first search
• set limit on depth of search in tree
– Iterative deepening search
• use depth-bounded search but increase limit as
search progresses
Best-first search
• What if the system has some knowledge about how to
find the goal, and selects its search in the direction of the
earliest possible achievement of the goal?
– enables the search to move as quickly as possible in
the direction of the goal
• Best-first search
– pick whichever element of frontier seems most
promising
• Information given to the system may or may not help in
finding the solution
– best-first search is an incomplete search
What is “best”?
• Best-first search builds tree by pursuing the more
promising paths to greater depths and consider alternate
paths only if our current path leads to a failure state
– strategic search
– similar to the process a human would follow
– follow option that appears best rather than pursing all
possible options at once
• How does one judge which option is most promising?
– intuition, reasoning, …
• How does one program a computer to judge which
option is most promising?
Heuristics
• General definition
– educated guess that reduces or limits the search for
solutions in spaces that are complex and poorly
understood
• In CS terms
– quantitative value associated with each state that
attempts to characterize the distance from that state
to the nearest goal
• Value to minimize cost or maximize gain
• Given a choice between two or more states the one with
the smallest cost (or largest gain) is the one representing
the direction we should pursue
Why do we use heuristics?
• Required when problems have many solutions and
performing an exhaustive search would be near
impossible
• We can perform an exhaustive search for Tic-Tac-Toe
– 9! = 362,880 states
• Not practical for games like checkers ( 1040 states) ,
chess ( 10 120 states) or Go (361!  10750 states)
• However …
– heuristics have no theoretical guarantee!
• solution not necessarily optimal or even feasible
Good heuristics
• Good heuristics should have the following characteristics
– give a reasonable estimate of the amount of work
required to reach the associated solution state
• provides meaningful information when selecting
among options
• the better the estimate given by the heuristic, the
better the decisions made based on that
information will be
– easy to compute
• use of the heuristic should not become a burden to
the search process (i.e. slow it down completely)