[ZFX Action] Quoridor

Dreizehnte ZFX Action vom 7.4.2017, 19 Uhr bis zum 30.4.2017, 19 Uhr. Thema ist "Brettspiel". Seid kreativ!
Antworten
PiIstGenauDrei
Beiträge: 87
Registriert: 23.09.2010, 17:18

[ZFX Action] Quoridor

Beitrag von PiIstGenauDrei »

Hallo zusammen,

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ü:
Bild

Spiel starten:
Bild

Im eigentlichen Spiel:
Bild

In-Game-Erklärung:
Bild

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
Zuletzt geändert von PiIstGenauDrei am 04.05.2017, 09:41, insgesamt 3-mal geändert.
Benutzeravatar
xq
Establishment
Beiträge: 1581
Registriert: 07.10.2012, 14:56
Alter Benutzername: MasterQ32
Echter Name: Felix Queißner
Wohnort: Stuttgart & Region
Kontaktdaten:

Re: [ZFX Action] Quoridor

Beitrag von xq »

Sehr lobenswert, einen Linux-Build anzubieten, aber: Bevorzuge bei Linux immer x86_64 über x86, da die meisten Installationen nur x86_64 können ;)

Zum Spiel:
Sparsame, aber aussagekräftige Darstellung, macht aber Gegen den KI-Gegner leider etwas wenig Spaß (muss mal jemand finden, der mit mir Spielen will).

Ich würde die Möglichkeiten bei der Bewegungsoption Highlighten, bevor ich sie mit der Maus hovere, ich musste erst mal das halbe Spielfeld absuchen ^^
War mal MasterQ32, findet den Namen aber mittlerweile ziemlich albern…

Programmiert viel in ⚡️Zig⚡️ und nervt Leute damit.
Benutzeravatar
Max Gooroo
Establishment
Beiträge: 341
Registriert: 08.12.2012, 23:16
Wohnort: Dresden
Kontaktdaten:

Re: [ZFX Action] Quoridor

Beitrag von Max Gooroo »

Yay ... ich bin direkt durchgelaufen und habe gewonnen :D

Also ... Steuerung ... könnte viel direkter ... immer erst Button und dann Aktion ist doof ...
How about ... wenn man auf ein angrenzendes Feld klickt automatisch Move, dazwischen automatisch Wand ... direkt gespart.

Und dass er bei Zug erst einmal wartet (vermutlich KI Berechnung?), ist auch mega verwirrend. Erst bewegen, dann vielleicht Text einblenden (Paul denkt gerade nach) :D

Ansonsten könnte auch das mit sound und netzwerk ganz spassig sein ... halt ein ordentliches Brettspiel.
Benutzeravatar
marcgfx
Establishment
Beiträge: 2050
Registriert: 18.10.2010, 23:26

Re: [ZFX Action] Quoridor

Beitrag von marcgfx »

Ich kenne das Spiel nicht, sieht interessant aus. Läuft ja schon gut, die KI macht aber echt nur Mist :) (aber immerhin hast du ne KI)
Gute Arbeit!
scheichs
Establishment
Beiträge: 845
Registriert: 28.07.2010, 20:18

Re: [ZFX Action] Quoridor

Beitrag von scheichs »

Interessante Spielidee. KI setzte bei mir nur (Random-)Wände? How To Play is immer nice.
Aber die Steuerung ist wirklich kompliziert und zumindest im WebGL hakte es auch des öfteren mit den Moves.
PiIstGenauDrei
Beiträge: 87
Registriert: 23.09.2010, 17:18

Re: [ZFX Action] Quoridor

Beitrag von PiIstGenauDrei »

Danke für das Lob & Kritik von allen. :-) Ich werde die nächsten Tage noch eure Beiträge anschauen und etwas dazu schreiben.

Was die Steuerung angeht: Ich hatte bei der Umsetzung auch Touch im Hinterkopf. Dabei dachte ich mir aber auch, dass die Gefahr zu groß ist, dass Leute mit Wurstfingern die falschen Aktionen drücken würden. Daher schon vorher quasi die Abfrage, was für eine Aktion getätigt werden soll.

Zum Laggen & KI-Ausfall: Sowohl die KI als auch das belanglose Berechnen der möglichen Züge ist leider recht teuer. Ich habe dazu im Ursprungspost noch ein paar Worte geschrieben.

@MasterQ32: Das Linuxbuild für x86_64 habe ich ergänzt.
Antworten