| [home] - [up] |
Abstract: Game trees formalize in a natural way the tree-like structure which arises when we start thinking about actions that we can take in a certain situation, which responses we might get from our environment, which actions we might take thereafter etc. etc. After some basics about game trees, I am going to present two applications: The success story of and internals about the top level chess program Hydra, and the Repair Game which is intended to manage disruptions e.g. in airline fleet assignments.
Computer Chess: Since the spectacular success of the chess program Deep Blue against G. Kasparov in a 6-game match in 1997, chess programs have increased their playing strength by a further margin. In June 2005, the chess program Hydra could defeat one of the top-10 human chess players, Grandmaster Adams, with 5.5 to 0.5. Computer chess is an example where game tree search and the speed with that we can generate game tree nodes play a key role. In order to speed up the search process as much as possible, and thus in order to increase the playing strength as much as possible, we make intensive use of parallelism utilizing FPGA-technology and compute clusters.
Disruption Management: The world around us seems to become more and more dynamic, and past data often loose their predictive power for future planning tasks. Therfore, we are interested in optimization problems with uncertainty, uncertainty modeled with the help of random distributions. The task of the Repair Game is to generate robust plans and to perform perturbation management for large planning tasks with the help of game tree search, in settings where the deterministic optimization problem is already NP-complete and cannot be approximated. We built a test bed for the example of "stochastic fleet assignment".
Colloquium - 16:00
Abstract: Let S{m,n} be the graph on the vertex set Zm × Zn with an edge between (a,b) and (c,d) if and only if either (a,b) = (c,d ± 1) or (a,b) = (c ± 1,d) modulo (m,n). We consider the simplicial complex Σ{m,n} of independent sets in S{m,n} and present a formula for the Euler characteristic of Σ{m,n}. In particular, we show that the unreduced Euler characteristic of Σ{m,n} vanishes whenever m and n are relatively prime, thereby settling a conjecture due to Fendley, Schoutens and van Eerten. For general m and n, we relate the Euler characteristic of Σ{m,n} to certain periodic rhombus tilings of the plane. Using this correspondence, we settle another conjecture due to Fendley et al. about a certain "transfer matrix" associated to {Σ{m,n} : n ≥ 1}. Finally, we demonstrate how to construct nonvanishing homology cycles from the rhombus tilings, thereby deriving some partial information about the homology of Σ{m,n}.