options random home http://nobi.ethz.ch/ralph/ (PC Press Internet CD, 03/1996)
Back to Research Group

Ralph Gasser

Portrait 
Ralph Gasser
Institut für Theoretische Informatik
IFW E 47.1
CH-8092 Zürich

Phone: +41 1 632 73 83
E-mail: gasser@inf.ethz.ch

Research interests

Research Description

With the advent of faster machines, massive parallelism, gigabyte RAM and terabyte disk storage, the methods used to tackle large problems are changing. Many space-efficient algorithms that traded computation time for reduced memory requirements are not as important today, because memory is no longer the prime bottle-neck. Instead researchers are focusing on problem-solving approaches that were viewed as impractical only a decade ago. In my research, I examined exhaustive search algorithms. These algorithms yield optimal solutions, but typically require long run-times. Examples for this type of algorithm are branch&bound or alpha-beta. Both of these start at an initial state and work forward toward a goal state. A different approach is employed by retrograde analysis, a method popularized by Ken Thompson. This method starts at the goal states and works backward toward the initial state. Characteristic for this algorithm is its large memory requirements, because the entire state space must be stored. For my Ph.D. thesis, I developed the SearchBench, a software tool that allows the quick and reliable construction of retrograde analysis programs. The SearchBench implements the application-independent components of retrograde analysis. Particular emphasis was placed on the efficient implementation of the algorithms and a simple programmer's interface. The software engineering benefits of such a tool are two-fold; rapid prototyping is facilitated and the resulting software becomes less error-prone. Thanks to its simple interface, the SearchBench was successfully used by students as part of their course assignments. The SearchBench has also been ported to a parallel machine with no changes to the interface. This gives immediate access to parallel machines with algorithms that show good speed-ups. To demonstrate the usefulness of the SearchBench, I applied it to two problem domains. The first was the game of Nine Men's Morris. The search space of this game is roughly 10^10 positions. Unlike other games where knowledge-based methods dramatically reduce the size of the search space, the entire Nine Men's Morris state space had to be searched. Thanks to my methods, I was the first to solve this game (it is a draw). The second contribution was made to the 15-Puzzle. The 15-Puzzle has an even larger state space comprising 10^13 positions. Two questions are of interest here: finding the hardest configuration and solving a given configuration as rapidly as possible. Both questions were addressed and furthered. The SearchBench has thus far been primarily applied to games for two reasons: First, games are simple to describe, making it easy for others to understand the implications of the research. Second, these domains can be adjusted so that their complexity can be handled by present-day methods. However, the algorithms and error-correcting techniques developed for the SearchBench can be transferred to many real-world applications. For instance sieve methods, shortest-path problems or dynamic programming techniques are closely related. I believe that future work will uncover even more useful applications of my research.

Publications