Intelligent Search & Games

Volledige vakbeschrijving

Intelligent Search & Games introduces the student to advanced techniques in the framework of game-playing programs. The course will start of 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, analyze and apply advanced search techniques autonomously to a wide variety of problems.