Künstliche Dummheit: Die Algorithmen eines Google-Ingenieurs für schlechtes Schachspiel

Was passiert, wenn wir modernste moderne Technologien auf das uralte Schachspiel anwenden? Und was passiert, wenn ein gelangweilter Geek mit einem Überschuss an Rechenleistung seine eigenen seltsamen Heimexperimente am Spiel durchführt?

In diesem Jahr beschloss ein Softwareentwickler aus Pennsylvania, der sich Tom Murphy VII nennt, einige lächerlich schlechte Schachspielalgorithmen zu erstellen, die alles von maschinellem Lernen und neuronalen Netzen bis hin zu einer grundlosen Anzahl von CPU-Zyklen verwendeten — und dann die schlechten Algorithmen gegeneinander ausspielten, um ein „Turnier der Narren“ zu schaffen.“

„Es ist meine Vorstellung von Spaß…“, sagt Murphy in einem humorvollen Video, das die Experimente beschreibt.

Erste Züge

Murphy hat die Intelligenz, es durchzuziehen. Er erzählt uns, dass er 2007 seinen Doktortitel in Informatik verteidigt hat. an der Carnegie Mellon – im selben Jahr begannen die Studenten, am Aprilscherz die jährliche SIGBOVIK-Konferenz abzuhalten. Gesponsert von der „Association for Computational Heresy,Es war eine Art satirische Interessengruppe, die sich einem fiktiven Forscher namens „Harry Quizmaster Bovik“ widmete,“Und einschließlich eines Aufrufs zu albernen Papieren zu Themen wie „künstliche Dummheit.“

In den letzten 11 Jahren war Murphy leitender Softwareentwickler bei Google (in seinen Büros in Pittsburgh). Aber dieses Jahr entschied er sich, wieder für die Aprilscherzkonferenz zurückzukehren – und steuerte wieder einige humorvolle Recherchen bei.

Murphy prahlt stolz damit, dass einige seiner früheren Präsentationen lächerliche Untersuchungen beinhalteten, die „nicht von“echter“ Forschung zu unterscheiden waren (zum Beispiel ist die erste Ebene von Super Mario Bros. einfach mit lexikographischen Ordnungen und Time Travel hat einige 20 Zitate in „echter“ akademischer Forschung).

Aber in diesem Jahr wandte sich Murphy dem Schach zu.

Lass die Spiele beginnen

In Murphys erstem Spiel haben menschliche Spieler die Augen verbunden und müssen sich daran erinnern, wo sich die Teile befinden. Aber was ist das Äquivalent für einen Computer? Sagen Sie ihm, wo sich Teile befinden, aber nicht, um welche Teile es sich handelt (oder sogar welche Farbe)…

Natürlich würde der Computer auch nicht mit den Zügen versorgt, die zu einer Position führen. Es würde nicht einmal wissen, wer an der Reihe war. Ja, es besteht die Möglichkeit, dass der König des Computers in Schach ist — an diesem Punkt ist so ziemlich jede Bewegung illegal, außer einer Bewegung, die Ihren König in Sicherheit bringt. Aber um das zu umgehen, Tom hat ein Programm erstellt, das eine Liste möglicher Züge generiert, in der Reihenfolge Ihrer Präferenz geordnet — aus denen der erste legale Zug ausgewählt wird.

„Ich spiele gerne dagegen, weil es nicht sehr gut ist“, sagt Murphy im Video. „Aber die natürliche Frage ist, wie nicht-sehr-gut ist es?“ Das Testen gegen Schachspielprogramme beweist, dass ja, es verliert mit großer Regelmäßigkeit – wie in, „jedes Mal.“

Dann machte er sich daran, andere schlechte Schachspielalgorithmen zu bauen, damit er ihre relative Leistung vergleichen konnte …

Man hatte eine Vorliebe dafür, seine Figuren auf die weißen Quadrate zu legen, wenn es weiß spielt, und auf schwarze Quadrate, wenn es schwarz spielt. (Sein Gegner? Ein Algorithmus, der es vorzog, seine Teile auf entgegengesetzt farbige Quadrate zu legen.) Am Ende spielten beide ziemlich schlecht. „Sie haben eine Vorliebe, aber es hat nicht wirklich mit Gewinnen zu tun.“ Tatsächlich sind sie beide nur ein bisschen schlechter als der Algorithmus, der seine Züge zufällig auswählt.

