CIS 391 - Artificial
Intelligence
Fall 2012
COURSE STRUCTURE * MODULES AND NOTES * ASSIGNMENTS * RESOURCES
Instructor
Mitch Marcus
Levine 503, 215-898-2538
mitch (AT) cis.upen.edu
Office Hours: Mon 2-4 & by appointment (e-mail).
Course Administrator
Cheryl Hickey
Levine 502, 215-898-3538
cherylh (AT) cis.upen.edu |
Teaching Assistant
Wes Luwei Zhou
Towne 221
luweiz (AT) seas.upenn.edu
Office Hours: Wed 5-7
|
Class
Schedule:Tuesday & Thursday 1-1:30 PM,
Towne 315
Artificial Intelligence is considered from the point of view of a
resource-limited knowledge-based agent who must reason and act in the
world. Topics include search, knowledge representation and reasoning,
probabilistic reasoning, machine learning, logic, automatic theorem
proving, and natural language processing. Programming assignments in
Python.
Prerequisites: CIS 121
COURSE STRUCTURE
Web Page:
http://www.seas.upenn.edu/~cis391/
- Textbook:
- Artificial Intelligence: A Modern Approach
- (Third Edition) 2009
- Stuart Russell and Peter Norvig
- Prentice Hall Series in Artificial Intelligence
- Grading:
- 40% Homeworks (Final project will count for 1/4 of that amount)
- 30% Midterm 1
- 30% Midterm 2
- Homework:
- Homework will be due at 11:00 a.m. on specified dates, unless otherwise specified
- Late homeworks will be penalized unless an extension has
been granted in advance :
- -- 15% reduction if 0-24 hours late
- -- 30% reduction if handed in at the following class
- -- 45% reduction if handed in two classes later
- -- no credit if more than a week late
Back to
Top
CLASS MODULES
Links to classroom slides will appear below.
Lecture Notes are in PDF format.
Module 0: Introduction
AIMA Textbook: Chapters 1-2
- Introduction
- 9/6 Introduction to Artificial Intelligence
[(pdf) ] ( AIMA, Chapter 2)
- 9/11 Intelligent Agents [(pdf) ] ( AIMA, Chapter 2)
- Python Programming
- Readings: Slides should be sufficient. See Resources for additional materials, including on-line Python library reference and on-line books.
- 9/13 Python Review [(pdf) ] Much more thorough Python tutorial [(pdf)]
Module 1: Search
AIMA Textbook: Chapters 3-6
- Search
- 9/20 Uninformed Search Part I [(pdf) ] (AIMA 3.1-3.2)
- 9/25 Uninformed Search Part II [(pdf) ](AIMA 3.3-3.4)
- 9/27 Uninformed Search Part III, Intro to Informed Search(pdf) ]
- 10/2 Informed Search Part 1I
[(pdf)] (AIMA 3.5.1, 3.5.2, 3.6)
- 10/4 Local Search & Genetic Algorithm [(pdf)] (AIMA 4.1 (skipping the rest of Chapter 4))
- Adversarial Search
- 10/9 2-Player Games: Adversarial Search [(pdf)] (AIMA 5.1-5.3)
- Constraint Satisfaction
- 10/16 Introduction to Constraint Satisfaction [(pdf)][(6-up)] (AIMA 6.1-6.4)
- 10/18 Interpreting Line Drawings vis Constraint satisfaction [(pdf)][(6-up)](AIMA 6.1(roughly), 6.2)
- 10/18 Handout: The Huffman-Clowes Labelling Set [(pdf)]
- 10/25 Interpreting Line Drawings vis Constraint satisfaction - Part II [(pdf)][(6-up)]
- 10/30 Penn shut - Hurricane Sandy
MIDTERM 1 - Tuesday, Nov 6
- 11/1 Review slides [(pdf)][(6-up)]
- A practice midterm (two years ago) with solutions is available here
Module 2: Machine Learning and Natural Language Processing
- Introduction to Probability
- 11/8 Uncertainty & Probability [(pdf)][(6-up)] (AIMA 13.1-13.5)
- Naive Bayes & Spam Filtering
- 11/13 Naive Bayes/Spam Filtering [(pdf)][(6-up)] (AIMA 22.2)
- 11/15 Language models and Markov Models
[(pdf)][(6-up)]
(some topics covered in AIMA 15.2; Markov Models in Jurafsky &
Martin, Speech and Language Processing, 4.1-4.3; Smoothing in
J & M Chap. 4.5 Intro and 4.5.1)
- 11/20 Part of Speech Tagging and Hidden Markov Models
[(pdf)][(6-up)]
(some topics covered in AIMA 15.3. Good discussion in J&M,
5.1, 5.2, 5.5)
- 11/27 Perceptrons and Support Vector Machines
[(pdf)][(6-up)]
Module 3: Knowledge Representation and Logic
- 11/29 Propositional Logic /& Inference
[(pdf)][(6-up)] (AIMA 7.1-7.4)
- 12/4 An Intro First Order Logic \& Inference[ (pdf) ][ (6-up) ] [][](AIMA 8.1-8.3, 9.1-9.2)
MIDTERM 2 - Thursday, Dec 6
- 11/1 Review slides [(pdf)][(6-up)]
- A practice midterm (two years ago) with solutions is available here.
Topics not covered this year, so you can ignore: Problems 1.2,1.6, Problem 4.
Back to Top
HOMEWORK
ASSIGNMENTS
- PDF Files
require Adobe
Acrobat Reader
- DOC Files
require Microsoft Word or Open Office
-
- Homework
1 - Due Friday., Oct 12, 2012 by 5 p.m. Problem 1-8, Extra credit: Problem 9. Emailing your solutions to Wes Luwei Zhou is fine (see Piazza)
You can find the encrypted file vfd.txt for the homework here. (Right click and then use "Save Link As..." or "Save Target As.." to save it...)
- Homework 2 - Due Tuesday, Oct. 30 at noon. UPDATE: EXTENDED TO THURSDAY, NOV. 1 AT NOON. You may email Luwei or hand in a hard copy of non-coding problems, but email any code to Luwei at the mailbox given on Piazza.
The code for the last question can be found here.
- Homework 3 - Due Wednesday, November 21 at 5 p.m. by email.
The sudoku problems to test on can be found here.
FINAL PROJECT
(Full handout is available in class, and will be posted here by Monday evening.)
You will implement a Connect 4 agent using algorithms that you have learned in class.
Specifically, you should adhere to the following guidelines.
Your agent should use the minimax algorithm to determine the next move. The game
space will be too large for you to construct the entire tree, and so your search tree will be
limited in depth. To determine which move is best, you need to develop a static evaluator
to be used in the leaves of your search tree. Remember that a static evaluator is a heuristic
function that tells you approximately how good a given game board is for you. It is up to
you to think of a good static evaluation function, which will have a large in
uence on how
well your algorithm performs.
You are also encouraged to use other AI techniques beyond just minimax. For example,
you might improve your algorithm by using alpha-beta pruning, or even a more advanced
pruning technique. You can also make your static evaluator as complex as you wish.
There will be a time/memory limit for each turn. I haven't decided on what these will
be yet, but as a rule you should be able to play against the machine in real-time.
In addition to the code, you should provide a write-up of the strategy of your agent.
This should include details on your static evaluator and of what other techniques you used
in your agent. This writeup can be brief, 1-3 pages.
You should turn in your AIConnect4Player.py as well as your writeup.
Important note: Connect 4 is a solved game in that an optimal strategy does exist.
You may not just implement these strategies. The goal of this project is for you to use AI
algorithms. You are, however, encouraged to research more than has been taught in class,
including other pruning algorithms or even machine learning techniques.
Due Wednesday, Dec 19 by midnight>
Auxiliary files (in .zip format): project_code.zip,
Back to Top
OTHER RESOURCES
Python Resources
-
Textbook Resources
Website for: Artificial
Intelligence: A Modern Approach
(http://aima.cs.berkeley.edu/)
Back to Top
For more information, please contact mitch (AT)
cis.upenn.edu