Python: Penta Game Action Space

In diesem Jahr habe ich das Brettspiel Penta Game von dem Entwickler Jan Suchanek hier aus Berlin kennen gelernt und möchte nun ein wenig von meiner Begeisterung für dieses Spiel berichten.

Wie auf der Homepage zu lesen, ist Penta Game ein würfelloses abstraktes Brettspiel für 2-4 Spieler mit so einfachen Regeln, dass es schnell zu erfassen ist und trotzdem für Groß und Klein nie langweilig wird.

Der Name ist Programm und leitet sich von der Geometrie der Spielanordnung ab. Dabei spielt man anders als bei anderen Spielen Figuren Formen statt Farbe. Was konkret bedeutet, dass jeder Spieler 5 unterschiedlich farbige Figuren aber von derselben Form bekommt. z.B. Hasen. Diese werden initial je auf einer Ecke des Pentagramms passend zur Farbe des Feldes positioniert. Und danach kommt noch ein schwarzer Blocker jeweils auf alle 5 inneren Kreuzungen, was für 2 Spieler dann so aussieht:

Ziel des Spiels ist es, 3 der 5 eigenen Figuren raus zu setzen, was geschieht, sobald eine Figur die farbgleiche Kreuzung erreicht hat. "Follow the white rabbit“ bedeutet in diesem Spiel, dass der weiße Hase beginnt und entlang aller 4 Richtungen maximal soweit ziehen kann bis er von einer Figur oder Blocker aufgehalten wird. Aus der Ausgangsstellung heraus ist es zwar nicht möglich, aber wären z.B. die inneren Blocker nicht auf den Kreuzungen, könnte der Weg auch um die Ecke führen.

Steht auf dem Ziel Feld eine Figur eines Spielers (eigene und/oder gegnerische), wird eine ausgewählt und tauscht Feld mit der ziehenden Figur. Steht auf dem Ziel Feld ein schwarzer Blocker, wird dieser geschlagen und irgendwo auf dem Spiel versetzt, wo noch kein Blocker oder eine Figur steht.

Etwas Besonderes sind die 5 grauen Blocker. Diese sind 1 Mal Blocker, die als Belohnung/Ersatz für eine raus gesetzte Figur auf einem beliebigen freien Feld platziert werden können. Allerdings gehen diese sofort wieder ins Aus, wenn sie geschlagen werden. Anders als die Schwarzen Blocker, die nach Schlagen immer wieder frei versetzt werden können.

Weitere Regeln sind auf der Rules Page https://www.pentagame.org/i/rules  nachzulesen.

Nun zum Action Space.

Die Entwicklung einer Computer Version des Spiels wirft die Frage nach einer eindeutigen Beschreibung von Zügen auf. Und dabei verstehe ich unter Action Space nachfolgend den Raum, der mit der Beschreibung eines Zuges mindestens abgedeckt werden muss, um jeden möglichen Zug abbilden zu können.

Als Messlatte dient der Zug mit maximal involvierten Figuren, wo zwei eigene Figuren durch Tausch der Position gleichzeitig raussetzen können und dafür 2 graue Blocker (ver)setzen dürfen. Damit kann ein Spielzug eines Spielers aus einer Folge von maximal 4 Figuren Bewegungen bestehen. Und jede dieser Figuren kann maximal eine beliebige Figur/Blocker des Spiels oder keine Figur sein. Als Zielfeld kommen alle 100 Spielfelder, das AUS-Feld und kein Feld in Frage.

Demnach gäbe es (Anzahl der [Figuren + Blocker +1] x (Anzahl der Spielfelder +1 +1)) ^{Anzahl der Bewegungen} mögliche Zugbeschreibungen.

Für 2 Spieler konkret: (21 x 102) ⁴ = 21.051.248.890.896.

Nach Optimierung:

• Die erste Bewegung wird nur von Spieler Figuren (10+1) durchgeführt.
• Die zweite Bewegung gibt lediglich die Tauschfigur ohne Zielfeld an.
• Die dritte Bewegung betrifft nur Blocker (10+1).
• Und die vierte nur graue Blocker (5+1).

Womit sich die Berechnung reduziert auf:

(11 x 102) x (11) x (11x102) x (6 x 102) = 8.474.807.088. Also ein Raum von ca. 8.5 Mrd. Zugmöglichkeiten.

Das ist echt viel!

Im Vergleich dazu, mutet der Go Action Space mit 361 Zügen auf einem 19x19 Spielfeld schon fast trivial an. Der Action Space eines Schach Zuges ließe sich für die 32 Figuren und 64 Felder mit 32x64=2048 zwar deutlich größer modellieren, kommt an Penta Game aber auch nicht nennenswert heran.

Nun leitet sich die Größe des Action Space aus der Notwendigkeit ab, tatsächlich jeden möglichen Zug beschreiben können zu müssen. Wo hingegen der maximale Verzweigungsgrad eher einen Eindruck davon vermitteln soll, wie aufwändig das automatische Durchsuchen des Spielbaumes nach bestmöglichen Zugfolgen sein kann.

