Wargames

März 28, 2019

Wargames und MCTS self-play

Spoilerwarnung: Wargames Spoilers, sollte tatsächlich jemand den Film noch nicht gesehen haben.

Auf Twitter kam die Frage auf:

Wenn Computer selbständig eine Analogie zwischen Tic-Tac-Toe und weltweitem Atomkrieg herstellen könnten -- welche Stufe der Künstlichen Intelligenz wäre das?

Spannenderweise gibt es tatsächlich ein populäres und sehr erfolgreiches Konzept das genau so funktioniert wie sich der Computer in Wargames (WOPR) verhält, nämlich, nämlich Monte-Carlo Tree Search. Das zu erklären braucht etwas mehr Platz als Twitter bietet, daher versuche ich es mal mit möglichst wenig Mathematik hier auszuführen.

Die Spiele in Wargames

Es lohnt sich erst einmal anzusehen, was WOPR (der Computer in Wargames) an Gesellschaftspielen kennt:

  • Tic-Tac-Toe
  • Black Jack
  • Gin Rummy
  • Hearts
  • Bridge
  • Checkers
  • Chess
  • Poker

Das ist gegenüber

  • Fighter Combat
  • Guerilla Engagement
  • Desert Warfare
  • Air-to-Ground Actions
  • Theaterwide tactical Warfare
  • Theaterwide biotoxic and chemical Warfare

und schließlich "Global thermonuclear war" natürlich eher langweilig, aber offensichtlich sind die Spiele dazu gedacht WOPR beizubringen strategisch zu denken. Mit Schach ist ein klassisches Strategiespiel enthalten, aber mit Spielen wie Blackjack werden auch Zufallselemente berücksichtigt.

Der Hinweis auf das Verfahren den ich hier sehe ist am Ende des Films, wenn WOPR in der Lage ist mit sich selber zu spielen und daraus zu lernen. Dieses "self-play" hat für viele Spielen das klassische "supervised learning" (Lernen aus Beispieldaten mit Musterlösung) abgelöst.

Monte-Carlo Tree Search für Computerspiele

Zunächst eine Erklärung wie das Verfahren funktioniert mit dem WOPR die Gesellschaftsspiele, wie zum Beispiel eine nette Runde Schach mit Prof. Falken, üben kann.

Computer & Go

Das Spiel "Go" galt lange als eins der wenigen Spiele, bei denen Computer Menschen die ein wenig Übung haben, also schon fortgeschrittene Amateure und nicht nur Weltmeister, nicht besiegen können. Das größte Problem dabei ist, dass es nicht einfach ist einem Zug anzusehen was er später auslösen kann. Der "Wert" einer Aufstellung ist schwer einzuschätzen und damit kann ein Algorithmus, der den nächsten Zug bestimmen soll, der die Aufstellung verbessert, leicht in die Irre geführt werden.

Das lässt sich an Schach einfach erklären: Angenommen wir bewerten einen Zug danach, welche Figuren nach dem eigenen Zug und dem nächsten Zug des Gegners noch auf dem Spielbrett stehen, dann ist es nur logisch mit dem Bauern einen Turm zu schlagen, selbst wenn der Bauer danach selber geschlagen wird, denn ein Turm ist viel mehr wert als ein Bauer. Das Ganze wäre auch ein guter Zug, wenn nicht danach der König schachmatt gesetzt wäre, weil der Bauer nicht mehr im Weg steht.

Beim Schach hat man für solche Probleme gute Heuristiken, das heißt Möglichkeiten einem Brett anzusehen ob ein Zug "Schachmatt in 10 Zügen" bedeuten kann. Außerdem wird sich meistens nach wenigen Zügen schon abzeichnen, dass der Zug gerade ein großer Fehler war.

