**CSCI 377: Artificial Intelligence**

###### REED COLLEGE, FALL 2018

An introduction to the construction of software systems that emulate intelligent behavior. Topics include knowledge representation, reasoning under uncertainty, logic, planning, and algorithmic strategies for large-scale combinatorial search. Students will explore these topics with a series of implementation projects. Prerequisites: Computer Science 221 and Mathematics 113.

### BASIC INFO

**Professor:** Mark Hopkins, hopkinsm@reed.edu

**Class Schedule:** MWF 9-950am in Eliot 314

**Office Hours:** Tu 445-6pm, W 10-11am, Th 10-1130am, F 4-5pm in Library 314

**Textbook:** *Artificial Intelligence: A Modern Approach (3rd edition)* by Stuart Russell and Peter Norvig. Make sure to get 3rd edition! AI has progressed a lot since the first edition.

**Syllabus:** downloadable here

### SCHEDULE

**Aug 27: Introduction and Propositional Logic**

**Reading (optional):**AIMA (Artificial Intelligence: A Modern Approach) Ch. 1

**Aug 29: Propositional Logic**

**Reading:**AIMA 7.1, 7.2. The title of Chapter 7 is “Logical Agents”.**Assignment (due Fri., Aug 31):**Create a truth table over the following four variables: Dog (whether one is a dog), Mammal (whether one is a mammal), Bird (whether one is a bird), and Fly (whether one can fly). Try to make the truth table represent reality. Also, create three propositional sentences over the signature {D, M, B, F} that you predict will be “true”.

**Aug 31: Propositional Logic**

**Reading:**AIMA 7.3, 7.4, 7.5 (intro), 7.5.1. The title of Chapter 7 is “Logical Agents”.**Assignment (due Wed., Sept. 5):**Prove DeMorgan’s law: I(not (A or B)) = I((not A) and (not B)). Complete AIMA Exercises 7.7, 7.8.

**Sep 5: Propositional Logic – Inference**

**Reading:**AIMA 7.5.2 (“Proof by Resolution”)**Assignment (due Fri., Sept. 7):**(pdf)

**Sep 7: Propositional Logic – Inference**

**Reading:**No new reading.**Assignment (due Mon., Sept. 10):**AIMA Exercise 7.12 (“Use resolution to prove the sentence…”)

**Sep 10: Propositional Logic – Inference**

**Reading:**No new reading.**Assignment:**Nothing due, just read the lecture notes and let me know if you find any bugs, particularly in the proofs.

**Sep 12: Propositional Logic – Inference**

**Reading:**No new reading. We will be trying things out on the computer during lecture.**Assignment (due Fri., Sep. 14):**AIMA 7.21 (“Is a randomly generated 4-CNF sentence with n symbols and m clauses more or less likely to be solvable than a randomly generated 3-CNF sentence with n symbols and m clauses? Explain.”)**Please also briefly discuss how the graph in Figure 7.19(a) would look for random 4-CNF sentences, compared to the graph for random 3-CNF sentences.**

**Sep 14: Propositional Logic – Inference**

**Reading:**AIMA 7.6 (intro), 7.6.1 (“A complete backtracking algorithm”), 7.6.3 (“The landscape of random SAT problems”).**Assignment (due Mon., Sept. 17):**(pdf)

**Sep 17: First Order Logic**

**Reading:**AIMA 8 (intro), 8.1 (“Representation Revisited”), 8.2 (“Syntax and Semantics of First-Order Logic”).**Assignment (due Wed., Sept. 19):**AIMA 8.10 (“Consider a vocabulary with the following symbols…”)

**Sep 19: First Order Logic**

**Reading (optional, if interested):**AIMA 8.3 (“Using First-Order Logic”), 8.4 (“Knowledge Engineering in First-Order Logic”)**Assignment (due Fri., Sept. 21):**(pdf)

**Sep 21: First Order Logic**

**Reading:**AIMA 9.1 (“Propositional vs. First-Order Inference”), 9.5.1 (“Conjunctive Normal Form for First-Order Logic”)

**Sep 24: Midterm**

**Sep 26: Midterm Review and Project Preview**

**Assignment (due Fri., Sept. 28):**The n-queens problem asks you to place n queens on an n x n chessboard so that no queen is attacking another. In class, we discussed one possible state graph formulation where each state (a vertex of the graph) is a board configuration with n queens on it, and each action (an edge of the graph) changes the position of a single queen. This formulation is cyclic. There is another formulation, where each state is a board configuration with 0 to n queens on it. What action could we use to ensure that the state graph is**acyclic**? Draw the resulting state graph for the 2-queens problem.

**Sep 28: Search Spaces**

**Reading:**AIMA 3.1 (“Problem-Solving Agents”), 3.2 (“Example Problems”)**Assignment (due Mon., Oct. 1):**In the notes on State Spaces (below), the state machine for word ladder has the annoying property that you can go back and forth indefinitely between two words by changing one letter and then changing it back, e.g. BRAIN -> TRAIN -> BRAIN -> TRAIN. Can you define the state machine differently, so that this doesn’t happen (i.e. there are no cycles of length 2 or less)?

**Oct 1: Uninformed Search**

**Reading:**AIMA 3.3 (“Searching for Solutions”), AIMA 3.4 (“Uninformed Search Strategies”).**Assignment:**No homework, but you might want to do Q1-Q3 of Pacman Project 1. Remember that the entire project is due on**Wed., Oct. 10**(before class).

**Oct 3: Analysis of Search Algorithms**

