Mensch gegen Maschine, eine Geschichte. Teil 1 - Die einzige Möglichkeit zu gewinnen?

Seit den Anfängen des Computerzeitalters vergleichen die Menschen die Fähigkeiten der "elektronischen Gehirne" mit ihren eigenen.

Eine der Möglichkeiten, sich dieser Frage zu nähern, besteht darin, eine Abstraktion eines Spiels zu verwenden, und zwar eines Spiels mit bestimmten Regeln und Siegbedingungen, und zu sehen, ob ein Computerspieler in der Lage ist, gegen einen menschlichen Spieler zu gewinnen. Mit anderen Worten: Kann ein Computer einen menschlichen Gegner überlisten?

Spiele wie Schach ermöglichen es uns, KI zu testen und zu trainieren, so dass sie eines Tages nicht nur Probleme schneller lösen kann als wir, sondern auch die Fragen, die wir noch gar nicht beantwortet haben.

Allerdings war es eine schrittweise Entwicklung, bei der immer fortschrittlichere KIs für immer kompliziertere Szenarien und Spiele entwickelt wurden. In diesem Artikel werden wir den Weg des Wettbewerbs zwischen uns und den Computern verfolgen, der sich auf den Bereich der Spiele unterschiedlicher Komplexität und Eigenschaften bezieht. In diesem ersten Teil werden wir uns einige der ältesten Herausforderungen wie Backgammon, Schach oder Go ansehen, die seit Jahrhunderten gespielt werden, sowie jüngere Erfindungen wie Scrabble oder sogar eine moderne Fernsehshow wie Jeopardy!

1950er Jahre - Spiele und KI zusammenbringen

Die künstliche Intelligenz als ein für dieses Unterfangen entscheidender Wissenschaftszweig begann in den fünfziger Jahren und etwa zur gleichen Zeit wurden die ersten einfachen Programme geschrieben, um Noughts and Crosses, Draughts und Chess zu spielen. Die Auswirkungen dieses Wettlaufs zwischen Mensch und Maschine gehen jedoch weit über die Spiele- und Unterhaltungsindustrie hinaus.

Aber jede gute Geschichte muss irgendwo beginnen, und unsere Spur beginnt im Jahr 1950.

Noughts and Crosses - Baby-Schritte

Noughts and Crosses, auch bekannt als Tic Tac Toe, ist ein einfaches, klassisches Stift- und Papierspiel, bei dem ein Spieler gewinnt, indem er 3 Markierungen in einer horizontalen, vertikalen oder diagonalen Reihe auf einer 3 x 3 Matrix anlegt. Aufgrund der begrenzten Anzahl von Zügen ist es sehr einfach zu entdecken, dass ein perfektes Spiel auf beiden Seiten immer zu einem Unentschieden führt.

Er war auch der erste, der die Form eines Videospiels annahm. Im Jahr 1950 wurde ein Computer namens Bertie the Brain auf der Canadian National Exhibition ausgestellt. Er gewann zwar nicht die ganze Zeit, aber er war leistungsfähig.

Das änderte sich zwei Jahre später, als ein Programm namens OXO für den EDSAC (Electronic Delay Storage Automatic Calculator) entwickelt wurde. Es war in der Lage, alle 26.830 möglichen Spielsequenzen perfekt zu spielen (ohne Brettdrehungen und Spiegelungen). Das Programm war ein klassisches Beispiel für einen Minimax-Algorithmus, der einen Baum von möglichen Zügen auswertet. Der Problemraum ist klein genug, selbst für einen siebzig Jahre alten Computer, der Ziffern von 1 bis 9, die von einem Telefon-Drehschalter ausgewählt wurden, als Eingabe akzeptierte und die Ergebnisse auf einem 35 x 16 Pixel großen CRT-Display anzeigte.

Übrigens wurde das Spiel Noughts and Crosses 1983 in dem Film WarGames gezeigt, in dem es als Analogie zu einem globalen thermonuklearen Krieg diente, um einer künstlichen Intelligenz beizubringen, dass manche Spiele nicht gewonnen werden können.

Backgammon - Der erste Triumph

