Neuronale Netze und Fuzzy-Systeme
Softwarepraktika Wintersemester 1999/2000
Neuronale Netze und Fuzzy-Systeme
Softwarepraktika Wintersemester 1999/2000 |
|
Alle Themen können auch mehrfach vergeben werden. Allerdings sollte dann die Programmiersprache unterschiedlich sein oder, bei Verwendung einer anderen Programmiersprache als Java, für unterschiedliche Oberflächen (MS Windows oder Unix/X11) entwickelt werden, damit nicht so leicht eine Gruppe von einer anderen abschreiben kann.
(2-3 Personen)
Das L-Spiel ist ein sehr einfaches, von Edward de Bono für sein Buch "In 15 Tagen Denken lernen" entworfenes Spiel für zwei Personen. Es wird auf einem 4x4 Felder großen Brett mit zwei L-förmigen, jeweils vier Felder bedeckenden, und zwei runden, jeweils ein Feld bedeckenden Steinen gespielt. Jedem Spieler ist ein L-Stein zugeordnet, die beiden anderen Steine sind neutral. Die Ausgangsposition ist:
 |
|
Die beiden Spieler ziehen abwechselnd. Ein Zug besteht darin, den eigenen L-Stein in eine neue Lage zu bringen. Anschließend darf noch einer der beiden neutralen Steine versetzt werden. Es besteht aber kein Zwang, einen neutralen Stein zu versetzen. Wichtig ist jedoch, das erst der L-Stein gezogen wird und erst anschließend (höchstens) ein neutraler Stein. Ein Spieler hat gewonnen, wenn sein Gegner keinen Zug mehr machen, d.h., seinen L-Stein nicht in eine neue Position bringen kann. In der folgenden Stellung hat z.B. Spieler 1 gewonnen, wenn Spieler 2 am Zug ist:
 |
|
Aufgabe des Softwarepraktikums ist es, eine graphische Oberfläche für das L-Spiel und einen Computergegner zu implementieren.
Vergabe: Bisher zweimal vergeben, einmal in Java, einmal in Borland Delphi.
| zurück zum Seitenanfang | 
|
(2-3 Personen)
"Bleib dran!" ist ein topologisches Spiel für zwei Personen, das von Sid Sackson erfunden und in seinem Buch "Spiele anders als andere", dtv, München, 1984, vorgestellt wurde. In der Grundversion wird es auf einem Raster aus 4x4 Punkten wie dem folgenden gespielt. Das Spielfeld kann jedoch vergrößert werden, um das Spiel komplizierter zu machen.
 |
|
Die beiden Spieler verbinden abwechselnd zwei oder mehr Punkte durch eine horizontale, vertikale oder diagonale gerade Linie. Der Spieler, der die erste Linie zeichnet, darf beide Endpunkte der Linie frei wählen. Der zweite Spieler setzt an einem Ende dieser Linie an und auch in den folgenden Zügen muß die neue Linie stets an einem der beiden freien Enden des bisher gezeichneten Linienzuges ansetzen (daher der Name "Bleib dran!"). Der Spieler, der die letzte Linie zeichnen kann, hat gewonnen. So hat z.B. der rote Linien zeichnende Spieler in der folgenden Situation das Spiel gewonnen, wenn der blaue Linien zeichnende Spieler das Spiel begonnen hat:
 |
