CIS 240: Artificial Intelligence Spring Quarter, 2008 Lectures: TuTh 12-145PM TTh Merrill Acad 003 Instructor: Robert Levinson Office Hours: W4-6pm, after class (in Crown Lab/study area) or by appointment. Phone number: 459-2087 (x2087 on campus) E-mail: levinson@cse.ucsc.edu (use it!) Newsgroup: ucsc.class.cmp240 (use it, too!) Optionally, also follow: comp.ai.alife Reader: ??? TA??? Required: AI Text: "Artificial Intelligence: A Modern Approach" Stuart Russell and Peter Norvig Prentice Hall, Second Edition. 2003 ISBN 0-13-790395-2 Webpage: http://aima.cs.berkeley.edu/ ET: Jaynes, E.T. and G. Larry Brethorstt Probability Theory: Logic of Science. Cambridge Press 2003 Or download from the web: http://omega.albany.edu:8008/JaynesBook.html Chapters 1-5 http://bayes.wustl.edu/etj/prob/book.pdf CH: the UCSC Reader by Chris Harrison: Determining Satisfiability Through Subtraction And a Binary Constrained XOR Form (BXCF). PH: Probability problems handout. (pick up in class). References: Rich, Elaine. Knight, Kevin Artificial Intelligence., Second Edition! McGraw-Hill Book Co.,New York,1990. Elementary Probability - David Stirzaker Cambridge University Press - 1994. An Introduction to Natural Computation Dana Ballard, The MIT Press, 1997. Prereqs: Grad. Standing, or instructor's permission. Previous AI course is helpful but not required. (CMPS140 = approximately chapters 1-5, 13, 18, 20 of above but at a somewhat lower level). PROJECT HELP: Knights and Knaves Logic Puzzles: http://www.hku.hk/cgi-bin/philodep/knight/puzzle Peirce's Existential Graphs for Propositional Logic: http://plato.stanford.edu/entries/peirce-logic/#EG Automatic Theorem Provers (including OTTER and VAMPIRE and benchmarks) http://www.answers.com/topic/automated-theorem-proving Satisfiability Benchmarks and Solvers and More! http://www.satlib.org/index-ubc.html http://www.satlive.org Tile Puzzles: A Pattern-Weight Formulation of Search Knowledge Gil Fuchs and Robert Levinson (to be made available) Some interesting web pages on intelligent agents: http://www.cs.umbc.edu/agents/ General AI links: http://www.cs.berkeley.edu/~russell/ai.html Internet Chess Club: telnet chessclub.com or http://www.chessclub.com Interesting Papers on Complex Adaptive Systems: http://www.santafe.edu/research/publications/working-papers.php COURSE THEME: Think for yourself! COURSE EQUATION: Total Information = Diversity (Complexity) + Mutual Information In Parts COURSE WORD: SUBSUMPTION COURSE SYMBOL: * During the course there will be a multi-stage programming project, regular homework problems and a final exam. The development of a Subtraction-Based Boolean Satisfier (see CH), FirstOrder--> SAT theorem prover, 8 puzzle Random Number prediction, and Morph (adaptive chess), "Knights and Knaves" are likely some of the projects. Projects will be distributed by the instructor and some students may not get their desired choices. Course Evaluation: Programming Project %35 Written Homework %35 Final Exam %20 Class Participation %10 The written homeworks are to be done INDIVIDUALLY. Programming projects may be done in teams of 2-3 that are setup at the beginning of the quarter and maintained throughout the quarter. All work may be graded competitively as well as qualitatively. Grade Levels: 90% A- or better 80% B- or better It is fine and encouraged to discuss homework problems with other students - BUT CHEATING or ACADEMIC DISHONESTY on any course item (such as direct verbatim copying from a member outside your group or during an exam) will result in not passing the course and other undesirable consequences. Written problem solutions should reflect YOUR OWN UNDERSTANDING and be in YOUR OWN WORDS. All references used should be cited. Exceptional performance may be recognized (extra credit). NO INCOMPLETES WILL BE GIVEN. =============================================================== Lecture Schedule (tentative) ---------------------------- Problems below are assigned unless otherwise announced in class and/or in the newsgroup. Other problems may be added in addition to these. In addition, to the text, chapters (ET) are assigned from the book, Probability Theory: The Logic of Science available at the book store. CH: refers to the Harrison reader EC= not required, extra credit. Due dates for project to be announced. There will be a series of project checkpoints. I. Introduction to Expert Systems AI Text: Chapters 1-3 are mainly review. 6-7. HW0: handout in class. Due Thursday april 3. HW1: Due Thursday april 10: AI Text Exercises: 7.4, 7.5, 7.6, 7.8, 7.9 ET: Chapter 10. No exercises. PH: Problems 1.1 and 1.2 CH: Chapter 1-2 Write an exercise for each chapter and answer it. 1. (Tues. April 1) 2. (Thurs April 3) HW0 is due. [see handout] II. Knowledge Bases and Inference HW2: Due: Thursday April 24 AI Text: Chapters 8-10: 8.2, 8.6adgjk, 9.3, 9.11, 9.18, 9.19 ET: Chapters 1-2: 2.1,2.3 CH: Chapters 3-4 Write an exercise for each chapter and answer it. PH: Problems 1.3 and 1.4 3. (Tues. April 8) 4. (Thurs. April 10) HW1 is due. 5. (Tues. April 15) 6. (Thurs. April 17) Project checkpoint1 is due. III. Reasoning Under Uncertainty HW3: Due Thur May 8: AI Text: Chapters 13,16 13.3, 13.8, 13.11, 13.15, 13.16 16.3, 16.7 (prove the problem statement is wrong!!), 16.11 ET: None CH: Chapters 5-6 Write an exercise for each chapter and answer it. PH: Problems 1.5 and 1.6 7. (Tues. April 22) 8. (Thurs. April 24 ) HW2 is due 9. (Tues. Apr. 29) 10. (Thurs. May 1) Project checkpoint2 is due. IV. Communication: Pattern Matching, Analogy and Retrieval HW4: Due Thursday May 22 AI Text: Read: Chap 22 ET: 4: 4.2,4.3 CH: Chapters 7-8 Write an exercise for each chapter and answer it. PH: Problems 1.7 and 1.9 and 1.17 and 1.21 11. (Tues. May 6) 12. (Thurs. May 8) HW3 is due 13. (Tues. May 13) 14. (Thurs. May 15) Project checkpoint 3 is due. 15. (Tues. May 20) 16. (Thurs. May 22) HW4 is due 17. (Tues. May 27) 18. (Thurs. May 29) Project Checkpoint 4 is due. 19. (Tuesday June 3) 20. (Thursday June 5) Projects are Due. Final Exam may be handed out. 21. FINAL EXAM Wed. June 11, 12-3PM