Go hingegen hat nicht nur eine viel größere Auswahl an möglichen Zügen (In jedem Zug darf ein Stein auf eine von 19x19=361 Stellen gelegt werden), sondern es ist auch nicht ungewöhnlich dass ein Zug erst viele Züge später Auswirkungen hat. Für ein einfaches Computerprogramm, das in jedem Zug versucht abzuschätzen was die Spielstellung nach dem Zug wert ist, scheint es also so als ob der Zug keine Verbesserung herbeiführt, wenn der Wert der Spielstellung über viele Züge gleich bleibt.

Die Lage hat sich drastisch geändert mit der Verwendung von Monte-Carlo-Algorithmen, wie sie auch in AlphaGo und AlphaGo Zero zum Einsatz kommen. Die verwendeten Algorithmen sind dabei eine Form des reinforcement learnings, das heißt der Algorithmus lernt allein aus positivem und negativem Feedback, welche Aktion in einer Situation eine möglichst gute neue Situation schafft.

Monte-Carlo Algorithmen

Monte-Carlo klingt nach Glückspiel und genau daher kommt der Name auch. Monte-Carlo Algorithmen sind Algorithmen, bei denen eine exakte Lösung sehr teuer ist (zum Beispiel viel Rechenzeit oder Arbeitsspeicher braucht), die einen Zufallsfaktor verwenden um eine näherungsweise Lösung des Problems die für die Aufgabenstellung exakt genug ist zu finden.

Zum Beispiel ist eine Methode mit Monte-Carlo Pi zu bestimmen, dass man in einem Quadrat mit Seitenlänge 2 zufällige Punkte einzeichnet. Dann zählt man wieviele Punkte innerhalb eines Kreises mit Radius 1 um den Mittelpunkt enthalten sind und kann damit eine Approximation von Pi bestimmen.

Entscheidungsbäume

Komplexe Abläufe lassen sich oft als "Baum" darstellen, das heißt von einer Frage ("Knoten" im Baum) aus gibt es Verzweigung die unterschiedlichen Antworten entsprechen und ggf. zu Knoten mit weiteren Fragen führen. Ein einfacher Entscheidungsbaum sieht zum Beispiel so aus:

  • Restaurant oder Kneipe?
    • Restaurant!
      Bist du Vegetarier?
      • Nein.
        Dann gehen wir ein gutes Steak essen!
      • Ja.
        Ich kenne da ein super Restaurant, das sogar viele vegane Gerichte anbietet!
    • Kneipe.
      Bist du mit dem Auto hier?
      • Ja.
        Dann trinken wir halt nur ein Radler.
      • Nein.
        Dann können wir ja tüchtig trinken!

Die "Wurzel" (oben) ist hier die Frage wohin man geht und die "Blätter" (Die Knoten an denen es sich nicht weiter verzweigt) enthalten das Ergebnis, was tatsächlich gegessen bzw. getrunken wird.

Ein Spiel wie Schach oder Go lässt sich genauso modellieren. In jedem Zug wird eine Entscheidung getroffen, zum Beispiel bei Schach welche Figur bewegt wird und wohin oder bei Go wohin ein Stein gesetzt wird.

Ein Spiel ist damit ein Pfad von der Wurzel (Spielstart) zu einem Blatt im Entscheidungsbaum (Spielende).
Das offensichtliche Ergebnis ist gewonnen vs. verloren, es lässt sich aber je nach Spiel auch feiner abstufen, indem man zum Beispiel jeder Figur einen Wert zuweist und damit hoch oder nicht so hoch verloren wird (zum Beispiel bei Backgammon).

Eine andere Art die Höhe des Gewinns bzw. Verlusts zu messen ist zum Beispiel über die Spielzeit. Wer nach drei Zügen verloren hat, hat davor schlechter gespielt als jemand der erst nach 150 schachmatt gesetzt wurde.

Suchbäume für Spiele

Wenn ein Spiel also eine Reihe von Entscheidungen ist, in welche Richtung bei einer Verzweigung abgebogen wird, kann man dadurch dass man jeweils alle Möglichkeiten ausprobiert den gesamten Suchbaum über alle Spiele, die möglich sind, berechnen. Von der Wurzel aus ist jedes Blatt erreichbar, aber mit jeder Entscheidung werden die Blätter, die noch erreicht werden können, weniger.