**Reading:**No additional reading.**Assignment:**AIMA Exercise 3.16 (a) and (b). Don’t get too hung up on overly formalizing the search problem (unless you want to); just define it in terms that a human could execute. Part (b) is the more important part of the problem.

**Oct 5: Heuristic Search**

**Reading:**AIMA 3.5 (“Informed (Heuristic) Search Strategies”)**Assignment:**Prove that if a heuristic function is consistent, then it must be admissible (hint: use induction on the length of the optimal completion path).

**Oct 8: Heuristic Search**

**Reading:**AIMA 3.6 (“Heuristic Functions”)**Assignment:**AIMA Exercise 3.30 (a): “The traveling salesman problem (TSP) can be solved…” The Traveling Salesman Problem is described in the textbook near the end of Section 3.2.

**Oct 10: Analysis of Search**

**Reading:**No reading assignment.**Assignment:**AIMA Exercise 3.18 (“Describe a state space in which iterative deepening search performs much worse than depth-first search.”)

**Oct 12: Project 1 Review/Project 2 Preview**

**Reading:**No reading assignment.

**Oct 22: Games and Minimax**

**Assignment:**AIMA Exercise 5.8abc (“Consider the two player game described in Figure 5.16…”)

**Oct 24: Alpha-Beta Search**

**Reading:**AIMA 5.1 (“Games”), 5.2 (“Optimal Decisions in Games”), 5.3 (“Alpha-Beta Pruning”), 5.4 (“Imperfect Real-Time Decisions”).**Assignment:**AIMA Exercise 5.24 (“Consider the game tree shown below…”)

**Oct 26: Expectimax**

**Reading:**AIMA 5.5 (“Stochastic Games”)**Assignment:**None; but remember that the second project is due before class on Monday.

**Oct 29: Markov Decision Processes**

**Reading:**AIMA 17.1 (“Sequential Decision Problems”), 17.2 (“Value Iteration”)**Assignment (note this is due next Monday, November 5):**AIMA Exercise 17.9 (“Consider the 101 x 3 world…”)

**Oct 31:** **Project 2 Review/Project 3 Preview**

**Nov 2:** **Midterm 2 (Search)**

**Nov 5: Markov Decision Processes**

**Reading (same as Oct. 29):**AIMA 17.1 (“Sequential Decision Problems”), 17.2 (“Value Iteration”)**Assignment:**(pdf)

**Nov 7: Markov Decision Processes**

**Reading:**No additional reading.**Assignment:**AIMA Exercise 17.8 (“Implement value iteration…”) For this problem, just use an Excel (or Google Sheets) spreadsheet. The solution should require around 45 (9*5) columns and K rows (where K is the number of iterations you run; 10 should be plenty,**except for R=100, which needs about 1000 iterations to see the convergence**).

**Nov 9: Markov Decision Processes**

**Reading:**No additional reading.**Assignment:**None, but please try to complete Q1-Q3 of Project 3 by Monday, just for your own peace of mind.

**Nov 12: Reinforcement Learning**

**Reading:**AIMA 21.1 (“Introduction”), 21.2 (“Passive Reinforcement Learning”)**Assignment:**None, but please try to complete Q1-Q7 of Project 3 by Wednesday, if you can.

**Nov 14: Reinforcement Learning**

**Reading:**AIMA 21.3 (“Active Reinforcement Learning”), 21.4 (“Generalization in Reinforcement Learning”)**Assignment:**None, but all Project 3 tasks are now do-able.

**Nov 16: Probability**

**Reading:**AIMA 13.1-13.5

### LECTURE NOTES

**Propositional Logic (Aug 29-31):**(pdf)**Propositional Logic – Inference (Sep 5-10):**(pdf)**DPLL (Sep 14):**(pdf)**First Order Logic (Sep 17-21):**(pdf)**State Spaces (Sep 26-28):**(pdf)**Uninformed Search (Oct 1-3):**(pdf)**Heuristic Search (Oct 5):**(pdf)**Heuristics (Oct. 8):**(pdf)**Analysis of Search (Oct. 10):**(pdf)**Minimax (Oct. 22-24):**(pdf)**Expectimax (Oct. 26):**(pdf)**Markov Decision Process (Nov. 5-9):**(pdf)**Passive Reinforcement Learning (Nov. 12):**(pdf)**Active Reinforcement Learning (Nov. 12-14):**(pdf)

### LECTURE CODE

**Resolution Solver (Sep 12):**(github)

### PROJECT LINKS

**Search (due Wed., October 10, before class):**(project description) To submit the project, please email me a zipped directory (.zip or .tar.gz) that contains all the project files needed to run your project. The tutorial here may be helpful to learn how to use the self autograder (and to brush up on Python, if necessary). This project uses Python 2.7, so make sure you have your computer set up so that you can switch easily between Python 2 and Python 3. Come to office hours if you don’t know how to do this.**Multiagent Search (due Mon., October 29, before class):**(project description) To submit the project, please email me a zipped directory (.zip or .tar.gz) that contains all the project files needed to run your project.**Reinforcement Learning (due Mon., November 19, before class):**(project description) To submit the project, please email me a zipped directory (.zip or .tar.gz) that contains all the project files needed to run your project.**Ghostbusters (OPTIONAL, due Wed., December 5, before class):**(project description) Note that this project is**optional**. If you complete it, then I will raise one of your exam scores by a letter grade, or replace the grade of your worst previous project (whichever works out better). To submit the project, please email me a zipped directory (.zip or .tar.gz) that contains all the project files needed to run your project.