Das Geheimnis des alten Go-Spiels. Warum hat der Computer noch keinen Mann geschlagen?


    Remy Kul (links) mit dem Crazy Stone-Computerprogramm gegen Großmeister Norimoto Yoda

    1994 besiegte der Computer den Weltmeister im Draft 1997 - im Schach. Heutzutage sind Computer Menschen in absolut allen populären Spielen mit vollständigen Informationen überlegen , mit einer Ausnahme.

    Ein klassisches Spiel mit einer 2500-jährigen Geschichte hat sehr einfache Regeln, aber Computerprogramme können nicht annähernd die besten Großmeister gewinnen, schreibt Wired.

    Das alte Spiel kann als "östliche Version des Schachs" betrachtet werden. Wie beim Schachspiel handelt es sich um ein Spiel mit vollständigen Informationen, dh zu jedem Zeitpunkt des Spiels verfügen alle Spieler über vollständige Informationen über den Status des Spiels und können mit diskreten Aktionen auf das Spiel einwirken. Hier hängt der Erfolg nicht vom Glück oder der Reaktionsgeschwindigkeit ab.

    Trotz der zunehmenden Rechenleistung von Computern (der heutige Schachweltmeister wird wahrscheinlich sogar an Ihren Heim-PC verlieren) bleiben die Algorithmen für das Spielen auf Expertenebene ungelöst und eine der interessantesten Aufgaben der KI. Das Problem ist, dass nur sehr wenige in der Lage sind, bis zum neunten Dan im Spiel aufzusteigen. Dazu müssen Sie mehrere Jahre in Japan oder Korea studieren. Dort werden begabte Kinder ab ca. 9 Jahren von zu Hause mitgenommen, um an der Go Academy zu studieren.

    Fortgeschrittene Amateure stecken fast immer auf einem bestimmten Level des Spiels fest und können das Ergebnis nicht verbessern: "Es erfordert einen mentalen Sprung, um diese Sperre zu entfernen, und das gleiche Problem besteht in der Softwareentwicklung", erklärt David Fotland, leitender Entwickler von PA-RISC bei Hewlett Packard Company in den 70er Jahren. Er testete das Go-Programm auf seinem Entwicklungsprozessor. "Die Frage ist, wie man das gesamte Board bewertet, nicht die einzelnen Fragmente."

    Das Spiel ist seit langem nicht nur im Osten, sondern auch im Westen beliebt, insbesondere bei Mathematikern und Physikern. Zum Beispiel spielte Einstein oft Go, genau wie die berühmten Mathematiker John Nash und Alan Turing.

    Computerprogramme für unterwegs werden seit 45 Jahren entwickelt, diesem Problem wurde fast ebenso viel Aufmerksamkeit geschenkt wie Schachprogrammen. Der erste wurde 1968 vom Genie der Spieltheorie Alfred Zobrist geschrieben. Sie konnte einen absoluten Anfänger schlagen, der gerade die Regeln erfüllt hatte ( Aufnahme des ersten Mensch-Computer-Spiels ). Der Anfang schien optimistisch. In den nächsten vier Jahrzehnten wurde eine enorme Menge an Zeit und intellektueller Anstrengung aufgewendet, aber selbst unter Berücksichtigung der Fortschritte bei der Rechenleistung konnten die Programme nicht einmal einen fortgeschrittenen Amateur besiegen.

    Der Grund kann durch den Vergleich mit Schach verstanden werden. Zu Beginn des Schachspiels hat Weiß 20 mögliche Züge und Schwarz 20 mögliche Antworten. Nach dem ersten Zug können 400 verschiedene Positionen auf dem Brett sein. Vergleichen Sie nun die Zahlen in go: Auf dem 19x19-Brett hat Schwarz 361 mögliche Anfangszüge, während Weiß 360 mögliche Antworten hat. Dies bedeutet 129.960 mögliche Kombinationen erst nach der ersten Runde.

    Der sogenannte "Verzweigungsfaktor" - die durchschnittliche Anzahl von Zügen, die in jeder Runde zur Verfügung stehen - beträgt im Schach 35, im Los 250. Spiele mit starker Verzweigung erschweren die Arbeit von Standardalgorithmen, die die Minimax-Regel verwenden, um einen Baum möglicher Kombinationen zu erstellen. Auch unter Berücksichtigung der Analyse nicht alle, sondern nur vielversprechende Branchen für eine tiefere Analyse. Was bei Dame und Schach funktioniert, funktioniert bei Go nicht. Die Auswahl vielversprechender Zweige im Baum möglicher Go-Kombinationen ist oft ein völlig mysteriöser Prozess. Sogar die Spieler verstehen nicht, wie sie es machen: "Man schaut nur auf das Brett und weiß," sagen sie.



    Auch beim Schach kann man fast immer nachvollziehen, wer gewinnt, zumindest an der Anzahl der Figuren. In go können nur Experten die Situation interpretieren.

    Die durchschnittliche Anzahl von Zügen in einem Spiel: im Schach - ungefähr 40, im Los - 200. Angesichts des Verzweigungsfaktors und dieser Statistiken wird die Impotenz von Computern deutlich.

    Der talentierte französische Programmierer Rémi Coulom erzielte 2006 seinen ersten Erfolg mit dem Crazy Stone-Programm, als er vermutete, Minimax und Monte Carlo zu kombinieren. Er nannte den neuen Algorithmus zur Astbaumberechnung Monte Carlo Tree Search oder MCTS. Der Franzose gewann 2007 und 2008 die UEC Cup- Computerprogramm- Meisterschaft , wurde jedoch nie berühmt, und Remy gab die Entwicklung auf. 2010 erhielt er ein Angebot des japanischen Spieleentwicklers Unbalance - und 2011 erschien die erste kommerzielle Version von Crazy Stone. Im Jahr 2013 kehrte Remy triumphierend in die Meisterschaft zurück.

    2014 gab es jedoch einen Misserfolg. Bei der letzten Konfrontation mit dem Zen-Programm stellten die Zuschauer fest, dass nach dem dritten Zug etwas Merkwürdiges passierte. Das Zen-Programm legte nach der Standardeinstellung von zwei Steinen in den Ecken plötzlich einen dritten Stein in die Nähe der Mitte. Niemand hat so gespielt, es war eindeutig eine "nicht-menschliche" Entscheidung. Bald stieg das Niveau der Gewinnerwartungen bei Crazy Stone auf unangemessen hohe Werte, mehr als 60%. Anscheinend betrachtete das Programm die Gruppe der Steine ​​in der oberen rechten Ecke als sicher, obwohl es nicht sicher war. Da eine erfolgreiche Strategie direkt von der richtigen Bewertung des Boards abhängt, begann das Publikum über die mögliche Niederlage von Crazy Stone zu flüstern. Und so geschah es: Im 186. Zug kassierte Crazy Stone eine Niederlage und Zen wurde der neue Champion des UEC-Pokals.

    Kulom hatte jedoch immer noch die Chance, sich zu rächen. Als Finalist erhielt er das Recht, gegen einen echten menschlichen Großmeister mit einem Vier-Steine-Handicap zu spielen. Dieses Jahr kam Norimoto Yoda zum Turnier. Der japanische Großmeister saß in einem traditionellen grünen Kimono am Tisch. Remy Cool - trug eine randlose Brille und einen blauen Pullover, in dem er bei der letzten Meisterschaft war.

    Die professionellen Kommentatoren, die die Online-Übertragung der Party begleiteten, waren sich einig, dass Crazy Stone gut spielt und sogar einen Vorteil hat. Das Essen war extrem genervt und sah streng aus, und Kulom schaute auf den Laptop, dann auf den Spielplan, dann auf den Chronometer - überall, aber nicht auf das Essen.

    Crazy Stone erlitt am Ende eine traurige Niederlage. Jede Person, die 11 Steine ​​gewinnt, würde mehrere offensichtliche Verteidigungsbewegungen ausführen, um zu verhindern, dass der Feind einen Vorteil wiedererlangt und beibehält. Aber Crazy Stone war nur darauf programmiert, zu gewinnen. Daher sollte ihr Algorithmus in einer Gewinnsituation bedeutungslose Züge in ihrer eigenen Zone ausführen und darauf warten, dass der Gegner die Niederlage zugibt. Aber hier hat ein solcher Trick nicht bestanden - und Yoda hat es geschafft, wieder hereinzukommen. Im zweiten Match gegen Zen sah er schon besser aus und gewann vier Steine ​​im Programm.



    Remy Kulam war trotzdem glücklich - und versprach, den Algorithmus der Aktionen am Ende für die nächste Meisterschaft fertigzustellen.

    Anscheinend wird der Computer bald das letzte Spiel mit vollständigen Informationen gewinnen, die für die Person verbleiben. Laut Kuloma wird das Programm innerhalb von 10 Jahren ohne Handicap gewinnen. Experten, die die Macht der besten Spieler kennen, sind sich nicht so sicher. Tatsache ist, dass bei höheren Levels das Spiel ein qualitativ anderes Level erreicht und die Spielzüge nicht mehr vorhersehbar sind. Gleichzeitig hängt die Qualität von Spielprogrammen weniger von der Rechenleistung als von der Codequalität ab: Beispielsweise besiegten derselbe Crazy Stone und das gleiche Zen auf 64-Core-Standardservern problemlos 2048-Core-Cluster von Gegnern. Das heißt, Programme können wieder gegen die Wand stoßen.

    Aber selbst wenn Computer gewinnen, können Sie nicht über den "Fall der letzten intellektuellen Bastion" sprechen, in der die Menschen dominieren, wie die Zeitungen nach dem Sieg von Deep Blue im Schach geschrieben haben. Programme für unterwegs sind einfach hochspezialisierte Werkzeuge zur Lösung spezifischer Probleme. Sie sind sehr weit vom menschlichen Verstand entfernt und versuchen nicht, die Arbeit des Gehirns nachzuahmen. "Für mich ist es nur Spaß", sagt Kulom, "nichts mehr."

    Jetzt auch beliebt: