Master of Science in Electrical Engineering Wintersemester 2005/2006 Prof. Dr. E.-G. Haffner Lernende Systeme Teil 1

Master of Science in Electrical EngineeringWintersemester 2005/2006

Prof. Dr. E.-G. Haffner

Lernende SystemeTeil 1

WS2005/06 Lernende Systeme - Prof. Dr. E.G. Haffner 2

Übersicht

1. Einführung 2. Psychologische Aspekte3. Spieltheorie4. Wissensrepräsentation5. Symbolische Lernverfahren6. Konnektionismus7. Zusammenfassung und Ausblick


1. Einführung

• Einleitung • Konzept der Lehrveranstaltung• Wichtige Begriffe• Historische Entwicklung• Klassifikationen• Lernszenario und Definition• Literaturübersicht


Einleitung Winston Churchill

Es ist ein großer Vorteil im Leben, die Fehler, aus denen man lernen kann, möglichst frühzeitig zu machen.

KonfuziusLernen, ohne zu denken, ist eitel; denken, ohne zu lernen, ist gefährlich.

Georg Berhard ShawDer Nachteil der Intelligenz besteht darin, dass man ununterbrochen dazulernen muss.


Sinn und Zweck

• Lernen ist eine der wichtigsten kognitiven Fähigkeiten

• Innovative Systeme werden häufig in komplexen Situationen eingesetzt, für die keine ad hoc Lösung bereitsteht

• Lernende Systeme können sich über die vorgesehenen Entwicklungsstufen hinaus (eigenständig) verbessern

• Auch menschliches Lernen kann besser ver-standen und effektiver angewendet werden


Konzept der Lehrveranstaltung

• Erarbeiten des Begriffs „Lernen“• Betrachtung psychologischer Aspekte• Klassifikation und Analyse von maschinellen

Lernmethoden• Symbolische• Konnektionistische (subsymbolische)

• Anwendung von 3 beispielhaften Konzepten in der (Labor-)Praxis• Spieleprogrammierung• Case-based-Learning System• Neuronales Netz


Wichtige Begriffe

• Inferenz• (automatisierte) Schlussfolgerung• Manipulation/Ergänzung von Informationen

• Lernprozess, Anwendung von Ableitungsregeln, Lernregeln

• Lerngegenstand / Lernziel / Lernaufgabe• Lernmethoden• Wissensbasis


Grundsatz der KI

The analytical engine has no pretensions whatever

to originate anything. It can do whatever we know how to order it to perform.

Ada Lovelace (1815-1852)

Aber wie sagen wir der Maschine, was sie tun soll?


Historische Entwicklung (I)

• Subsymbolische Phase • Neuronale Modellierung gemäß Vorbildern in

der Natur• Selbstorganisierende Systeme• Evolutionäres Lernen (Mutation etc.)

• Symbolische Phase• Wissenserwerb erfordert Wissen• Konzeptlernen• Deduktionssysteme, logische Beweiser


Historische Entwicklung (II)• Wissensintensive Phase

• Wissensintensive Lernmodelle• Kombinationen von Lernstrategien• Man beginnt mit bspw. 100 Mio. Fakten• Eigenständiges Gebiet: Maschinelles Lernen

• Integrierte Phase• Kombination aus allen Modellen• Erklärungsbasierte und

EntscheidungsunterstützendeVerfahren• Ausdehnung auf Robotik, Natürliche Sprache,

Planen, Problemlösen, Expertensysteme ....


Klassifikationen (I)

• Inferenztyp• Induktive Inferenz, synthetisches Lernen • Deduktive Inferenz, analytisches Lernen

• Wissensrepräsentation• Symbolisch• Subsymbolisch, Konnektionistisch

• Wissenserhebung• Interview, explizit• Beobachtung, explizit• Indirekt, implizit


Klassifikationen (II)• Inferenzart

• Destruktiv, allgemeine Gesetze verfeinern • Konstruktiv, spezielle Gesetze erweitern

• Lernstrategie [Umfang der Inferenz]• Mechanisch, Routinelernen [keine]• Durch Instruktion, Unterweisung [gering]• Durch Operationalisierung, neue Operationen,

Reihenfolge verändern etc. [unterschiedlich]• Durch Induktion [groß]• Durch Analogie [mittel]• Durch Deduktion [erheblich]


Klassifikationen (III)• Darbietung des Wissens

• Als (fertiges) Konzept• Aus Beispielen

• Art der Generalisierung• Klasse aus Instanzen ermitteln• Das Ganze aus Einzelteilen ermitteln

