CMPUT 657 Heuristic Search with Applications to Games

Winter 2020, Instructor: Michael Buro
Lectures: MW 12:00-13:20 CSC B43, F 9:30-10:50 CSC B43 (starting Jan-6)
Office hour: M 13:30-14:00 (ATH 337)

Important: If you consider me to become your thesis supervisor, taking this course is mandatory

eClass (submit coursework here)
Course material (assignments, lecture notes) (id/passwd required, revealed in first lecture)


Tentative Schedule

(Lectures are front-loaded to give students the chance to apply all lecture materials to their projects)
Week of M   M (+0)      W (+2)       F (+4)    Topics
 1. Jan 06  L1/A1r      L2           L3        Intro, Game AI Successes, MiniMax Search
 2. Jan 13  L4          L5           L6  [R1]  AlphaBeta Search, Transposition Tables, Move Sorting
 3. Jan 20  L7          L8           L9        Playing with Search Windows and Search Depth
 4. Jan 27  L10         L11   [R2]   L12       Evaluation Functions, Parameter Optimization, DNNs
 5. Feb 03  L13/A2r     L14  T:A1d   L15       Single-Agent Search, A*, IDA*, Pattern Databases
 6. Feb 10  L16         L17          L18       Hierarchical/Triangulation/Multi-Agent Pathfinding
 7. Feb 17  ------- READING WEEK -------------
 8. Feb 24  L19         L20          L21       Chance and Sampling, Monte Carlo Tree Search, UCT, AlphaGo
 9. Mar 02 L22/A2d    L23/CPA        L24       Imperfect Information Games, Card Game AI, RTS Game AI
10. Mar 09  CPR          -            -
11. Mar 16   -           -         PAP/PAS     [(TBA+1) minutes each]
12. Mar 23  PRO          -            -
13. Mar 30   -           -            -
14. Apr 06   -        PRP/PRR         %        [(TBA+1) minutes each]

Legend:  Ajr / Ajd : assignment j released / due (end of day)
         Li        : lecture i
         Ri        : reading assignments
         CPA       : choose recent research paper (Mar. 4)
         CPR       : choose project topic (Mar. 9)
         PAP       : paper presentations (Mar. 18+20)
         PAS       : paper summary + presentation slides (Mar. 20)
         PRO       : project progress report (Mar. 23, 5% malus if not sent in time)
         PRP       : project presentation (Apr. 6/8)
         PRR       : project report due (Apr. 8)

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. At the end of the course students will know how video game engines find shortest paths quickly, how strong board game, card game, and video game AI systems work, and what current research challenges in this AI area are. Course projects can become seeds for theses!

There will be 4 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 and 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 3) summarize a recent research paper of their choice and 4) choose a project to work on (if more than 10 students take the course, projects will be done in teams of 2 if possible). 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


Familiarity with Java or C/C++ and fundamental algorithms

Grading Scheme

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

>= 90% A+   >= 85% A   >= 80% A-
>= 75% B+   >= 70% B   >= 65% B-
>= 62% C+   >= 59% C   >= 56% C-
>= 53% D+   >= 50% D   <  50% 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

Update: in the light of the global pandemic, changes were made to grading this term's course work: letter grades will be replaced by Credit/No-Credit. As for graduate courses letter grades below C+ constitutes failure, Credit will be awarded if the achieved course work percentage meets or exceeds 62%.

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


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 Aug/31/2019