NNUE (revertiertes Akronym für , ursprünglich gespiegelt ИИUƎ geschrieben,Yu Nasu: ИИUƎ – Efficiently Updatable Neural-Network-based Evaluation Functions for Computer Shogi. Publikation zur 28. Computer-Shogi-Weltmeisterschaft. 28. April 2018. ) 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 mini|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 ausEvolution 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. und bildete dazu aus den Anfangsbuchstaben von Efficiently Updatable Neural Network, also EUNN, das Inverse ИИUƎ.Yu Nasu: ИИUƎ – Efficiently Updatable Neural-Network-based Evaluation Functions for Computer Shogi. Publikation zur 28. Computer-Shogi-Weltmeisterschaft. 28. April 2018, S. 1. Lautmalerisch ergibt sich so darüber hinaus die Assoziation zu , 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.Stockfish goes NN (englisch): „A new revolution in computer chess is taking place…“ Abgerufen am 22. September 2020. 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:Much stronger Stockfish NNUE now as option in Stockfish development builds (englisch), abgerufen am 2. Oktober 2020.
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.stockfish-nnue-2020-05-30 (englisch), abgerufen am 2. Oktober 2020. 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:Stockfish 12 (englisch), abgerufen am 2. Oktober 2020.
NNUE ersetzt bei Stockfish 12 optional (Parameter: Use NNUE) die herkömmliche Bewertungsfunktion.Introducing NNUE Evaluation im Stockfish Blog, abgerufen am 29. August 2020. 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.Stockfish schluckt NNUE und verbessert seine Leistung um 100 Elo Punkte, abgerufen am 29. August 2020.
Danach folgten weitere Schach-Engines wie RubiChess (Version 1.8 NNUE),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. Minic (Version 2.48 NNUE), Orion (Version 0.7.nnue)Orion 0.7 : NNUE experiment (englisch), abgerufen am 26. September 2020. und Igel (Version 2.70 NNUE),Igel and NNUE (englisch), abgerufen am 24. September 2020. die mithilfe von NNUE ihre Spielstärke teilweise um mehr als zweihundert Elo-Punkte steigern konnten.Speedy Ratings (englisch), abgerufen am 22. September 2020. 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.Zeus 9.3 NNUE wins JCER Fritz Tournament (englisch), abgerufen am 22. September 2020.
Seit Februar 2024 wird zum ersten Mal in der Version Stockfish 16.1 ein sekundäres neuronales Netzwerk, genannt Dual NNUE verwendet, das zur schnellen Bewertung leicht zu entscheidender Positionen dient. Der oben genannte Parameter Use NNUE entfiel. NNUE wurde zur standardmäßig aktivierten alleinigen Bewertungsfunktion.Stockfish 16.1 (englisch), abgerufen am 27. Februar 2024.
Prinzip mini|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.Conrad Schormann: Stockfish 12 – das Beste aus zwei Welten, in Perlen vom Bodensee – das Schachmagazin vom 5. September 2020, abgerufen am 17. September 2020.
Struktur mini|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 (), 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
Kategorie:Computerschach Kategorie:Abkürzung Kategorie:Spieltheorie Kategorie:Suchalgorithmus Kategorie:Künstliche Neuronale Netze