• Quelle der Beispiele• Labor, Umwelt, Systemimmanent

• Art der Beispiele• Nur positive negative und positive

• Darbietung der Beispiele• Inkrementell einmalig


Klassifikationen (IV)• Lernen als Suchen im Lösungsraum

• Suchverfahren• Breadth first search, …• Depth first search, …

• Komplexität des Algorithmus• Systematik

• Heuristisch• Vollständig


Klassifikationen (V)• Lernen mit Lehrer

• Auswendiglernen• Lernen durch Instruktion• Präsentation von Beispielen• Bewertung

• Im Detail• Im Ergebnis

• Korrektur

• Lernen ohne Lehrer• Passives Beobachten• Aktives Experimentieren


Klassifikationen (VI)• Lerzielvorgabe, Erfolgskriterien

• Explizit• Konkrete Vorgabe des Lernziels• Vorgabe von Güte- und Qualitätskriterien

• Implizit• Versteckt in den Algorithmen• Durch Anordnung von Neuronen u.a.


Das Lernszenario (I)

Lernendes System

Daten

Vorhersagen

Minimal


Das Lernszenario (II)Verfeinert

Inference

Hypothesis Generator

Verificator

Data Integrator

Knowledge Base


Definition

• A computer program is said to learn from Experience E with respect to some class of tasks T and performance measure P, if its performance at tasks in T, as measured by P, improves with E.(Tom Mitchell, Machine Learning)


Beispiele• Experience E

• Gewonnene, remisierte, verlorene Spiele (GT)• Korrekt, falsch, irrelevant diagnostizierte Verläufe von Krankheiten

(CBL)• Vorstellung zahlreicher Muster mit ihrer jeweilig (korrekten)

Klassifikation (NN)• Tasks T

• Ausführung erlaubter Züge (GT)• Diagnostizierung von Krankheiten (CBL)• Klassifikation von Mustern (NN)

• Performance measure P• Spielerfolg in Prozent, Turniererfolge (Platzierung) (GT)• Prozentsatz korrekter Diagnosen, Recall, Precision (CBL)• Anteil korrekt klassifizierter Muster (NN)

Literaturübersicht• Tom Mitchel, Machine Learning, McGraw Hill, 1997• Werner Emde, Modellbildung, Wissensrepräsemtatoin im Maschinellen Lernen,

Springer-Verlag, 1991• Hubert Keller, Maschinelle Intelligenz, Vieweg, 2000• David J.C. MacKay, Information Theory, Inference,

and Learning Algorithms, Cambridge University Press, 2003, 2004• Zimbardo, Psychologie, Springer-Lehrbuch, 1992• John Anderson, Kognitive Psychologie, Spektrum Lehrbuch, 2001• Russel Norvig, Künstliche Intelligenz, Ein moderner Ansatz, Pearson Education, 2004• Lämmel, Cleve, Künstliche Intelligenz,

Fachbuchverlag Leipzig, 2004• Richter, Prinzipien der Künstlichen Intelligenz,

Teubner Stuttgart, 1989• Elaine Rich, Künstliche Intelligenz, McGraw Hill, 1988• Dorffner, Konnektionismus, Teubner Stuttgart, 1991• Brause, Neuronale Netze, Teubner Stuttgart, 1995• Penrose, Computerdenken, Spektrum Verlag, 1991


2. Psychologische Aspekte• Einleitung und Definition

• Was ist Lernen?• Welches sind die Grundannahmen?• Was leistet unser Gehirn?

• Klassische Konditionierung• Pawlows Versuche• Paradigmen der Konditionierung

• Lernen über Konsequenzen• Thorndikes Theorie• Weitere Ableitungen


Einleitung und Definition (I)

• Was ist Lernen?• Lernen ist ein Prozess, der zu relativ stabilen

Veränderungen im Verhalten oder im Verhaltenspotenzial führt und auf Erfahrung aufbaut (Zimbardo)

• Lernen kann nicht direkt beobachtet werden• Lernen kann nur indirekt über die Beobachtung

des Verhaltens geschlossen werden


Einleitung und Definition (II)

• Möglichkeit 1:• Neue Fähigkeit, Verbesserung der

Leistung bzgl. Fähigkeit• Auto fahren, Rad fahren, schwimmen ...• Leistung schwankt aber sehr stark

• Methode: Training• Leistungsplateaus• Übertrainiert• Optimale Stimulationsimpluse


Einleitung und Definition (III)

