CSCI 373: Artificial Intelligence

WILLIAMS COLLEGE, SPRING 2023

Artificial Intelligence (AI) has become part of everyday life, but what is it, and how does it work? This course introduces theories and computational techniques that serve as a foundation for the study of artificial intelligence. Potential topics include the following: problem solving by search, logic, planning, constraint satisfaction problems, reasoning under uncertainty, probabilistic graphical models, and automated learning.

BASIC INFO

Professor: Mark Hopkins, mh24@williams.edu

Class Schedule: MWF 9-950am, Schow 30B

Office Hours: Sun 5-7pm (TCL 307)

TA Office Hours (Nathan Hu): MW 6-8pm, F 230-4 (TCL 312 — the “back lab” of the UNIX lab)

Textbook: Artificial Intelligence: A Modern Approach (4th edition) by Stuart Russell and Peter Norvig. Williams Bookstore should have it in stock. If ordering online, make sure to get the newest (4th) edition.

Syllabus: downloadable here

UPCOMING DATES

Mon, May 15 at 11pm: Minesweeper (Project 3)
Mon, May 15, 715pm-845pm: Review Session (TCL 206)
Wed, May 17 at 130pm: Final Exam (2 hours long, open book, open notes, Wachenheim 017)

FINAL EXAM STUDY MATERIALS

Search-Based Reasoning: (practice questions) (solutions)
Probabilistic Reasoning: (practice questions) (solutions)
Logical Reasoning: (practice questions) (solutions)

IN-CLASS PRACTICE PROBLEMS

Magic Squares: (problem) (solution)
Iterative Deepening: (problem) (solution)
TwoDoku: (problem) (solution)
MoveDoku: (problem) (solution)
Elimination Orders: (problem) (solution)
Treewidth: (problem) (solution)
Complexity of Belief Propagation: (problem) (solution)
Flight Delay: (problem) (solution)
Logical Equivalence: (problem) (solution)
Minimal Redundant Sets: (problem) (solution)
Complexity of Resolution: (problem) (solution)

LECTURE NOTES

State Spaces: (pdf)
Uninformed Search: (pdf)
Analysis of Search: (pdf)
Minimax: (pdf)
Expectimax: (pdf)
Heuristic Search: (pdf)
Heuristics: (pdf)
Probability: (pdf)
Bayesian Networks: (pdf)
Exact Inference: (pdf)
Exponential Distributions (e.g. the normal distribution): (pdf)
Markov Decision Processes: (pdf)
Passive Reinforcement Learning: (pdf)
Active Reinforcement Learning: (pdf)
Language and Semantics: (pdf)
Propositional Logic: (pdf)
Propositional Inference: (pdf)
Resolution: (pdf)
DPLL: (pdf)

PROJECT LINKS

Wordle (due Mon Mar 13 at 11pm): (assignment)
Turbo Coding (due Mon Apr 17 at 11pm): (assignment)
Minesweeper (due Mon May 15 at 11pm): (assignment)

ASSIGNMENT LINKS

Blocks (due Mon, Feb 13 at 11pm): (assignment)
8 Out of 10 Cats Does Search (due Mon, Feb 20 at 11pm): (assignment) (solution)
Multiplayer Pacman (due Mon, Feb 27 at 11pm): (assignment)
Nim (due Mon, Feb 27 at 11pm): (assignment) (solution)
Single-Agent Pacman (due Mon, Mar 6 at 11pm): (assignment)
Bloodlines 1 (due Mon, Apr 3 at 11pm): (assignment)
Bloodlines 2 (due Mon, Apr 3 at 11pm): (assignment)
The Squid and the Whale (due Mon, Apr 10 at 11pm): (assignment)
Blackjack (due Mon, Apr 24 at 11pm): (assignment)
Youdoku, Part One (due Mon, May 1 at 11pm): (assignment) This assignment may be done either individually or jointly with your Project 3 partner.
Youdoku, Part Two (due, Mon, May 8 at 11pm): (assignment) This assignment may be done either individually or jointly with your Project 3 partner. It is a double-point homework (i.e. it counts for twice the value of a regular homework). Start early and work through it methodically.

VIDEOS

Github Classroom Walkthrough: (mp4)

SCHEDULE

Feb 3: Course Information Session

Feb 6: Search Spaces (slides A1) (slides A2)

Before class, please read AIMA 3.1, 3.2.

Feb 8: Uninformed Search and Breadth-First Search (slides A3) (slides A4) (slides A5)

Prior to lecture, please read: AIMA 3.3 (intro), 3.3.1-3.3.2, 3.4.1

Feb 10: Uniform-Cost Search and Depth-First Search (slides A6) (slides A7) (slides A8)

Prior to lecture, please read: AIMA 3.3.3, 3.4.2, 3.4.3

Feb 13: Analysis of Search (slides A9) (slides A10)

Prior to lecture, please read: AIMA 3.3.4, 3.4.4, 3.4.6

Feb 15: Iterative Deepening (slides A11) (slides A12)

No additional reading.

Feb 17: Winter Carnival (no lecture)

Feb 20: Multiplayer Games and Minimax (slides A13) (slides A14) (slides A15)

Suggested reading prior to lecture: AIMA 5.1, 5.2, 5.3

Feb 22: Alpha-Beta Pruning (slides A16)

No additional reading should be necessary. We will be unpacking AIMA 5.2.3, 5.3.1, and 5.3.2.

Feb 24: Evaluation Functions and Expectimax (slides A17) (slides A18)

Suggested reading prior to lecture: AIMA 5.5.

Feb 27: Heuristic Search (slides A19) (slides A20)

Suggested reading prior to lecture: AIMA 3.5.1, 3.5.2.

Mar 1: Admissible Heuristics (slides A21)

Suggested reading prior to lecture: AIMA 3.6

Mar 3: Probability and Conditional Independence (slides B1) (slides B2)

Suggested reading prior to lecture: AIMA 12.1-12.5

Mar 6: Bayesian Networks (slides B3) (slides B4)

Suggested reading prior to lecture: AIMA 13.1, 13.2.1, 13.2.2, 13.2.4

Mar 8: Introduction to Inference (slides B5)

Suggested reading prior to lecture: AIMA 13.3.1, 13.3.2

Mar 10: Variable Elimination (slides B6) (slides B7)

Suggested reading prior to lecture: AIMA 13.3.3

Mar 13: Treewidth (practice 5) (practice 6)

No additional reading.

Mar 15: The Junction Tree Algorithm (slides B8) (slides B9)

Suggested reading prior to lecture: AIMA 13.3.4

Apr 3: Probability of Continuous Variables (slides B10)

Suggested reading prior to lecture: AIMA 13.2.3, Appendix A.3

Apr 5: Kalman Filters (slides B11)

Optional reading: AIMA 14.1, 14.2, 14.4

Apr 7: Markov Decision Processes (slides B12)

Suggested reading: AIMA 17.1 (intro), 17.1.1

Apr 10: Policies (slides B13)

No additional reading necessary.

Apr 12: Value Iteration (slides B14)