15-780, Spring 2016

Graduate Artificial Intelligence


Key Information

Mondays + Wednesdays, 10:30am - 11:50am, Baker Hall A51

Guillermo Cidre, Zhaohan (Daniel) Guo, Christian Kroer, Wennie Tabib

Class Participation (5%), Homeworks (50%), Final Project (25%) and the Midterm (20%)

Artificial Intelligence: A Modern Approach (3rd Edition), Chapters 1-4, and 6

We will use Piazza for questions, so please try to post your questions there. The site can be found here

This course is targeted at graduate students who are interested in learning about artificial intelligence. The focus is on modern AI techniques. The course also covers techniques from the intersection of AI and other disciplines such as integer programming, continuous optimization, and game theory. The course content is profiled so as to not have too much overlap with narrower specialized AI courses offered at CMU.


No formal pre-requisites. But, substantial programming background is required (assignments will be in Python). Additional background in data structures and algorithms, linear algebra, and probability will all be helpful, but not required.

Office Hours

Name Email Hours Location
Tuomas Sandholm sandholm@cs Mon. 12-1pm. Exception: none on 2/15. GHC 9205
Zhaohan (Daniel) Guo zguo@cs Mon. 3-4pm. Exception: 5-6pm on 3/14; 2-3pm on 4/18 GHC 8127
Christian Kroer ckroer@cs Tue. 2-3pm. GHC 9221
J. Zico Kolter zkolter@cs Wed. 12-1pm. Exception: none on 2/17. GHC 7115
Guillermo Cidre gcidre@andrew Thurs. 7-8pm. GHC 4th green sofas near Rashid
Wennie Tabib wtabib@andrew Fri. 10-11am NSH 1113


Date Topic Readings Due Dates
1/11 Introduction slides RN Chapers 1 & 2
1/13 Uninformed Search slides, Constraint Satisfaction slides RN Chapters 3.1-3.4, begin reading Chapter 6
1/18 MLK Day
1/20 Constraint Satisfaction, SAT RN Chapter 6
1/25 Constraint Satisfaction, SAT
1/27 Informed Search slides RN Chapters 3.5-3.7
2/1 Linear Programming slides
2/3 Linear Programming slides
2/8 Advanced Informed Search, Integer Programming slides Sandholm, T. 2006. Optimal Winner Determination Algorithms. Chapter 14 of the book Combinatorial Auctions, Cramton, Shoham, and Steinberg, eds., MIT Press.
2/10 Advanced Informed Search, Integer Programming
2/15 (Guest lecture) Willem-Jan van Hoeve: Binary Decision Diagrams (BDDs) in Search/MIP Optional reading, which will be the topic of this lecture: David Bergman, Andre A. Cire, Willem-Jan van Hoeve, J. N. Hooker. 2016. Discrete Optimization with Decision Diagrams. INFORMS Journal on Computing 28(1):47-66.
2/17 (Guest lecture) Michael Trick: Benders' Decomposition in Search/MIP, sports scheduling Optional reading, which will be the topic of this lecture: Rasmus Rasmussen and Michael A. Trick. 2007. A Benders approach for the constrained minimum break problem. European Journal of Operational Research 177: 198–213.
2/22 Probabilistic Graph Models slides
2/24 Probabilistic Inference slides
2/29 Markov Decision Processes slides
3/2 Reinforcement Learning slides
3/7 Spring break
3/9 Spring break
3/14 Continuous Optimization slides
3/16 Continuous Optimization slides
3/21 Machine Learning slides Project Proposal Due
3/23 Machine Learning slides
3/28 Midterm
3/30 Deep Learning slides
4/4 Deep Learning Applications - Deep Reinforcement Learning slides
4/6 Game Representations, Solution Concepts, and Complexity slides
4/11 Algorithms for Sequential Complete-Information Games slides The Nature paper on AlphaGo.
4/13 Rest of AlphaGo. THEN: Algorithms for (Tree) Games of Incomplete Information slides Sandholm, T. 2010. The State of Solving Large Incomplete-Information Games, and Application to Poker. AI Magazine, special issue on Algorithmic Game Theory, Winter, 13-32.
4/18 Rest of Algorithms for (Tree) Games of Incomplete Information. THEN: Opponent Modeling & Exploitation slides Ganzfried, S. and Sandholm, T. 2015. Safe Opponent Exploitation. In the Best of EC-12 special issue of ACM Transactions of Economics and Computation (TEAC), 3(2), Article 8, 1-28.
4/20 Algorithms for (Tree) Games of Incomplete Information: Recent Advances in and around the CFR Family slides Noam Brown and Tuomas Sandholm. 2015. Regret-Based Pruning in Extensive-Form Games. In Proceedings of the Neural Information Processing Systems: Natural and Synthetic (NIPS) conference. Extended version.
4/25 Gradient-Based Algorithms for (Tree) Games of Incomplete Information, and Lossy Game Abstraction with Bounds slides1, slides2 Kroer, C. and Sandholm, T. 2014. Extensive-Form Game Abstraction With Bounds. In Proceedings of the ACM Conference on Economics and Computation (EC). Extended version that includes the appendices.
4/27 Future Directions of AI and Q&A slides1 slides2
5/2 Project Presentations Project Writeups Due 5/4


There will be seven sets of assignments for the course: homeworks will involve both written answers and programming assignments. Written questions will involve working through algorithms presented in the class, deriving and proving mathematical results, and critically analyzing the material presented in class. Programming assignments will involve writing code in Python to implement various algorithms presented in class.

Homework due dates

Topic Files Due Dates
Homework 1 hw1.pdf (files: problems.py, sample.py) 2/4
Homework 2 hw2.pdf (files: hw2_handout.tar) 2/16
Homework 3 hw3.pdf (files: hw3_handout.tar) 2/28
Homework 4 hw4.pdf (files: hw4_handout.tar) 3/4
Homework 5 hw5.pdf (files: hw5_handout.tar) 3/23
Homework 6 hw6.pdf (files: hw6_handout.tar) 4/19
Homework 7 hw7.pdf (files: hw7_handout.tar) 4/28

Homework Policies

Strict honor code with severe punishment for violators. CMU’s academic integrity policy can be found here. You may discuss assignments with other students as you work through them, but writeups must be done alone. No downloading / copying of code or other answers is allowed. If you use a string of at least 5 words from some source, you must cite the source


In lieu of a final exam, students will complete a course project. The project can be theoretical, experiment, or both. We encourage creativity in both the project topic choice and execution. One possible type of project is to combine techniques from AI with your own research. Projects will be accompanied by a paper due at the end of the semester and a public poster presentation session.


Project proposals should consist of a short (2–3 pages) but well-researched summary of your project idea accompanied by a plan of execution. Students are allowed (and encouraged) to work in groups; however, the expectations we will have for your project rise proportional to the group size. As an example of a reasonable project proposal, please take a look at the following example from a previous Graduate AI (pdf). The proposal begins with motivation and a brief explanation of the problem, and then sets a series of goals. If the project is harder than expected, only the "75%" goals will be completed; if it's difficult level is as expected, the "100%" goals will be completed; finally, if it's easier than expected, the student plans to complete the ambitious "125%" goals as well. The more you plan now, the easier it will be to complete your project well and on time!


The class has a midterm but no final exam. The midterm will take place during the regular class time on 3/28. A list of the material to be covered during the midterm will be posted here prior to the exam.