• Möglichkeit 2:• Erwerb von (Fakten-)Wissen, Methodik• Erkenntnisse über Zusammenhänge• „Natürliche“ Erfahrungen

• Gravitation (Gegenstände fallen zu Boden)• Beispiel: „Heiße Kochplatte“

• Problem: latentes Wissen steht dem (systemimmanente) Vergessen gegenüber


Einleitung und Definition (IV)

• Welches sind die Grundannahmen?• Gesetz der Assoziation• Prinzip des adaptiven Hedonismus


Gesetz der Assoziation

• Wir erwerben Wissen, indem wir „Ideen“ verbinden• 2 Ereignisse in zeitlicher/räumlicher Nähe

werden „verbunden“, assoziiert• Sigmund Freud:

• Freie Assoziation zur Aufdeckung unterbewusster Zwänge / Neurosen

• Assoziative Netze / Neuronale Netze• Zur Musterklassifikation• Zum Erwerb von Wissen, Fähigkeiten, etc.


Assoziationen / Analogien


Prinzip des adaptiven Hedonismus

• Worin besteht die Motivation des Handelns?• Gewinn von Lust• Vermeidung von Schmerz

• Gegenpol• Altruismus, Selbstlosigkeit• Vorteile bei der Überwindung von Egoismus• Kooperatives Handeln, Kooperative Ziele


Leistungen unseres Gehirns

• Gesetzmäßigkeiten der visuellen Verarbeitung von Informationen

• Beispiele• Folgerungen


Gesetz der Nähe


Gesetz der Ähnlichkeit


Gesetz des glatten Verlaufs


Gesetz der Geschlossenheit


Funktionsweise des Gehirns


Fantasie und Kreativität


Klassische Konditionierung

• Pawlows Versuche• Paradigmen der Konditionierung• Funktionsweise des Konditionierens


Pawlows Versuche• Iwan Pawlow, russ.Physiologe (1849-1936)

• Stößt bei der Untersuchung von Verdauungs-prozessen (Speichel, Magensekret) zufällig (!) auf ein „merkwürdiges Phänomen“: Sekretion von Hundespeichel beginnt (später: nach Konditionierung) bereits vor Futtereingabe

• Jeder Reiz konnte Sekretion auslösen• Pawlow ändert mit 50 Jahren seine

Forschungsschwerpunkte• Nobelpreis 1904

http://de.wikipedia.org/wiki/Bild:Pawlow.jpg


Paradigmen der Konditionierung

• Vorgaben & Begriffe• Neutraler (unkonditionierter) Reiz (N), z.B. „Glocke“• Biologisch signifikanter Reiz (B), z.B. „Futteransicht“• B ist zugleich auch unkonditionierter Stimulus (US)• B kann unkonditionierten Reflex bewirken (UR),

z.B. Speichelfluss (unkonditioniert, da nicht gelernt)

• Idee der Konditionierung ( Lernen): • Verknüpfung von N und B• Aus dem Reiz N wird dann ein konditionierter Reiz

(CS), aus UR wird ein konditionierter Reflex (CR)• Z.B.: Glocke führt zum Speichelfluss

Funktionsweise des Konditionierens

• Erwerb• In dieser Phase wird aus N ein CS• Jeder Konditionierungsdurchgang heißt Trial• Assoziation zwischen US und B

• Unabhängige Variablen• Anzahl der Trials• Zeitliche Abstände• Qualität und Intensität der gebotenen Reize N, B

• Abhängige Variabeln• Stärke der Reaktion (Amplitude)• Zeit bis zur Reaktion (Latenz)• Wie lange dauert es, bis NCS? (Erwerbsrate)• Wie lange hält CR vor? (Persistenz, Löschrate)


Zeitmuster der Konditionierung

• Vorwärtsgerichtet (verzögert) VV• CS vor US, Beste Lernrate (1-5 Sekunden Zeitintervall)• Konditionierter Furchterwerb (15 Sekunden und mehr!)

• Vorwärtsgerichtet (Gedächtnisspur) VG• CS vor US• CS beendet, bevor US anfängt

• Gleichzeitig GZ• Geringerer Lernerfolg

• Rückwirkend RW• Geringster Lernerfolg

• Wichtig: starker Kontrast von N zur Umgebung


Weitere Ergebnisse• Löschung

• Bleibt Kombination von CS und US aus, so tritt (mit zeitl. Verzögerung) eine Löschung ein

• Aber nach erneutem Lernen kann eine Spontane Erholung wieder konditionieren

