Mathematik | Informatik

 

Brian Barth, 2002 | Oberflachs, AG

 

Beim maschinellen Lernen handelt es sich um die automatische Verbesserung von Algorithmen mithilfe von Daten. Diese werden verwendet, um ein neuronales Netzwerk durch den Backpropagation Algorithmus auf eine arbiträre Funktion zu trainieren. Es wird aber eine grosse Menge an gelabelten Daten benötigt. In diesem Projekt wurden diese selbst generiert. Die Alternative wäre eine Datenbank mit menschlichen Spielen, die es nicht gibt. Zudem stellt sich die Frage, ob die KI aus eigenen Fehlern nicht besser lernt. Es wird gezeigt, wie sich eine KI zusammen mit Monte Carlo Tree Search und einem neuronalen Netzwerk über mehrere Generationen im Dame-Spiel verbessern kann. In jeder Generation werden Lerndaten generiert, indem die KI gegen sich selbst spielt und anschliessend mit Backpropagation das Netzwerk verbessert. So spielt jede Generation besser als die vorherige. Mit Kombinatorik findet man heraus, dass es im Dame-Spiel ungefähr 5 × 10^20 mögliche Positionen gibt. Anstatt diese in einer Lookup-Tabelle zu speichern, bietet das Netzwerk mit einer Generalisierung eine Abkürzung, indem es ähnliche Positionen erkennt und dementsprechend bewertet. Kombiniert mit MCTS, gewinnt die KI über 90 Prozent aller Spiele gegen andere maschinelle Gegner. Sie kann als Tool verwendet werden, um Partien zu analysieren und mögliche gute Züge zu finden.

Fragestellung

Diese Arbeit behandelt das Design eines Algorithmus, um ohne menschliches Vorwissen Dame zu spielen. (I) Wie werden neuronale Netzwerke verwendet, um bei Dame gute Züge zu finden? (II) Welches Wissen erlernt die KI nur mit Kenntnissen der Spielregeln?

Methodik

Das gesamte Projekt wurde von Grund auf mit Visual Studio in C++ geschrieben. Um gute Züge zu finden, wird der Monte Carlo Tree Search Algorithmus verwendet. Anstelle des sehr rechenaufwändigen Simulationsschrittes bei MCTS wird eine viel schnellere Evaluierung durch ein neuronales Netzwerk gebraucht. Dieses wird durch selbst generierte Daten über mehrere Generationen mit Backpropagation verbessert.

Ergebnisse

Nach ca. 26 Stunden Lernen erreichte die KI eine Spielstärke, die es ihr ermöglichte, neun verschiedene menschliche Gegner auf allen Schwierigkeitsstufen zu besiegen und in über 90 Prozent der Spiele gegen eine andere KI ebenfalls zu gewinnen. Das Netzwerk allein schafft es in über 50 Prozent der Fälle, denselben Zug wie MCTS zu finden. Zudem hat sie sowohl die Wichtigkeit des Materialunterschieds als auch andere Vorteile erlernt.

Diskussion

Die Verwendung eines Convolutional Neural Networks wäre wohl besser gewesen, um verschiedene taktische Motive im Spiel besser zu erkennen. Des Weiteren wäre ein spezifischer Endspiel-Trainingsprozess von Vorteil gewesen, um dem Netzwerk die Ideen dieses Teils des Spiels besser beizubringen. Erst mit dem verbesserten Benchmarking wäre es möglich, die Hyperparameter besser zu wählen, was allerdings ein sehr zeitaufwendiger Prozess wäre. Auch gibt es noch einige Ideen zur Verbesserung der Lerndatengenerierung und des Lernprozesses.

Schlussfolgerungen

In dieser Arbeit wurde ein Algorithmus entwickelt, der ohne die Anwendung menschlichen Vorwissens über mehrere Generationen ein neuronales Netzwerk darin trainiert, zusammen mit einer modifizierten Version von Monte Carlo Tree Search Dame zu spielen. Es ist dazu in der Lage, sämtliche menschliche Gegner zu besiegen und gewinnt in über 90 Prozent aller Spiele gegen die KI von Hsankesara. Das trainierte, neuronale Netzwerk ist in der Lage, taktische sowie strategische Vorteile zu erkennen. Das Programm kann angewendet werden, um Fehler in eigenen Partien zu finden und bessere Züge zu finden, die die KI einem vorschlägt.

 

 

Würdigung durch den Experten

Alpha Renner

Maschinen Spiele zu lehren war seit ihren Anfängen eine der grossen Herausforderungen der künstlichen Intelligenzforschung (KI), da sie als Meilensteine dienen, um Fortschritt anzuregen und zu zeigen. In den letzten Jahren wurden Algorithmen entwickelt, die fast alle Spiele besser als Menschen spielen. In der Arbeit von Herrn Barth werden einige dieser Methoden auf Dame angewandt. Bemerkenswert ist, dass sein Algorithmus von den eigenen Spielen lernen kann, ohne jemals menschlichen Input zu benötigen. Dies von Grund auf zu entwickeln braucht besonderes Verständnis, Ausdauer und Begeisterung für KI.

Prädikat:

sehr gut

 

 

 

Kantonsschule Wettingen
Lehrer: Peter Skrotzky