Lectures
Week of M T R F Topics
1. Jan 10 L1 L2 L3 Intro, Game AI Successes
2. Jan 17 L4 L5 L6/A1r MiniMax, AlphaBeta Search
3. Jan 24 L7 L8 L9 Transposition Tables, Selective Search
4. Jan 31 L10 L11 L12 Eval. Function Constr., Odds and ends
5. Feb 7 L13 L14 L15 Single-Agent Search, Pattern Databases
6. Feb 14 L16 L17 L18/A2r/A1d Hierarchical Pathfinding, *-Minimax
7. Feb 21 ------- READING WEEK ---------
8. Feb 28 - L19 L20 Sampling based methods, UCT
9. Mar 7 L21 L22 -A2d/CPA Imperfect Information Games
10. Mar 14 L23 - -
11. Mar 21 - - PA(9:45am-12:00pm)/CPR
12. Mar 28 - - -
13. Apr 4 - - -
14. Apr 11 PR (10:00am-12:15pm, ATH-332)
Legend: Ajr / Ajd : assignment j released / due (before lecture)
Li : lecture i
- : no lecture
CPA/CPR : choose paper / project topic
PA : paper presentations
PR : project presentations
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 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 current research challenges in this area of artificial intelligence are. Course projects can become seeds for theses!
There will be 3 assignments and a project in the course. Two assignments are designed to be fun and competetive: 1) Writing a two-player game program. 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 choose a project to work on. Project presentations will finish the course. There is no final exam.
Final grades will be based on the 4-point grading system and assigned in accordance with the University of Alberta grade distribution guidelines for undergraduate courses as specified in the University of Alberta Marking and Grading Guidelines. 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.
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 (online at www.ualberta.ca/secretariat/appeals.htm) 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.
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.