ich habe mir die Implementierung des Brettspiels Quoridor vorgenommen. Quoridor ist ein abstraktes Logikspiel, was mit sehr einfachen Regeln auskommt; dessen Spieltiefe sich aber aus subtilen Strategien ergibt.
Aufbau & Ziel des Spiels:
Das Spielfeld besteht aus einem 9x9 Brett. An den gegenüberliegenden Enden befindet sich je der Spielstein eines Spielers. Ziel des Spielers ist es, die andere Seite vor allen Mitspielern zu erreichen.
Bewegung:
Man bewegt sich in der Regel pro Zug nur ein Feld vom aktuellen Feld weg. Es existieren Wände, die den Weg zu benachbarten Feldern blockieren. Wenn ein Spieler an einem anderen Spieler angrenzt, so kann er diesen umlaufen oder sogar überspringen - auch hier darf keine Wand im Weg stehen.
Wände setzen:
Jeder Spieler hat eine bestimmte Anzahl von Wänden, die er an beliebige Stelle setzen darf. Einmal gebaute Wände können während des Spiels nicht entfernt werden. Es dürfen keine Wände gesetzt werden, die einen Spieler den Weg zum Ziel versperren würden.
Weitere Features:
- Es können lokal bis zu vier Spieler spielen.
- Es gibt theoretisch eine KI (welche allerdings absolut unbrauchbar ist - Weiteres dazu siehe unten)
Screenshots:
Hauptmenü:
Spiel starten:
Im eigentlichen Spiel:
In-Game-Erklärung:
Selber spielen:
* WebPlayer
* Windows Executable (38 MB)
* Linux Executable x86 (51 MB)
* Linux Executable x86_86 (16 MB)
Genutzt Ressourcen
- Font: Source Sans Pro
- Werkzeuge: GIMP, Unity, OpenOffice Draw
Entwicklung:
Ich habe Quoridor für die Action gewählt, weil es als abstraktes Spiel auch mit einer einfachen Repräsentation auskommt und meine Energie dafür ins Gameplay investieren konnte. Die eigentliche Umsetzung mit Unity ging wie zu erwarten ziemlich gut voran. Die Logik habe ich streng von der Repräsentation getrennt. So kennt der Client bspw. nur die angebotenen legalen Züge und darf nur diese Eingaben ermöglichen. Beim Anwenden der Züge wird nochmal auf Sinnhaftigkeit geprüft. Die Teile, bei denen der menschliche Spieler involviert ist, waren also weitesgehend zufriedenstellend.
Kommen wir zum Multiplayer: Ich hatte anfangs überlegt, dass ich vielleicht einen Online-Multiplayer ermögliche und habe mir dafür schon Photon angeschaut. Ich dachte mir aber, dass die ZFX-Community so klein ist, dass sich sowieso kaum zwei finden werden. :P Daher der Gedanke eine KI zu erstellen. Das Problem hierbei ist, dass Quoridor leider einen sehr breiten und tiefen Spielbaum besitzt. So sind Anfangs 132 Züge möglich und theoretisch könnten Spieler nur hin und her springen, ohne einem Spielende wirklich entgegenzukommen. Zum anderen ist es sehr teuer die Züge zu berechnen. Denn man darf beim Wände-Platzieren keinen Spieler einsperren. Ich habe dafür A* genutzt, um festzustellen, ob eine Spieler einen Weg zu seiner Siegesseite finden kann. Selbst wenn in den meisten Pfad-Berechnungen nicht der teure worst-case eintritt, so summiert sich der ganze Berechnungsaufwand beträchtlich. Das dürfte dem Laggen entsprechen von dem einige Tester berichtet haben. Und der eigentliche Clou folgt: Ich habe Monte Carlo als Suchverfahren gewählt, dessen wirklicher Nutzen nur dann ensteht, wenn möglichst viele Situationen für jede Aktion simuliert werden können. Normalerweise rechnet man mit über 100'000 berechneten Spielen in wenigen Sekunden. Bei meinem Rechner kam ich auf wenige Tausend - zu wenig, um anfangs gute Züge zu finden. Auch nachdem ich Tricks versucht habe, der KI illegale Züge für die Simulation zu erlauben und falls der beste Zug zufällig illegal ist, den nächstbesten legalen Zug zu wählen. Dies brachte aber letztlich keinen großen Mehrgewinn. Es hätte hier noch ein großer Optimierung bedarft (effizientere Spielbrett-Repräsentation, Zügeberechnung, Ausnutzung von paralleler Berechnung). Dafür fehlte im letzten Wochenende allerdings noch die Zeit...
Im Nachhinein hätte ich wohl gleich auf gute Heuristiken setzen sollen oder vielleicht doch eher stattdessen den Online-Multiplayer bauen sollen. Letztlich hat aber die Umsetzung wieder Spaß gemacht und konnte etwas abgeben, was zumindest in Teilen fertig ist und funktioniert. :)
fin
