COMP30260 AI for Games and Puzzles

Academic Year 2018/2019

Competitive mind games, in particular Chess and Go, have long been recognised as proving grounds for Artificial Intelligence techniques, partly because they provide environments in which simple and thus easily formalised rules can lead to extremely complex skilled behaviours which are most challenging to simulate automatically. Even though the target of world-champion strength Chess programs has long been surpassed, parity with Go champions has only recently been achieved using techniques very different to those which succeeded with Chess. Some puzzles are so complex that algorithmic solution is not practical, and heuristic means of solving them is necessary. Some games with an element of chance, such as Poker and BackGammon, cannot be solved algorithmically either. Such games and puzzles require novel techniques, including learning from experience and (in games) modelling the reasoning of opponents, that bear more closely upon practical real-world problems than the idealisation of Chess does. The module covers elementary game theory, and presents a variety of heuristic game-tree search techniques. It proceeds to treat issues of pattern matching, reasoning using chunking, and machine learning, all in the realm of game playing and puzzle solving.