Latrones

Einleitung

In diesem Projekt wurde das antike römische Spiel Latrones als Webanwendung mit dem Flask-Framework programmiert. Die Spiellogik wurde in Python entwickelt, während die grafische Benutzeroberfläche mit HTML, CSS und JavaScript realisiert wurde. Die Anwendung ermöglicht das Spielen gegen einen anderen Benutzer oder gegen einen automatisierten Gegner, dessen Verhalten auf dem Minimax-Algorithmus mit Alpha-Beta-Pruning basiert.

Der Quellcode ist im folgenden Repository verfügbar: https://github.com/rj-engineeringde/latrones.git
Das folgende Video zeigt eine Demonstration des Programms:

Warum Latrones?

Schon seit geraumer Zeit faszinieren mich Logikspiele wie Schach, Damen oder Shōgi. Bei der Auswahl meines nächsten Programmierprojekts wollte ich jedoch bewusst vermeiden, eines dieser bekannten Spiele einfach nur zu reproduzieren. Im Internet sind umfassende Tutorials verfügbar, die detailliert erläutern, wie man Schach- oder Damenspiele implementiert, was den kreativen und technischen Anspruch erheblich mindert. Angesichts der Vielzahl bereits existierender Implementierungen, die oftmals einfach kopiert werden können, besteht eine große Versuchung, sich an diesen Vorlagen zu „inspirieren“. Andererseits wäre es ebenso unzweckmäßig und wenig zielführend, das Rad komplett neu zu erfinden und auf bewährte Ressourcen zu verzichten. Mein Ziel war es, eine Herausforderung anzunehmen, die es erfordert, die Spielmechanik von Grund auf zu konzipieren. Auf dieser Suche stieß ich auf Latrones (auch Ludus Latrunculorum genannt), ein antikes römisches Strategiespiel, dessen Regeln im Verlauf der Geschichte verloren gegangen sind. Die geringe Bekantheit und uneindeutigkeit der Regeln machen es zu einem idealen Kandidaten für eine rekonstruktive Neuentwicklung. Figuren und Spielbrett wurden bei verschiedenen archäologischen Ausgrabungen entdeckt, doch die genaue Spielweise bleibt bis heute Gegenstand von Mutmaßungen.

Implementierung

Das Spiel wurde als Webanwendung unter Verwendung des Flask-Frameworks realisiert. Die Entwicklung der Spiellogik erfolgte in Python, während die grafische Benutzeroberfläche mit HTML, CSS und JavaScript umgesetzt wurde. Die Benutzeroberfläche ermöglicht die direkte Interaktion mit dem Spielbrett und zeigt für jeden Spieler eine individuelle Countdown-Anzeige an. Zusätzlich wurde ein Menü zum Neustart der Partie integriert, das die Konfiguration verschiedener Parameter erlaubt – darunter die Spielzeit pro Spieler, die Größe des Spielfelds, die Farbe des Hauptspielers sowie die Wahl zwischen einem menschlichen oder einem computergesteuerten Gegner.

Diese Implementierung basiert auf die von dem Historiker W. J. Kowalski vorgeschlagenen Regeln:

Im Hinblick auf die Spielmechanik wurden alle zentralen Regeln umgesetzt: die Darstellung des Spielbretts, die zulässigen Zugmöglichkeiten, die Gefangennahme von Figuren, der Wechsel der Spielzüge zwischen den Spielern sowie die Erkennung des Gewinners. Für Partien gegen den Computer wurde ein automatisierter Gegner entwickelt, dessen Entscheidungsfindung auf dem Minimax-Algorithmus beruht. Dieser Algorithmus durchsucht rekursiv die möglichen zukünftigen Züge, um die für den Bot günstigsten Spielzüge zu maximieren und gleichzeitig die Vorteile des Gegners zu minimieren. Durch die Verwendung von Alpha-Beta-Pruning wird die Effizienz des Minimax-Algorithmus deutlich gesteigert, indem Entscheidungszweige verworfen werden, die das Endergebnis nicht beeinflussen. So sind tiefere Analysen in kürzerer Zeit möglich.