|
Man beachte, daß die rote Linie auf der rechten Seite in zwei Zügen gezeichnet wurde.
Aufgabe des Softwarepraktikums ist, eine graphische Oberfläche für das Spiel "Bleib dran!" und einen Computergegner zu implementieren. Die Größe des Rasters sollte möglichst nicht auf 4x4 festgelegt sein. Je nach Teilnehmerzahl können auch noch Variationen des Spiels implementiert werden, z.B. eine Version, in der die Linien auch anders geneigt sein dürfen.
Nachtrag: Zu bemerken ist, daß für jedes rechteckige Punktraster der anziehende Spieler eine einfache Gewinnstrategie hat (Welche?). Offenbar hat der Erfinder des Spiels diese Möglichkeit übersehen. Die Anwendung dieser Strategie kann man jedoch verhindern, indem man die Ausgangslinie vorgibt und nicht vom anziehenden Spieler zeichnen läßt.
Vergabe: Bisher einmal in C/C++ für MS Windows, einmal in Borland Delphi und einmal in Java vergeben.
| zurück zum Seitenanfang |
|
(2-4 Personen)
Sprouts (Pflanzensprossen) und Brussels Sprouts (Rosenkohl) sind einfache topologische Spiele für zwei Personen. Bei beiden Spielen wird zunächst eine beliebige Menge von Punkten auf ein Blatt Papier gezeichnet. Die Spieler ziehen abwechselnd. Ein Zug besteht darin, zwei Punkte durch eine Linie zu verbinden, und auf dieser Linie einen neuen Punkt zu zeichnen. Die Verbindungslinie darf keine bereits früher gezeichneten Linien schneiden. Bei Sprouts dürfen von einem Punkt nie mehr als drei Linien, bei Brussels Sprouts nie mehr als vier Linien ausgehen. Auch die auf Verbindungslinien gezeichneten Punkte dürfen wieder mit anderen verbunden werden. Man beachte jedoch, daß durch die Verbindungslinie, auf die sie gezeichnet wurden, von ihnen bereits zwei Linien ausgehen.
Aufgabe des Softwarepraktikums ist es, eine graphische Oberfläche für diese beiden Spiele zu entwickeln. Je nach Teilnehmerzahl kann auch versucht werden, einen Computergegner zu implementieren. Ein Computergegner ist jedoch ggf. schon eine recht anspruchsvolle Aufgabe, da es zu seiner Implementierung wahrscheinlich nötig, auf jeden Fall aber hilfreich ist, sich in die Theorie der plättbaren Graphen einzuarbeiten.
Vergabe: Bisher einmal in Java vergeben.
| zurück zum Seitenanfang |
|
(2-4 Personen)
Bridg-It ist ein von dem amerikanischen Mathematiker David Gale erfundenes Spiel für zwei Personen, in dem es darum geht, eine Brücke zu bauen. Gespielt wird auf einem Spielfeld wie dem folgenden:
 |
|
Die farbigen Punkte stellen Stützpfeiler dar, die durch Brückenteile verbunden werden können. Jede Farbe ist einem Spieler zugeordnet. Die Spieler ziehen abwechselnd. Ein Zug besteht darin, daß zwei beliebige, horizontal oder vertikal benachbarte Stützpunkte der Farbe des Spielers durch ein Brückenteil verbunden werden. Gewonnen hat derjenige Spieler, dem es gelingt, eine durchgehende Brücke von links nach rechts (Spieler 1, rot) bzw. eine Brücke von oben nach unten (Spieler 2, blau) zu bauen. Z.B. hat in der folgenden Stellung Spieler 2 gewonnen:
 |
|
1951 hat Claude Shannon einen einfachen, auf einer Eigenschaft elektrischer Schaltkreise beruhenden Automaten konstruiert, der dieses Spiel recht gut, wenn auch nicht perfekt spielt. Eine Beschreibung des Prinzips dieses Verfahrens findet man z.B. in Martin Gardners Buch "The Second Scientific American Book of Mathematical Puzzles and Diversions", Dover, 1987.
Aufgabe des Softwarepraktikums ist es, eine graphische Oberfäche für das Spiel Bridg-It und einen Computergegner zu implementieren, der auf dem von Shannon verwendeten Prinzip beruht. Weiter kann, je nach Teilnehmerzahl, versucht werden, einen besseren Computergegner zu konstruieren als ihn das Shannonsche Prinzip liefert.
Das Spiel läßt außerdem folgende Variante zu: Die Zahl der Brückenteile für die beiden Spieler wird begrenzt. Gelingt es keinem der beiden Spieler, eine Brücke zu bauen, bis er alle seine Brückenteile verbraucht hat, so können in einer zweiten Phase des Spiels bereits plazierte Brückenteile versetzt werden. Auch für diese Variante könnte man einen Computergegner implementieren.
Vergabe: Bisher einmal in C/C++ für MS Windows vergeben.
| zurück zum Seitenanfang |
|
(2-4 Personen)
Der Streichholzschachtelcomputer wurde vor einigen Jahren als sehr einfache Illustration eines automatischen lernenden Systems in der Zeitschrift "Spektrum der Wissenschaft" vorgestellt. Er wurde an einem aus dem Schach abgeleiteten, sehr einfachen Brettspiel erläutert. Dieses Brettspiel wird von 2 Personen auf einem 3x3 Brett gespielt. Jeder Spieler verfügt über 3 Figuren, die am Anfang so aufgestellt werden:
 |