• Reizgeneralisierung• Wenn Reiz N konditioniert ist und zu CS geworden

ist, können auch ähnliche Reize CR hervorrufen (ähnliche Töne, etc.)

• Reizdiskrimination• Trennung zwischen ähnlichen Reizen • Viele negative Beispiele, wenige positive Beispiele


Arten der Konditionierung• Appetitive Reize

• Positive Reize• Futter, Streicheln, etc.• ...

• Aversive Reize• Negative Reize• Elektroschocks, Luftstöße• ...

• Achtung: Aversive Reize führen zu generalisierten Furchtreaktionen, d.h. sie führen auch bei neutralen (neuen) Reizen zu Reaktionen!


Ausflug: Immunsystem• Bei Versuchen an Ratten mit einer süßen

Saccharinlösung (CS) und einem Brechmittel (US), (aversive Konditionierung) sterben Ratten während der Löschungsdurchgänge, obwohl US nicht tödlich war, wie kann das sein?

• Nebenwirkung von US: Schwächung des Immunsystems

• Problem: Ratten hatten die Schwächung des Immunsystems konditioniert

• Folgerung: Die Immunsysteme von Lebewesen unterliegen auch lernbaren Vorgängen!


Lernen über Konsequenzen

• Unterschiedliches Verhalten führt zu unterschiedlichen Reaktionen

• Das Verhalten nimmt die Rolle des Reizes an

• Die Reaktion (der Umwelt etc.) nimmt die Rolle des Reflexes an

• Lernen heißt hier: bestimmte Verhaltensmuster mit bestimmten Reaktionen in Verbindung zu bringen


Thorndikes Theorie(Edward Thorndike, 1874-1949)

• Thorndikes Gesetz des Effektes• Entscheidend sind nicht CSUS, sondern

Assoziation zwischen Stimulus (S) und der Reaktion (R) der Reiz-Reaktions-Assoziation (RRA)

• Befriedigende Reaktionen werden verstärkt, erfolglose Reaktionen werden gelöscht

• Also: Lernen wird durch Konsequenzen gesteuert• Verfahren: Trial-and-Error• Beispiel: Katzen im Käfig mit Öffnungsautomatik


Operante Konditionierung• Operantes Verhalten wird nicht durch Reize

ausgelöst (Tauben picken, manche Menschen gestikulieren, sagen ständig „äh“, u.a.m.)

• Operantes Verhalten wirkt sich auf Umwelt aus• Operantes Konditionieren ändert die

Wahrscheinlichkeit der operanten Reaktionen als Funktion ihrer Konsequenzen

• Operantes Konditionieren besteht aus 3 Teilen:• Verhaltenskontingenzen• Verstärker• Diskriminierende Reize


Verhaltenskontingenzen

• Konsistente Beziehung zwischen Verhalten (X) und folgenden Reizbedingungen (Y)

• Kontingenz: Regel der Form „X Y“• Beispiel

• Pickrate der Taube erhöht sich, wenn jedes Mal ein Korn gefunden wird

• Taube lernt, dass das Picken die Reaktion hervorruft (und nicht andere Tätigkeiten)


Verstärker• Ereignisse, die die Reaktion eines Organismus

festlegen, wenn sie kontingent auftreten, heißen Verstärker

• Positiver Verstärker:• Reiz, der zum Anstieg der Auftretenswahrscheinlichkeit

durch Hinzufügen führt (Futter, Wasser, etc)• Negativer Verstärker:

• Reiz, der zum Anstieg der Auftretenswahrscheinlichkeit durch Elimination führt (Lärm, Kälte, elektrische Schocks, etc)

• Positive Verstärker funktionieren i.a. besser!


Folgerungen

• Operantes Konditionieren setzt unmittelbare Konsequenz voraus

• Kontingente Verstärkung stärkt Reaktion• Kontingente Bestrafung unterdrückt Reaktion• Aber: Kontingenz ist wesentlich!• Gegenbeispiele:

• Eltern loben gute und schlechte Dinge• Lehrer kritisieren gute und schlechte Arbeiten

• Zumindest kausaler Zusammenhang muss erkennbar sein!


KontingenzpläneReiz Reaktion Konsequenz

• Positive Verstärkung• Getränkeautomat Münze einwerfen Getränk erhalten (trinken)

• Negative Verstärkung (Flucht)• Hitze Luft zufächeln Kühlung spüren

• Negative Verstärkung (Vermeidung)• Licht brennt noch Signal Licht ausschalten Geräusch vermeiden