Kennt man den gesamten Baum, kann man seine Entscheidung danach ausrichten. Eine Möglichkeit wäre zum Beispiel immer die Verzweigung zu nehmen, von der aus man die meisten gewonnenen Spiele erreicht.. Ein Problem entsteht bei dieser Strategie allerdings, wenn der Zug des Gegners das Verhältnis der übrigen Spiele deutlich verändern kann, sodass eine Bewertung über das Verhältnis der Spiele nicht mehr sinnvoll ist.

Nehmen wir ein Spiel an bei dem die Spieler "A" und "B" abwechseln entscheiden von einer Zeichenkette entweder die linke oder rechte Hälfte zu behalten und Spieler A gewinnt, wenn "A" übrig bleibt und Spieler "B", wenn B übrig bleibt.

AAAAABABAAABAABB

Mit der "gierigen" Strategie immer die Hälfte zu nehmen, in der man am häufigsten gewinnt, wird Spieler "A" verlieren obwohl es für ihn eine Strategie gibt mit der er immer gewinnt.

Das Spiel verläuft dann so:

AAAAABAB|AAABAABB <-- A wählt links, weil dort mehr A sind
AAAA|ABAB <-- B wählt rechts
AB|AB <-- A wählt eine der beiden Seiten
A|B <-- B gewinnt

Minimax-Bäume

Wie kann A jetzt seine Entscheidungen fällen damit er immer gewinnt, wenn es möglich ist? A muss dazu die Reaktion seines Gegners einplanen, welche versucht den Gewinn zu verhindern.

Eine optimale Strategie dafür ist der Minimax-Algorithmus, in dem abwechselnd der Gewinn von A maximiert (Im Interesse von A) und minimiert (Im Interesse von B) wird. Das heißt in jedem zweiten Zug schaut sich Spieler A an, was das Schlimmste ist, was sein Gegner in diesem Fall tun könnte, und richtet seinen Zug dann danach aus dass der Schaden durch den nächsten Zug möglichst gering bleibt.

Damit verläuft das Spiel etwas anders:

AAAAABAB|AAABAABB <-- A schaut sich links an
AAAA|ABAB <-- A denkt wie sein Gegner und schaut sich rechts an 
AB|AB <-- A wählt eine der beiden Seiten
A|B <-- B würde gewinnen
AAAAABBB|AAABAABB <-- A schaut sich rechts an
AAAB|AABB <-- A denkt wie sein Gegner und nimmt rechts
AA|BB <-- A optimiert seinen Gewinn und nimmt links
A|A <-- Egal was B wählt, er hat verloren

Alpha-Beta Suche

Die Minimax-Suche ist ein schönes Verfahren und theoretisch in der Lage Spiele wie Schach oder auch Go komplett zu lösen. Das Problem ist, dass die Lösung zu viele Ressourcen benötigt um praktikabel zu sein. Der Suchbaum für ein Schachspiel würde einfach so groß werden, sodass es mit heutigen Computern (und denen die wir in absehbarer Zukunft haben werden) nicht machbar ist.

Eine Optimierung, die hilft den Suchbaum kleiner zu halten, ist die Alpha-Beta-Suche, welche Züge die keinen Gewinn erzielen vorher auszusortiert. Dabei werden zwei Werte Alpha und Beta im Baum weitergegeben, welche den minimalen und maximalen Wert der über diesen Zug erreichbaren Spielausgänge enthalten.

Bei Spielen mit unterschiedlich hohem Gewinn und Verlust kann das zum Beispiel heißen, dass der höchste zu erwartende Gewinn bei einem Zug unter dem kleinsten zu erwartenden Gewinn bei einem anderem Zug liegt. Dann lohnt es sich nicht weiter zu prüfen, was der exakte Gewinn (bzw. Verlust) sein wird, da bereits ausgeschlossen werden kann, dass der Zug für ein gutes Spiel Sinn ergibt.