Backgammon ist eines der ältesten bekannten Brettspiele, das bereits vor fünf Jahrtausenden im alten Mesopotamien gespielt wurde. Beim Backgammon würfeln Sie und bewegen 15 Figuren über ein Brett mit 24 Dreiecken. Derjenige, der seine Spielsteine zuerst vom Brett nimmt, gewinnt.

Dieses Spiel ist für unsere Geschichte von entscheidender Bedeutung, da es der erste Fall in der Geschichte der Menschheit war, in dem ein menschlicher Champion von einem Computerprogramm in einer anerkannten intellektuellen Tätigkeit geschlagen wurde. Im Jahr 1979 trat das Programm BKG 9.8 gegen Luigi Villas an und gewann 7 Spiele zu 1. Das Programm basierte auf Heuristiken zur Lösung einer Reihe von linearen Gleichungen sowie auf der ursprünglichen SNAC-Methode (Smooth Nonlinear functions and Application Coefficients).

Draughts - Eine gelöste Strategie

Draughts, auch bekannt als Dame, wird oft als der jüngere Bruder von Schach bezeichnet und wird auf demselben 8 x 8 Brett gespielt, allerdings mit 12 identischen Figuren pro Seite (es gibt allerdings auch andere Varianten). Ziel des Spiels ist es, alle gegnerischen Figuren zu schlagen, indem man sie in diagonalen Bewegungen auf dem Brett überspringt.

Das erste Programm zum Spielen von Draughts wurde von Arthur Samuel geschrieben und lief 1951 auf dem Ferranti Mark 1 Computer. Damit war es einer der ersten Versuche, einen menschlichen Spieler mit einem maschinellen Gegner in unserer Geschichte herauszufordern. In den frühen Sechzigern war es in der Lage, respektable Amateurspieler zu besiegen.

Wir mussten jedoch bis 1994 warten, um einen menschlichen Champion zu sehen. Ein Programm namens Chinook konnte gegen Marion Tinsley gewinnen. Das Ergebnis war 4 zu 2, mit 33 Unentschieden. Im Jahr 2007 gab das Team hinter Chinook bekannt, dass es das Damespiel gelöst hat und bewiesen hat, dass ein perfektes Spiel auf beiden Seiten immer zu einem Unentschieden führt.

Schach - Vielfältige Bewegungen und massiver Parallelismus

Das Spiel der Könige, wie Schach auch genannt wird, ist eine der prominentesten Methoden, um die Überlegenheit über den Gegner zu beweisen. Wir erinnern uns noch an die Zeit des Kalten Krieges, als sowjetische Schachspieler ein wichtiger Teil der kommunistischen Propaganda waren.

Dieses Spiel ist komplizierter als Draughts, da wir zu jedem Zeitpunkt des Spiels viel mehr Möglichkeiten haben, unsere Figuren zu bewegen. Das macht es problematischer für traditionelle KI-Methoden, die darauf basieren, einen Baum möglicher Züge für viele Runden im Voraus zu suchen und zu bewerten.

Dennoch gelang es der IBM-Maschine Deep Blue in einem berühmten Match im Jahr 1997, den amtierenden Weltmeister Gary Kasparov mit dieser Methode mit einem knappen Ergebnis von 3,5 zu 2,5 zu schlagen. Deep Blue nutzte die Vorteile von massiv parallelisierten, speziell angefertigten VLSI-Chips (Very Large Scale Integration - manchmal ist das Akronym einfach besser), um seine Berechnungen durchzuführen. Es verfügte über 30 Knoten, die jeweils eine einzelne Mehrzweck-CPU enthielten und 480 solcher Chips orchestrierten. Viele Journalisten verkündeten damals, dies sei das Ende des Wettlaufs Mensch gegen Maschine, mit einem Gewinner aus Silikon.

Das war jedoch viel zu früh. Es lagen noch viele weitere Herausforderungen vor uns...

Scrabble - Unvollkommene Informationen und bösartige Züge

Scrabble ist über 80 Jahre alt, aber im Vergleich zu den Spielen, die wir gerade erkundet haben, immer noch recht neu. Bei diesem Spiel bilden die Spieler ein Kreuzworträtsel auf einem 15 mal 15 großen Spielbrett und versuchen, eine maximale Punktzahl zu erreichen, die je nach Buchstabe und Ort variiert.

