Selbstständig lernender Algorithmus: Unterschied zwischen den Versionen

Aus Physik
Zur Navigation springen Zur Suche springen
(Klassenerklärungen)
Zeile 1: Zeile 1:
= Selbstständig lernender Algorithmus in Form eines einfachen Spielecomputers =
 
 
== Einleitung und Motivation ==
 
== 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.
 
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.

Version vom 20. Februar 2010, 00:40 Uhr

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

Analyse

Klassendiagramm

Die Analyse der Anforderungen ergab folgendes vereinfachtes Klassendiagramm.

Klassendiagramm des Projekts

Erklärung der Klassen

  • Game
    Hier handelt es sich um eine abstrakte Klasse, die Attribute und Methoden vorgibt, welche eine abgeleitete Klassen besitzen muss, um mit dem Programm verwendet werden zu können. Die drei kursiven Methoden sind die einzigen Methoden, die von einer vererbten Klasse implementiert werden müssen, da sich diese von Spiel zu Spiel unterscheiden.
  • TicTacToe
    Abgeleitet von Game. Die Methode getPossiblePositions() gibt alle leeren Felder zurück auf die noch gesetzt werden kann. checkState() überprüft, ob einer Spieler gewonnen hat oder ob ein Unentschieden erspielt wurde. draw() ist eine Methode, die das Spielfeld auf der Konsole ausgibt und wird in späterer Folge durch die GUI ersetzt.
  • ThreeWins
    Abgeleitet von Game. Die Methode getPossiblePositions() überprüft welche Spalten noch nicht mit vier Steinen voll sind und gibt die restlichen möglichen Spalten zurück. checkState() überprüft in allen Reihen, Spalten und Diagonalen, ob es einem Spieler gelungen ist drei Steine gleicher Farbe in Folge gesetzt zu haben.
  • Player
    Diese Klasse kann sowohl einen menschlichen als auch einen computerbasierten Gegner repräsentieren. Die Klasse Game besitzt ein Feld von Spielern und interagiert über die Methode getStep() mit diesen. Dabei macht es für die Klasse Game keinen Unterschied ob die Koordinaten von getStep() per Benutzerinteraktion eingegeben wurden oder im Falle eines künstlichen Gegners berechnet wurden. Dies ist hier der große Vorteil der objektorientierten Programmierung. Über die Methode giveFeedback() teilt die Klasse Game dem Spieler mit, ob das vorherige Spiel gewonnen oder verloren wurde, was im Falle eines künstlichen Gegners weiter verarbeitet wird.
  • DrM
    Die zentralste Klasse dieses Projekts. Diese Klasse verwaltet die gesamten Lerndaten, berechnet Gewinn- und Verlustwahrscheinlichkeiten und kann bei vorgegebenen Spielsituationen den optimalsten nächsten Schritt zurückliefern. Um dem Spielecomputer eine gewisse Persönlichkeit zu verleihen wird er nachfolgend Dr. M. genannt, woraus sich auch der Klassenname herleitet. Fordert das laufende Spiel in der Methode run() der Klasse Game einen nächsten Spielzug über die Methode getStep() der Klasse Player an, so wird im Falle eines Computergegners die Methode lookup() der Klasse DrM aufgerufen.
  • java.util.hashTable
    Eine vordefinierte Java-Klasse, die das Speichern der Daten in sogenannten Hashtables ermöglicht.

Design

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 jedesmal alle bereits abgespeicherten Situationen 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 verschiedene Spielverläufe 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 eines Clusters für dieses Projekt gleichermaßen übertrieben wie das zweiwöchig durchgängige Rechnen mit dem Privatrechner für dessen temperaturempfindliche Teile schädlich ist, wurde beschlossen 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.

Literaturverzeichnis

[1]: http://de.wikipedia.org/wiki/Tic_Tac_Toe
[2]: 1.↑ *Victor Allis Master's Thesis mit der Lösungsstrategie (PDF - Datei) in: 1988 as Report IR-163 by the Faculty of Mathematics and Computer Science at the Vrije Universiteit Amsterdam, The Netherlands. Also published in 1992 as Report CS 92-04 by the Faculty of General Sciences at the University of Limburg, Maastricht, The Netherlands. (http://www.connectfour.net/Files/connect4.pdf)