Bachelor's theses

A General Game Playing System is one that can accept a formal definition of a game and play the game effectively without human intervention. Unlike specialized game players, general game players do not rely on algorithms designed in advance for specific games, and they are able to play different kinds of games.

Besides two-player and multi-player games, the games that have to played successfully at the AAAI General Game Playing Competition also include single-player games. Due to algorithmic reasons, it is preferable to develop different modules handling the different kinds of games. Since single-player games described in the Game Description Language (GDL), in which the competition games are encoded, are essentially classical planning problems, it is possible to solve them using according algorithms.

The goal of this thesis was to integrate state-of-the-art algorithms and heuristics used in classical planning into a General Game Playing system currently under development. The resulting system should be evaluated using some of the benchmark games available online.

The purpose of this work is to give a detailed analysis of SGPlan. SGPlan achieved good results in the last international planning competitions (in particular at the 4th and 5th IPC). The source code of the planner wasn't accessible until now, but was made available for free use within the 6th IPC. Using this code, the achievement of the results and the algorithmic background of SGPlan shall be examined, because up until now the code was not sufficiently explained through the publicly available descriptions.

Fluent merging is a reformulation technique for classical planning problems that can be applied automatically or semi-automatically. The reformulation strives to transform a planning task into a representation that allows a planning algorithm to find solutions more efficiently or to find solutions of better quality. This work introduces different approaches for fluent merging and evaluates them within state-of-the-art planning systems.

In contrast to the common propositional representation of planning tasks, where each state variable can only take the values true and false, the Finite Domain Representation allows arbitrary finite domains. This permits a much more natural formalization of the planning tasks. In addition, it explicitly states certain mutexes, which can be exploited by planning systems to solve the task more efficiently. The objective of this thesis is to examine the influence of the representation on the performance of several planning systems empirically.

This work is concerned with a subproblem of the problem of finding strong plans for non-deterministic planning problems via the approach of planning as heuristic search, more precisely, AO* search guided by domain-independent pattern database (PDB) heuristics. Strong plans guarantee that a goal state is reached in a finite number of steps independently of the non-deterministic outcomes. The focus of this work is on the automatic selection of approproate patterns through heuristic search in the space of pattern collections, alalogous to the work by Haslum et al. in the context of deterministic planning. The aim of this work is the implementation and evaluation of a pattern selection algorithm.

A General Game Playing System is a system that can accept a formal definition of a game and play the game effectively without human intervention. Unlike specialized game players, general game players do not rely on algorithms designed in advance for specific games, and they are able to play different kinds of games.

In this work, a player based on the General Game Playing System Jocular was developed that uses an automatically generated evaluation function derived from the FF heuristic known from research in action planning. The evaluation function generalizes the FF heuristic in that it is designed for two-player games with numeric preferences over terminal states.

A Boolean function is monotonic if it can be represented by a combinatorial circuit of AND- and OR-gates. Monotonic Boolean functions play an important role in complexity theory and naturally occur in a number of applications.

The goal of this project is to compute a compact representation for monotonic Boolean functions given as circuits or propositional logic programs, i.e., to find a circuit with a small number of gates which computes the given function. The resulting algorithm shall then be applied to the problem of computing relaxation heuristics for AI planning tasks, and to the problem of line of sight computation in discrete 2D worlds.