CMPUT 657 - Heuristic Search
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 search like A*, over two-player search (alpha-beta), to Monte-Carlo simulations. 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 and card-playing programs work, and what the current research challenges in this area of artificial intelligence are. Course projects can become seeds for theses!
Objectives
- Become familiar with basic game theoretic concepts and the knowledge vs. search tradeoff in heuristic search
- Learn how to construct high-quality search heuristics and how to apply various search enhancements in the context of single-agent and two-player settings
Course Work
- Assignments
- Project
- Presentations