Zur Bestimmung der Alpha- und Beta-Faktoren werden häufig Heuristiken benutzt. So werden die meisten Schachspieler wissen dass, bestimmte Züge ein absolutes "No-Go" sind, und auch ein Laie hat eine gewisse Ahnung, dass es kein gutes Zeichen ist wenn die Dame geschlagen wird.
Solches Expertenwissen kann man einfließen lassen um zu vermeiden, dass alle Spiele in denen die Dame zu Anfang schon geschlagen wurde analysiert werden müssen, indem man Züge, welche die Dame schon früh im Spiel opfern, als sehr ungünstig klassifiziert.

Monte-Carlo Tree Search

Auch die Alpha-Beta Suche ist für viele Spiele zu aufwendig, da die Anzahl der Verzweigungen, die besucht werden müssen, immernoch sehr groß sein kann. Ein weiteres Problem sind Spiele wie Go, bei denen keine so guten Heuristiken wie bei Schach zur Verfügung stehen.
Ein zu Begin plazierter Stein kann ein großer Fehler sein, aber das erkennt ein Laie nicht und es gibt auch wenige Heuristiken, die ein Computerprogramm benutzen könnte.

Aber was wäre, wenn wir die genaue Heuristik gar nicht brauchen, sondern einfach nur viele Spiele ausprobieren? An dieser Stelle bringt Monte-Carlo Tree Search (MCTS) den Zufallsfaktor des Monte-Carlo Verfahrens ins Spiel.
Wenn man mit einer Strategie verliert, lohnt es sich eine andere auszuprobieren. Möglicherweise ist diese schlechter, vielleicht aber auch besser. Je mehr Strategien man ausprobiert, desto eher findet man heraus welche die Optimale ist.

Während Minimax systematische alle Strategien, die es gibt, durchprobiert und Alpha-Beta-Suche zumindest die ganz dummen Ideen aussortiert, versucht MCTS etwas zufälliges und benutzt die Strategie, wenn sie gut ist weiter und verwendet sie ansonsten immer seltener.

Wie MCTS lernt

Monte-Carlo Tree Search braucht um ein Spiel zu lernen nur zwei Informationen:
  • Eine Funktion, die für das aktuelle Spielfeld alle gültigen Züge für den Spieler der am Zug ist erzeugt.
  • Eine Funktion, die sagt ob ein Spiel beendet ist und welcher Spieler gewonnen hat und ggf. mit welcher Punktezahl.

Im MCTS-Suchbaum bekommt jede Verzweigung zwei Werte zugewiesen:

  • Die Anzahl der Spiele, die diesen Zug bisher enthalten haben.
  • Die gesamte Punktezahl am Ende der Spiele, die diesen Zug enthalten (+/-1 wenn es nur um Sieg oder Niederlage geht)

Das Lernen fängt an mit einem einzigen Spielzustand (Knoten) "Spielstart". Das erste Spiel verläuft zufällig, das heißt in jedem Spielzeug wird die Entscheidung völlig zufällig getroffen. Am Ende des Spiels enthält der Suchbaum einen Knoten unter "Spielstart" und die Besuchszähler beider Knoten stehen auf "1" und die Ergebniszähler enthalten das Ergebnis des ersten Spiels.

In jedem weiterem Lernspiel wird jetzt ein neuer Zug ausprobiert, entweder am Ende einer Reihe bekannter Züge, oder es wird irgendwo in der Mitte ein anderer Zug als vorher ausprobiert.

Dazu folgt der Algorithmus vom Spielstart aus den bisherigen Zügen, wobei er bei jeder Entscheidung welcher Zug ausgeführt wird einen UCT-Faktor (Upper confidence-bound applied to trees) ausrechnet um zu entscheiden, ob Spiele die diesen Zug enthalten interessant sind oder besser ein neuer Zug probiert werden sollte.

