General Game Playing

In General Game Playing (GGP) the aim is to create intelligent programs that can automatically learn how to play many different abstract games at an expert level without any human intervention. This poses many research challenges in several areas of Artificial Intelligence, such as knowledge acquisition, heuristic search, and machine learning. A recent development in GGP is the successful application of simulation-based search methods such as Monte-Carlo Tree Search and Nested Monte-Carlo Search. These search methods overcome to some extent the knowledge-acquisition bottleneck. Still, all relevant search-control knowledge required for expert-level play must be discovered using machine-learning techniques during online play. This is a challenging task, for which more effective methods are required than currently exist. Therefore, this proposal aims to develop new and more effective methods for online learning of search control, which will lead to improved search algorithms. These methods, although developed within GGP, will have a much wider applicability because search is such a fundamental problem-solving paradigm.

The game studied are one-, two- and multi-player games, simultaneous and turn-taking games, constant-sum games and general-sum games. Examples are Sudoku, Frogs and Toads, Zhadu, GridGame, 3DTicTacToe, Five-in-a-Row, Checkers, Breakthrough, Knightthrough, Othello, Skirmish, Merrills, Quad, Sheep and Wolf, Farmers, Chinese Checkers, Battle, Runners, and Pawn Whopping.

Key Publications: