Othello, ein Spiel mit 10²⁸ Variationen, wurde von einem Supercomputer geknackt!

Othello ist auch als Schwarz-Weiß-Schach bekannt, und der Spitzname stammt aus Shakespeares berühmtem Stück „Othello“ – die schwarzen und weißen Seiten symbolisieren den Protagonisten Othello und seine Frau Desdemona; Das Schachspiel symbolisiert die Interaktion zwischen beiden. Nun haben Wissenschaftler mithilfe von Supercomputer-Clustern alle Varianten des Spiels ausgeschöpft und Othello geknackt. Die Liebenden durchlebten mehr als vierhundert Jahre voller Eifersucht und Verrat, Reue und Tränen und umarmten sich schließlich fest und gleichgesinnt.

Geschrieben von | Jiawei

Eine Minute zum Lernen, ein Leben lang zum Meistern.

——Ein Sprichwort, das Othello-Fans auf der ganzen Welt bekannt ist

Ich glaube, dass die meisten Menschen, die in den 1980er und 1990er Jahren geboren wurden, zum ersten Mal über ein elektronisches Wörterbuch namens „Wenquxing“ mit Othello in Berührung kamen. Gleichzeitig ist der „soziale Status“ von Othello bei weitem nicht mit dem von Go, das eine tiefgreifende kulturelle Tradition hat, oder mit dem von Schach, das sein eigenes elitäres Temperament mit sich bringt, vergleichbar. Daher denken viele Leute vielleicht, dass Othello nur ein einfaches und leicht zu erlernendes Schachspiel für Kinder sei. Die wenigsten wissen, dass sich Othello aufgrund seiner einzigartigen Regeln von anderen Schachspielen unterscheidet. In Situationen, in denen die Dynamik der Situation begrenzt ist, wie etwa im Endspiel bei Gobang oder Schach, können die Spieler die Situation oft leicht erkennen. Aber selbst wenn nur die letzten 6 Felder des schwarz-weißen Schachs leer bleiben, ist es immer noch ziemlich schwierig zu berechnen. Diese relative Komplexität wird durch die Eigenschaften von Othello bestimmt. Es ist nicht so leicht, es auf den ersten Blick zu verstehen wie andere Schachspiele, daher kann die Situation auch leicht umgekehrt sein. Im späteren Spielverlauf kann es schon nach wenigen Runden dazu kommen, dass sich eine große Zahl gegnerischer Spielsteine ​​gegen Sie wendet und sich die Situation somit umkehrt.

Daher verfügt Othello nicht nur über eine theoretisch erstaunliche Anzahl von 10^28 Kombinationen, sondern erfordert auch ein extrem tiefes Denkvermögen. Spitzenschachspieler müssen bereits in der frühen und mittleren Phase über ihre Schachstrategien für den Endkampf nachdenken.

Die Komplexität von Othello lässt sich auch an folgendem Punkt erkennen: Das populärere Gobang (Fünf in einer Reihe) wurde bereits 1993 vom Informatiker Victor Allis geknackt (gelöst) und es wurde bewiesen, dass es in Ermangelung spezieller Eröffnungsregeln eine Gewinnstrategie für den ersten Spieler bei Gobang gibt; Doch obwohl die Rechenleistung des Menschen in den letzten 30 Jahren exponentiell zugenommen hat, war es nicht möglich, alle Varianten von Othello auszuschöpfen – bis Ende Oktober dieses Jahres der japanische Informatiker Hiroki Takizawa einen Meilenstein erreichte und bekannt gab, dass er Othello geknackt habe!

Gleichzeitig weist die Forschung zu Othello auch eine seltsame Verbindung zum „Putsch“ im Management von OpenAI auf, der vor nicht allzu langer Zeit ein Erdbeben in der KI-Branche auslöste.

Doch bevor ich fortfahre, möchte ich für diejenigen Leser, die Othello nicht kennen, zunächst kurz die Regeln und die Geschichte dieses Spiels vorstellen.

Was ist Reversi