|
Die Spieler ziehen abwechselnd eine Figur. Die Figuren ziehen wie die Bauern in Schachspiel. D.h., sie können ein Feld nach vorn (Spieler 1 nach oben, Spieler 2 nach unten) ziehen, wenn das voraus liegende Feld frei ist, und sie können eine gegnerische Figur schlagen, wenn diese auf einem der beiden diagonal vorausliegenden Felder steht. Gewonnen hat derjenige Spieler, dem es gelingt, eine Figur auf die andere Seite des Brettes zu bringen. Z.B. hat in der folgenden Stellung Spieler 1 gewonnen:
 |
|
Es ist klar, daß das Spiel auf jeden Fall nach einer bestimmten, kleinen Zahl von Zügen endet und daß es folglich nur eine relativ geringe Zahl möglicher Spielstellungen gibt. Dies ermöglicht folgende einfache "Streichholzschachtelimplementierung" eines Spielprogramms. Die möglichen Spielstellungen, in denen die jeweils möglichen Züge farbig eingezeichnet sind, werden auf Streichholzschachteln geklebt; je eine pro Schachtel. In die Schachtel kommt für jede Farbe eines Zuges, der in der Stellung auf der Schachtel verzeichnet ist, eine bestimmte Anzahl gleichfarbiger Kugeln. Gespielt wird mit diesem "Programm" wie folgt: Man zieht aus der Streichholzschachtel mit der aktuellen Spielstellung zufällig eine Kugel und macht den durch die Farbe der Kugel angezeigten Zug.
Das System kann nun folgendermaßen lernen, gut zu spielen: Hat der "Streichholzschachtelspieler" ein Spiel gewonnen, so wird für die Züge, die er gemacht hat, je Zug eine Kugel (mit der dem Zug entsprechenden Farbe) mehr in die entsprechende Streichholzschachtel gelegt. Hat er verloren, so wird für den letzten Zug, den er gemacht hat, eine Kugel mit dem zu dem Zug gehörenden Farbe entfernt. Wird die entsprechende Schachtel dadurch leer, wird auch für den vorletzten Zug eine Kugel entfernt. Nach genügend vielen Spielen beherrscht der Streichholzschachtelspieler das Spiel perfekt. Natürlich kann man die obigen Lernregeln auch abändern; z.B. nur Verluste durch Kugelentfernen bestrafen, aber Siege nicht durch Kugelhinzufügen belohnen, nur den letzten Zug bei einem Sieg belohnen o.ä.
Aufgabe des Softwarepraktikums ist es, ein Simulationsprogramm für den Streichholzschachtelcomputer (mit geeigneter graphischer Oberfläche) zu schreiben. Je nach Teilnehmerzahl können auch andere Spiele, z.B. Tic-Tac-Toe o.ä., mit einem Streichholzschachtelcomputer implementiert werden.
Vergabe: Bereits mehrfach vergeben, einmal für das oben beschriebene Spiel in Java, einmal für Tic-Tac-Toe in Java, einmal für Drei gewinnt in Java, einmal für Tic-Tac-Toe und Drei gewinnt in C/C++.
| zurück zum Seitenanfang |
|
(2-3 Personen)
Unter "Schiebepuzzle" verstehen wir die oft als Werbegeschenke verteilten Puzzle, in denen ein Bild oder eine Zahlenfolge in ein 4x4-Raster zerlegt wird. Ein Feld bleibt jedoch frei, so daß man 15 Teile hat. Die an das freie Feld angrenzenden Teile können in das freie Feld geschoben werden. Ziel ist es, die anfangs zufällig angeordneten Teile in die richtige Position zu bringen, so daß das Bild erkennbar wird bzw. die Zahlen in der richtigen Reihenfolge stehen.
Der A*-Algorithmus ist ein heuristischer Suchalgorithmus aus der künstlichen Intelligenz. Er läßt sich sehr schön mit Hilfe eines Schiebepuzzles illustrieren (siehe N. Nilsson, Artificial Intelligence, M. Kaufmann, 1998), jedenfalls, wenn man sich auf eine 3x3-Version beschränkt. Eine genaue Beschreibung des A*-Algorithmus, der mit Hilfe heuristischer Suchkriterien einen Suchbaum aufbaut, würde hier zu weit führen. Eine ausführliche Beschreibung findet sich hier oder in dem oben angegebenen Buch von N. Nilsson. Ein Beispiel ist in Aufgabe 27 auf diesem Übungsblatt und der zugehörigen Lösung aus der Vorlesung "Grundlagen der Wissensverarbeitung" (Prof. R. Kruse, WS 1998/1999) gezeigt.
Aufgabe des Softwarepraktikums ist es, den A*-Algorithmus für ein 3x3 Schiebepuzzle zu implementieren und eine graphische Oberfläche zu schaffen, auf der der aufgebaute Suchbaum zusammen mit der Heuristikfunktion dargestellt wird, möglichst auch die Schritte des Aufbaus nacheinander ausgeführt werden können.
Vergabe: Bisher dreimal vergeben: Einmal in C/C++, einmal in Java, einmal in Borland Delphi.
| zurück zum Seitenanfang |
|
(1-2 Personen)
Beim Springerproblem geht es darum, eine Wanderung eines Springers (Figur beim Schachspiel) über ein n x n-Schachbrett zu finden, so daß er jedes Feld genau einmal betritt. (Als erschwerende Bedingung kann man außerdem einführen, daß er von dem letzten Feld seiner Wanderung wieder auf das erste ziehen können, sein Weg also geschlossen sein soll.) Wie ein Springer zieht, ist in dem untenstehenden Diagramm gezeigt. Der weiße Springer kann auf genau die Felder ziehen, die durch rote Punkte markiert sind.
 |