• Löschen• Keine Reize albernes Verhalten Umwelt ignoriert dies

• Bestrafung• Streichholz Spielen/Anzünden Verbrennen, Schimpfe erhalten


Verbesserung durch Üben

Durchgänge

Leistung


3. Spieltheorie

• Allgemeine Grundsätze • Heuristische Suche

• Greedy-Algorithmen• A* - Algorithmen

• Das Mini-Max Suchverfahren• Zusammenfassung und

Laborübungen


Allgemeine Grundsätze (I)

• Warum sind Spiele geeignet, Grundsätze der Lerntheorie anzuwenden?• Lernerfolg ist leicht messbar• Die „Welt“ ist sehr „übersichtlich“:

• Fest definierte Zahl an Handlungsoptionen• Klar strukturierte Merkmalserfassung

Spielregeln & Zugmöglichkeiten• Wissensbasis ist vergleichsweise gering


Allgemeine Grundsätze (II)

• Lernen entspricht Suchen• Handlungen spannen einen Baum auf• Blätter (direkt) oder Knoten (indirekt)

stellen erstrebenswerte oder zu vermeidende Optionen dar

• Ein Spiel entspricht einem Weg• Der gesamte Baum entspricht der „Welt“• Lernen bedeutet, Wege zu beschreiten,

die zu besseren Zielen führen Suche!


Allgemeine Grundsätze (III)

• Verbesserung kann geschehen durch• Intensivere, erweiterte, tiefere, breitere

Suche• Bessere (zutreffendere) Bewertung des

erreichbaren Knotens• Ideal: vollständige Baumsuche (nur bei

Trivialsituationen)• Kritisch: Keine Tiefensuche (zu viele

Handlungsmöglichkeiten)


Konkrete Spielsituation

• Baum entspricht „Stellungsbaum“• Verzweigungsgrad und Höhe hängen vom

Spiel ab • Beispiele

• Solitaire• TicTacToe• Dame• Schach• Go


Ansätze

• Bei hinreichend komplexen Spielen lässt sich Baum nicht mehr angeben Heuristische Suche erforderlich

• Stellung wird mittels Auswertungsfunktion linear bewertet

• Beispiele• Turing (Schach): W/S

(Werte der weißen und schwarzen Figuren)• Allgemein: f(x) = a1·m1+ a2·m2+ a3·m3+ ...

Koeffizienten werden gelernt


Problem des Koeffizientenlernens

• Welcher Zug war für das Ergebnis verantwortlich?

• Ein schlechter Zug kann sich durch eine schlechte Antwort des Gegners dennoch als gut erweisen

• Ein guter Zug kann durch (eigene) nachfolgende Fehler zu einem schlechten Zug werden

Verdienstzuweisungsproblem


Spieleklassen

• Allgemein• Generator für plausible Züge• Statistische Auswertungsfunktion

• Ein-Personen-Spiele• A*-Algorithmus• Greedy-Algorithmus

• Zwei-Personen-Spiele• MINIMAX-Suchverfahren


Der Stellungsbaum


Heuristische Suche

• Heuristik-Funktion h(n):• h(n) = geschätzte Kosten für den

billigsten Pfad vom Knoten n zu einem (erstrebenswerten) Zielknoten

• Oft: h(n) 0, h(n) = 0 n ist Zielknoten• In Lernenden Systemen ist die

Heuristik-Funktion häufig der Lerngegenstand!


Greedy-Algorithmen

• „Gierige“ Bestensuche• Wert des Knotens wird mit Heuristik-

Wert identifiziert, d.h. f(n) = h(n)• Stets der Knoten, der „am nächsten“

am Ziel liegt, wird expandiert• Suchkosten sind minimal• Suche ist nicht optimal• Diskussion anhand eines Beispiels!


Der A*- Algorithmus (I)

• Idee: Auch Kosten berücksichtigen, die (vom Anfang) zu dem aktuellen Knoten (tatsächlich) entstanden sind

• Dies ermittelt die Funktion g(n)• Der Wert des Knotens ergibt sich

dann zu: f(n) = g(n) + h(n)• A* expandiert stets Knoten mit

minimalem f(n).


Der A*- Algorithmus (II)• Implementierung erfordert die Verwaltung zweier Listen,

„offene“ OK und „behandelte“ Knoten BK• Ablauf: Startknoten s Endknoten e

(1) Füge Startknoten s zu OK(2) Ermittle Knoten k aus OK mit minimalem

