New Course – Spring 2011

cs6501: Imperfect Information Games
(a.k.a. Principles Of Knowledge Engineering & Reconstruction)

Overview. Imperfect information games are games where players do not know the entire state of the game. Unlike perfect information games (e.g., chess) where fairly simple search strategies can outplay nearly all humans, imperfect information games (e.g., poker) are much more challenging for computers to play well. Such games are also a better model for most real world adversarial situations including political and commercial strategy. In this course, we will study computer science issues related to imperfect games. The main topics include game theory, machine learning, probability, and high-performance computing.

Meetings. Tuesdays and Thursdays, 11:00AM – 12:15PM in MEC 215.

Course Leader. David Evans

Expected Background. Students are expected to have background comparable to one course in theory of computation (e.g, cs3102 or cs6160), be competent in software development, and be comfortable with basic probability and statistics. It is not expected to have previous background in artificial intelligence or game theory. Experience with poker is helpful, but not necessary or expected.

Course Website. http://www.cs.virginia.edu/evans/poker/. See the course site for a reading list, relevant links, and detailed topics and schedule information.

Course Format. Course meetings will be a mix of discussions of foundational ideas and recent research papers. Students will be expected to lead presentations of topics and papers.

Project. In addition to reading and presenting course material, there will be a series of projects culminating in the construction of a poker bot suitable for competition at the Sixth Annual Computer Poker Competition (to be held in conjunction with the Twenty-Fifth Conference on Artificial Intelligence, AAAI-11). Students will work in groups of 3-4 on preliminary projects and sub-projects, and we will aim to combine the best ideas from several projects into the competition bot.

Evaluation. Students will be evaluated based on their overall contribution to the course including leading topic and paper presentations (30%), preliminary projects (30%), and the final project (40%).