Othello wird auf Chinesisch auch Reversi oder Othello und auf Englisch Reversi oder Othello genannt.

Der Prototyp von Othello wurde erstmals im späten 19. Jahrhundert von den Briten erfunden. Es wurde in den 1970er Jahren vom Japaner Goro Hasegawa entwickelt und gefördert. Er benannte das Spiel nach Shakespeares berühmtem Stück „Othello“ (japanisch „オセロ“) um, und so haben wir den Othello, den heute jeder spielt. Warum Anleihen bei Shakespeares berühmten Stücken nehmen? Dies liegt daran, dass der Protagonist Othello ein Schwarzer und seine Frau weiß ist. Othello wurde von einem Bösewicht dazu angestiftet, seine Frau der Untreue zu verdächtigen und tötete sie schließlich eigenhändig. Als später die Wahrheit ans Licht kam, empfand er Reue und beging Selbstmord. Das Spiel Othello ist nach der Geschichte des Kampfes zwischen Schwarzen und Weißen benannt, daher haben die Schachfiguren zwei Seiten, eine schwarze und eine weiße.

Othello-Schachfiguren und -brett. Bildquelle: Reversi – Wikipedia

An manchen Stellen sind die Schachfiguren auf der Vorder- und Rückseite rot und grün. Zu dieser Zeit wird es auch „Apfelschach“ genannt, da Äpfel in rote und grüne Äpfel unterteilt werden.

Grundregeln:

• Der üblichste Start besteht darin, vier schwarze und weiße Schachfiguren auf die vier Felder in der Mitte des Bretts zu stellen. Normalerweise ziehen die schwarzen Figuren zuerst und die beiden Seiten sind abwechselnd mit ihren Zügen dran.

Othello-Eröffnung. | Bildquelle: Japans schwächste Othello-KI-Kampfplattform, schwächste Osero-Spieloberfläche

• Solange die Schachfigur, die Sie platzieren, auf einer Linie (horizontal, vertikal oder diagonal) mit einer Ihrer eigenen Schachfiguren auf dem Brett steht und die Schachfiguren des Gegners einschließt, können Sie die Schachfiguren des Gegners in Ihre eigenen Figuren verwandeln (drehen Sie sie einfach um). Die umschlossenen Positionen müssen alle von den Steinen des Gegners besetzt sein und dürfen keine leeren Felder enthalten. Außerdem können Sie ein Stück nur dort platzieren, wo Sie es umdrehen können.

• Ein Zug kann eine Figur in mehrere Richtungen umdrehen und jede gefangene Figur muss umgedreht werden, wobei der Spieler nicht die Möglichkeit hat, eine Figur nicht umzudrehen. Die gegnerische Figur muss durch die gerade platzierte Figur festgeklemmt werden, bevor die gegnerische Figur umgedreht werden kann. Die durch das Umdrehen der gegnerischen Figur festgeklemmte Figur kann nicht umgedreht werden.

• Wenn ein Spieler keinen regelkonformen Zug machen kann, muss er dem anderen Spieler erlauben, so lange Züge zu machen, bis dieser einen regelkonformen Zug machen kann. Wenn keiner der Spieler einen gültigen Zug machen kann, ist das Spiel vorbei.

Es gewinnt die Seite, die am Ende des Spiels die meisten Spielsteine ​​auf dem Brett hat. Bei gleicher Steinzahl endet das Spiel unentschieden.

Zermelos Theorem und das gelöste Spiel

Das Studium eines jeden Schachspiels ist untrennbar mit dem berühmten Theorem verbunden, das der deutsche Mathematiker Zermelo 1913 veröffentlichte:

Wenn in einem endlichen Spiel zwischen zwei Personen beide Spieler über perfekte Informationen verfügen und kein Glück im Spiel ist, muss einer der ersten oder zweiten Spieler über eine gewinnende/unschlagbare Strategie verfügen.