Im Gegensatz zu den anderen Spielen, die wir bisher betrachtet haben, führt es ein Element der unvollkommenen Information ein, da wir nicht wissen, welche Buchstaben unser Gegner zur Verfügung hat. Das bedeutet, dass es keine perfekten Informationen gibt und dass die Maschinen die Daten berücksichtigen müssen, die ihnen verborgen sind.

Wir mussten bis 2007 auf den ersten KI-Sieg warten, als das Computerprogramm Quackle den menschlichen Champion David Boys schlug. Das Programm verfolgt einen Brute-Force-Ansatz, der dem ähnelt, was wir bisher gesehen haben, indem es einen Baum von möglichen Zügen aufbaut und auswertet. Das Interessante an der Scrabble-Strategie eines Computers ist jedoch, dass er nicht intuitiv optimiert, um das Wort mit der höchsten Punktzahl auf das Brett zu bringen, sondern dass er versucht, das Blatt seines Gegners zu erraten und auf der Grundlage der Wahrscheinlichkeit einen Zug auszuführen, der für uns weniger direkt von Vorteil ist, aber die besten Optionen des Gegners blockiert und so die Wahrscheinlichkeit eines Sieges effizienter auf die Seite des Computers verschiebt.

Jeopardy! - Natürliches Sprachverstehen

Jeopardy! ist eine Fernsehshow, in der die Teilnehmer Hinweise zum Allgemeinwissen erhalten und eine Lösung in Form einer Frage geben müssen. Um das Spiel zu gewinnen, muss der Spieler in einem scheinbar unbegrenzten Problemraum logisches Denken mit Wissen kombinieren.

In einem Schaukampf im Jahr 2011 gewann die IBM-Maschine Watson ein Match gegen zwei der bestverdienenden professionellen Spielteilnehmer - Ken Jennings und Brad Rutter. Watson ist ein komplexes Computersystem, das natürliche Sprachverarbeitung, Information Retrieval, Wissensrepräsentation, automatisiertes Reasoning und maschinelles Lernen einsetzt, um beliebige Fragen zu beantworten.

Wenn Watson mit einem Satz konfrontiert wird, zerlegt er ihn in Teile und durchläuft dabei parallel über 100 verschiedene Algorithmen zur Verarbeitung natürlicher Sprache, die auf der Grundlage seiner Wissensdatenbanken Hypothesen formulieren. Anschließend führt er eine weiche Filterung durch und vergleicht diese Hypothesen mit einer anderen Datenbank. All diese Ergebnisse werden dann zusammengeführt und anhand eines mit maschinellem Lernen trainierten Modells gegeneinander abgewogen. Als Informationsquellen verwendet Watson individuell zusammengestellte Enzyklopädien, Wörterbücher, verschiedene Artikel, Bücher und Online-Quellen. Die ursprüngliche Hardware bestand aus 90 POWER7-Prozessoren mit acht Kernen.

Go - Komplexitätsexplosion und Deep Learning

Go wurde vor über 2.500 Jahren in China erfunden und wird immer noch in seiner ursprünglichen Form gespielt. Bei diesem Spiel geht es darum, mit den Spielsteinen auf einem Brett mit 19 mal 19 Feldern ein größeres Gebiet zu umschließen als der Gegner.

Doch trotz seiner einfachen Regeln ist Go für Computer viel schwieriger als Schach. Beim Schach haben wir durchschnittlich 37 mögliche Züge zur Verfügung, während es beim Go über 150 sind. Es ist auch schwieriger, den Wert eines Zuges zu ermitteln, als den Materialvorteil zu berücksichtigen, der durch das Schlagen einer gegnerischen Figur entsteht, wie es beim Schach der Fall ist.

Nach dem Sieg über Kasparov dachten viele, dass wir hundert Jahre warten müssten, um die Rechenleistung zu erreichen, die erforderlich ist, um einen menschlichen Champion in Go herauszufordern, doch es kam anders! AlphaGo, das vom Deep Mind Team entwickelt wurde, gewann 2016 ein berühmtes Match gegen den Profispieler Lee Sedol (9. Dan) mit 4 zu 1 und nur ein Jahr später besiegte es den amtierenden Champion Ke Jie.

