| [home] - [up] |
Abstract: An abstract strategy game is a board game with perfect information, no chance, and (usually) two players. Most of the world's classic board games, including chess and go, fit into this category. Considering two well known games, Abalone and Pyraos, we present two different approaches to analyze a game for computer use.
1) Abalone (http://uk.abalonegames.com)
[Joint work with Tino Werner (master thesis)]
One of the 'modern classics', played with black and white marbles on a hexagonal grid. The goal is to push out six marbles of the opponent. In the talk we present some ideas which are used by the program ABAPRO. Based on the well known alpha-beta pruning for search trees we present heuristics (for example the so-called funnel-cut) which reduce the search complexity to about 1/100 of the theoretical minimal search tree. Combining this with a simple geometric evaluation function the resulting program ABAPRO is the first one to play at world-class level and won the Abalone Tournament at the 8th ICGA computer Olympiad 2003. Moreover it is still unbeaten by human players (though two human world champions already played against it).
2) Pyraos (alias Pylos) (http://www.gigamic.com/jeuxanglais/pylose.htm)
[Joint work with Joerg Weber (programming project)]
A game played with 15 light and 15 dark spheres to build a pyramid based on a 4x4 board. The player who at the end of the game owns the sphere on top of the pyramid wins. The game is especially interesting because a player may take back some of her spheres, leading to loops in the game-tree. We used Pyraos to apply a general framework for completely analyzing a game, i.e., to decide whether it is a winning position for the first or second player. This provides us with a database which allows to find a perfect move for any legal game position. The main result is that under optimal play the non-beginning player can always win Pyraos.
Colloquium - 16:00
Abstract: Given two convex polytopes A,B ⊂ R^2, one is interested in how these sets resemble each other. One good measure for this resemblance is the minimal Hausdorff-Distance under translation.
Since the known exact algorithms to calculate this distance are not very efficient, approximation algorithms based on reference points are used to get faster results. An algorithm using reference points computes the reference points and moves the polytopes so that these points coincide. One possible reference point of a convex polygon is the Steiner point which is a weighted sum of its vertices. Due to Alt, Aichholzer, and Rote it is known that the Steiner point is a reference point which induces an approximation algorithm with approximation ratio 4/π with respect to translations. Additionally, it is shown that any approximation algorithm using reference points cannot achieve a ratio better than 4/π. However, the proof of the lower bound is not constructive.
I will explain our approach of finding better lower bounds on the quality of reference point based approximation algorithms using a relaxation of the problem and linear programming. Finally, I will show the newest results and examples.