Ohne Mathematik erklärt trifft der UCT-Faktor eine Abwägung zwischen "Der Zug hat oft zu Spielen mit Sieg geführt" und zwischen "Ich kenne noch nicht viele Spiele mit diesem Zug und möchte noch mehr ausprobieren um mir sicher zu sein ob die Gewinnwahrscheinlichkeit korrekt ist".
Dieser Faktor berechnet sich aus den zwei gespeicherten Zählern, wobei der Wert wie oft ein Zug verwendet wurde den Zug als "langweilig" markiert und der Zähler wieviele Spiele gewonnen wurden den Zug als "interessant" markiert.

Das führt dazu, dass ein Zug der zu einem guten Ergebnis geführt hat eine Weile bevorzugt in Trainingsspielen verwendet wird. Bleibt die Wahrscheinlichkeit mit diesem Zug zu einem Gewinn zu kommen aber gleich während der Spielzähler immer weiter erhöht wird, sinkt der UCT-Faktor wieder und es werden wieder neue Züge ausprobiert.

Wie MCTS spielt

Nachdem MCTS durch self-play der durch UCT ausgewählten Züge einen Spielbaum aufgebaut hat, kann der Baum zum Spielen verwendet werden. Wenn die KI am Zug ist, dann hat sie für das aktuelle Spielbrett Daten zu möglichen Zügen gesammelt und verwendet diese um den besten Zug auszuwählen.

Mögliche Auswahlkriterien dabei sind zum Beispiel:

  • Der Zug der am häufigsten ausprobiert wurde, denn über Spiele die den Zug enthalten ist viel bekannt.
  • Der Zug der in dem Spiel mit dem höchsten Gewinn enthalten ist, in der Hoffnung genau dieses Spiel zu spielen.
  • Der aktuelle UCT-Faktor.
  • Der Zug mit dem größten durchschnittlichen Gewinn.
  • Der Zug mit den meisten Spielen die gewonnen wurden.

In dem Moment, in dem die KI ihren Zug ausführt, fallen alle Simulationen die diesen Zug nicht enthalten weg und können (für dieses Spiel) gelöscht werden. Nachdem der Nutzer seinen Zug ausgeführt hat fallen auch hier alle Spiele, die diesen Zug nicht enthalten, weg.

Irgendwo, Irgendwie, Irgendwann

MCTS ist ein Anytime-Algorithmus. Das heißt der Algorithmus kann sowohl dauerhaft laufen als auch jederzeit gestoppt werden um dann ein Ergebnis zu produzieren. Der Schachcomputer kann zum Beispiel während der Nutzer nachdenkt weiter neue Spiele ausprobieren und damit den Suchbaum erweitern. In dem Moment, in dem Nutzer spielt, kann der Algorithmus anhalten und aus seinem aktuellem Suchbaum das beste Ergebnis nutzen um sofort selber zu spielen.

Umgekehrt ist es aber auch so, dass man für ein besseres Spiel dem Computer Bedenkzeit geben kann und dieser die Zeit nutzen kann um den nächsten Zug besser zu planen. Eine theoretische Obergrenze dabei ist, dass MCTS irgendwann den gesamten Suchbaum aufgebaut haben könnte und damit ab dann dem Minimax-Verfahren entspricht.

In dem Fall braucht die KI keine Bedenkzeit mehr und die Optimalität jedes Zuges bis zum Ende des Spiels ist garantiert. In der Praxis kommt es bei den meisten Spielen aber nicht vor, dass MCTS tatsächlich während des Spiels den gesamten Baum aufbaut.

Shall we play a Game?

Zurück zur Ausgangsfrage: Wie spielt WOPR wohl seine Spiele?

Die Idee, dass WOPR ein System wie MCTS nutzt, liegt nahe wenn man sich die zwei Spiele, die der Computer im Film lernt, ansieht.

Die Schlusszene in der ein Tic-Tac-Toe Spiel WOPR klarmacht, dass man nicht jedes Spiel gewinnen kann, zeigt ein rasantes self-play aller möglichen Tic-Tac-Toe Spiele. Wer es einmal selber einmal ausprobiert hat wird wissen, dass wenn der Gegner keinen dummen Fehler macht, das Spiel immer unentschieden endet.