f(k) = h(k)+g(k)(3) Lösche k aus OK, füge k in BK ein(4) Für k = e terminiert der Algorithmus(5) Expandiere k. Führe für jeden Nachfolger n von k aus:

(1) Ist nOK? Entferne ggf. Schleifen im Pfad.(2) Ist nBK? Entferne ggf. Schleifen im Pfad, propagiere dann

Information zu Nachfolgern von n(6) Füge n in OK ein.(7) Gehe zu (2)


Der A*- Algorithmus (III)• Betrachte A* mit f(n) = h(n) + g(n)

• Für g=0 findet A* eine beliebige Lösung• Für g=c mit c >>h findet A* kürzesten Pfad• Für g reale Kosten findet A* billigsten Pfad• Für h ist perfekter Schätzwert konvergiert A*

unmittelbar, d.h. ohne Suche• Für h=0 wird Suche von g gesteuert• Für g=0 h=0 ist A* eine zufällige Suche• Für g=1 h=0 liefert A* eine Breitensuche BFS• Falls h niemals die Kosten überschätzt, dann dann

heißt h zulässig; A* ist dann optimal


Der A*- Algorithmus (IV)

• Beispiel für eine derartige Heuristik:• Suche nach der kürzesten Straßenroute

verwendet als Heuristik die Luftlinie

• Diskussion anhand eines Beispiels!


Das Mini-Max Suchverfahren

• Zwei-Personen Nullsummenspiele mit vollständiger Information

• Spieler: MAX, MIN• MAX beginnt, dann MIN, dann MAX, ...• Ausgangszustand (Anfangsaufstellung)• Nachfolgerfunktion (mögliche Züge)• Endzustände (gewonnen, remis, verloren)• Nutzenfunktion

(Wert der jeweiligen Endposition)


Beispiele

• TicTacToe• MAX: 9 Zugmöglichkeiten am Anfang• Maximal 9 Züge insgesamt

• Schach• Durchschnittlich ca. 35 Züge• Durchschnittlich ca. 45 Züge insgesamt

• Backgammon• Ergebnisse zwischen +192 und –192 möglich


Die Mini-Max-Strategie

• Gegner wird als optimal spielend angenommen

• Wähle den Zug aus, der die Punktezahl maximiert, unter der Annahme, dass der Gegner (im Folgezug) die Punktezahl minimiert

• Wende das Verfahren rekursiv auf Folgepositionen an

• Verfahren setzt vollständige Tiefensuche voraus! Beispiel!


Alpha-Beta Pruning (I)

• Problem: vollständige Suche ist nicht immer möglich

• Lösung: Abschneiden von Zweigen, die (vermutlich) die Mini-Max-Werte nicht beeinflussen

• Wann? Wenn an einem Knoten n ein Wert entsteht, der schlechter ist als eine Alternative m weiter oben im Baum (eine Stelle mit geringerem Level), wird er vermutlich nie erreicht und daher eliminiert


Alpha-Beta Pruning (II)• Alpha:

Wert des bisherigen besten (maximalen) Knotens entlang des Pfades für MAX

• Beta: Wert des bisherig besten (minimalen) Knotens entlang des Pfades für MIN

• Alpha-Beta Suche aktualisiert Werte von Alpha und Beta und schneidet Zweige an einem Knoten ab, sobald der Wert des aktuellen Knotens schlechter als Alpha für MAX oder Beta für MIN ist.


Weitere Probleme

• Abbrechen der Suche, falls es sich „anbietet“• Ruhe in der Stellung (z.B. nach

Figurenabtausch-Kombinationen)• Horizonteffekt (entscheidendes Problem wird

nur durch mehr oder weniger sinnlose Züge hinausgezögert)

• Mustererkennung• Z.B. im Go, nur gedrehte/gespiegelte

Positionen (Go: Verzweigungsfaktor initial 361)


Horizonteffekt

Schwarzam Zug


Zusammenfassung und Laborübungen

• Lernen als Baumsuche• Optimierungs- und

Beschneidungsverfahren• Spezialprobleme und –lösungen• Historie und Stand der modernen

Spielprogramme• Laborübung: Sukzessive Erweiterung

des TicTacToe-Programmes!

Master of Science in Electrical EngineeringWintersemester 2005/2006

Prof. Dr. E.-G. Haffner

Lernende SystemeEnde Teil 1

Documents

Master of Science in Electrical Engineering Wintersemester 2005/2006 Prof. Dr. E.-G. Haffner Lernende Systeme Teil 1