Jonathan Schaeffer


Heuristic Search

September, 2004

Time: TR 14:00 - 15:20
Place: CSC B41
Professor: Jonathan Schaeffer
Office Hour: send email to make an appointment

Course Description

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.


    25% Assignment 1 (programming - two-player search)
    20% Assignment 2 (programming - single-agent search)
    15% Assignment 3 (presentation of a recent research paper)
    30% 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.

    Course Notes

    1. Introduction
    2. Games
    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
    11. Evaluations
    Case Study (Sokoban)
    12. Pattern DataBases (Rob Holte)
    13. *-Minimax
    14. Sampling
    15. Conclusions

    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 academic offences.

    [University of Alberta] 
    University of Alberta 
    [Department of Computing Science] 
    Computing Science