|
Das einfachste Verfahren, um eine Lösung des Springerproblems zu finden, ist das sogenannte Backtracking: Es wird eine Tiefensuche über die Wege des Springers ausgeführt. D.h. der Springer beginnt seinen Weg mit nach einem bestimmten Schema festgelegten Zügen. Gerät er in eine Sackgasse, wird der letzte Zug rückgängig gemacht und ein anderer versucht. Führen alle Züge in Sackgassen, wird der vorletzte Zug rückgängig gemacht usf. Wegen dieses Zurückgehens auf dem Weg, auf den der Springer gekommen ist, heißt dieses Verfahren Backtracking (back - zurück, track - Weg, Pfad, Spur).
Es ist klar, daß das Backtracking-Verfahren auf jeden Fall eine Wanderung findet, wenn es eine gibt. Für größere Schachbretter erweist es sich jedoch als sehr ineffizient. Es kann erhebliche Zeit dauern, bis eine Lösung gefunden wird. Daher verwendet man bei größeren Brettern heuristische Suchverfahren, die zwar nicht zwingend, aber doch sehr häufig eine Lösung finden. Ein solches Verfahren ist das sogenannte "simulated annealing" (simuliertes Ausglühen). Die Idee dieses Verfahrens ist, mit einem zufälligen Weg anzufangen und ihn zu bewerten (hier, wie gut die Schritte den erlaubten Springerzügen entsprechen). Dann wird der Weg zufällig abgeändert und erneut bewertet. Ist der neue Weg besser, wird er auf jeden Fall, ist er schlechter, wird er nur mit einer gewissen Wahrscheinlichkeit übernommen. Diese Wahrscheinlichkeit wird im Laufe der Suche über einen Temperaturparameter (daher simuliertes Ausglühen) langsam vermindert. Ziel dieses Vorgehens ist es, ein Steckenbleiben der Suche in lokalen Minima zu verhindern.
Aufgabe des Softwarepraktiums ist, die Lösung des Springerproblems mit dem Backtracking- und dem Simulated-Annealing-Verfahren zum implementieren. Allerdings sollen nicht nur quadratische, sondern beliebig geformte Bretter verarbeitet werden können. Je nach Teilnehmerzahl kann auch eine graphische Benutzeroberfläche entwickelt werden.
Vergabe: Bisher dreimal vergeben, einmal in C/C++, einmal in Java/Javascript und einmal in Borland Delphi.
| zurück zum Seitenanfang |
|
(1-2 Personen)
Die lernende Vektorquantisierung ist ein Verfahren aus dem Bereich der neuronalen Netze, bei dem sogenannte Codebook- oder Referenzvektoren, die jeweils durch ein Neuron dargestellt sind, so im Eingaberaum angeordnet werden, daß sie diesen gemäß seiner Besetzung mit Datenpunkten möglichst gut abdecken. Beschränkt man sich auf zwei Dimensionen, so läßt sich der Lernprozess sehr leicht visualisieren, indem man die Datenpunkte und die Codebookvektoren durch verschiedene Farben darstellt und die Lageveränderung im Laufe des Lernens zeigt. Eine genaue Beschreibung der lernenden Vektorquantisierung würde hier zu weit führen. Sie kann z.B. in dem Buch "Simulation neuronaler Netze" von A. Zell, Addison-Wesley, 1994, nachgelesen werden.
Aufgabe des Softwarepraktikums ist es, ein Visualisierungsprogramm für eine zweidimensionale lernende Vektorquantisierung zu schreiben, in dem verschiedene Abstandsmaße gewählt werden können. Je nach Teilnehmerzahl kann die Aufgabe auch auf Kohonen-Netze (neuronale Netze für sogenannte topologieerhaltende Abbildungen) für zweidimensionale Eingaben erweitert werden.
Vergabe: Bisher einmal in C vergeben.
| zurück zum Seitenanfang |
|
(1-2 Personen)
Klassifikatoren sind Programme die ein Fall oder ein Objekt gemäß seiner Eigenschaften klassifizieren, d.h., ihn bzw. es einer von mehreren vorgegebenen Klassen zuordnen. Eine sehr bekannte Form von Klassifikatoren sind die sogenannten Naiv-Bayes-Klassifikatoren, die einen wahrscheinlichkeitstheoretischen Ansatz verfolgen. Eine genaue Beschreibung von Naiv-Bayes-Klassifikatoren würde hier zu weit führen. Eine kurze Einführung findet sich z.B. in diesem Aufsatz.
Im Ottominer-Projekt der Arbeitsgruppe von Prof. Kruse im Institut für Wissens- und Sprachverarbeitung soll ein Data-Mining-System entwickelt werden, in dem verschiedene Data-Mining-Verfahren leicht zusammengeschaltet werden können. Auch ein Naiv-Bayes-Klassifikator soll eingebaut werden.
Aufgabe des Softwarepraktikums ist es, einen Naiv-Bayes-Klassifikator zusammen mit einer geeigneten Visualisierung für den Ottominer zu entwickeln. Dabei kann von einem C-Kommandozeilenprogramm ausgegangen werden.
Vergabe: Bereits vergeben.
| zurück zum Seitenanfang |
|