CMPUT 657

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.

Grading

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

Computing Science

---