¶ Einführung
Abalone ist ein zwei Spieler Brettspiel aus dem Jahr 1987, trotz simpler Regeln ist das Spiel sehr komplex und hat einen riesigen Suchraum. [3] Viele klassische Algorithmen kommen schnell an ihre Grenzen und auch Algorithmen, welche für andere zwei Spieler Spiel optimiert wurden erweisen sich als uneffektiv für Abalone. Deshalb hat Aichenholzer mit Kollegen einen neuen Algorithmus entworfen, der auf dem Prinzip von einem Trichter basiert, um einem Computer die menschliche Intuition beizubringen.
¶ Regeln
Abalone wird auf einem hexagonalem Spielfeld mit 61 Feldern gespielt, zum Start der Partie besitzt sowohl der schwarze als auch der weiße Spieler 14 gleichwertige Kugeln, welche wie in Abb. 1 angeordnet werden. Schwarz beginnt mit dem ersten Zug und danach wird immer abwechselnd ein Zug ausgeführt. Während eines Zuges darf der Spieler ein bis drei Kugeln in einer Reihe bewegen, wichtig dabei ist, dass die Kugeln sich alle in die gleiche Richtung auf dem hexagonalen Spielfeld bewegen müssen (Abb. 2).
¶ Ziel des Spiels
Es gibt noch eine Besonderheit beim Ausführen eines Zuges, nämlich das Schlagen eines anderen Spielers, das so genannte Sumito. Wenn ein Spieler beim ausführen eines Zuges in der Überzahl, also mehr Kugeln in eine Richtung bewegt, als Kugeln vom Gegner im Weg stehen, kann der Spieler die gegnerischen Kugeln schieben (Abb. 3). Ziel ist es als ersten sechs Kugeln des Gegner vom Feld zu schieben, um das Spiel zu gewinnen.
¶ Bewertungsfunktion
Damit der Computer entscheiden kann, ob eine Stellung gut oder schlecht ist, braucht dieser eine numerische Bewertung. Dafür wurde in diesem Fall ein geometrischer Ansatz gewählt:
- Zuerst werden die Schwerpunkte der beiden Kugel Farben berechnet
- Dann wird ein Referenzpunkt R erzeugt, welcher sich aus den beiden Schwerpunkten und der Brettmitte zusammensetzt, wobei allerdings die Brettmitte eine Gewichtung hat, die kleiner als 1 ist. R stellt somit das geometrische Zentrum der Partie dar.
- Dann misst man die Manhattan-Distanz aller Kugeln zu diesem Punkt, also entlang der sechs hexagonalen Linien. Man bestimmt somit den kürzesten Weg aller Kugeln zum Referenzpunkt. Kugeln, die vom Spielfeld gestoßen wurden erhalten dabei eine festgelegten Wert zugewiesen.
- Die Bewertung ist dann die Differenz der beiden Gesamtdistanzen.
Mit dieser Bewertungsfunktion soll zentrales und kompaktes Spielen bevorzugt werden[1].
¶ Optimierung der Suche
Die Bewertungsfunktion wurde zuerst auf dem MiniMax-Algorithmus angewendet. Da es in Abalone ungefähr 60 Züge pro Position gibt, wächst der Baum exponentiell mit Faktor . Eine Suche der Tiefe acht dauert bereits mehrere Jahre [1].
Auch bei der Anwendung auf den Alpha-Beta-Algorithmus werden immer noch ca. 20 Züge pro Position betrachtet und eine Suche mit Tiefe acht zu aufwendig ist [1].
¶ Der Trichter
Um effizient rechnen zu können braucht es eine neue Methode und dafür wurde folgende Beobachtung benutzt: In Abalone verändern sich die Bewertungen sehr glatt und ohne extreme Ausreißer, da alle Figuren gleichwertig sind.[1]
Das Ziel dabei ist es den Menschen zu imitieren und sich nur interessante Züge anzuschauen.
Deshalb erstellte man einen heuristischen Trichter für den Alpha-Beta-Algorithmus mit folgenden Eigenschaften:
- Züge, die schon am Anfang unrealistisch schlechte Bewertungen haben, werden komplett ignoriert, da es keine großen Sprünge in der Bewertung von einer Stellung gibt.
- Nur Züge innerhalb eines plausiblen Bereichs werden weiter untersucht.
- Die optimale Breite wurde experimentell bestimmt. Ein engerer Trichter hat immer eine Einsparung an Zeit gebracht, allerdings wenn dieser zu eng gewählt wurde, wurde kein korrektes Ergebnis mehr gefunden.[1]
- Die Autoren haben sich darauf geeinigt, dass eine Suche mit Trichter bei einer Tiefe von mindestens ein genauso gutes Ergebnis wie bei normaler Alpha-Beta-Suche bei Tiefe erzielt werden soll in kürzerer Zeit.[1]
Wie zu sehen ist in Abb. 4, wird der Trichter immer enger, je tiefer gesucht wird, dadurch können viele Züge eliminiert werden. Der Verzweigungsgrad sinkt von ca. 60 bei naiver Suche auf 5 bis 8, somit ist die Suche erst jetzt praktikabel.[1]
¶ Ergebnisse
Durch die Trichter-Heuristik wird die Berechnungsdauer massiv reduziert (Abb. 5), sodass diese jetzt getestet werden kann. Dies wurde auch getan, gegen den damaligen Abalone-Weltmeister. Dieser konnte auch besiegt werden, da das Programm besonders in der Defensive sehr stark war. Zusätzlich hat es eine neue Eröffnung erfunden, die der Weltmeister erst für schlecht hielt, sich aber als sehr effektiv heraus stellte. [1]
Allerdings konnte das Programm nur bei einer kurzen Zeitbeschränkung von 5 Sekunden pro Zug gewinnen. Weiterhin kritisierte der Weltmeister, dass teilweise die Kompaktheit der Kugeln und die Relevanz der Brettmitte unterschätzt werden von dem Algorithmus.[1] Trotzdem ist er von der Überzeugung, dass dies ein großer Fortschritt für die zukünftige Entwicklung von Abalone Strategien bringt.
Daher gibt es noch viel Verbesserungspotential für den Algorithmus.
¶ Ausblick
Spätere Arbeiten haben den Alpha-Beta-Algorithmus für Abalone noch stark erweitert. Zum einen wurde eine neue, deutlich komplexere Bewertungsfunktion erstellt, welche unter anderem Zentrumkontrolle, Formation und Rauswurf potential betrachtet.[2]
Des weiteren wurde noch eingeführt, dass abhängig von der Spielsituation tiefer gesucht wird, wenn zum Beispiel ein Rauswurf bedroht wird.[2]
Außerdem werden auch Transposition Tables genutzt, in denen bereits berechnete Stellungen gespeichert werden, um Rechenzeit zu sparen.[2]
Dadurch wird nicht nur die Zeit, die es braucht, einen Zug zu finden, weiter verkürzt, sondern auch durch die neue Bewertungsfunktion allgemein bessere Züge gefunden.
Insgesamt kann man also sagen, dass die Trichter Heuristik von Aichenholzer einen soliden Grundbaustein für die Entwicklung von Abalone Algorithmen geliefert hat. Durch die Weiterentwicklung dieser gibt es heute sehr leistungsfähige Abalone Engines.
¶ Quellen
¶ Literatur
[1] Aichholzer, Oswin, Franz Aurenhammer, and Tino Werner. "Algorithmic fun-abalone." Special Issue on Foundations of Information Processing of TELEMATIK 1 (2002): 4-6. Link
[2] Papadopoulos, Athanasios, et al. "Exploring optimization strategies in board game abalone for alpha-beta search." 2012 IEEE Conference on Computational Intelligence and Games (CIG). IEEE, 2012. Link
[3] Wikipedia, „Abalone (Spiel)“, Online-Enzyklopädie. [Online]. Verfügbar unter: https://de.wikipedia.org/wiki/Abalone_(Spiel). [Zugriff am: 12. Jan. 2026].
¶ Bilder
Abb. 1: Haffner, François. (2006). Abalone, normale Startposition. Wikipedia. https://de.wikipedia.org/wiki/Datei:Abalone_standard.svg [Zugriff am: 12. Jan. 2026]
Abb. 2: Lalet, Michel. (1988). Abalone Spielregeln, Abbildung 2 & 3. Spielezar. https://www.spielezar.ch/modules/genzo_zar/views/pdf/spielregeln-abalone-classic.pdf [Zugriff am: 12. Jan. 2026]
Abb. 3: Haffner, François. (2006). Abalone après la poussée. Wikipedia. https://de.wikipedia.org/wiki/Datei:Abalone_push_after.svg [Zugriff am: 12. Jan. 2026]
Abb. 4: Aichholzer, Oswin, Franz Aurenhammer, and Tino Werner. "Algorithmic fun-abalone." Special Issue on Foundations of Information Processing of TELEMATIK 1 (2002): S. 4. Link
Abb. 5: Aichholzer, Oswin, Franz Aurenhammer, and Tino Werner. "Algorithmic fun-abalone." Special Issue on Foundations of Information Processing of TELEMATIK 1 (2002): S. 5. Link