So gibt es für Schach nach "Verzweigungsgrad von Schach" von Klaus Wich einen maximalen Verzweigungsgrad von 257 Halbzügen. Für Go liefert der erste Zug auf einem 19x19 Spielfeld 361 Zug Alternativen und liegt damit deutlich über Schach.

Für Penta Game gab es bis vor kurzem noch keine amtlichen Zahlen. Aber anhand einiger Berechnungen und Simulationen konnten wir uns, wie nachfolgend gezeigt, dennoch ein Bild vom maximalen Verzweigungsgrad machen. Gehen wir also einmal von folgender hypothetischen Stellung aus, bei der Igel am Zug ist:

Charakteristisch für diese Stellung ist, dass alle Figuren jeweils alle Felder außer die 3 zwischen der roten und der gelben Kreuzung (mit grauen Blockern) erreichen können.

3 Igel (rot, gelb, weiß) können mit Abracadabra raussetzen, womit sie zunächst einen schwarzen Blocker auf (85+2) Felder platzieren dürfen. Danach dürfen sie einen beliebigen der 5 grauen Blocker auf (85+1) Felder versetzen bzw. +1 wenn nicht.

Ein Igel (grün) kann einfach raussetzen und darf dann auch einen beliebigen der 5 grauen Blocker auf (85+1) Felder versetzen bzw. +1 wenn nicht.

Es gibt 17 replace Möglichkeiten bei denen eine Figur einen schwarzen Blocker schlägt und diesen dann auf eines der (85+1) Felder versetzt. Die 17 Möglichkeiten ergeben sich aus den Igel-schlägt-schwarzen-Blocker Optionen wie folgt:

   4 (rot)
+  4 (gelb)
+  4 (weiß)
+  5 (grün)
===========
  17

Die Igel können darüber hinaus mit allen Figuren auf dem Board tauschen. Was zu 10 unterschiedlichen Varianten führt:

   4 (alle 4 Igel tauschen mit rotem Hasen)
+  3 (roter Igel tauscht mit gelbem, grünem oder weißem Igel) 
+  2 (gelber Igel tauscht mit grünem oder weißem Igel)
+  1 (grüner Igel tauscht mit weißem Igel)
=============================================================
  10

Jeder der 4 Igel kann auf eines der 85 leeren Felder setzen. Für den grünen Igel wurde aber die grüne Kreuzung bereits beim einfachen Raussetzen mitgezählt, daher -1.

Und zu letzt können alle 4 Igel einen der 2 freien grauen Blocker schlagen.

Was in der Summe nun, wie durch nachfolgendes Programm berechnet, die Anzahl der möglichen Zug Optionen ergibt.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

exp_abracadabra_cnt = 3 * (85+2) * (5*(85+1)+1)
exp_simple_out_cnt = 5*(85+1)+1
exp_replacement_cnt = 17*(85+1)
exp_swap_cnt = 10
exp_empty_cnt = 4*85-1
exp_grey_cnt = 4*2
exp_next_states_count = sum( [exp_abracadabra_cnt, exp_simple_out_cnt, 
                              exp_replacement_cnt, exp_swap_cnt, 
                              exp_empty_cnt, exp_grey_cnt] )
print(exp_next_states_count)

Ergebnis:

114741

Nicht schlecht!

Und tatsächlich ergab sich bei der Simulation von 100.001 Zufalls Partien eine besondere mit 76.297 Zug Optionen und einige andere mehr mit ca. 40.000. Allgemein lassen sich nun einige Ergebnisse der Simulation wie folgt zusammenfassen:

Spiel Tiefe:

• Minimale Spiel Tiefe: 4 Züge
• Maximale Spiel Tiefe: 53 Züge
• Durchschnittliche Spiel Tiefe: 14 Züge
• Median der Spiel Tiefe: 13 Züge

Details: Zug Statistik

Hier betrachten wir die Anzahl der Züge (=2 Halb Züge) bis zum Spielende.

{'max': 53.0, 'min': 4.0, 'avg': 14.0, 'median': 13.0}

Verzweigungsgrad:

• Minimaler Verzweigungsgrad ausgenommen Spielende: 8 Zug Optionen
• Maximaler Verzweigungsgrad: 76.297 Zug Optionen
• Durchschnittlicher Verzweigungsgrad: 1.739 Zug Optionen
• Median des Verzweigungsgrades: 1.280 Zug Optionen

Details: Zug Optionen Statistik

Hier untersuchen wir die Anzahl der Zug Optionen (Verzweigungsgrad) von 2.706.113 Stellungen aus 100.001 Zufallsspielen.

{'max': 76297, 'min': 8, 'avg': 1739, 'median': 1280}

Updates:

14.01.2022

• Die anfänglich beobachteten bis zu 500.000 Zug Optionen während der Simulation, waren auf Programmfehler zurück zu führen und wurden nun durch neue Daten ersetzt.
• Die ursprünglich auf 10.001 Zufalls Partien begrenzte Simulation wurde nun auf 100.001 Partien ausgedehnt.
• Fehlender Bedarf nach Nachvollziehbarkeit der gezeigten Ergebnisse und das Übersteigen des Webserver Speicherkontingentes mit der Datei für die Historie, bewogen mich, auf weitere Ressourcen zu verzichten.