AlphaGo verwendet eine viel ausgefeiltere Methode als die, die wir zuvor besprochen haben. Es konstruiert und durchsucht zwar auch einen Baum, um den optimalen Zug zu finden, aber es nutzt das Wissen, das aus dem Training mit einem tiefen neuronalen Netzwerk auf einer riesigen Menge historischer Matches stammt, die alle zwischen menschlichen Gegnern gespielt wurden.

Diese Technik des Deep Learning versucht zu imitieren, wie unser Gehirn Informationen verarbeitet. Das Netzwerk hat viele Schichten, von denen jede die Eingabedaten auf einer anderen Abstraktionsebene verarbeitet. Eine frühere Version von AlphaGo stützt sich auf Graphics Processing Units zur effizienten Durchführung von Matrixoperationen, die das Herzstück von neuronalen Netzwerken bilden und die Vorteile vieler parallel arbeitender Kerne nutzen. Spätere Versionen gingen noch einen Schritt weiter und liefen auf Tensor Processing Units - Hardware, die speziell für Berechnungen des maschinellen Lernens optimiert ist.

Zusammenfassung - Was haben wir bis jetzt gelernt?

Dies ist nicht das Ende unserer Reise - es gibt sogar so viel zu berichten, dass ich diesen Bericht in zwei Teile aufgeteilt habe. Aber selbst zu diesem frühen Zeitpunkt ist klar, dass wir einen langen Weg zurückgelegt haben. Wenn die Optionen begrenzt sind, mit festgelegten Zügen und einer begrenzten/vordefinierten Anzahl von Ergebnissen, hat die Technologie solche Probleme schon lange gelöst - es geht oft nur darum, die Verarbeitung mit dem größeren Umfang der Spiele zu skalieren.

Wir haben jedoch begonnen, Probleme zu erkennen, die verborgene Informationen nutzen oder darauf beruhen, Ihren Gegner zu "verstehen". Hier haben wir begonnen, neue Ansätze zu entwickeln, die das Potenzial von KI, maschinellem Lernen und Deep Learning gegenüber herkömmlichen baumbasierten Entscheidungsfindungsprozessen deutlich machen.

Was kommt als Nächstes?

Uns bleiben nur noch zwei Jahre, um unsere Geschichte zu erzählen, aber glauben Sie mir, hier fangen die Dinge an, wirklich interessant zu werden. Im zweiten Teil werden wir über Herausforderungen sprechen, deren Problembereiche weit über das Go-Spiel hinausgehen, einschließlich solcher, die noch vor einiger Zeit als zu unlösbar galten, um sie in naher Zukunft zu lösen. Vor allem aber werden wir erörtern, wie sich diese Errungenschaften auf eine Vielzahl anderer Bereiche jenseits von Spielen übertragen lassen. Verpassen Sie also auf keinen Fall den zweiten Teil dieses Artikels.

Geschäftsperspektive

Maschinelles Lernen ist auf dem Vormarsch. Wir können künstliche Wesen schaffen, die erfolgreich herausfinden, wie sie sich in immer komplexeren Umgebungen selbständig zurechtfinden können. Es gibt unzählige Anwendungsfälle in allen Bereichen menschlicher Aktivitäten. Es ist jedoch auch erwähnenswert, dass sowohl das Cloud Computing als auch der Zugang zu einer riesigen Menge an Daten zwei der wichtigsten Faktoren in diesem Bereich sind.

Quellen:

• Wie Quackle Scrabble spielt
• KIs sind bessere Gamer als wir, aber das ist OK
• Top 5 Computer vs. Mensch Spiel Matchups
• Backgammon-Computerprogramm besiegt Weltmeister
• Ein Computerprogramm gewinnt sein erstes Scrabble-Turnier
• Das Priestertum im Spiel: Computerspiele in den 1950er Jahren
• Computer gewinnt bei 'Jeopardy!': Das ist nicht trivial
• Treffen Sie Bertie the Brain, das erste Arcade-Spiel der Welt, gebaut in Toronto