NNUE

NNUE (revertiertes Akronym für englisch Efficiently Updatable Neural Network, ursprünglich gespiegelt ИИUƎ geschrieben, deutsch „Effizient aktualisierbares neuronales Netz“) ist eine spezielle Architektur eines neuronalen Netzwerks, das – anders als üblich – nicht auf Grafikprozessoren (GPU) angewiesen ist, sondern bereits auf dem Zentralprozessor (CPU) eines Computers effizient läuft.

Wichtige Anwendung ist der Ersatz der klassischen Bewertungsfunktion in Computerbrettspielen, insbesondere beim Computerschach, wodurch eine erhebliche Steigerung der Spielstärke erreicht wird.

Namensgebung

Nue ist ein Mischwesen aus der japanischen Mythologie mit dem Kopf eines Affen, dem Körper eines Marderhunds, den Beinen eines Tigers und einer Schlange als Schwanz.

Als Namenspaten wählte der Entwickler das japanische Fabelwesen Nue aus und bildete dazu aus den Anfangsbuchstaben von Efficiently Updatable Neural Network, also EUNN, das Inverse ИИUƎ. Lautmalerisch ergibt sich so darüber hinaus die Assoziation zu englisch New, also Neu.

Geschichte

NNUE wurde von dem japanischen Softwareentwickler Yu Nasu für das Computer-Shōgi, einer japanischen Variante des Computerschachs, entwickelt und in seiner zur 28. Computer-Shōgi-Weltmeisterschaft veröffentlichten Publikation im April 2018 vorgestellt (siehe Literatur). Grundidee ist, die durch menschliche Experten oft über viele Jahre hinweg mühsam heuristisch optimierte Bewertungsfunktion durch eine maschinell erzeugte zu ersetzen. Hierzu wird vorab ein neuronales Netzwerk, bestehend aus nur vier Schichten, anhand von vielen Millionen Schachstellungen automatisch trainiert und das so optimierte Netzwerk anschließend, als neuer Teil des Schachprogramms, zur Stellungsbewertung genutzt.

Die neue Methode wurde zunächst öffentlich wenig wahrgenommen und vermutlich von einigen völlig unterschätzt, bis die Meinung umschlug und sie als „Revolution“ bezeichnet wurde. Der niederländische Computerschach-Pionier Ed Schröder, Programmierer des legendären Schachprogramms Rebel, das 1992 die Computerschachweltmeisterschaft (WCCC) gewann, schrieb im Sommer 2020 zu NNUE:

“A new revolution in computer chess is taking place, in my opinion, it will (once again) change computer chess dramatically the coming years looking at the first results.”

„Eine neue Revolution im Computerschach findet statt, meiner Meinung nach wird sie (noch einmal) das Computerschach in den kommenden Jahren dramatisch verändern, wenn man die ersten Ergebnisse betrachtet.“

– Ed Schröder

Dies geschah, kurz nachdem es im Mai 2020 einen ersten „Proof of Concept“ für NNUE zusammen mit einer Schach-Engine (nicht Shōgi) gegeben hatte. Probeweise wurde es in eine Entwicklungsversion des freien Schachprogramms Stockfish implementiert. Nachdem dies erfolgreich gelungen war, wurde ab August 2020 NNUE regulärer Bestandteil der auf Stockfish 11 basierenden neuen Entwicklungsversionen. Am 2. September 2020 schließlich wurde die Version Stockfish 12 mit dem folgenden Kommentar veröffentlicht:

“This version of Stockfish plays significantly stronger than any of its predecessors. In a match against Stockfish 11, Stockfish 12 will typically win at least ten times more game pairs than it loses.”

„Diese Version von Stockfish spielt deutlich stärker als alle ihre Vorgänger. In einem Match gegen Stockfish 11 gewinnt Stockfish 12 normalerweise mindestens zehnmal mehr Spielpaare als es verliert.“

– stockfishchess.org

NNUE ersetzt bei Stockfish 12 optional (Parameter: Use NNUE) die herkömmliche Bewertungsfunktion. Bereits nach weniger als einem Monat zeigte sich der neue „Stockfish + NNUE“ gegenüber dem bisherigen (ohne NNUE) um mehr als hundert Elo-Punkte verbessert. Eine Spielstärkesteigerung um solch einen Wert benötigt in der Regel etwa zwei Jahre traditioneller Entwicklungsarbeit und beweist das Potenzial der neuen Methode.

Danach folgten weitere Schach-Engines wie RubiChess (Version 1.8 NNUE), Minic (Version 2.48 NNUE), Orion (Version 0.7.nnue) und Igel (Version 2.70 NNUE), die mithilfe von NNUE ihre Spielstärke teilweise um mehr als zweihundert Elo-Punkte steigern konnten. Auch Programme wie Zeus (Version 9.3 NNUE), Cfish (Version 180820 NNUE), AI (Version 13.3 NNUE), ShashChess (Version 13 NNUE), BrainLearn (Version 10 NNUE) und CorChess (Version NNUE 170820) setzten NNUE mit Erfolg ein und erreichten damit obere Plätze bei Computerschachturnieren.

Prinzip

Alpha-Beta-Suche

Zur Ermittlung der optimalen Spielstrategie für endliche Zwei-Personen-Nullsummenspiele mit perfekter Information wird grundsätzlich der Minimax-Algorithmus benutzt. Zu diesen Spielen gehören Brettspiele, bei denen beide Spieler den kompletten Spielverlauf der Partie sowie die aktuelle Position kennen. Beispiele sind Schach, Go, Othello, Dame, Mühle und Vier gewinnt. Eine optimierte Variante dieses Algorithmus ist die Alpha-Beta-Suche (Bild).

Ein wichtiger und zeitkritischer Bestandteil des Algorithmus ist die Berechnung der Bewertungsfunktion am Ende jeder Verzweigung des Suchbaums (am unteren Rand im Bild). Je besser die Brettstellung für den zu betrachtenden Spieler ist, desto größer ist der Wert dieser Funktion. Ist die Stellung ausgeglichen, dann ist der Wert null. Gesucht wird der nächste Zug, der, bei angenommenem, nach Möglichkeit optimalem Gegenspiel, den höchsten Wert ergibt und damit die Gewinnwahrscheinlichkeit maximiert. Da dazu oft Millionen von unterschiedlichen Positionen betrachtet und bewertet werden müssen, ist zeitliche Effizienz bei der Berechnung der Bewertung von entscheidender Bedeutung.

Falls der Algorithmus sowie der Rest des Spieleprogramms komplett auf GPUs läuft, ist es zweckmäßig, auch die Bewertungsfunktion mit deren Hilfe berechnen zu lassen. Allerdings ist meist die Programmierung von GPUs, insbesondere für Computerspiele-Software, deutlich aufwendiger, komplizierter und fehlerträchtiger als mithilfe von CPUs. Auch sind viele leistungsfähige Spieleprogramme (aus historischen Gründen, da damals noch keine GPUs zur Verfügung standen) auf CPUs entstanden und optimiert worden. Eine Portierung des Programm-Codes ist daher nicht sinnvoll und wäre sehr aufwendig.

Darüber hinaus sollen für Spieleprogramme allgemein keine leistungsfähigen GPUs für die Lauffähigkeit des Programms vorausgesetzt werden müssen. Daher laufen sie in der Regel auf CPUs. Wenn man allerdings für die Bewertungsfunktion neuronale Netzwerke einsetzen will und sie, wie es fast immer gemacht wird, auf GPUs implementiert, ergibt sich ein „Flaschenhals“ bei der laufenden Datenübertragung zwischen CPU und GPU, der die Effizienz des Spieleprogramms konterkariert.

Ein innovativer Aspekt von NNUE fußt auf der Idee, den Flaschenhals dadurch zu vermeiden, dass auch das neuronale Netz, anders als üblich, auf der CPU läuft und so die Kommunikation mit dem Rest des Programms ohne jeden Zeitverzug direkt möglich ist.

Struktur

Vierlagiges neuronales Netzwerk hier als vereinfachtes Beispiel und anders als bei NNUE mit nur 8 Eingängen (oben).

Wie schon erwähnt, besteht das neuronale Netzwerk aus vier Schichten. Dabei ist die erste Schicht stark überparametrisiert. Anders als im Bild hat sie nicht 8, sondern 82.048 Eingänge. Durch sie wird die interne Brettdarstellung für alle Positionen des weißen und schwarzen Königs eingespeist. Gearbeitet wird hier mit der sogenannten HalfKP-Struktur. Sie besteht aus zwei Hälften (englisch Half), die jeweils die Eingangsschicht und die erste verborgene Schicht umfassen. Der Buchstabe K steht für den König. Außer den Königen gibt es für jede Seite noch fünf andere Spielsteine, englisch pauschal Pieces genannt, in Summe zehn „Nicht-König“-Steine, bezeichnet mit P.

Jede der beiden Hälften der HalfKP-Struktur ist einem der beiden Könige zugeordnet. Der König (K) kann auf einem von 64 Feldern stehen. Dies gilt ebenso für jeden der zehn unterschiedlichen „Nicht-König“-Steine (P). Dass auf jedem Feld nur höchstens ein Stein stehen kann, ist selbstverständlich, wird aber aus Vereinfachungsgründen (KISS-Prinzip) hier nicht berücksichtigt. Insgesamt gibt es somit 64 Positionen für K mal 64 Positionen für P mal 10 unterschiedliche P. Als Produkt ergibt sich 64·64·10 = 40.960. Aufgrund eines hier unwichtigen Relikts aus den Ursprüngen der Shōgi-Programmierung erhöht sich diese Zahl auf 64·(64·10+1) = 41.024. Dies ist die Anzahl der Eingänge jeder Hälfte der HalfKP-Struktur des neuronalen Netzwerks. Für beide Hälften zusammen sind es folglich 82.048 Eingänge. Die Eingangswerte für jede Hälfte werden mit einer 16-Bit-Ganzzahl-Gewichtung für 256 Ausgänge pro Hälfte multipliziert. Insgesamt gibt es hier pro Hälfte 41.024·256 = 10.502.144 Gewichte.

