Selbstständig lernender Algorithmus

Aus Physik
Zur Navigation springen Zur Suche springen

Selbstständig lernender Algorithmus in Form eines einfachen Spielecomputers

Einleitung und Motivation

Trotz der immer höher werdenden Rechenleistungen der heutigen Computer, kann der Rechner nach wie vor nur die vom Programmierer vorgegebenen Befehle ausführen. Dieses Projekt startet einen Versuch einen primitiv selbstständig denkenden Algorithmus zu entwickeln, ohne die Theorie von neuronalen Netzen oder den Besitz eines Supercomputers vorauszusetzen.

Planungsphase

Vision

Es soll ein Algorithmus entwickelt werden, der in der Lage ist Gelerntes abzuspeichern und später darauf wieder zuzugreifen. Zu diesem Zweck wird das einfache Spiel Tic Tac Toe implementiert, bei welchem zwei Spieler abwechselnd Markierungen in ein Gitter einfügen und der Sieg durch eine durchgehende waagrechte, senkrechte oder diagonale Reihe erzielt wird. Grundsätzlich ist es üblich bei der Implementierung von künstlichen Gegnern dem Computer eine Strategie zur Erreichung eines Siegs fest vorzugeben und nach jedem Spielzug die Abfrage durchzuführen, ob ein Sieg oder eine Niederlage erreicht wurde.

Bei diesem Projekt sollen jedoch nur die Befehle für die Benutzerinteraktion und die Gewinnabfrage fest vorgegeben werden. Das System soll mit jedem Spiel lernen, ob die gewählten Züge gewinnbringend oder nicht waren und so mit der Zeit eine immer größere Spielzug-Datenbank aufbauen.

Grundkonzept des Algorithmus

Der menschliche Spieler und der Computer machen abwechselnd Züge, wobei die allerersten Züge des Computers völlig zufällig sind. Nach jedem Zug wird abgefragt, ob einer der beiden Kontrahenten einen Sieg erreicht oder das Spiel in einem Unentschieden geendet hat. Sollte der Benutzer gewonnen haben (wovon bei den ersten Runden natürlich auszugehen ist, da der Computer noch nichts gelernt hat), so wird sich der Algorithmus den Spielverlauf merken und beim nächsten Mal nicht mehr die gleichen Züge durchführen, da sie nicht gewinnbringend waren. Bei einem Sieg des Computers wird der Spielverlauf ebenso gespeichert und die Züge in Zukunft bevorzugt ausgeführt. Jederzeit gilt, dass bei einer unbekannten Spielsituation wieder der Zufallsgenerator den nächsten Zug bestimmt, solange bis wieder bekannte Situationen auftauchen.

Ziele

Durch eine Analyse der Anforderungen sollen Klassen identifiziert werden, um die Möglichkeit der objektorientierten Programmierung in Matlab zu nützen. Das System soll dabei so gestaltet werden, dass eine bestimmte Klasse für die Speicherung der Daten verantwortlich ist und nichts vom dahinter liegenden Spiel weiß. Somit ist es möglich das Programm durch eine neue Klasse des Typs Spiel sofort auf ein anderes Spiel zu erweitern. Die Grundidee bleibt dabei dieselbe, so dass wieder nur eine Gewinnabfrage definiert wird und keine Strategie zur Erreichung des Siegs. Diese ergibt sich automatisch aus den gelernten Daten.

Durch eine allgemein gehaltene Spieler-Klasse soll es möglich sein, dass zwei menschliche Spieler gegeneinander spielen bzw. der Mensch gegen den Computer. Die wichtigste Funktion des Programms wird allerdings die Möglichkeit des selbstständigen Lernens sein, so dass zwei Computer in hohem Tempo gegeneinander spielen können und eine immer größer werdende Lerndatenbank aufbauen. Damit sollte es nach einer bestimmten Zeit dieses Lernvorgangs nicht mehr möglich sein, gegen den Computer zu gewinnen. Die objektorientierte Programmierung wird im späteren Punkt zur Realisierungsphase noch genauer erklärt.

Weiters soll eine grafische Benutzeroberfläche erzeugt werden, die mit den dahinter liegenden Klassen interagiert. Dabei sollen die Namen der Spieler, der Schwierigkeitsgrad des Computers und die Art des Spiels ausgewählt werden können und die Spielfelder grafisch dargestellt werden.

Realisierungsphase

Seite in Bearbeitung

Resultate

Es zeigte sich bald, dass die größte Hürde in den großen Datenmengen liegt, welche bei dieser Art der Programmierung auftreten. Dies kann man sich leicht veranschaulichen wenn man bedenkt, dass während der Lernphase in jeder Spielsituation überprüft werden muss, ob diese Situation nun schon einmal aufgetreten ist oder ob es sich um eine gänzlich neue Situation handelt. Natürlich müssen hierfür alle bereits abgespeicherten Situationen durchlaufen und mit der gerade vorherrschenden verglichen werden.
Im Falle des Spiels Tic-Tac-Toe stellten diese Fakten noch kein nennenswertes Problem dar, da es hier nur 255.168 verscheidene Spielsituationen gibt [1]. Dies stellt für einen modernen Rechner keine große Hürde dar und ist sogar ohne aufwändige Optimierungen programmierbar.
Anders sieht es hier schon beim Spiel Vier gewinnt aus, bei dem es immerhin 7,1*10^13 verschiedene mögliche Bilder gibt [2]. Selbst unter Zuhilfenahme der hier einzig sinnvollen Symmetrieoperation (Spiegelung an der vertikalen Mittelachse) lässt sich diese Zahl nur halbieren, was immer noch 3,55*10^13 verschiedene Möglichkeiten bedeutet. Nun lässt sich diese Zahl an Spielsituationen bei heutigen Speicherdichten immer noch mit herkömmlichen Rechnern abspeichern, doch während dem Lernprozesses müssen wie bereits oben erwähnt immer alle bereits bekannten Situationen überprüft werden um eine neue Situation erkennen zu können. Was dies schon bei Durchgang 1*10^10 bedeutet wird dem Leser sofort klar sein. Da nun das Verwenden eine Clusters für dieses Projekt gleichermaßen übertrieben wie das zweiwöchig durchgängige Rechnen mit dem Privatrechner für diesen schädlich ist, wurde beschlossen das Ausmaß des Projektes zu reduzieren und stattdessen eine kleine Version eines Drei gewinnt auf einem 4*4 Spielfeld zu realisieren.
Durch die bereits vorigen Abschnitt beschriebenen Optimierungsmaßnahmen war die Durchführung dieses Projektes nun möglich. Dies zeigt, dass mit dem gewählten Ansatz auch das Spiel Vier gewinnt programmiert werden könnte, wenn man im Lernprozess über die erforderliche Rechenleistung verfügt. Eine weitere Verkomplizierung, zum Beispiel durch die dreidimensionale Form des Spieles (Sogo), würde dann wahrscheinlich auch im Spielverlauf zu Verzögerungen führen.