Zur Optimierung der Bewegungsgeschwindigkeit des Bots wurde eine Strategie implementiert, welche die Reihenfolge der Auswertung von Zügen anpasst, sodass die vielversprechendsten Spielzüge (beispielsweise solche, die eine Gefangennahme beinhalten) zuerst bewertet werden. Diese Vorgehensweise erhöht die Effizienz des Alpha-Beta-Prunings erheblich, da die Wahrscheinlichkeit steigt, frühzeitige Schnittpunkte in den Zweigen des Suchbaums zu finden. Zusätzlich wurde eine iterative Suchtechnik angewandt, bei der mehrere aufeinanderfolgende Minimax-Durchläufe mit zunehmender Suchtiefe durchgeführt werden. Obwohl dadurch bestimmte Berechnungen mehrfach ausgeführt werden, ergeben sich zwei wesentliche Vorteile:

1. Dadurch verbessert sich die Qualität der Zugreihenfolge bei der Bewertung, was die Ausführung des Algorithmus beschleunigt
2. Zudem lässt sich damit ein Zeitlimit für die Entscheidungsfindung des Bots festlegen. Dabei werden Ergebnisse aus vorherigen, flacheren Suchen weiterverwendet, um innerhalb der vorgegebenen Zeit eine Antwort zu liefern.

Performance-Optimierungen

Nach der Implementierung der Bot-Logik unter Verwendung des Minimax-Algorithmus mit Alpha-Beta-Pruning war das Spiel zwar funktionstüchtig, jedoch in Hinblick auf die Reaktionszeiten nicht praxistauglich. Der erste Spielzug erforderte bei einer Suchtiefe von 3 auf einem 8×8-Brett etwa 20 Sekunden Rechenzeit, was das Spiel nahezu unspielbar machte. In fortgeschritteneren Spielsituationen, in denen die Zahl möglicher Züge weiter steigt, verlängerte sich die Ausführungszeit pro Zug sogar noch deutlich.

Bei der Analyse des Codes stellte sich heraus, dass einer der Hauptengpässe in der Darstellung des Spielbretts und den verwendeten Datenstrukturen lag. Ursprünglich war das Brett als eine Liste von Listen implementiert, wobei jede Zelle eine Referenz auf eine Instanz der Klasse „Piece“ enthielt. Diese Struktur ist zwar intuitiv und für Spiele zwischen zwei menschlichen Spielern ausreichend, erweist sich jedoch als äußerst ineffizient, wenn der Bot tausende mögliche Spielzustände analysieren muss. Ständige Iterationen über dynamische Strukturen und der Overhead durch den Einsatz von Klassen führten zu einer erheblichen Verlangsamung. Trotz des bereits weit fortgeschrittenen Entwicklungsstands der bisherigen Struktur blieb als einzige sinnvolle Lösung, die Darstellung des Spielfelds grundlegend zu überarbeiten – einschließlich der Anpassung nahezu aller bereits implementierten Funktionen.

Eine binäre Darstellung des Spielbretts wurde gewählt. Dabei wird für jede Gruppe von Spielfiguren – weiße Männer, schwarze Männer, weiße Könige und schwarze Könige – eine eigene binäre Variable verwendet. Jeder Bitwert innerhalb dieser Variablen steht für ein Feld auf dem Spielbrett: Ist ein Bit gesetzt (1), befindet sich auf dem entsprechenden Feld die zugehörige Figurengruppe; ist es nicht gesetzt (0), ist das Feld leer oder von einer anderen Figur belegt. Dadurch lässt sich ein 8×8-Brett mit lediglich vier Variablen vom Typ Int64 abbilden. Spielzüge, Schlagzüge oder die Erkennung von Figuren können so mithilfe logischer Operatoren durchgeführt werden – was eine deutlich effizientere Verarbeitung erlaubt.

Durch die Implementierung dieser Darstellung ließ sich die Berechnungszeit für den ersten Zug bei einer Suchtiefe von 3 auf einem 8×8-Brett auf etwa 3 Sekunden reduzieren – eine deutliche Verbesserung gegenüber den ursprünglichen 20 Sekunden. Dennoch war die Berechnungszeit aus meiner Sicht noch nicht zufriedenstellend, da weiteres Optimierungspotenzial erkennbar war.

