Inhalt:

Fuchs und Henne ist ein traditionelles Brettspiel...

...für 2 Personen. Es gehört zu den Strategie- oder Belagerungsspielen.

"Das große Spielebuch" von Erwin Glonnegger erwähnt es nicht, es werden dort aber sehr ähnliche Spiele wie "Bären und Hunde" oder "Ritterspiel" vorgestellt. Ich vermute, dass es sich bei Fuchs und Henne um eine österreichische Variante dieser Spiele handelt, zumindest weisen drei Einträge der Datenbank des Österreichichen Spielemuseums darauf hin.

Die Besonderheit ist die Asymmetrie der Aufgaben

Die Gegner haben unterschiedliche Aufgaben, aus denen ebenso unterschiedliche Strategien entwickelt werden müssen. Dennoch sind die Chancen ausgewogen. Die Asymmetrie ist in diesem Zusammenhang nicht als ein Begriff der Spieltheorie zu verstehen.

Das Spiel erfordert eine strategische Ausrichtung über den ganzen Spielverlauf und taktisches Geschick in bestimmten Zweikampf-Situtationen. Allerdings sind die Anteile der Taktik und Strategie nicht gleichmäßig auf die Spielpartner verteilt (Anfänger spielen meist den Fuchs erfolgreicher).

Während der Fuchs öfter taktische Re-Aktionen zeigen muss und eine explizite Strategie ruhig fehlen kann, ist es für das Spiel der Hennen unbedingt nötig, eine über das gesamte Spiel angelegte Strategie zu entwickeln, z.B. anfangs geschlossenes Vorrücken, dadurch dem Fuchs wenig Aktionsraum geben, eine Nachhut hinten behalten, um Reserven und Lockvögel für das Endspiel zu haben. Taktisch geschickt muss bei dieser Strategie der Zeitpunkt gewählt werden, in dem von der geschlossenen Formation zum Vorrücken auf die Zielfelder übergegangen wird.

Programmierung von Strategie-Spielen (Bezüge zur Künstlichen Intelligenz)

Grundsätzlich stellt sich bei Strategie-Spielen (egal ob Schach, Tic-Tac-Toe oder eben Fuchs und Henne) für Programmierer immer wieder die gleiche Frage:

Wie bringt man den Computer dazu, auf nicht vorhersehbare Reizsituationen angemessen zu reagieren ?

Es geht darum, einigermaßen universelle Problemlösungsstrategien zu entwerfen und dann auf ihre Brauchbarkeit zu testen.

Möglichkeiten strategische Spiele zu programmieren ?

Suchbaum erstellen

Alle möglichen Züge und Spielstellungen werden in einer Baumstruktur dargestellt. An der Wurzel ist die Ausgangstellung, und in der Krone befinden sich alle möglichen Endstellungen. Die Aufgabe des Programms besteht darin, den optimalen Weg durch den Baum zu einer Gewinnstellung zu finden.

Diese Möglichkeit ist nur bei ganz einfachen Spielen mit einer eng begrenzten Zahl potenzieller Züge ( wie Tic Tac Toe) anwendbar. Ich habe sie auch schon einmal bei Master-Mind mit vier Farben verwendet.

Alle folgenden Spielsituationen vorausberechnen

Bei entsprechender Rechnerkapazität ist es möglich, von einer bestimmten Stellung aus alle möglichen Folgestellungen (siehe Suchbaum) bis zu einem Spielende zu berechnen und dann die Entscheidung für die erfolgversprechendste zu treffen. Frühe Schachprogramme haben so gearbeitet. Diese Variante ist wenig elegant und hat auch nur im Output etwas mit Künstlicher Intelligenz zu tun, denn kein Schachmeister (und schon gar nicht ein Anfänger) berechnet pro Zug alle Folgevarianten voraus. Man kann davon ausgehen, dass lediglich die augenblickliche Stellung bewertet und danach die Entscheidung getroffen wird.
Je geübter ein Spieler ist, umso intuitiver erfolgt die Entscheidung. Was wiederum nur aussagt, dass Intuition auf Erfahrung beruhendes Erkennen und Verallgemeinern von Situationen ist.

