MSV Incognito Knowledge Base

Intelligent Search & Games introduces the student to advanced techniques in the framework of game-playing programs. The course will start off with a brief discussion of basic search techniques such as Alpha-beta and A*. This is followed by more advanced search techniques such as IDA*, B*, transposition tables, retrograde analysis and endgame databases, proof number search, expectimax, and Monte-Carlo Search techniques. After this several heuristics will be discussed to gain additional performance such as killer moves, history heuristic, PVS, windowing techniques, null-moves, forward pruning, and selective search. The course is concluded by a discussion of combinatorial game theory applied to combinatorial games. Here the focus will be on combinatorial games, P and N positions, NIM, graph games, the Sprague-Grundy functions, sums of games, the Sprague-Gruny theorem, and Green-Hackenbush. The course is accompanied by a large practical part in which students implement their own search techniques to a specific game. After completing this course the student will be able to use specialized techniques for finding appropriate solutions to complex problems. The student will be able to develop, program, analyse and apply advanced search techniques autonomously to a wide variety of problems.

Good programming skills are required.

• Berlekamp, E.R., Conway, J.H., and Guy, R.K. (2001-2004). Winning Ways for your Mathematical Plays, 2nd edition. A.K. Peters, Ltd., 4 volumes. Vol. 1: ISBN 1-56881-130-6; vol. 2: ISBN 1-56881-142-X; vol. 3: ISBN 1-56881-143-8; vol. 4: ISBN 1-56881-144-6.
• Bolc, L. and Cytowski, J. (1992). Search Methods for Artificial Intelligence. Academic Press, London. ISBN 0-12-111240-3.
• Millington, I. and Funge, J. (2009), Artificial Intelligence for Games, 2nd Edition, Morgan Kaufmann Publishers, ISBN: 978-0123747310.
• Pearl, J. (1984). Heuristics: intelligent search strategies for computer problem solving. Addison-Wesley, Reading, Massachusetts.
• Russell, S.J. and Norvig, P., Artificial Intelligence: A Modern Approach, 3rd edition. Pearson Education, New Jersey, 2010. (Chapters 3- 17). ISBN 0-13-207148-7.