Transcript AI - Computer Science

Aside on AI



Will computers ever be intelligent?
Really intelligent?
Tasks that previously were thought to require intelligence:










adding and subtracting
playing chess
driving a car
recognizing speech or handwriting
translating to a foreign language
proving mathematical theorems
What does it mean to say that a computer is intelligent?
Is that the same as being a person? What is a person?
Is a computer program a person?
Is a person a computer program?
Achieving “Intelligence”


How do AI program achieve “intelligent”
behavior?
Currently, four main paradigms:




Neural Nets
Genetic Algorithms
Symbolic knowledge representation and search
Statistical machine learning
Neural Nets







Model behavior of neurons
Each neuron has many Inputs
Output is weighted sum of inputs
Training: adjusting the weights to improve behavior
Learning: networks improve performance with time
Feedback: large networks with feedback have very
complicated behavior (pondering? dreams?)
Success: many (small) problems are handled well;
bigger problems are problematic
Genetic Algorithms






Many similar simulated organisms, each with its own
program governing behavior
The organisms are run for a time, and their behavior
is measured for fitness
The more successful organisms are more likely to
cross (reproduce)
Random mutations can also be introduced in the
programs
Each generation tends to have more successful
behavior than the last, on average
Results: good for some optimization problems
Statistical machine learning


Gather much data
Find patterns
Symbolic AI






Represent a problem as a collection of logic
(symbolic) statements
Characterize the initial condition symbolically
Characterize goal state symbolically
Characterize actions that are possible in the world as
productions or changes to the initial condition
Search through possible actions to find a path to the
goal
Google’s knowledge graph
Search in Artificial Intelligence

Represent your problem as a graph where nodes are
states and edges are operators that go between states





Define problem states (nodes)
Identify start and goal states
Define operators (edges)
Use DFS or BFS to find goal
Example: Missionaries and cannibals problem

states: (3,3,1)  3 missionaries, 3 cannibals, and 1 boat on
left side of river.
Operators: one or two people cross the river in the boat, so
that there isn’t a cannibal majority on either side.
Goal: get to the other side?
Moves?

(331)–(220)–(321)–(210)–(221)–(020)–(031)–(010)–(021)–(000)



Computer Chess


How would you program a computer to play
chess?
Brute force or intelligence? The slow rise of
computer chess
Game Playing

We could use DFS but…can’t search whole tree!


limit depth of search and use an evaluation function
We could use DFS but…how do we know which
move the opponent will choose?


minimax algorithm: assume the opponent does what
looks best.
i.e. at nodes where it is the human’s turn, pick the move
that looks best for human. Where computer’s turn, pick
the move that looks best for the computer
DFS/BFS Resource Requirements

DFS:

Runtime?



O(n), n=number of nodes expanded
Space required?
O(d), d = depth of search

Can I cut off a search after 3 seconds?
BFS:

Runtime? O(n)

Space required?
O(breadth of tree) = O(bd), b=branching factor

Can I cut off a search after 3 seconds?
Staged DFS: do a DFS of depth 1, 2, 3, … until out of time

Runtime?
O(n)

Space required? O(d)
Mankalah



An ancient gamed called Kalah or Mankalah uses stones and pits: 6 to
a side and one on each end.
4 stones are initially placed in each side pit. None are in the end pits
(called Kalahs – a player’s kalah is on her right).
A move consists of picking up the stones in a pit and distributing
them, one at a time, in successive pits.




If the last stone is placed in your Kalah, you go again
If the last stone is placed in an empty pit on your side, you capture the
stones in that pit and the opposite one, on the opponent’s side of the
board. These are put into your Kalah.
The game ends when one player has no stones left; the other player
puts all the remaining stones on her side into her Kalah.
Whoever ends with more stones in her Kalah wins.
 Can you make your Kalah program smarter than Bonzo?
Mankalah minimax
Result minimaxVal(Board b, int d)
// d is depth
if (b.GameOver() or d==0)
return new Result(0, evaluate(b))
if (b.whoseMove()==Board.TOP)
//TOP is MAX
bestVal = -infinity
for (move=first; move<=last; move++)
if (b.legalMove(move) [and time not expired])
Board b1 = new Board(b) //duplicate board
b1.makeMove(move)
//make the move
val=minimaxVal(b1,d-1)
//find its value
if (val>bestVal)
//remember if best
bestVal=val; bestMove=move
else // similarly for BOTTOM’s move
return new Result(bestMove,bestVal);
Parallelizing minimax?

Algorithm- or data-parallelism?
C# Task Parallel Library (TPL)
Other ideas for improving play?





Better evaluation function
Optimize program speed
Learning for feature-weight tuning
Opening or closing book
Alpha-beta pruning with move reordering
(potentially 33% deeper search)
Heuristic Search Techniques


What do you do when the search space is
very large or infinite?
We’ll study three more AI search algorithms:



Backtracking search
Greedy search (Best-first)
A*
Example: the 8-puzzle

How would you use AI techniques to solve
the 8-puzzle problem?
Symbolic AI solution



Start state: 5 4 0 6 1 8 7 3 2 (e.g.)
Goal state: 1 2 3 8 0 4 7 6 5
Edges: sliding a tile. From start state:


548610732
504618732
What search algorithm should I use?
Backtracking search





Start at the start state
Search in any direction
Backtrack when stuck
This is really the same as
Used very frequently



Depth-first search
E.g. Perl regular expression matching
E.g. finding a traveling salesman’s circuit
E.g. graph coloring
Is there any way I can be smarter than a blind search?
09-08-04


How to get from Arad to Bucharest?
How to get from Isai to Fagaras?
Greedy Search (Best-first)


Best-first search: like DFS, but pick the path
that gets you closest to the goal first
Need a measure of distance from the goal
h(n) = estimated cost of cheapest path from n to goal
h(n) is a heuristic

Analysis





Greed tends to work quite well (despite being one of the
seven deadly sins)
But, it doesn’t always find the shortest path
Susceptible to false starts
May go down an infinite path with no way to reach goal
How to ensure you’ll find the best solution?
A*


Can we apply the ideas of Dijkstra’s
algorithm?
Pay attention to total path length, not just
distance to the goal
f(n) = g(n) + h(n)
g(n) = distance traveled so far
h(n) = estimated remaining distance (heuristic)


A*: do a DFS-like search with lowest f(n) first
Does this guarantee an optimal solution?
Optimality of A*




Suppose h(n) never overestimates
(such heuristics are called admissible)
Note that f(n) always increases as search
progresses
A* is complete and optimal (though often
slower than best-first search)
The first limitation you are likely to run into
with A* search: not enough RAM in your
computer…
Heuristics for the 8-puzzle



What would a good, admissible heuristic be
for the 8-puzzle?
h1: number of tiles out of place
h2: total distance of squares from destinations
Results of A*

Consider solving the 8-puzzle by search, using
the following algorithms








DFS
BFS
IDS (iterative deepening search): like staged DFS.
A* with heuristic h1
A* with heuristic h2
Will each be able to find the shortest solution?
Which one will find it most quickly?
Which ones will use lots of memory?
Search Cost
IDS
A*(h1)
Effective Branching Factor
A*(h2)
IDS
A*(h1)
A*(h2)
2
10
6
6
2.45
1.79
1.79
4
112
13
12
2.87
1.48
1.45
6
680
20
18
2.73
1.34
1.30
8
6384
39
25
2.80
1.33
1.24
10
47127
93
39
2.79
1.38
1.22
12
364404
227
73
2.78
1.42
1.24
14
3473941
539
113
2.83
1.44
1.23
16
1301
211
1.45
1.25
18
3056
363
1.46
1.26
20
7276
676
1.47
1.27
22
18094
1219
1.48
1.28
24
39135
1641
1.48
1.26
AI and Personhood

AI proponents:



a machine as complex as a brain would be as
intelligent as a person
maybe it would be a person.
Hidden assumptions:



intelligence: I/O, storage, and processing
capabilities
the brain: a machine whose function can be
duplicated by other machines (and function is
what matters)
a person: an intelligent hunk of meat
What makes a person?

Is there anything to being a person besides
“intelligence”?





Consciousness: is it an ‘epiphenomenon’ – or
can it affect the body?
Will: do we make real choices, or are they
determined by the laws of physics?
Affections: is there a ‘love’ algorithm?
Spirit: is there a human capability to know God
beyond the five sense?
Moral responsibility: what are you doing when
you kick your computer – punishment?
What are these views called?

“all the world (including the brain and mind)
operate according to physical laws”


“There is a part of the mind (or soul or spirit)
that is outside of nature, exempt from
physical laws”


Materialism [or metaphysical materialism]
Dualism [or Cartesian dualism]
“The mind is the program running on the
‘wet-ware’ of the brain”

Functionalism [or non-reductive materialism]
Non-Reductive Materialism

Characteristics




there is no non-physical part of a person
mental processes can be localized in the brain
consciousness, will, etc. are real, but they are an ‘emergent
property’ of brain function
Questions





How could there be a real will or moral responsibility?
Where is the intensionality or meaning?
What then can a verse like Matt. 10:28 mean? [Do not be afraid
of those who kill the body but cannot kill the soul.]
What about the existence of angels, God if there is no
second substance?
What of church history and doctrine?
Cartesian Dualism

Characteristics




The soul is a second substance, created by God, like the
Angels
The mind is a faculty of the soul, and it can affect the body
Whatever the brain does, it is not the mind
Questions




A second substance is messy…
Where does this soul come from? How does it affect the
body without breaking the laws of nature?
It seems that current research is localizing more and more
mental processes in the brain…
What does this do to the science of AI?