Pfadfinder-Algorithmus

Ein Spiel, das vom Weg abkommt - und wie Sie ihn dennoch finden.

Das Spiel ist laut Hersteller ab dem Alter von 5 Jahren empfohlen. Da die Regeln komplex sind und auch einiges gezählt und gerechnet werden muss, sollten Jüngere beim Spiel von Erwachsenen begleitet werden. Aber sollte das Spiel überhaupt gespielt werden? Das Team des Wiener Bildungsservers hat "Pfadfinder-Algorithmus" getestet und sich auf die nervenaufreibende Suche nach dem Eiswagen gemacht.

Und so viel sei bereits jetzt vorweggenommen: Leider kommt das Spiel sehr rasch vom Weg ab. Wir zeigen Ihnen dennoch, wie Sie auf den richtigen Pfad zurückfinden und sich Wissen zu Wegfindungsalgorithmen aneignen können.

Kontext

Der Name "Pfadfinder-Algorithmus" ist eine direkte Übersetzung aus dem Englischen (pathfinding algorithm) und im Deutschen nicht gebräuchlich. Hier ist die Bezeichnung "Wegfindungsalgorithmus" üblich. Diese Algorithmen dienen dazu, einen optimalen Pfad von einem Startpunkt zu einem Zielpunkt zu finden. Ein solches Programm berechnet den Weg in einem Netzwerk (Graph) von möglichen Zielpunkten, oder auch Knoten, und Verbindungswegen, den sogenannten Kanten. Diese Wegfindung versucht das Spiel abzubilden.

Inhalt

Das Spiel ist für zwei bis drei Personen spielbar. Das umfangreiche Spielmaterial besteht aus einem Holzkasten, der ein Tablet darstellen soll. Drei Lochplatten aus Holz können als unterschiedliche Spielpläne eingeschoben werden. Für die dritte Spielvariante gibt es 15 zusätzliche Vorlagen zum Einschieben (zwischen Lochplatten und Holzkasten). Das Spielfeld stellt einen Park dar, der mit doppelseitigen Wegkarten auf eine der eingeschobenen Lochplatten aufgelegt wird. 

Die einzelnen Wegpunkte im Park werden durch Holzzylinder markiert. Es ist damit eine große Zahl an unterschiedlichen Konfigurationen des Spielfelds möglich. Die Spielfiguren sind herzige hölzerne Hunde. Jede:r Spieler:in markiert den gegangenen Weg auf Legetafeln mithilfe von Wegpunkt-Plättchen und Pfötchen-Chips, die die Zahl der Schritte symbolisieren. 

Durch das in sechs Sprachen vorliegende und in winziger Schrift gedruckte Handbuch führen die Comicfiguren Pixi und Cody. Deren Roboterhund WiFi (die Nerdversion von Wuffi?) soll, so die Rahmenhandlung, immer schlauer werden und wird daher mit immer neuen Algorithmen trainiert. Ziel des Spiels ist es, in einem Park den schnellsten Weg zum Eiswagen zu finden.

Spielablauf - wie es funktionieren sollte

Zu Beginn werden die Spielmaterialien vorbereitet. Jede:r Spieler:in bekommt eine Legetafel und einen Satz von Wegpunkt-Plättchen, um den gegangenen Pfad zu markieren. Dabei fällt auf, dass die Zeichnungen auf den Wegpunkt-Plättchen teilweise nicht klar unterscheidbar sind. So sieht der Fuchs dem Eichhörnchen zum Verwechseln ähnlich. Die Pfötchenkarten werden in die Mitte gelegt. Das Spielfeld wird auf dem Holzkasten aufgebaut.

Es gibt drei Spielvarianten:

Spielvariante 1
Bei der ersten, dem Zufallsweg, gehen alle Spielenden einen beliebigen Weg vom Startfeld zum Eiswagen. Die Wegkarten sind umgedreht und zeigen nur die Verbindungen zwischen den Punkten, nicht die Weglänge - es gibt schnelle Asphaltwege, Schotterwege und verschlungene Waldwege. Wie lang der Weg dann tatsächlich war, zeigt sich erst, wenn die Wegkarten aufgedeckt werden - der scheinbar kürzeste Weg kann damit deutlich länger werden. Jede Person zählt nun ihre tatsächliche Weglänge anhand der Pfötchenkarten zusammen, und der/die tatsächliche Sieger:in wird ermittelt.

Schon in dieser Variante zeigen sich grundlegende Probleme. Da nur eine Spielfigur auf einem Punkt stehen darf, aber vom Startfeld nur zwei Pfade wegführen, darf die dritte Spielfigur in der ersten Runde eigentlich keinen Schritt machen. Weil keine weiteren Informationen zur Verfügung stehen, wird man immer bestrebt sein, den scheinbar kürzesten Weg zu gehen, da dieser doch die höchste Wahrscheinlichkeit hat, der tatsächlich kürzeste zu sein. Dieser Weg steht aber nur der Person offen, die den ersten Zug macht: Es ist verboten, einer anderen Figur auf dem exakt gleichen Weg nachzugehen. 

So ist auch ein echter Zufallsweg kaum möglich, da oftmals ohnehin nur ein einziger Weg zur Verfügung steht. Zufallsweg würde außerdem bedeuten, dass auch ein Schritt rückwärts gemacht werden kann. Abgesehen davon, dass das im Spielkontext sinnlos wäre, lässt sich auf den Legetafeln auch kein Weg abbilden, der länger als sieben Schritte ist. Damit werden zwar alle Punkte auf dem Spielfeld erreicht, aber ein Umweg (bzw. eben ein Schritt rückwärts) kann in vielen Fällen schon nicht mehr dargestellt werden.

Spielvariante 2
In der zweiten Spielvariante stehen auf der Rückseite der Wegkarten mehr Informationen zur Verfügung: Asphalt-, Schotter- und Waldwege sind markiert, aber nicht ihre Länge. Auch hier zeigen sich die gleichen Probleme wie in Variante 1. Der/die Startspieler:in ist unschlagbar, da er/sie den optimalen Weg, der nun besser zu erkennen ist, als Erste:r gehen darf.

Spielvariante 3
In der dritten Spielvariante werden Vorlagekarten eingeführt, die unter den Lochkarten eingeschoben werden und durch immer dunkler werdende Farbpunkte den Weg zu einem geheimen Ziel zeigen. Nur der neu eingeführte "Superspürhund" darf die Wegpunkte aufdecken und sieht so den kürzesten Weg zum Ziel. Dies führt zu neuen Problemen. Die Farbwechsel auf den Vorlagekarten sind so subtil, dass sie oft kaum erkennbar sind. 

Während der Superspürhund über alle Informationen verfügt, sind die übrigen Spielenden auf den Zufall angewiesen. Und nicht nur das: Sie wissen erst, wo das geheime Ziel ist, wenn der Superspürhund es erreicht und aufgedeckt hat. Es kann also sein, dass jemand das Ziel bereits vorher zufällig erreicht hat, ohne es zu wissen.

Kurz: Mit Verwirrung, Frust und Ärger ist in jeder der drei Varianten zu rechnen.

Fazit

Das Spiel in seiner derzeitigen Form hätte bereits in der ersten Testphase vor der Veröffentlichung verworfen werden sollen. Eine solche Testphase hat aber wahrscheinlich nicht stattgefunden. Die Zugregeln schreiben etwa vor, dass immer nur eine Spielfigur auf einem Platz stehen darf. 

Da schon vom Startfeld aus nur zwei Wege zum nächsten Feld führen, das Spiel aber angeblich zu dritt spielbar ist, müsste bereits in der ersten Runde der/die dritte Spieler:in aussetzen. Wäre das Spiel auch nur ein einziges Mal getestet worden, wäre das sofort aufgefallen.

Wir waren beim Test geradezu entgeistert, wie ein hochwertig aussehendes Spiel eines renommierten Herstellers in jeder, wirklich jeder Beziehung derart versagen kann. Dabei ist das Spielmaterial stabil und hochwertig. Die Spielregeln liegen in sechs Sprachen übersetzt vor. Auch bei der technischen Umsetzung, etwa mit den einschiebbaren Vorlagekarten für den Bergsteiger-Algorithmus, hat man sich einiges überlegt. Es ist schwer nachvollziehbar, dass niemandem in dem zweifellos umfangreichen Entwicklungsteam die frappierende Sinnlosigkeit des Unterfangens aufgefallen ist.

Das Gameplay ist uninteressant, lässt jegliche Rückschlüsse auf den aktuellen Spielerfolg vermissen und ermöglicht keinerlei Taktik. Ein gutes Spiel muss nach jedem Zug Feedback über den aktuellen Spielstand geben. Habe ich erfolgreich ein Paar Memorykarten aufgedeckt? Hat der gegnerische Turm meinen Läufer geschlagen? Muss meine Monopoly-Figur ins Gefängnis? Das sind notwendige Informationen, die meine weiteren Entscheidungen im Spiel beeinflussen. 

Spielerfolg oder Misserfolg der einzelnen Spielenden bleiben hier jedoch während des gesamten Spielverlaufs im Unklaren und werden erst am Ende aufgedeckt. Menschliche Denkfähigkeit ist daher nicht notwendig; spannender wäre es wahrscheinlich, Hühner, Wombats oder die sprichwörtlichen Affen die Figuren nach dem Zufallsprinzip ziehen zu lassen und auf diese Wetten abzuschließen.

Für Fünfjährige ist das Spiel zu komplex und der Spielverlauf zu langweilig. Das hübsch gemachte Spielmaterial und die netten Figuren sind hier die einzigen Anziehungspunkte. Ältere vermissen die Möglichkeit, eine eigene Strategie zu entwickeln. Durch die begrenzte Zahl der Wege und das Verbot, auf demselben Feld wie ein:e andere:r Spieler:in zu stehen, bleibt oft ohnehin nur ein einziger Weg Richtung Ziel übrig.

Auch als Lernspiel funktioniert es nicht. Das Spiel vermittelt kein greifbares Wissen über Wegfindungsalgorithmen. Allenfalls erfährt man, dass für die Ermittlung des optimalen Weges die Wegekosten bekannt sein müssen. Je mehr Informationen über den Weg zur Verfügung stehen, desto besser funktioniert der Algorithmus. Das wird tatsächlich im Spiel dargestellt, doch in der ersten und dritten Spielvariante stehen mir eben keine Informationen über den richtigen Weg zur Verfügung. Blind einen Weg zu gehen, dessen tatsächliche Kosten ich nicht kenne, ist frustrierend und trägt gerade NICHT dazu bei, einen Algorithmus zu verstehen.

Womöglich ist das "Spiel" nur als Illustration eines Konzeptes ohne tatsächlichen beabsichtigten Spielwert zu verstehen? Abgesehen davon, dass immer wieder ein "Spielspaß" in den Regeln behauptet wird, verfängt auch diese Erklärung nicht. Der einzige hier vorgestellte Algorithmus, der Bergsteiger-Algorithmus, gilt als Optimierungs-, nicht als Wegfindungsalgorithmus. Tatsächliche Wegfindungsalgorithmen wie der Dijkstra- oder der A*-Algorithmus werden zwar in den Regeln erwähnt, aber im Gameplay nicht abgebildet.

Schließlich ist das Spiel mit den vorgegebenen Regeln unspielbar und offensichtlich nicht ausbalanciert. Schon der erste Zug ist für die dritte Person unmöglich. Der/die Erstspieler:in hat den unschätzbaren Vorteil, den scheinbar schnellsten Weg gehen zu können, ohne jedoch zu wissen, ob es tatsächlich der schnellste ist. Das sorgt für Frustration bei allen Beteiligten.

Darüber, dass die Spielregeln natürlich nicht gegendert sind, regen wir uns dann schon gar nicht mehr auf.

Was wir stattdessen empfehlen

Wer stattdessen herausfinden möchte, wie Wegfindungsalgorithmen funktionieren, findet auf der Webseite von Red Blob Games eine Reihe von interaktiven Animationen zum Thema. Hier wird leicht verständlich (wenn auch in englischer Sprache) erklärt, wie ein Netzwerk aufgebaut sein muss, damit es von einem Wegfindungsalgorithmus analysiert werden kann. Dann werden die Funktionsweisen des Breadth First Search Algorithmus, des Dijkstra- und des A*-Algorithmus demonstriert sowie ihre Vor- und Nachteile erläutert.

Die Arbeitsweise der Algorithmen wird in einem regelmäßigen Raster gezeigt, wo sie sich am einfachsten darstellen lässt. Breadth First Search (BFS) kann feststellen, welche Felder (oder Zellen) in diesem Raster überhaupt erreichbar sind. Dabei werden die Felder vom Startfeld aus in einer konzentrischen "Welle" schrittweise erfasst und die Schrittzahl dorthin gespeichert. 

Hindernisse blockieren den direkten Weg zum Nachbarfeld und müssen umgangen werden. Um anschließend einen Weg zu jedem beliebigen Zielpunkt zu finden, muss in jeder Zelle die Richtung gespeichert werden, von welchem Nachbarn die Suchfunktion gekommen ist. Dann kann rückwärts vom Zielpunkt aus der Weg ermittelt werden.

Eine Weiterentwicklung von BFS ist der nach seinem Entwickler benannte Dijkstra-Algorithmus. Er ist in der Lage, unterschiedliche Wegekosten einzubeziehen, also zB. Unterschiede zwischen Fortbewegung auf der Straße oder durch einen Wald, und daraus den optimalen Weg zu bestimmen. 

Wenn nur ein einziges Ziel erreicht werden soll, sind beide nicht effizient. Hier wird oft der A*-Algorithmus (englisch A-Star ausgesprochen) verwendet. Er bezieht sowohl die Entfernung vom Startpunkt als auch zum Zielpunkt ein und sucht immer in der erfolgversprechendsten Richtung.