¶ Blokus Duo
Blokus Duo ist die zwei-Spieler Variante des deterministischen Spieles Blokus von Bernard Tavitian und wurde von Mattel 2005 herausgegeben. Dabei werden abwechselnd Spielsteine (Polyominos), auf ein Spielbrett gelegt und versucht viele eigene Spielsteine auf das Spielfeld zu legen und den Gegner zu blockieren.
¶ Spielregeln
¶ Züge
Gespielt wird auf einem 14x14 großen Spielbrett. Beide Spielende haben 21 Polyominos in einer Farbe. Am Anfang kann ein belieger Spielstein auf eine der beiden Startpositionen in Abbildung 2 platziert werden, der andere Spieler platziert an die jeweils andere Startposition.
Danach werden abwechselnd Spielsteine plaziert. Ein Spielstein darf nur an einen anderen gelegt werden, wenn
- der Spielstein einen anderen der gleichen Farbe über deren Ecken berührt.
- keine Kanten unterschiedlicher Spielsteine der gleichen Farbe sich berühren.
Polyominos dürfen vor dem Ausspielen beliebig gedreht und gewendet werden, sodass es bis zu 8 unterschiedliche Positionen geben kann.
Sobald eine spielende Person keine Spielsteine mehr platzieren kann, muss sie passen. Wenn beide Spielenden gepasst haben, endet das Spiel.[1]
¶ Bewertung
Die Quadrate der nicht gespielten Polyominos werden gezählt und gelten als Minuspunkte. Sollten alle Steine gespielt worden sein, bekommt die Person 15 Pluspunkte und 5 weitere, wenn der letzte Stein der Monomino (mit einem Quadrat) ist. Die Person mit den meisten Punkten gewinnt.
¶ Lösungsansätze
Für Blokus Duo können viele verschiedene Algorithmen verwendet werden, um einen guten Zug in einer gegebenen Stellung zu finden. Einer von ihnen ist der Alpha-Beta Pruning Algorithmus, der mithilfe von einer Evaluationsfunktion und Zugsortierung einen guten Zug findet. Ein anderer gängiger Algorithmus für Spiele mit hohem Branchingfaktor ist Monte Carlo Tree Search. Im folgenden wird der Ansatz von João Vieira in dem Paper "Playing BlokusDuo in a ZYNQ Device: A Quest for an Efficient Algorithm"[2] vorgestellt.
¶ Anker und Ankerpunkte
Damit ein Spielstein an einen anderen der gleichen Farbe angelegt werden darf, müssen sich diese nur über Eck berühren. Dies wird mit Ankern und Ankerpunkten formalisiert. Anker sind die Quadrate eines Spielsteines, an die über Eck weitere Spielsteine platziert werden können. In der Abbildung 3 unten sind alle Polyominos abgebildet und deren Anker rot markiert.
[2:1]
Abb. 3 Spielsteine und deren Anker
Ankerpunkte hingegen sind die Felder auf dem Spielbrett, an die neue Polyominos der gleichen Farbe platziert werden können. Das sind genau die Quadrate, die Eckkontakt mit einem Anker haben. In Abbildung 4 sind die Ankerpunkte rot markiert.
[2:2]
Abb. 4 Ankerpunkte
¶ Berechnung möglicher Züge
Bei MCTS werden sehr viele Spielzüge simuliert. Damit dies schnell funktioniert, müssen die Züge, die für einen Spielenden möglich sind, effizient berechnet werden können. Dies geschieht folgendermaßen:
- Überprüfung vorheriger möglicher Züge: Die Liste der möglichen Züge aus dem letzten Zug wird einzelnd durchgegangen und die Züge, die durch den letzten Spielstein blockiert wurden, werden entfernt.
- Berechnung neuer Ankerpunkte: Anhand der Anker des letzten Spielsteins werden die freien Ankerpunkte auf dem Spielfeld berechnet
- Hinzufügen neuer gültiger Spielzüge: Unter Verwendung der neu berechneten Ankerpunkte werden mögliche Platzierungen für die verbleibenden Spielsteine ermittelt, überprüft ob diese erlaubt sind und dann der Liste hinzugefügt.
¶ Monte Carlo Tree Search
Der Monte Carlo Algorithmus wurde in der Selektion um Heuristiken erweitert, damit er früher bessere Züge auswählt und so die Anzahl der besuchten Knoten verkleinert wird.
Dafür werden folgende Faktoren in der Selektion verwendet:
- UCB
- Anzahl an Quadraten des Spielsteins
- Anzahl an Anker des Spielsteins
- Nähe zu dem letzten gespielten Spielstein des Gegenspielers
- Nähe zur Gegendiagonale des Spielfelds
Die anderen Schritte des MCTS weichen nicht ab.
¶ Beispiel
Abb. 5 Platzieren eines Spielsteines
In Abbildung 5 ist zu sehen, wie ein Plus-Polyomino platziert wird. Der letzte Zug des Gegners war der längliche Spielstein unterhalb des L-Polyominos. Für den Spielstein an dem Anker links von dem letzten Zug des Gegners ergaben sich vorher folgende Werte:
Anzahl Quadrate: 5
Anzahl Anker: 4
Nähe Spielstein des Gegners: 1
Nähe Gegendiagonale: 1
¶ Ergebnisse
Abb. 6 platzierte Spielsteine und Gewinnverteilung über tausend Spiele
Abb. 7 Simulationen pro Zug in einer Sekunde
In Abbildung 6[2:3] ist links zu sehen, dass über tausend Spiele immer mindestens 67% der Spielsteine platziert wurden. In diesen gespielten Spielen wurde Spieler 2 ein höheres Zeitbudget gegeben. Dies zeigt sich in der Abbildung rechts, bei der Spieler 2 deutlich mehr Siege errungen konnte. In Abbildung 7[2:4] ist dargestellt, wie viele Simulationen mit einem festen Zeitbudget von einer Sekunde pro Runde berechnet werden. Da in späteren Runden die Simulationsphase kürzer ist, wird auch insgesamt mehr simuliert, je mehr Steine auf dem Spielbrett liegen.
¶ Vergleich mit anderen Algorithmen
Ein Großteil der wissenschaftlichen Artikel über Blokus Duo wurden für einen Wettbewerb geschrieben. Die größten Wettbewerbe waren die Games and Puzzles Competitions on Computers (GPCC) von 2007 bis 2010[3], die ICFPT Design Competition 2013[4] und 2014[5], sowie der MathWorks Blokus Duo Design Contest 2015[6]. Bei den GPCCs von 2007 bis 2009 gewann ein Japaner mit dem Pseudonym "Irori". Dafür nutzte er den Alpha-Beta Pruning Algorithmus und etablierte für Blokus Duo das Konzept der "sphere of influence"[7]. Dabei handelt es sich um einen Bereich um die Polyominos eines Spielers. In der Evaluationsfunktion wird diese benutzt, um zu schauen, wie viel vom Spielfeld ein Spieler kontrolliert. Alpha-Beta Pruning war auch bei der ICFPT Design Competiton 2013 und 2014 am stärksten. Bei beiden Wettbewerben gewann ein Team aus Shizuoka.[8] Das gleiche Team gewann auch den MathWorks Blokus Duo Design Contest. 2014 schieden alle Teams mit anderen Algorithmen als Alpha-Beta Pruning in der Vorrunde aus, während 2015 ein Team mit MCTS auf dem zweiten Platz landete.
Neuere Artikel, die die Effizienz von MCTS mit Alpha-Beta Pruning vergleichen wären wünschenswert, da zu beiden Algorithmen inzwischen Verbesserungen und Änderungen vorgeschlagen wurden.
¶ Referenzen
Vieira, João. Playing BlokusDuo in a ZYNQ Device: A Quest for an Efficient Algorithm. Conference XVI Jornadas sobre Sistemas Reconfiguráveis (REC 2020) pdf ↩︎ ↩︎ ↩︎ ↩︎ ↩︎
Games and Puzzles Competitions on Computers (2007-2010) url (jp) ↩︎
International Conference on Field-Programmable Technology Design Competition (2013) url ↩︎
International Conference on Field-Programmable Technology Design Competition (2014) url ↩︎
Kojima, Akira. An implementation of Blokus Duo player on FPGA. 2013 International Conference on Field-Programmable Technology (FPT). IEEE, 2013. url ↩︎
Yoza, Takashi, et al. FPGA Blokus Duo Solver using a massively parallel architecture. 2013 International Conference on Field-Programmable Technology (FPT). IEEE, 2013. url ↩︎