Es gab auch zwei Algorithmen, die er „Huddle“ und „Swarm“ nannte — bei denen ein automatisierter Spieler nach Zügen sucht, die seine Figuren in der Nähe seines eigenen Königs halten, während der andere nach Zügen sucht, die seine Figuren in der Nähe des gegnerischen Königs platzieren. Dies führt manchmal dazu, dass Huddles König gezwungen ist, seinen eigenen Bauern auf der ganzen Linie zu folgen, wobei zumindest in einigen Fällen sein Bauer dann versehentlich in mächtigere Stücke befördert und versehentlich den gegnerischen König Schachmatt gesetzt hat.

Aber öfter funktioniert es umgekehrt. „Wenn du es vorziehst, den Gegner anzugreifen, wirst du ihn manchmal versehentlich Schachmatt setzen.“ In dem Video enthüllt Murphy, dass dieser unter den schlechten Schachalgorithmen überraschenderweise nicht so schlecht ist. „‚Swarm’ist in der Tat viel besser als’Random Move.““

Und eine weitere erfolgreiche Strategie ist ein Algorithmus, der vier spezifische Arten von Zügen (in dieser Reihenfolge) priorisiert: Schachmatt, Check, capture a piece oder push into its opponent’s territory.

Aber es gibt noch andere schreckliche Ideen — wie einen Algorithmus, der versucht, die Figuren seines Gegners zu spiegeln oder alle seine Figuren auf die andere Seite des Bretts zu verschieben. Ein Algorithmus wählt einfach, welcher Zug zuerst in alphabetischer Reihenfolge kommt.

Und es gibt einen anderen Algorithmus, bei dem jeder Zug aus einer Liste möglicher Züge ausgewählt wird – wobei die Auswahl willkürlich durch die Ziffern von pi bestimmt wird …

Überleben im Schachland

Aber letztendlich begann sein ausgefeiltester Algorithmus mit einer Frage: welche einzelne Schachfigur wird am ehesten „überleben“ — bis zum Ende des Spiels auf dem Brett bleiben und mit allen anderen Schachfiguren als Sieger hervorgehen? Pflichtbewusst untersuchte Murphy die Antwort und besuchte die free / libre Chess-Site LiChess.org (das sieht jetzt mehr als eine Million Spiele pro Tag). Es bietet auch Spiele zum Herunterladen — so Murphy heruntergeladen alle 506.000.416 von ihnen.

Er fasste die Ergebnisse in einem Papier mit dem Titel „Survival in Chessland“ zusammen, das seine Methodik erklärt. Murphy hat jedes komplette Spiel heruntergeladen, das sie bis November 2018 hatten – obwohl in den acht Monaten seitdem anscheinend weitere 200 Millionen verfügbar geworden sind. Sogar sein November-Haul repräsentierte satte 875 GB Schachspiele, „also wurde bei der Verarbeitung auf Effizienz und Parallelität geachtet“, sagt Murphy in dem Video.

„Zum Glück habe ich einen Computer mit nur einer obszönen Anzahl von Kernen und wirklich übermäßigem RAM, also musst du das für etwas verwenden.“

Äh, wie obszön? In einer E-Mail beschreibt er sein „unentgeltliches“ Heimsystem, einen 32-Kern AMD ThreadRipper 2990WX. Das Ausführen der Multithread- C ++ – Programme für einige Stunden reichte aus, um den gesamten Datensatz zu durchsuchen. „Ich denke, die Leute unterschätzen, was man mit einer einzigen Maschine effizient machen kann!“

“ Die Arbeit ist ziemlich einfach: Ich analysiere die PGN (die das Spiel beschreibt), führe dann die Züge im Spiel aus, verfolge das Schicksal jedes Stücks und summiere dann die Zählungen für jedes Schicksal …“

„Ich habe im Grunde den gesamten Code von Grund auf neu geschrieben, weil das mehr Spaß macht, als den Code anderer Leute zum Laufen zu bringen. :)“