Nach diesem rasanten durchprobieren aller möglichen Spiele hat WOPR also gelernt, dass es bei Tic-Tac-Toe keine Möglichkeit gibt zu gewinnen, wenn beide Seiten keine dummen Fehler machen.

Mit 9 Spielfeldern, die abwechselnd markiert werden dürfen, kann auch ein realer Computer sämtliche Spiele durchprobieren.
Es sind nur 9x8x7x6x5x4x3x2x1 = 362880 mögliche Spiele, wenn man ignoriert dass einige Spiele enden bevor alle Felder ausgefüllt sind und einige Spiele wegfallen können wenn man Symmetrien und Spiegelungen ausnutzt.

The only winning move is not to play

Auch das Fazit "The only winning move is not to play" lässt sich in Tic-Tac-Toe einfach abbilden. Dazu erweiteren wir die Regeln:
  • Ein Feld markieren hat Kosten, z.B. 1/100 der Punkte die man gewinnen kann.
  • Das Spiel zu beenden ist ein gültiger Zug.

Sofort wird der Algorithmus lernen, dass es billiger ist im ersten Zug das Spiel zu beenden, als auch nur ein einziges Feld zu markieren. Alle Spiele in denen der Computer das Spiel nicht im ersten Zug beendet enden weiterhin unentschieden, kosten aber etwas, während das Spiel zu beenden keine Kosten hat.

MCTS und der thermonukleare Krieg

Als dem Computer in Wargames durch Tic-Tac-Toe klar wird, dass er nicht gewinnen kann, ist seine Erkenntniss, dass für den thermonuklearen Krieg das Gleiche gilt. Wieso weiß WOPR das nicht eigentlich nicht schon vorher?

Auch das spricht wieder für einen Algorithmus der MCTS ähnlich ist, und offensichtlich für die Anwendung völlig fehl am Platze ist. Das wird deutlich in einem Zitat aus einer Vorlesung am MIT (Protokoll unter Creative Commons Lizenz):

PROFESSOR 3: [...] The idea of "War Games" is that one of the core characters in this world is this computer that has been put in charge of the national defense strategy with respect to Russia. And that it needs to think through the possible future scenarios and decide whether it's going to launch the nukes or not. Do you think that WOPR can be MCTS-based?
AUDIENCE: No.
PROFESSOR 3: No?
AUDIENCE: It could, it just wouldn't be very good.
PROFESSOR 3: Absolutely. Once you fire the nukes you're not going to get another chance. So you can't particularly simulate through what the possible scenarios are going to be like. Yeah.

Das Problem von WOPR ist, dass er denkt er könnte über self-play herausfinden ob ein Atomkrieg zu gewinnen ist, indem er die realen Streitkräfte dazu benutzt herauszufinden was passiert, wenn eine Rakete losgeschickt wird.
Die modifizierten Regeln des Tic-Tac-Toe Spiels bringen dabei für das Kriegsspiel wenig, da sie erst zur Erkenntnis führen, wenn tausende von Spielen ausprobiert wurden.

Da aber der erste Versuch schon zur Katastrophe führen würde, musste WOPR also ohne dass er es testen kann, klargemacht werden, dass es keine Möglichkeit gibt zu gewinnen.

Selbständig eine Analogie zwischen Tic-Tac-Toe und weltweitem Atomkrieg herstellen

Die Liste von Spielen die WOPR kennt umfasst nicht nur Tic-Tac-Toe und thermonuklearen Krieg, also kann man davon ausgehen dass sein Erbauer vorgesehen hatte, dass WOPR mehrere Spiele spielen lernt um die Erfahrungen bei einem auf ein anderes anzuwenden. Wer eine gute Strategie für Schach hat, kann vielleicht auch Dame lernen. Und Black Jack und Poker enthalten beide Strategie- und Glückselemente.

Die Kriegsspiele sind offensichtlich das eigentliche Ziel gewesen, aber nie vorher zur Anwendung gekommen, vermutlich weil WOPR bisher weder genug Schach noch genug Tic-Tac-Toe gespielt hat um mit seiner Macht vernünftig umzugehen.

Aber ist eine Spielaufstellung bei Schach und Dame vergleichbar? Und wie sieht es beim thermonuklearen Krieg aus?
Hier scheint mir, gibt es tatsächlich ein interessantes Thema, wenn es darum geht ob die gelernten Regeln generalisieren können. Eine einfach Verwendung der Paares "(aktuelles Schachbrett --> bester Zug)" ist auf eine Situation bei Dame sicher nicht möglich. Möglicherweise wäre es beim Räuberschach denkbar, zumindest passen dort die Spielfelder und möglichen Züge noch zusammen.

Hilft Wissen aus einem Spiel bei einem anderem?

Es ist eine spannende Frage zwischen welchen Spielen man Funktionen finden könnte, die zuerst das Spielbrett von Spiel A in ein Spielbrett von Spiel B umwandeln um dann den optimalen Zug in Spiel B zurück verwandeln um ihn in Spiel A auszuführen. Es ist allerdings fraglich inwieweit der Zug dann auch in Spiel A optimal sein wird.

Aber wenn man sich komplexere Systeme ansieht, wie AlphaGo Zero, welches MCTS zusammen mit Deeplearning verwendet, könnten diese Optimierungen möglicherweise zwischen Systemen übernommen werden, wenn sie von den Daten wie den Spielfiguren beim Schach etwas abstrahiert werden können.

Die einfache UCT-Formel hat eine einfache Tuningmöglichkeit, welche die Verteilung zwischen Exploitation (Immer die bisher besten Züge benutzen) und Exploration (Immer bisher unbekannte Züge ausprobieren) steuert. Wenn zu viel Exploitation verwendet wird, ist die KI "gierig" und ein Mensch kann schnell herausfinden wie man sie in eine Falle locken kann. Zu viel Exploration heißt hingegen, dass sie zwar unvorhersehbar spielt, dabei aber nicht besonders gut ist.

Während der Faktor normalerweise fest ist und vom Entwickler zum Spiel passend gewählt wurde, kann AlphaGo Zero ihn abhängig vom Spielstand neu bestimmen. Damit kann AlphaGo Zero zum Beispiel lernen in einer Situation in der es den Gegner in 3 Zügen schachmatt setzen kann nicht zu viele Alternativen zu untersuchen, während es in unsicheren Situationen sich mehr neue Züge ansieht, weil es sich nicht sicher sein kann wie der Gegner spielen wird.

Beim Trainieren von Netzwerken, die entscheiden welches Risiko ein Spieler eingehen soll abhängig davon wie sicher die aktuelle Spielposition ist, könnte möglicherweise verallgemeinert werden zwischen unterschiedlichen Spielen.

Alles in allem ist allerdings vermutlich ein sehr hoher Abstraktionsgrad nötig damit eine KI tatsächlich ohne eine einzige Simulation herausfinden kann, dass es keine gute Idee ist überhaupt zu spielen. Insofern ist vermutlich die beste Lösung: Implementiert eure Simulationen für thermonuklare Kriege im PC und nicht in der realen Welt!

Kategorien Technik
Tagged MCTS AlphaGo AlphaGo Zero Deeplearning machine learning KI AI Wargames WOPR Schach Go Monte-Carlo Atomkrieg
Mobil qrcode zeigen

0 Kommentare

April 16, 2008

A strange game ...

A strange game ... The only winning move is not to think about it.
Mist, verloren ... Kam mir gerade so in den Sinn, wobei das Original ja auch zutreffend ist:
a strange game ... the only winning move is not to play
Naja, Regel 1 steht dagegen ;).

Kategorien Allgemeines Kurz bemerkt Fun
Tagged Game Spiel Zitat verloren Wargames
Mobil qrcode zeigen

2 Kommentare