MM 812: Game Programming and AI

Fall 2016, Instructor: Michael Buro
Lectures: M 11:00-12:50, R 14:30-15:50 (C W4-44 Chemistry 4th Floor West), F 14:00-14:50 (CAB 369)
Office hours: M 13:00-13:30, T 12:30-13:00 (Ath 337) or by appointment

eClass Forum Post general course related questions there.
Course material (assignments, lecture notes) (id/passwd required, will be announced in the first lecture)
C++ Introduction

News

Tentative Schedule

  Week of   
  (Monday)  M (+0)      R (+3)       F (+4)    Topics
 1. Aug.29  -           L1           L2        Intro, Game AI Successes,
 2. Sep.05  %(Lab.Day)  L3           L4/A1r    Game Theory Primer, Minimax, AlphaBeta Search
 3. Sep.12  L5          L6           L7        Transposition Tables, Move Sorting, 
 4. Sep.19  L8          L9           L10       Null-Window Search, Selective Search, Evaluation 
 5. Sep.26  L11         L12          L13       Function Construction, Parameter Learning
 6. Oct.03  L14         L15       L16/A2r/A1d  Single-Agent Search, A*, IDA*
 7. Oct.10  %(Thanksg.) L17          L18       Creating Heuristics, Pattern Databases, Hierarchical A*
 8. Oct.17  L19         L20          L21       Hierarchical/Triangulation Pathfinding, Chance Events
 9. Oct.24  L22/CPA     L23          L24       MCTS, UCT, Imperfect Information Games
10. Oct.31  L25          -           -/A2d     AI for RTS Games
11. Nov.07  ------- READING WEEK ----------  
12. Nov.14 PPA/CPR       -            -         
13. Nov.21   -           -            -    
14. Nov.28  PSS          -            -    
15. Dec.05  PPR      Dec.07: PFD

Legend:  Ajr / Ajd : assignment j released / due (before lecture)
         Li        : lecture i
         CPA       : choose paper (Oct. 24) (1-page pdf, email)
         CPR       : choose project topic (Nov. 14) (1-page pdf, email)
         PPA       : paper presentations  (Nov. 14, CSC 333, 11:00-13:30)
                     paper summary due (astep ... paper.tar)
         PSS       : project snapshot (astep ... snapshot.tar) if you need advice for staying/dropping
         PPR       : project presentations (Dec. 5, CSC 333, 11:00-13:30)
         PFD       : project files due Dec. 7 (astep -c c812 -p proj project.tar)

Course Overview

Search is at the heart of artificial intelligence (AI) research. AI applications often have to search among the alternatives for either the optimal answer (optimizing) or the best result given limited resource constraints (satisficing). This was best epitomized by the chess match between Deep Blue and Garry Kasparov. The computer, searching 200 million chess positions per second, narrowly edged the human world champion (2 chess positions per second).

This course will cover many important search algorithms used in AI ranging from single-agent A* search, over two-player search (alpha-beta), to Monte-Carlo Tree Search (MCTS). Algorithms will be evaluated in terms of their algorithmic complexity, implementation considerations, utility, interaction with application-dependent knowledge, etc.

In addition to abstract games, the course also looks at AI topics related to video games, discussing efficient algorithms for pathfinding, collision tests, combat, and build order optimization.

At the end of the course students will know how video game engines find shortest paths quickly, how they resolve object collisions efficiently, and how abstract-game search methods can be applied to them. Moreover, students will learn how strong board and card-playing programs work, and what current research challenges in this area of artificial intelligence and game programming are. Course projects can become seeds for papers and Ph.D. theses!

There will be 3 assignments and a project in the course. Two assignments are designed to be fun and competetive: 1) Writing a program that plays a two-player perfect information game. 2) Writing a single-agent search program to solve a puzzle. Programs will be evaluated (in part) by competing in a round-robin tournament, allowing each student's program to test its ability against all other programs. In the second half of the course, students will choose a project to work on. Project presentations will finish the course. There is no final exam.

Tentative Course Syllabus

Suggested Reading

The course is mostly self-contained. Links to research papers will be provided.

Prerequisites

Familiarity with Java or C/C++ and fundamental algorithms and data structures.

Grading Scheme

In this course grades will not be curved, they are absolute - following these cut points:

>= 95% A+   >= 90% A    >= 85% A-
>= 80% B+   >= 75% B    >= 70% B-
>= 65% C+   >= 60% C    >= 55% C-
>= 50% D+   >= 45% D    <  45% F

Please visit this page to learn about our interpretation of letter grades. I have the discretion in setting the borderline between passing and failing and, in doing so, may consider a students entire performance across the term as well as their overall percentage.


Presentations in General

Project Presentations


Academic Integrity

The University of Alberta is committed to the highest standards of academic integrity and honesty. Students are expected to be familiar with these standards regarding academic honesty and to uphold the policies of the University in this respect. Students are particularly urged to familiarize themselves with the provisions of the Code of Student Behaviour. and avoid any behaviour which could potentially result in suspicions of cheating, plagiarism, misrepresentation of facts and/or participation in an offence. Academic dishonesty is a serious offence and can result in suspension or expulsion from the University. (GFC 29 SEP 2003)

Copying and cheating on assignments will be penalized with a mark of 0 (see the standard handouts for academic dishonesty and copying and cheating), and Section 30.3.2 Inappropriate Academic Behaviour.

Course Policies

Unless otherwise noted, the CS Department Policies are in effect.

Collaboration

Students are encouraged to discuss and solve problem sets in small groups to speed up learning and stimulate idea exchange. In the end, however, students must write down their own solutions and be able to solve similar problems independently. You must give credit to any source that substantially assisted you in completing the assignment. A source includes fellow students, books, papers, TAs, and me. Failure to give proper credit is considered plagiarism.


last modified on  ; you are visitor # since July/15/2016