Instructor: James R. Glenn, Ph.D.
Office: AKW 013
Office Phone: TBD
Office Hours: Tue 4-6pm and Thu noon-2pm, or by appointment, or drop by and see if I'm in
e-mail: [first name][dot][last name]@yale.edu

Course Home Page:
Piazza Page: https://piazza.com/yale/spring2018/cpsc474/home

Class Meeting: Lecture Tue, Thu 9:00am – 10:15am in DL 220

Prerequisites: CPSC 202 and CPSC 223 or equivalent

Recommended Readings:

• On Numbers and Games by John H. Conway ISBN 978-1568811277 (retail price $67.95)
• Game Theory through Examples by Erich Prisner ISBN 978-1614441151 (available online through the Yale Library)
• Artificial Intelligence for Games (2nd edition) by Millington and Funge ISBN 978-0-12-374731-0 (retail price $93.95; available online through the Yale Library as part of Safari Books Online)
• Artificial Intelligence and Games by Yannakakis and Togelius ISBN 978-3319635187 (avaliable through the Yale Library's subscription to SpringerLink; more information at the book website)
• Procedural Content Generation in Games: A Textbook and Overview of Current Research by Shaker, Togelius, and Nelson ISBN 978-3319427140 (retail price $49.99; available online from the authors)
• A survey of Monte Carlo Tree Search methods, C.B. Brown et al. IEEE Transactions on Computational Intelligence and AI in Games 4:1, Mar 2012, 1-43.
• Finite-time analysis of the multiarmed bandit problem, Auer, Cesa-Bianchi, Fischer. Machine Learning Journal, 47(2-3):235-256, 2002. IEEE Transactions on Computational
• Genetic Algorithms for Evolving Computer Chess Programs, David et al. IEEE Trans. on Evolutionary Computation, 18(5):778-789, 2014.
• Mastering the game of Go with deep neural networks and tree search, Silver et al. Nature 529(7587):484-489, 2016.
• Mastering the game of Go without human knowledge, Silver et al. Nature 550(7676):354-359, 2017.
• A panorama of artificial and computational intelligence in games, Yannakakis and Togeliuis. IEEE Transactions on Computational Intelligence and AI in Games 7:4, Dec 2015, 317-335.

Other Resources:

• Combinatorial Game Theory
  • Notes from Alan Chang, Univ. of Chicago
  • Introduction to Combinatorial Game Theory from GeeksforGeeks
  • Sprague-Grundy theorem from Wikipedia (reviewed Jan 15, 2018)
  • Minimax in combinatorial game theory from Wikipedia (reviewed Jan 18, 2018)
• Backward Induction (Dynamic Programming) and Value Iteration
  • Pig Resources from Todd Neller and Cliff Presser at Gettysburg College, including
    • Todd W. Neller and Clifton G.M. Presser, Optimal Play of the Dice Game Pig, The UMAP Journal 25(1) (2004), pp. 25-47
• • Game Theory: An Introduction by E. N. Barron ISBN 978-1118533895 (available online through Safari via the Yale library)
• Game Rules
  • Yahtzee
  • Can't Stop
  • North American gridiron football
  • NFL Strategy
• Neural Networks
  • Neural Networks and Deep Learning by Michael Nielsen (free online book)

Catalog Description:
The recent success of Google’s AlphaGo represents a milestone in computational intelligence. This course introduces the problems encountered and techniques used to overcome them, starting with techniques from combinatorial and classical game theory that can be used to create perfect computer players for simple games, followed by the computational intelligence concepts used in AlphaGo and other successful systems, including stochastic search (Monte Carlo Tree Search and evolutionary computation) and neural networks. AlphaGo was designed specifically to play Go; this course also introduces general game playing, which attempts to making the leap to systems that can play many games well. The use of computational intelligence techniques in procedural content generation for games is also included.

Course Outcomes:
Students will be able to

• apply combinatorial game theory, classical game theory, and computational intelligence to design agents that play board games.

Academic Dishonesty:
Please see Yale College's Undergraduate Regulations and Definitions of Plagiarism, Cheating, and Documentation of Sources.

The implications for this course:

• Programming Assignments: The code you submit must be the result of your understanding of the problem. You may discuss concepts and approaches with other students, but you may not take any written or electronic records from such discussions (this includes discussions on Piazza; such discussions are electronic records so you may not post code there). Furthermore, you must engage in a full hour of mind-numbing activity (such as watching back-to-back episodes of Gilligan's Island) before resuming work. This no-record/"Gilligan's Island" rule applies to code found in online or other published sources as well (aside the class notes, which can be used without attribution and without triggering the "Gilligan's Island" rule). Under no circumstances may you examine a copy of another student's code nor may you provide a copy of your code to another student. You may consult course staff for help writing and debugging without attribution and doing so does not trigger the Gilligan's Island rule. (The Gilligan's Island rule originated with Stanley Eisenstat and I obtained it through Stephen Slade.)
• Exams: each student must work individually.

Grading:

• Programming Assignments: 75%
• In-Class Exams: 25% (Tue Mar 6 in Loria 250 and Thu Apr 26 in DL220 during regular class period)

Schedule (approximate and subject to change):

---