Intelligent Search & Games
Full course description
In this course, the students learn how to apply advanced techniques in the framework of game-playing programs. Depending on the nature of the game, these techniques can be of a more or less algorithmic nature. The following subjects will be discussed:
(1) Basic search techniques. Alpha-beta; A*.
(2) Advanced search techniques. IDA*; B*, transposition tables; retrograde analysis and endgame databases; proof-number search and variants; multi-player search methods; Expectimax and *-minimax variants.
(3) Heuristics. World representations; killer moves; history heuristic, PVS; windowing techniques; null-moves; forward-pruning techniques; selective search, GOAP.
(4) Monte Carlo methods. Monte Carlo tree search (MCTS) techniques, enhancements and applications; AlphaGo and AlphaZero approaches.
(5) (5) Game design. Evolutionary game design; game quality metrics; self-play evaluation; procedural content generation (PCG); puzzle design.
Prerequisites
None.
Desired Prior Knowledge: Data Structures & Algorithms.
Recommended reading
- Millington, I. and Funge, J. (2009). Artificial Intelligence for Games, 2nd Edition Morgan Kaufmann Publishers, ISBN: 978-0123747310
- Russell, S.J. and Norvig, P. (2010). Artificial Intelligence: A Modern Approach, 3rd edition. Pearson Education, New Jersey. ISBN 0-13-207148-7.
- Yannakakis, G.N. and Togelius, J. (2018) Artificial Intelligence and Games, Springer, Berlin. ISBN 978-3-319-63519-4 (eBook) 978-3-319-63518-7 (hardcover)