Und dann führte dies zu mehr schlechten Schachspielalgorithmen. Erstens gibt es dasjenige, das nur Teile auf die Quadrate bewegt, auf denen sie statistisch gesehen eher überleben. Oder einfach zu den Plätzen, wo sie am Ende eines Spiels am wahrscheinlichsten sind. Und andere Algorithmen machen genau das Gegenteil – Bewegen von Teilen zu Quadraten, wo sie am wenigsten überleben (oder enden). Zwei Algorithmen berechnen, welches Quadrat die höchste Überlebensrate (im Vergleich zur Erfassungsrate) für ein Stück auf jedem Quadrat hat, wobei ein Algorithmus das höchste Verhältnis sucht, das das Überleben begünstigt — und der „fatalistische“ Algorithmus das niedrigste Verhältnis.

„Seltsamerweise hat es die besten Gewinnchancen dieser Strategien.“

Und schließlich beschloss er, sie alle auf mehreren Ebenen mit der Stockfish-Schachengine zu vergleichen (einschließlich eines speziellen Algorithmus, bei dem sie gezwungen ist, ihren am wenigsten vielversprechenden Zug zu spielen). „Wenn man sich die Ergebnisse ansieht, überrascht es nicht, dass dies die insgesamt schlechteste Strategie ist und es gelingt, gegen fast alle zu verlieren.“

Aber erinnerst du dich an Toms ursprünglichen „Blindfolded“ -Algorithmus, der nicht wusste, welches Stück ein Quadrat (oder sogar seine Farbe) besetzte? Er beschloss, es mit einem neuronalen Netzwerk zu erweitern, das maschinelles Lernen durchführte — unter Verwendung der Milliarden von Positionen, die in den Spielen von LiChess verfügbar waren.Organisierungstafel. Es war jetzt in der Lage, die tatsächlichen Teile an jeder Position mit 100% Genauigkeit korrekt vorherzusagen … etwa ein Fünftel der Zeit. Und selbst wenn es falsch ist, ist es nur falsch erraten durchschnittlich 3,22 Stück für jede Position.

Und dies wird zum Ausgangspunkt für noch wildere Berechnungen. Irgendwann folgert er, dass alle Spiele in ihrer Datenbank schließlich 21.553.382.902 eindeutige Positionen durchlaufen. Mit 204GB könnte man sie alle speichern – zusammen mit dem nächsten Zug — aber es gibt noch eine andere interessante Statistik. Satte 76% der Positionen traten genau einmal auf. „Diese nehmen also viel Platz in Anspruch und sind nicht sehr nützlich zum Spielen, da ich sie wahrscheinlich nie wieder sehen werde.“ Wenn man diese einmaligen Positionen wegwirft, kann jede andere mögliche Spielposition mit etwa 500 MB Speicher gespeichert werden. Dies kann leicht in einen Algorithmus umgewandelt werden, der den beliebtesten Zug für jede Position spielt, auf die er trifft (während er einen zufälligen Zug austauscht, wenn er sich in einer einzigartigen Position befindet).

Aber dann gibt es einen einfachen Trick, um es zu schlagen. „Sobald ich einen seltsamen Zug mache, beginnt es einfach zufällig zu spielen. Und dann ist es sehr leicht zu schlagen.“

Ein abschließendes Experiment beinhaltet verschiedene „Verdünnungen“ des Stockfisch—Motors – in dem seine bevorzugte Bewegung durch eine zufällig gewählte Bewegung x Prozent der Zeit ersetzt wird.“

„Wir können jetzt tatsächlich beurteilen, wie gut ein Spieler ist, indem wir ihn direkt mit einer bestimmten Verdünnung von Stockfisch vergleichen …“

Nachdem alle ausgeklügelten Schachspielalgorithmen von Murphy pflichtbewusst getestet worden waren, fasste er die Ergebnisse in einer riesigen Tabelle zusammen und schloss sein Video triumphierend ab, indem er ankündigte, dass er endlich bereit sei, anderen Interessen nachzugehen.

„Jetzt geht es zum nächsten Projekt, das diesem Hund das Schachspielen beibringt.“

• Was passiert, wenn maschinelles Lernen die Menschheit zu Antworten führt, die wir nicht verstehen?
• Lernen Sie Sophie kennen, den Nudelroboter.
• Nach 15 Jahren enthüllen Forscher einen künstlichen Arm, der fühlen kann.