Strength estimation in the game of go

Abstract

To quantify the performance of players in the game of Go and other competitive domains, we usually employ a paired comparison rating system like Elo or Glicko-2. Such systems assign a rating to a player based solely on their win/loss record. In this work, we compare an implementation of the classical rating system Glicko-2 with a newly developed approach based on a learned strength model. This model uses information about all of a player's moves played in available recent games, providing a clear picture with significantly fewer games to accurately determine the rating. We construct our strength model as a neural network. We take advantage of the domain neural network of the existing expert Go-playing program KataGo by transfer learning for board position evaluation. Therefore we avoid learning game knowledge from scratch. Our strength model uses the internal knowledge representation from the domain network's trunk as input and does not require us to manually engineer features. The architecture of our strength model is based on a Set Transformer. This architecture employs effective elements from the trendy Transformer architecture, such as residual blocks and attention, on an unordered set of input elements. Its number of operations grows just linearly in the size of the set because the attention queries are limited to a fixed number of inducing points. These inducing points focus the attention of the model on a few significant telling game moves among hundreds. We determine a suitable configuration for training this architecture by executing a random search in five iterations over all hyperparameters. The resultant model from the training run that produces the most accurate predictions over the games in the test set becomes our final strength model. Our experiments show that our model can, with a mean log-likelihood of -0.58, estimate the outcome of a game approximately as well as Glicko-2. In comparison over a selection of games between players with scarce history, our model leverages the behavioral aspect, being able to draw on every move of the players' preceding games. Through this it can achieve a mean log-likelihood of -0.55, surpassing Glicko-2 with -0.64 in this scenario. We demonstrate our strength model in two practical applications. For one, we provide a public website where interested players can query the strength model. For the other, we perform a complete strength evaluation on a collection of trick play problems.

Um die Stärke von Spielern im Go-Spiel und anderen Bereichen des Wettkampfes zu beziffern, bedienen wir uns üblicherweise eines paarweisen Wertungssystems wie Elo oder Glicko-2. Derartige Systeme ordnen dem Spieler anhand seiner errungenen Siege und Verluste eine Wertungszahl zu. In dieser Arbeit vergleichen wir eine Implementierung des klassischen Wertungssystems Glicko-2 mit einem neu entwickelten, verhaltensbasierten Ansatz, welcher auf einem gelernten Stärkemodell basiert. Dieses Modell verarbeitet die Information über alle Züge aus verfügbaren Spielen eines Spielers in der jüngeren Vergangenheit, wodurch es mit erheblich weniger Partien ein klares Bild zur akkuraten Wertung erhält. Wir konstruieren unser Stärkemodell in Form eines neuronalen Netzwerks. Da wir uns zur Auswertung der Brettstellungen das fachspezifische neuronale Netzwerk des bestehenden Go-spielenden Programms KataGo durch Transfer Learning zunutze machen, müssen wir das Wissen über das Spiel nicht von vorne lernen. Unser Stärkemodell verwendet die interne Wissensdarstellung aus dem neuronalen Netzwerk von KataGo als Eingabe weiter und benötigt somit keine eigenhändig ausgearbeiteten Features. Die Architektur unseres Stärkemodells basiert auf einem Set Transformer. Diese Architektur wendet wirkungsvolle Elemente aus der leistungsfähigen Transformer-Architektur, wie Residual Blocks und Attention, auf eine ungeordnete Menge von Eingabe-Elementen an. Die Anzahl der Rechenoperationen wächst nur linear mit der Größe der Menge, da die Attention-Aufrufe auf eine konstante Zahl von Induktionselementen beschränkt sind. Diese Induktionselemente richten die Aufmerksamkeit des Modells auf wenige aussagekräftige Spieler-Züge unter Hunderten. Um eine geeignete Konfiguration für das Training unter dieser Architektur zu bestimmen, führen wir eine randomisierte Suche in fünf Etappen über die Hyperparameter durch. Das Modell aus jenem Trainingslauf, welcher die genauesten Vorhersagen über den Ausgang der Test-Partien hervorbringt, wird als unser Stärkemodell im Endergebnis ausgewählt. In Experimenten zeigt sich, dass unser Modell mit -0.58 durchschnittlicher log-Wahrscheinlichkeit generell etwa gleich genau wie Glicko-2 den Partie-Ausgang abschätzen kann. Im Vergleich über eine Auswahl von Partien zwischen Spielern mit wenig Vorgeschichte kommt unserem Modell der verhaltensbasierte Aspekt zugute, dass es jeden einzelnen Zug aus den vorherigen Spielen heranziehen kann. Dadurch kann es eine durchschnittliche log-Wahrscheinlichkeit von -0.55 erreichen und Glicko-2 mit -0.64 in diesem Szenario übertreffen. Wir demonstrieren unser Stärkemodell an zwei praktischen Anwendungsfällen. Zum einen stellen wir eine öffentliche Website zur Verfügung, wo interessierte Spieler das Stärkemodell aufrufen können. Zum anderen führen wir eine vollständige Auswertung einer Problemsammlung von Trickzügen durch.