Bewertungsalgorithmus

Bei dieser Methode gilt es, einen allgemeingültigen Bewertungsalgorithmus für die Spielstellungen zu finden. Ein Regelwerk sorgt dafür, dass eine beliebige Stellung als erfolgreich oder erfolglos eingeschätzt werden kann. Diese Einschätzung kann auf den Gesamterfolg aber auch nur auf Teilziele ausgerichtet sein.

Selbststeuerung und lernfähige Programme

Die edelste Form und die, die meiner Vorstellung von Künstlicher Intelligenz am nächsten kommt, ist es, ein Programm so zu konzipieren, dass es selbst in der Lage ist, von seinem Gegner zu lernen und auf Basis dieser Erfahrung seine eigenen Züge auswählt. Eine einfaches Modell einer Lernmaschine wird nach Donald Mitchie, einem schottischen Biologen benannt.

Man kann es sich so vorstellen, dass jede mögliche Spielstellung auf einer Zündholzschachtel aufgezeichnet wird. Auf dieser Zeichnung markiert man dann mit bunten Pfeilen alle möglichen Züge. In das Innere der Schachtel wird für jeden Pfeil eine Perle gleicher Farbe gelegt. Zu Anfang befinden sich in jeder Schachtel genauso viele Perlen wie Züge möglich sind. Hat man das erledigt, kann das Spiel beginnen. Wenn die Maschine am Zug ist, sucht man die Schachtel mit der betreffenden Spielstellung, legt eine Perle aus dem Inneren auf den Deckel der Schachtel und führt den Zug mit dieser Farbe aus. Dies geht so lange, bis das Spiel entschieden ist. Hat die Maschine gewonnen, werden die Perlen wieder in das Innere gelegt. Die Maschine hat nichts dazu gelernt. Verliert aber die Maschine, wird sie "bestraft", indem alle Perlen auf dem Deckel entfernt werden. Auf diese einfache Art lernt die Maschine, in Zukunft jene Züge zu vermeiden, die nicht zu einem Erfolg führen.

Die Programmierung des Fuchs und Henne –Spieles Fh2002

Allein die Anzahl der möglichen Hennen-Postionen beträgt über 8 Milliarden. Für schieden deshalb die Suchbaum- und Vorausberechnungs-Varianten von vorherein aus.
Es wurden deshalb die letzten beiden der oben dargestellten Möglichkeiten kombiniert. Ein allgemeiner Bewertungsalgorithmus wird unterstützt durch Versuchs- und Irrtumslernen.

Welche grundsätzlichen strategischen Überlegungen gelten für das Spiel.

Überlegungen für den Fuchs

  • Ein guter Fuchsspieler erkennt Schwachstellen der Hennen (schutzlose Hennen, leere Felder, die wegen ihrer Rundumsicht zu besetzen sind) und bewegt sich aktiv darauf zu.
  • Oberstes Ziel ist es, Hennen zu fressen und nicht Felder zu blockieren; sonst wird der Fuchs sehr schnell eingesperrt.
  • Es aber trotzdem günstig, sich in der Nähe der Zielfelder aufzuhalten.
  • Potenzielle Lockvögel der Hennen, die in der Schlußphase den Fuchs aus dem Bau holen sollen, müssen schon frühzeitig bekämpft werden.
  • Da die Hühner nur nach oben ziehen dürfen, erwischt man sie von oben und nicht, in dem man hinter ihnen herfährt.

Diese Überlegungen habe ich im Spiel so realisiert, dass ich bei der Bewertung der Stellung nicht von den unmittelbaren Zugmöglichkeiten der Füchse ausgegangen bin, sondern für jedes freie Spielfeld ein Potenzial errechnen lasse, dem sich die Füchse so gut wie möglich annähern. Wie Haie, die das Blut im Wasser riechen, werden die Füchse von hoch bewerteten Feldern angelockt.

Überlegungen für die Hennen

  • Die Hennen müssen als Schwarm agieren und einen Weg zwischen Risiko und Sicherheit finden.
  • Am Anfang lohnt es sich, eher auf Sicherheit zur gehen, während es in der Schlussphase wichtig ist, den Fuchs durch gezielte Köder aus dem Bau zu locken, um die blockierten Felder füllen zu können.

