Transcript Intro to AI, Search, and Game Playing

Artificial Intelligence
and Searching
CPSC 315 – Programming Studio
Spring 2008
Project 2, Lecture 1
Adapted from slides of
Yoonsuck Choe
Artificial Intelligence

Long-standing computational goal


Field of AI very diverse




Turing test
“Strong” AI – trying to simulate thought itself
“Weak” AI – trying to make things that behave intelligently
Several different approaches used, topics studied
Sometimes grouped with other fields


Robotics
Computer Vision
Topics in Artificial Intelligence











Problem solving
Reasoning
Theorem Proving
Planning
Learning
Knowledge Representation
Perception
Agent Behavior
Understanding brain function and development
Optimizing
etc.
Game Playing and Search

Game playing a long-studied topic in AI


Seen as a proxy for how more complex reasoning can be
developed
Search


Understanding the set of possible states, and finding the
“best” state or the best path to a goal state, or some path
to the goal state, etc.
“State” is the condition of the environment
 e.g. in theorem proving, can be the state of things known


By applying known theorems, can expand the state, until reaching
the goal theorem
Should be stored concisely
Really Basic
State Search Example

Given a=b,b=c,c=d, prove a=d.
a=b, b=c, c=d
a=b, b=c, c=d
a=c
a=b, b=c, c=d
b=d
a=b, b=c, c=d
b=d, a=d
Operators

Transition from one state to another





Fly from one city to another
Apply a theorem
Move a piece in a game
Add person to a meeting schedule
Operators and states are both usually limited
by various rules


Can only fly certain routes
Only valid moves in game
Search



Examine possible states, transitions to find
goal state
Interesting problems are those too large to
explore exhaustively
Uninformed search


Systematic strategy to explore options
Informed search

Use domain knowledge to limit search
Game Playing


Abstract AI problem
Nice and challenging properties




Usually state can be clearly, concisely represented
Limited number of operations (but can still be large)
Unknown factor – account for opponent
Search space can be huge
 Limit response based on time – forces making good
“decisions”
 e.g. Chess averages about 35 possible moves per turn,
about 50 moves per player per game, or 35100 possible
games. But, “only” 1040 possible board states.
Types of games


Deterministic vs. random factor
Known state vs. hidden information
Examples
Deterministic
Perfect Info
Chess, Checkers, Monopoly,
Othello, Go
Backgammon
Imperfect Info Stratego,
Bridge?
Chance
Poker, Scrabble
Bridge?
Game Playing


In upcoming lectures, we will discuss some of
the basic methods for performing search
Project will focus on a deterministic game
with perfect information