Es wurde Caching bei Funktionen getestet, deren Eingabeparameter nur geringe Variabilität aufweisen. Da viele Funktionen jedoch den vollständigen Spielbrettzustand als Eingabe benötigen, blieb der Effekt dabei begrenzt. Auch der Einsatz von Numba, einem Just-in-Time-Compiler für Python, war mit Einschränkungen verbunden: Wichtige Funktionen wie bit_count() und divmod() waren nicht kompatibel oder verursachten Fehler. Da diese für binäre Operationen stark optimiert sind, wurde dieser Ansatz nicht weiterverfolgt.

Eine interessante Beobachtung war, dass selbst einfache Operationen wie die Zuweisung „bit_mask = 1 << bit_idx“ einen spürbaren Einfluss auf die Ausführungszeit haben, wenn sie tausend- oder millionenfach ausgeführt werden. Das liegt daran, dass Python im Vergleich zu anderen Programmiersprachen wie C oder C++ deutlich langsamer ist. Deshalb wurden die Umwandlungen zwischen Indizes und Bitmasken auf ein Minimum reduziert. Außerdem wurden Variablen, die wiederholt ermittelt werden – etwa die Größe des Spielfelds – als globale Konstanten definiert und nur beim Neustart aktualisiert. So konnte die Anzahl der notwendigen Berechnungen verringert werden.

Trotz dieser Änderungen war die Auswirkung auf die Ausführungszeit nur begrenzt. So konnte die Berechnung des ersten Zuges des Bots (bei einer Suchtiefe von 3 auf einem 8×8-Brett) auf etwa 2 Sekunden reduziert werden. In späteren Spielphasen, in denen die Figuren weiter verteilt sind und die kombinatorische Komplexität steigt, lag die Berechnungszeit pro Zug zwar etwas höher, blieb aber deutlich unter den anfänglichen 20 Sekunden.

Zu diesem Zeitpunkt wurde deutlich, dass nur zwei Optionen eine spürbare Verbesserung der Ausführungszeit bringen konnten: Entweder das gesamte Programm in C++ neu zu schreiben oder die Anzahl der Bewertungen pro Zug zu reduzieren. Da das Programm bereits mehrfach überarbeitet worden war, fiel die Wahl auf die zweite Möglichkeit – mit dem Ziel, die Suchtiefe gezielt zu optimieren.

Die Bewertung im Minimax-Algorithmus stützt sich auf zwei Hauptfaktoren: die ausgeführten Schlagzüge und die Anzahl der möglichen Züge pro Spieler. Um den Einfluss eines Zuges auf die Mobilität eines Spielers realistisch einzuschätzen, ist keine tiefe Suche notwendig. Bereits eine Bewertung des unmittelbar folgenden Zugs (Suchtiefe 1) oder der zwei nächsten Züge (Suchtiefe 2) liefert eine ausreichend genaue Abschätzung. Daher wurde eine Standardsuchtiefe von 2 definiert, wodurch sich die Anzahl der notwendigen Bewertungen erheblich verringert.

Anders verhält es sich bei Schlagzügen: Hier ist es besonders wichtig, auch die nachfolgenden Züge zu berücksichtigen, da sich daraus häufig weitere Schlagmöglichkeiten ergeben. Daher wurde der Minimax-Algorithmus um eine dynamische Tiefenerweiterung ergänzt, die automatisch ausgelöst wird, sobald ein Schlagzug erkannt wird. In solchen Fällen wird die Suche fortgesetzt, bis einer der folgenden Zustände erreicht ist:

1. Die maximale Suchtiefe von 4 wird erreicht
2. Einer der beiden Spieler gewinnt die Partie
3. Im darauffolgenden Zug besteht keine Möglichkeit mehr, eine Figur zu schlagen

Durch diese Ähnderung konnte die Berechnungszeit für den ersten Zug (auf einem 8×8-Brett) auf etwa 0,1 bis 0,2 Sekunden reduziert werden. Das Spielniveau des Bots wurde dabei im Vergleich zur vorherigen Version nicht spürbar beeinträchtigt.

An diesem Punkt war die Ausführungsgeschwindigkeit aus meiner Sicht zufriedenstellend. Natürlich wären noch zahlreiche Verbesserungen möglich – etwa die Integration einer ausgefeilteren Spielstrategie oder die Auslagerung besonders rechenintensiver Funktionen in C oder C++. Doch der erzielte Leistungszuwachs hatte das Spielerlebnis bereits deutlich verbessert, sodass der richtige Moment gekommen war, mich einer neuen Herausforderung zu widmen.