Beachten Sie, dass viele Leute diesen Satz nicht richtig verstehen und sogar denken, dass es sich einfach nur um offensichtlichen Unsinn handelt. Um die Bedeutung des Theorems zu verdeutlichen, denken Sie bitte zunächst an das Spiel „Schere, Stein, Papier“.

Ohne Schummeln ist „Schere, Stein, Papier“ ein Glücksspiel und es gibt keine Gewinnstrategie. Warum können wir also glauben, dass in einem Spiel, bei dem es nicht auf Glück ankommt, eine Seite eine siegreiche/unvermeidliche Strategie haben muss? Es besteht tatsächlich ein grundlegender Unterschied zwischen Spielen, bei denen Glück eine Rolle spielt und solchen, bei denen es nicht darauf ankommt. Dieser Unterschied ist jedoch keineswegs offensichtlich und erfordert einen mathematischen Beweis.

Hier ist ein populärer Beweis, der leicht zu verstehen ist: Wir nehmen an, dass beide Spieler Götter mit unendlicher Weisheit sind. Wenn ein Spieler bei einem bestimmten Zug verliert (z. B. beim Schachmatt), dann verliert er auch nach dem Zurückziehen seines Zuges, andernfalls widerspricht dies unserer „unendlichen Weisheit“ (weil er im vorherigen Zug einen falschen Zug gemacht hat). Analog dazu wissen wir, dass der Ausgang des Spiels bereits zu Beginn feststeht, d. h., ein Spieler verfügt über eine Gewinnstrategie.

Tatsächlich ist Zermelos Theorem der Grundstein der Spieltheorie mit perfekter Information. Daraus wissen wir, dass es in jedem herkömmlichen Brettspiel, das mit einer begrenzten Anzahl von Zügen beendet werden kann, eine Seite gibt, die mit Sicherheit gewinnt oder zumindest mit Sicherheit nicht verliert. Die nächste Frage ist: Finden Sie die Seite mit der unbesiegbaren Strategie.

Wenn wir bestätigen, dass der erste oder zweite Spieler in einem Spiel über eine gewinnbringende/unschlagbare Strategie verfügt, sprechen wir von einem gelösten Spiel. Derzeit gibt es keine einheitliche Standardübersetzung für „gelöstes Spiel“, aber es kann natürlich direkt mit „gelöst“ oder „geknacktes Spiel“ übersetzt werden.

Bei gecrackten Spielen gibt es drei Schwierigkeitsstufen.

Ultraschwache Lösung: Es ist theoretisch bewiesen, dass eine Partei garantiert das Spiel gewinnt oder dass das Spiel definitiv unentschieden endet, es besteht jedoch keine Notwendigkeit, eine bestimmte Möglichkeit für den Sieg oder das Unentschieden anzugeben. Diese Lösung erfordert lediglich den Einsatz mathematischer Werkzeuge zur Analyse der abstrakten Eigenschaften des Spiels, ohne alle Möglichkeiten aufzuzählen.

Schwache Lösung: Geben Sie einen Algorithmus an, der vom Anfangszustand des Spiels ausgehen und garantieren kann, dass ein Spieler das Spiel gewinnt oder kein Spieler das Spiel verliert. Diese Lösung erfordert normalerweise eine vollständige Aufzählung aller Zweige des Spielbaums oder die Verwendung einer vorgenerierten Datenbank.

Starke Lösung: Geben Sie einen Algorithmus an, der in jedem Spielzustand beginnen und den besten Zug liefern kann, unabhängig davon, ob die vorherigen Züge perfekt waren. Diese Lösung erfordert die Aufzählung aller Knoten des Spielbaums oder die Verwendung einer vorgenerierten Datenbank.

1993 wurde Gobang geknackt. Im Oktober dieses Jahres erhielt auch Othello eine schwache Lösung. Wir wissen heute, dass ein Spiel zwischen zwei Göttern mit unendlicher Rechenleistung gegen Othello immer unentschieden ausgehen würde. Mit anderen Worten: Reversi ist ein sehr faires Brettspiel. Die Partei, die zuerst oder als Zweite geht, erlangt dadurch nicht den geringsten Vorteil. Dies entspricht dem Gefühl eines hochrangigen Othello-Spielers.

Da es sich jedoch um eine schwache Lösung handelt, hat Takumi Takizawa, ein Bioinformatiker und Informatiker von Preferred Networks, einem japanischen Start-up-Unternehmen für KI-Forschung und -Entwicklung, gleichzeitig auch gleich zu Beginn des Spiels die besten Strategien für beide Spieler aufgelistet.

(Man sollte beachten, dass der Mensch weder Go noch Schach geknackt hat. Obwohl die heutigen Schach spielenden KIs weitaus leistungsfähiger sind als Menschen, haben sie nicht die korrekteste Spielweise gefunden. Sie haben einfach eine korrektere Spielweise gefunden als wir Menschen.)

Technologie und Bedeutung

Seit den Anfängen der Informatik gilt das vollständige Knacken reiner Strategiespiele wie Schach als bemerkenswerte Leistung der menschlichen Intelligenz. Seitdem ist es auch im Bereich der Künstlichen Intelligenz (KI) ein großes Thema. Zu den frühen Forschern gehörten Charles Babbage und Claude Elwood Shannon. Mit der Verbesserung der Technologie des maschinellen Lernens und der Rechenleistung haben Menschen KIs mit extrem hohen Schachfähigkeiten geschaffen (wie beispielsweise den Meilenstein AlphaGo), aber diese Super-KIs können diese Spiele nicht perfekt knacken. Vor nicht allzu langer Zeit war man allgemein der Meinung, Othello sei zu komplex, um geknackt zu werden. Es handelte sich also schon immer um eine große Herausforderung im Bereich der künstlichen Intelligenz.

Um Othello zu knacken, nutzte Takizawa moderne Technologie, um Edax, ein leistungsstarkes Schachprogramm aus den 1990er Jahren, zu verbessern und zerlegte die Aufgabe dann in überschaubarere Teile. Er analysierte zunächst die Situation, in der auf dem Schachbrett noch 50 leere Felder übrig waren, und untersuchte dann alle sinnvollen Situationen, in denen 36 Felder leer waren. Er war angenehm überrascht, dass die vorhandene Rechenleistung offenbar ausreichte, um eine schwache Lösung für Othello zu unterstützen.

Der fett markierte Weg ist die beste Abzweigung. Der perfekte Spieler sollte gemäß dem fettgedruckten Strategiebaum für die entsprechende Position spielen. | Quelle: OTHELLO IST GELÖST

Er führte sein Programm auf einem Supercomputer-Cluster namens MN-J aus, der Preferred Networks gehörte. Zum Cluster gehört der Supercomputer MN-3, der in puncto Energieeffizienz derzeit weltweit den 11. Platz belegt (Platz 1 im Jahr 2020).

Schließlich verkündete Takizawa in seinem Aufsatz „Othello ist gelöst“, dass er Othello geknackt habe. Dies ist eine große Errungenschaft für die Menschheit und zeigt den großen Fortschritt der Informatik und der künstlichen Intelligenz.

Ein weiterer bemerkenswerter Punkt ist, dass die Zahl der Positionen, die tatsächlich erkundet werden müssen, um Othello zu knacken, viel kleiner ist als die in früheren Studien geschätzte Zahl. Takizawa führt dies auf die ausgefeiltere Konfiguration des Suchalgorithmus seines Teams zurück. Bisher schreckte man hiervon jedoch ab, da der geschätzte Rechenaufwand extrem groß war. Die Moral dieser Geschichte ist vielleicht, dass Analysen auf dem Papier oberflächlich sind und man üben muss, um sie wirklich zu verstehen.

Reversi und KI

Japan ist möglicherweise das Land mit der größten Zahl an Othello-Fans. Statistiken aus dem Jahr 2005 zufolge gibt es in Japan etwa 60 Millionen Othello-Fans (etwa 15 Millionen Shogi-Fans, etwa 5 Millionen Go-Fans und etwa 3 Millionen Schach-Fans).

Daher war es nur natürlich, dass japanische Wissenschaftler Othello schließlich knackten. Takizawa freut sich darauf, in Zukunft Durchbrüche im Schach zu erzielen. Die Komplexität des Schachspiels ist 15 Größenordnungen höher als die von Othello. Das Knacken von Schach ist sogar eine der treibenden Kräfte hinter der Entwicklung der Computer- und KI-Technologie.

Allerdings planen manche Leute neben der Super-KI auch das Gegenteil. Das japanische KI-Unternehmen AVILEN ist der Ansicht, dass die heutige Schach-KI zu leistungsfähig ist, und hat daher eine Schwarz-Weiß-Schach-KI namens „Othello“ entwickelt. Sein Ziel besteht darin, möglichst oft gegen menschliche Spieler zu verlieren, statt wie andere KIs nach dem Sieg zu streben.

Das Prinzip dieser KI besteht darin, ihr Verständnis der Othello-Regeln so zu modifizieren, dass die KI jedes Mal den für sie nachteiligsten Zug wählt und dem menschlichen Spieler gleichzeitig den größten Vorteil verschafft. Auf diese Weise ist es für menschliche Spieler sehr schwierig, gegen die KI zu verlieren, und sie müssen dazu möglicherweise sogar spezielle Strategien anwenden. Othello fordert menschliche Spieler öffentlich online heraus. Bis zum 29. Juli 2019 wurden 220.000 Spiele gespielt und nur mehr als 1.000 Spiele gewonnen, mit einer Gewinnrate von weniger als 0,5 %. Es zog sogar einige professionelle Othello-Spieler als Herausforderung an, die sehen wollten, ob sie es schaffen würden.

Einige Forscher glauben, dass Othello das konventionelle Denken im Bereich der künstlichen Intelligenz durchbricht und eine weitere Möglichkeit für KI aufzeigt. Es hat bei manchen Menschen auch zu Überlegungen über KI geführt, etwa darüber, ob KI einen eigenen Willen hat, ob KI menschliche Emotionen verstehen kann …

Bis zu einem gewissen Grad liefert das KI-Experiment zu Othello tatsächlich Hinweise auf die oben genannten Überlegungen.

Am 17. November gab OpenAI, das durch die Entwicklung von ChatGPT und GPT-4 zu einem führenden Unternehmen im Bereich der KI geworden ist, ohne Vorwarnung bekannt, dass der Vorstand den ehemaligen CEO Sam Altman seines Amtes enthoben habe. Dies wurde als „Putsch“ angesehen. Die weitere Handlung ist noch wechselhafter und viele Details wurden noch nicht verraten.

Eine der Theorien besagt, dass OpenAI einen weiteren großen Durchbruch auf dem Gebiet der KI erzielt hat und ihr Chefwissenschaftler Ilya Sutskever Zweifel an der neuesten Technologie hat und sie nicht kommerzialisieren möchte, weshalb er mit Sam Altman nicht einer Meinung ist. Schließlich eskalierte der Konflikt und löste eine umfassende Säuberung der Geschäftsführung aus. Natürlich erfuhren wir später, dass Ilya seine Entscheidung erneut bereute und beschloss, sich auf die Seite von Ultraman zu stellen, um sich der Entscheidung des Vorstands zu widersetzen.

In welcher Richtung also dürfte OpenAI am ehesten einen Durchbruch erzielen? Tatsächlich hat Ilya den Medien vor kurzem seine Überzeugung geäußert:

Wenn man ein großes neuronales Netzwerk trainiert, das nächste Wort in verschiedenen Texten präzise vorherzusagen, baut man tatsächlich ein Modell der Welt. Diese Texte sind im Wesentlichen eine Abbildung der realen Welt. Neuronale Netzwerke lernen ständig über alle Aspekte der Welt, über Menschen, menschliche Umgebungen, Erwartungen, Träume, Motivationen und so weiter. KI lernt, die menschliche Welt zu komprimieren, zu abstrahieren und nutzbar darzustellen.

