BUILD 2018: Wie Microsofts AI die volle Punktzahl in Pac-Man erreichte

Schon im Jahr 2017 schaffte es die KI von Microsofts Tochterfirma Maluuba, das Spiel Ms. Pac-Man komplett durchzuzocken und als erster Spieler die volle Punktzahl zu erreichen. Auf der BUILD 2018 hat das Team über ihr Geheimnis des Programmierens gesprochen und welches Einsatzgebiet man sich für ein ähnliches Projekt in der realen Welt vorstellen könnte.

Ms. Pac-Man ist ein Arcade-Spiel aus den 80er-Jahren. Leider bin ich zu jung, um den Hype des Games persönlich miterlebt zu haben. So richtig beschäftigt habe ich mich mit dem Spiel erst, als ich das Buch „Ready Player One“ gelesen habe, in dem die Hauptperson [Achtung Spoiler] die Maximalpunktzahl von 999.990 Punkten knackt. In Wirklichkeit hat das noch nie ein Mensch geschafft. Die Betonung liegt absichtlich auf der menschlichen Komponente, denn tatsächlich konnte eine künstliche Intelligenz diesen Weltrekord erreichen. Zum Vergleich: Die besten menschlichen Spieler erzielten bislang rund 250.000 Punkte.

Im Juni 2017 war es also soweit: Die dazu genutzte KI stammt von Microsofts Tochterfirma Maluuba, die mehrere Jahre an der künstlichen Intelligenz forschte. Zunächst bestand das Team aus zwei Leuten, die ihr Projekt mit der Frage nach der Skalierbarkeit von dem sogenannten „Reinforcement Learning“ begannen. Auf der BUILD 2018 sprach das Team über die Anfänge ihrer Idee, die Umsetzung und schlussendlich das Programmiergeheimnis, mit dem sie es schafften, die volle Punktzahl in Pac-Man abzusahnen.

GIF

Genau wie die Entwickler in ihrer Keynote, fange ich mal damit an, zu erklären was „Reinforcement Learning“ (RL) eigentlich ist. So blöd das auch klingen mag: Im Prinzip wenden wir RL täglich bei unseren Hunden oder Kindern an, zumindest auf eine einfache Art und Weise. Es beschreibt nämlich das Konzept des bestärkenden Lernens. Bedeutet: Hat mein Hund seinen Haufen brav in den Garten anstatt auf den Teppich gesetzt, bekommt er ein Leckerli. Umgekehrt wird er natürlich ausgeschimpft. Dadurch lernt das Tier, dass es ihm zugute kommt, wenn er sein Geschäft im Freien verrichtet. Für jede Aktion gibt es also ein positives oder negatives Feedback.

Ähnlich, aber doch viel komplexer, passiert Reinforcement Learning auf der Ebene der künstlichen Intelligenz. Doch das Konzept ist viel weitreichender. Denn anstatt der KI zu zeigen, wie sie an noch höhere Belohnungen kommen kann, muss sie dies durch Ausprobieren selbstständig herauszufinden. So kann das Programm nach und nach trainiert werden. Dazu entwickelte das Team zunächst das sogenannte „Pac-Boy“-Programm, also eine abgeschwächte Form von Pac-Man. Im Vergleich zum Originalspiel hat das Programm nämlich „nur“ 10 hoch 28 mögliche Zustände, wohingegen Pac-Man insgesamt 10 hoch 50 Möglichkeiten bietet. Selbst die möglichen Züge bei Schach kommen nicht an diese Zahl heran.

Beim Training kann es passieren, dass die künstliche Intelligenz entweder ängstlich oder erfolgreich agiert. Klingt zwar im ersten Moment lächerlich, da einem Programm natürlich nicht vor Angst die Einsen und Nullen schlottern. Dadurch, dass es aber von sich aus lernt und jede seiner Aktionen entweder positiv oder negativ bewertet werden, können seine Erfahrungen mit der Zeit negativ geprägt werden. Dann geht das sogar soweit, dass die Pac-Boys Angst vor den Geistern des Spiels haben, sodass sie das Level nicht zu Ende bringen können und sich nur noch in einer Ecke bewegen.

Zusätzlich zu der Methode des bestärkenden Lernens hat das Team das Programm in 150 unterschiedliche Aufgaben aufgeteilt. Jede verantwortliche Komponente hat dabei einen speziellen Job bekommen, den es bis zur Perfektion trainierte. Einzelne sogenannte Agenten wurden stückweise mit Aufgaben betraut, wie der Suche nach einem bestimmten Pellet, um dann zusammen mit anderen Agenten das Ziel der höheren Belohnung zu verfolgen.

Als nächstes wurde ein Top-Agent ernannt, der Vorschläge von allen anderen annahm, um Entscheidungen darüber zu treffen, wohin Ms. Pac-Man gehen soll. Die Entwickler erzählten, dass einzelne Agenten „sehr egoistisch agierten“, doch der Top-Agent konzentrierte sich nur auf das Beste für das gesamte Team. Mit dieser Methoden wurden die besten Ergebnisse erzielt.

„Diese Idee, die Dinge in kleinere Probleme zu zerlegen, ist die Grundlage dafür, wie Menschen Probleme lösen. Ein Unternehmen, das Produktentwicklung betreibt, ist ein gutes Beispiel. Das Ziel der gesamten Organisation ist es, ein Produkt zu entwickeln, aber individuell gibt es Gruppen, die ihre eigene Belohnung und ihr eigenes Ziel für den Prozess haben.“ Kaheer Suleman, CTO Maluuba

Insgesamt wurde der Prozess mit mehr als 800 Millionen Frames des Spiels trainiert, sodass es von der KI schlussendlich komplett durchgespielt wurde. Ein ähnliches Projekt hat Googles Tochter Deep-Mind ja vor einer Weile vorgestellt. Ihre künstliche Intelligenz hat sich selbstständig das Spiel AlphaGo beigebracht, sodass es mögliche menschliche Konkurrenten einfach besiegen konnte.

Das Projekt von Maluuba hat auch Potenzial, um in der realen Welt zum Einsatz zu kommen. Ein ähnliches System könnte im Einzelhandel verwendet werden und zwar mit einer KI, die den menschlichen Vertriebsmitarbeitern hilft, festzustellen, welche Kunden zuerst Hilfe brauchen. So könnte der Umsatz maximiert werden. All dies jedoch in eine wirkliche Anwendung umzusetzen, wird eine noch viel größere Herausforderung für sich sein. Zurzeit ist das Team von Maluuba stolz darauf, Ms. Pac-Man als erstes und einziges Team gewonnen zu haben.

Lesenswert: KI-Experimente: Wie Google Algorithmen die natürliche Sprache lehrt

Alle Beiträge zu unserer Berichterstattung von der BUILD 2018 findet ihr unter diesem Link.