Stipendiaten 2007

Stefan Faußer

Projekttitel: Maschinelles Lernen für 2-Personen Brettspiele
Hochschule: Universität Ulm
Studiengang: Informatik

Kurzbeschreibung

Bereits seit jahrzehnten implementieren Anwendungsentwickler Brettspiele auf Computer. Ob Backgammon, Vier Gewinnt, Schach, Mühle oder Dame: Computerprogramme versuchen stehts gegen den menschlichen Gegenspieler zu gewinnen. Die Vorgehensweise, wie ein Computerprogramm ein Brettspiel spielt, ist jedoch häufig die selbe: Es wird in einer aktuellen Spielsituation ein Spielbaum mit einer bestimmten, beschränkten Tiefe berechnet und aufgrund des Spielbaumes die beste Zugmöglichkeit gewählt. Dies bedeutet, dass das Computerprogramm aufgrund der Tiefe des Suchbaumes nur eine bestimmte Anzahl von Spielrunden "voraus" denken kann, da diese Art der Auswahl des besten Spielzuges sehr viel Rechenzeit und Speicherkapazität benötigt.

Diese klassischen Methoden der Künstlichen Intelligenz werden im durch das Karl-Steinbuch-Stipendium geförderten Projekt durch Methoden aus dem Bereich der Optimierung (Reinforcement learning) und der Neuroinformatik ersetzt. Das neuartige Computerprogramm soll nur durch Kenntnis der Spielregeln, dem allgemeinen Prinzip von Belohnung und Bestrafung und durch Beispiele ein 2 Personen Brettspiel erlernen. Dies bedeutet, dass das Computerprogramm keine festen Regeln (Logik) einsetzen wird und durch Abfolgen von Spiel-Beispielen sein Wissen verbessert. Im Detail werden allgemeine Ansätze im Bereich der Optimierung hinsichtlich ihrer Anwendbarkeit für 2 Personen Brettspiele untersucht und speziell wird auf die Problematik eingegangen, dass die Zustandsräume (Kombination möglicher Spielzüge) verschiedenster Brettspiele sehr groß sind und die Speicherkapazitäten selbst modernster Rechensysteme nicht ausreichen um diese Zustandsräume zu speichern. These: Diese Einschränkung kann durch eine Kombination mit neuronalen Netzen zur Approximation der Zustandsbewertungsfunktionen überwunden werden.

Das Resultat wird aus einem trainierbaren Server mit einer speicherbaren Wissensbasis und einem Client Teil, der GUI, bestehen. Im Projekt wird sich Herr Faußer auf das Dame Spiel konzentrieren, d.h. dass das Computerprogramm Dame spielen erlernen soll. Im Laufe der Trainingsphase soll sich die Wissensbasis verbessern, so dass die Wahl der Spielzüge bei Dame entsprechend intelligent erfolgt und es dem Computerprogramm möglich ist, gegen einen menschlichen Spieler zu gewinnen.

Neural Network Schemata