Testing Our Assumptions about AI: part
3 - Problem-Solving – March 17, 2003
1. Approaches to Problem-solving
-->as seen through problems to solve (getting
dressed, Tower of Hanoi, chess, train
puzzle –distributed in lecture)
**********
1. Approaches to Problem-solving
Problem-solving involves a search for
an ideal or winning solution among a
very large number of possibilitie….s
How do we know how “to search”?
Let’s say your problem this morning
was what to wear to university.
Problem #1: getting dressed.
You could have chosen your wardrobe in
at least 4 ways:
1. totally randomly
2. “Brute-force” search:
By taking all your clothes, dumping everything
on your bed, and going through all the
choices (pants, shirts/tops, etc.) till
you have an esthetically-pleasing combination.
3. By setting up a series of hard and
fast rules--called an algorithm: say,
always wear blue jeans and a white top.
[Definition of an algorithm: a precise
set-by-step description of a procedure
for solving a problem (carried out the
same way each time)] A good example is
the way we learn to find an average mark.
4. Or by picking clothes by some set
of heuristics.)
[Definition of a heuristic: a rule of
thumb, or a set of guidelines that might
help you solve the problem.]
-->We’re such good problem solvers
that we have many thousands of heuristics
that allow us to be efficient problem
solvers (first two choices above are
inefficient; the third is too rigid).
Problem #2: Tower of Hanoi Puzzle
-->the heuristic of "means-end analysis" which
is used to solve many problems, like
the Tower of Hanoi. (See Wessells, in
kit).
-->
you have to break the goal down into
sub-goals and then you’ve solved
the problem. (Make sure you can solve
it!)
Problem #3 Chess:
à a closed system where the possible moves,
the role of each piece, and the goal
is always the same
à
YET it’s very complicated: each
player has approximately 30 possible
moves at each stage. (see game tree in
Wessell’s article)
à It would theoretically be possible to
have 12010 different games
How do humans play? clearly not by the "brute
force" problem-solving solution?
--> it isn't feasible for a human
to go through even a small percentage
of all the choices, so in order to win
we have to follow a different problem-solving
strategy which is to follow various heuristics:
--> for example, capture opponent's
pieces--without losing many of your own
and you may win the game (However, games
are lost even when an opponent has fewer
pieces.)
But can every strategy that the grand
master uses be programmable? NO (see
notes below from Deep Blue web site)
How does Deep Blue work?
--> doesn’t use brute force
entirely; eliminates irrelevant searches
at the beginning
--> looks at the pieces, computes
everything it knows about the current
position, integrates the chess information
pre-programmed by development team, and
then
--> can generate 200,000,000 positions
per second when searching
--> chooses its best move.
This was written in 1993 (before the
match between Kasparov and Deep Blue):
"
Since the knowledge that a master chess
player has that enables him or her to
play a strong game of chess remains partially
tacit [not capable of being made explicit],
the programmer (of chess programs) must
rely on those principles of strategy
and tactics that can be made explicit
[like old game plans of past Grand Masters],
and hope that those heuristics [and plans],
in conjunction with a superhuman
ability to examine large numbers of board
positions
will result in a win for the computer." (Moody,
1993, p. 107)
The IBM Chess Program, Deep Blue, beat
the world Grand Master, Gary Kasparov
recently. Does this prove that a computer
is “smarter” than a human?
absolutely NOT...
Follow-up questions:
1. Is it really exhibiting “intelligence?
http://www.chess.ibm.com/meet/html/d.3.3a.html#ai
“
The short answer is "no." Earlier
computer designs that tried to mimic
human thinking weren't very good at it.
No formula exists for intuition. So Deep
Blue's designers have gone "back
to the future." Deep Blue relies
more on computational power and a simpler
search and evaluation function.”
“Deep Blue's strengths are the strengths of a machine. It has more chess
information to work with than most computers and all but a few chess masters.
It never forgets or gets distracted. And its orders of magnitude are better at
processing the information at hand than anything yet devised for the purpose.
"There is no psychology at work" in Deep Blue, says IBM research scientist
Murray Campbell. Nor does Deep Blue "learn" its opponent as it plays.
Instead, it operates much like a turbocharged "expert system," drawing
on vast resources of stored information (For example, a database of opening games
played by grandmasters over the last 100 years) and then calculating the most
appropriate response to an opponent's move.”
2. What is the usefulness of the program for other applications?:
( see http://www.chess.ibm.com/meet/html/d.3.4.html
-->applications in financial modeling, data mining and molecular dynamics
The Train Puzzle
{If you weren’t in lecture, you need to obtain a handout of the train puzzle}
