eClass (submit coursework here)
Course material (assignments, lecture
notes) (id/passwd required, listed on eClass)
Week of M M(+0) T(+1) W(+2) R(+3) F(+4) Topics
1. Jan 11 L1/A1r L2 L3 Intro, Game AI Successes, MiniMax Search
2. Jan 18 L4 L5 L6 [R1] AlphaBeta Search, Transposition Tables, Move Sorting
3. Jan 25 L7 L8 L9 Playing with Search Windows and Search Depth
4. Feb 01 L10 L11 L12 Evaluation Functions, Parameter Optimization, DNNs
5. Feb 08 L13 A1d/A2r L14 L15 [R2] Single-Agent Search, A*, IDA*, Pattern Databases
6. Feb 15 ------------ READING WEEK -------------
7. Feb 22 L16 L17 L18 Hierarchical/Triangulation/Multi-Agent Pathfinding
8. Mar 01 L19 L20 L21 Chance and Sampling, Monte Carlo Tree Search, UCT, AlphaGo
9. Mar 08 L22 A2d L23 CPA L24 Imperfect Information Games, Card Game AI, RTS Game AI
10. Mar 15 CPR - -
11. Mar 22 - - PAP/PAS
12. Mar 29 PRO - -
13. Apr 05 - - -
14. Apr 12 - - PRP/PRR
Legend: Ajr / Ajd : assignment j released / due (end of day)
Li : lecture i
Ri : reading assignments
CPA : choose recent research paper (Mar-11)
CPR : choose project topic (Mar-15)
PAP : paper presentations (~15 minutes each)
PAS : paper summary + presentation slides (Mar-26)
PRO : project progress report (Mar-29)
PRP : project presentation (~15 minutes each)
PRR : project report due (Apr-16)
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 searching ~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 Tree Search (MCTS). 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 game, card game, and video game AI systems work, and what current research challenges in this AI area are. Course projects can become seeds for theses!
There will be 4 assignments and a project in the course. Two assignments are designed to be fun and competetive: 1) Writing a program that plays a two-player perfect information game and 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 3) summarize a recent research paper of their choice and 4) choose a project to work on. Project presentations will finish the course. There is no final exam
In this course grades will not be curved, they are absolute - following these cut points:
>= 90% A+ >= 85% A >= 80% A- >= 75% B+ >= 70% B >= 65% B- >= 62% C+ >= 59% C >= 56% C- >= 53% D+ >= 50% D < 50% FThe minimum passing grade is C+
Please visit this page to learn about our interpretation of letter grades. 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 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 assignments in groups to speed
up learning and stimulate idea exchange. However, students must write
down their own solutions/code, and are not supposed to share them. You
must give credit to any source that substantially assisted you in
completing the assignment. A source includes fellow students, books,
papers, and me. Failure to give proper credit is considered plagiarism