Die Bewertung einer Situation kann so erfolgen, dass jede Hennen-Position bewertet wird und so der Gesamtwert über alle ermittelt wird. Jeder mögliche Zug wird darauf untersucht, ob die daraus resultierende neue Stellung eine höher oder niedrigere Gesamtbewertung ergibt.

Ich bin auch hier nicht nur von der Bewertung der möglichen Züge, sondern der Annäherung an die optimale Position ausgegangen. Mein Bild dazu war es, die Hennen wie auf einer schiefen Ebene ins Ziel rollen zu lassen und dabei auftretende Hindernisse (z.B. bedrohte Felder) zu umgehen.

Die Spielstärke die allein durch diesen Bewertungsalgorithmus (Spielstärke 1) erreicht wurde, hat mich schon zufriedengestellt. Verblüffend für mich war vor allem, wie die oben angestrebte Strategie wie von selbst "erschienen" ist (Ameisen-Intelligenz).

Selbst altruistisches Verhalten einzelner Hennen zum Wohle des Schwarmes konnte ich beobachten, ohne es eigens programmiert zu haben. Manchmal erscheint etwas intelligent, ohne es wirklich zu sein (siehe Cruse, Dean und Ritter unter Links und Literatur)

Selbstanpassungprozess (Lernfähiges Programm)

Nach einigen Spielen mit dem Bewertungsalgorithmus habe ich entdeckt, dass es sowohl beim Fuchs als auch bei den Hennen trotz grundsätzlich richtigem Spiel ab und zu ganz schlechte Züge gibt, die nicht einmal ein Anfänger machen würde.

Ich habe festgestellt, dass es sich in diesen Fällen um spezielle Situationen handelt, die über den Bewertungsalgorithmus nicht richtig gelöst werden können. Eine Anpassung des Bewertungsschemas an diese Stellungen war nicht sinnvoll, weil es dann seine Allgemeingültigkeit verloren hätte.

Die Lösung war eine Prozedur zu schrieben, die es dem Programm ermöglicht, Erfahrungen zu sammeln und damit genau jene kritischen Situationen durch Versuchs- und Irrtumslernen zu bewältigen.

Das Schema ist recht einfach.

Jede Stellung wird gespeichert. In den Fällen, in denen es einem Hendl gelingt, ins Ziel zu kommen, werden die vorangegangenen drei Hendl-Züge belohnt (Plus-Punkt) und die letzten drei Fuchs-Züge bestraft (Punkteabzug). Wird ein Hendl gefressen, werden die letzten drei Hendl-Züge bestraft und die Fuchs-Züge belohnt.

Der Sieger eines Spieles erhält für jeden Zug des ganzen Spieles einen Pluspunkt. Die Züge des Verlierers werden um eins abgewertet.

In einer Datenbank werden alle Züge gesammelt, und die Bewertungen werden nach jedem Spiel entsprechend ergänzt. Somit entsteht für jeden möglichen Zug ein Wert, der die Bewertung durch den Algorithmus ergänzt. Diese sollte keinesfalls ganz ersetzt werden, denn wie beim menschlichen Lernen soll nur die Auftrittswahrscheinlichkeit für ein früher erfolgreiches Verhalten erhöht bzw. für ein erfolgloses vermindert werden. Gegen einen anderen Gegner oder unter anderen Bedingungen kann das gelernte Verhalten sich als nutzlos oder sogar schlecht erweisen. Seine Auftrittswahrscheinlichkeit soll sich dann wieder entsprechend ändern können. So kann sich das Programm seinem Gegner anpassen.

Ich habe die Lernphase so realisiert, dass ich den Computer in einer Endlosschleife gleichzeitig sowohl den Fuchs als auch die Henne spielen ließ.

Nach 25 Spielen erreichte er für beide Spielstärke 2, nach ca. 50 Spielen war Spielstärke 3 erreicht.

Offensichtlich brauchte der Bewertungsalgorithmus nur geringfügige Korrekturen durch die Erfahrung.