Die 2·256 Ausgangswerte der ersten Schicht werden durch die zweite Schicht mithilfe von 2·256·32 Gewichtungswerten auf 32 Ausgangswerte reduziert. Dadurch werden auch die zuvor getrennten beiden Hälften zusammengefasst. Die nun 32 Ausgänge werden in der dritten Schicht alle miteinander verknüpft. Es gibt somit weitere 32·32 Gewichtungswerte. Diese werden schließlich mithilfe von 32 letzten Gewichtungswerten in der vierten Schicht zum finalen Ergebnis verknüpft: der Bewertung der Schachstellung.

Die Effizienz von NNUE basiert ganz wesentlich auch darauf, dass aufgrund der beschriebenen Architektur bei jedem Zug, vorausgesetzt es ist kein Königszug, nur ein kleiner Bruchteil aller Neuronen der ersten Schicht aktualisiert werden muss. Man spricht hier von einer inkrementellen Aktualisierung. Im Gegensatz zur extrem effizient arbeitenden ersten Schicht sind die übrigen drei Schichten zwar rechenintensiver, aber in Summe erweist sich dieses ursprünglich für Shōgi entwickelte Konzept auch beim Schach als sehr erfolgreich.

Literatur

• Yu Nasu: ИИUƎ – Efficiently Updatable Neural-Network-based Evaluation Functions for Computer Shogi. Publikation zur 28. Computer-Shogi-Weltmeisterschaft vom 28. April 2018. PDF; 250 kB (japanisch und teilweise englisch).

Weblinks

• Stockfish schluckt NNUE und verbessert seine Leistung um 100 Elo Punkte bei Chess.com.
• NNUE im Chess Programming Wiki (englisch).
• Stockfish NNUE im Chess Programming Wiki (englisch).
• Partie von Leela Chess Zero gegen Stockfish NNUE (kommentiertes YouTube-Video; englisch).
• Logo von Stockfish NNUE.

Einzelnachweise

1. Yu Nasu: ИИUƎ – Efficiently Updatable Neural-Network-based Evaluation Functions for Computer Shogi. Publikation zur 28. Computer-Shogi-Weltmeisterschaft. 28. April 2018.
2. Evolution of a Chess Fish: What is NNUE, anyway? „What does NNUE stand for? NNUE stands for Efficiently Updateable Neural Network. It's "NNUE" instead of "EUNN" because the technique was adopted from a shogi engine, and NNUE is wordplay in Japanese.“ (englisch), mit Link zum Artikel Nue in der englischsprachigen Wikipedia, abgerufen am 31. Dezember 2020.
3. Yu Nasu: ИИUƎ – Efficiently Updatable Neural-Network-based Evaluation Functions for Computer Shogi. Publikation zur 28. Computer-Shogi-Weltmeisterschaft. 28. April 2018, S. 1.
4. Stockfish goes NN (englisch): „A new revolution in computer chess is taking place…“ Abgerufen am 22. September 2020.
5. Much stronger Stockfish NNUE now as option in Stockfish development builds (englisch), abgerufen am 2. Oktober 2020.
6. stockfish-nnue-2020-05-30 (englisch), abgerufen am 2. Oktober 2020.
7. Stockfish 12 (englisch), abgerufen am 2. Oktober 2020.
8. Introducing NNUE Evaluation im Stockfish Blog, abgerufen am 29. August 2020.
9. Stockfish schluckt NNUE und verbessert seine Leistung um 100 Elo Punkte, abgerufen am 29. August 2020.
10. Evolution of a Chess Fish: What is NNUE, anyway? „And since its release there has been a wave of projects implementing NNUE: Dragon, Igel, Minic, RubiChess, and others. All reported huge strength improvements upon switching.“ (englisch), abgerufen am 31. Dezember 2020.
11. Orion 0.7 : NNUE experiment (englisch), abgerufen am 26. September 2020.
12. Igel and NNUE (englisch), abgerufen am 24. September 2020.
13. Speedy Ratings (englisch), abgerufen am 22. September 2020.
14. Zeus 9.3 NNUE wins JCER Fritz Tournament (englisch), abgerufen am 22. September 2020.
15. Conrad Schormann: Stockfish 12 – das Beste aus zwei Welten, in Perlen vom Bodensee – das Schachmagazin vom 5. September 2020, abgerufen am 17. September 2020.