Time: TR 14:00 - 15:20
Place: CSC B41
Professor: Jonathan Schaeffer
Office Hour: send email to make an appointment
Search is at the heart of artificial intelligence (AI) research.
Among a myriad of application-dependent possibilities -- whether
they be states, plans or theorems -- an AI application must 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 recent 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).
The course will cover artificial intelligence search algorithms,
with an emphasis on single agent (one player) search (A*),
two-player search (alpha-beta),
imperfect information search (simulations), and
search in stochastic domains (expectimax).
Algorithms will be evaluated in terms of their algorithmic
complexity, implementation considerations, utility, interaction with
application-dependent knowledge, etc.
There will be four assignments in the course.
Two are designed to be fun and competetive:
Writing a two-player game program.
Programs will be evaluated (in part) by competing in a round-robin tournament,
allowing each student's program to test its ability against all the
other students in the class.
This will be the fourth CMPUT 657 Game Programming Championship.
Writing a single-agent search program to solve a puzzle.
Students will be evaluated (in part) based on the efficiency of the search.
Assignment 1 (programming - two-player search)
Assignment 2 (programming - single-agent search)
Assignment 3 (presentation of a recent research paper)
Assignment 4 (project)
10% Participation (based on class participation and/or an oral exam)
Final grades for the course will be determined by a distribution.
3. Alpha-beta algorithm
4. Trees and DAGs
5. Iterative deepening and move ordering
6. Evaluation functions
7. Search windows
8. Search depth
9. Odds and ends
10. Single-agent Search
Case Study (Sokoban)
12. Pattern DataBases (Rob Holte)
Plagiarism and Cheating
Make sure you have read and are familiar with the Code of Student
Behaviour in the University of Alberta Calendar specified here.
Plagiarism and other forms of cheating are considered to be serious