Die obige Aussage mag verwirrend erscheinen, aber um eine gängige Analogie zum Thema dieses Artikels zu verwenden: Wir zeigen der KI Schachrekorde, sagen ihr aber nicht, dass es Schachrekorde sind. Am Ende lernte die KI, Schach zu spielen, aber sie wusste nicht, dass sie Schach spielte.

Ob OpenAI dieses Konzept verifiziert hat – und damit bewiesen hat, dass das Large Language Model (LLM) die Welt letztlich in Sprache neu darstellt, indem es einfach Sprache lernt – wissen wir noch nicht, aber eine andere aktuelle Othello-Studie unterstützt diese Theorie.

Bildquelle: https://openreview.net/forum?id=DeG07_TcZvT

Die Forscher verwendeten 20 Millionen Sequenzproben aus einer großen Anzahl tatsächlicher Spielpartien, um ein neuronales Netzwerk namens OthelloGPT zu trainieren. OthelloGPT kennt weder die Spielregeln noch die durch die Eingabesequenz dargestellten Spielkonzepte, sondern ist lediglich aufeinanderfolgenden Zeichenfolgen von Texttoken ausgesetzt. Ähnlich wie beim Training großer Sprachmodelle für natürliche Sprache besteht das Trainingsziel von OthelloGPT darin, die nächste mögliche Zeichenfolge in der Sequenz vorherzusagen.

Nachdem genügend Schachaufzeichnungen vorliegen, kann OthelloGPT zukünftige legale Schachzüge genau vorhersagen, sogar für Zeichenfolgen, die in den Trainingsdaten noch nie vorgekommen sind (d. h. Sequenzen in Schachaufzeichnungen)!

OthelloGPT wusste nicht, dass es Othello spielte, aber durch das Lesen einer großen Anzahl von Schachaufzeichnungen (Buchstaben- und Zahlenfolgen) fand es die Muster und lernte tatsächlich, Schach zu spielen. Bei OthelloGPT wird jedoch nur das Generierungsmuster von Zeichenfolgen vorhergesagt.

Falls sich jemand von Ihnen nach der Lektüre dieses Artikels für Othello interessiert, möchte ich Ihnen ein Einführungsbuch empfehlen: „Othello Guide“ (geschrieben von Brian Rose), das online verfügbar ist.

Verweise

[1] OTHELLO IST GELÖST, 2310.19387.pdf (arxiv.org)

[2] Reversi – Wikipedia

[3] Japans schwächste Othello-KI-Kampfplattform: The Weakest Osero | PROJEKTE (Projekt) | AVILEN Co., Ltd.

Dieser Artikel wird vom Science Popularization China Starry Sky Project unterstützt

Produziert von: Chinesische Vereinigung für Wissenschaft und Technologie, Abteilung für Wissenschaftspopularisierung

Hersteller: China Science and Technology Press Co., Ltd., Beijing Zhongke Xinghe Culture Media Co., Ltd.

Besondere Tipps

1. Gehen Sie zur „Featured Column“ unten im Menü des öffentlichen WeChat-Kontos „Fanpu“, um eine Reihe populärwissenschaftlicher Artikel zu verschiedenen Themen zu lesen.

2. „Fanpu“ bietet die Funktion, Artikel nach Monat zu suchen. Folgen Sie dem offiziellen Account und antworten Sie mit der vierstelligen Jahreszahl + Monat, also etwa „1903“, um den Artikelindex für März 2019 zu erhalten, usw.

Copyright-Erklärung: Einzelpersonen können diesen Artikel gerne weiterleiten, es ist jedoch keinem Medium und keiner Organisation gestattet, ihn ohne Genehmigung nachzudrucken oder Auszüge daraus zu verwenden. Für eine Nachdruckgenehmigung wenden Sie sich bitte an den Backstage-Bereich des öffentlichen WeChat-Kontos „Fanpu“.