Kurz-Motivation

“Morphling” ist ein Computer-Programm, mit dem sich ganze Klassen von kombinatorischen Zwei-Personen-Spielen gestalten und spielen lassen. Programme wie Morphling helfen, den Prozess des Spiele-Erfindens zu beschleunigen.

Inhalt

1. Einleitung
2. Kriterien zur automatischen Bewertung der Interessantheit eines Spiels
3. Das Multi-Spiel-Programm “Morphling” und seine Spielklasse “Clobber”
4. Bewertung des Muster-Spiels SideKicker
5. Abschließende Bemerkungen und ein Blick nach vorn
6. Danksagungen

1. Einleitung

Tom Werneck hat das Büchlein “Leitfaden für Spiele-Erfinder und solche, die es werden wollen” geschrieben. Es ist ein Klassiker geworden mit inzwischen fünf Auflagen [Wer2002]. Werneck misst dem folgenden Aspekt beim Spiele-Erfinden eine Schlüsselstelle zu:

Bevor ein neues Spiel einem Hersteller vorgeschlagen werden kann, hat der Erfinder intensive Testspiel-Serien durchzuführen, mit etlichen Zyklen von Verbesserung, Modifikation und neuem Testen. Freunde und Verwandte mancher Spiele-Erfinder können ausführlich erzählen, wie sie solche Testmarathons genossen oder ehrlicher, unter ihnen gelitten haben. Das Hauptproblem ist, dass das Testspielen ermüdend werden kann, wenn sehr viele Varianten – meist nur Mikro-Mutationen voneinander – auf den Tisch kommen, Abend für Abend, Woche für Woche. Am Ende hat mancher Testspieler seine Begeisterung für das Spiel vollkommen verloren und ist so abgestumpft, dass er Detail-Unterschiede gar nicht mehr wahrnimmt.

Meine Idee war, ein Computerprogramm zu entwickeln, dass einen beträchtlichen Teil der Testarbeit übernehmen kann. An meinem Lehrstuhl (der Lehrstuhl für Mathematische Optimierung, Anm. d. Red.) an der Uni Jena hat der Diplomand Thomas Rolle mit “Morphling” solch ein Programm realisiert.

2. Kriterien zur automatischen Bewertung der Interessantheit eines Spiels

Angenommen, für ein bestimmtes Spiel A gebe es ein Computer-Programm X, welches A spielen kann. Die folgende Aufzählung enthält etliche Kriterien, um die “Interessantheit von A modulo X” zu messen. Mit dem Konzept des computer-unterstützten Spiele-Erfindens im Hinterkopf war meine Hauptabsicht, nur solche Aspekte in die Liste zu nehmen, die automatisch bewertet werden können. Ein Computerprogramm (wie Morphling) soll automatisch lange Serien von Testspielen (so genannte “Sparrings-Wettkämpfe”) gegen sich selbst bestreiten, und anschließend wird das Spiel A mittels statistischer Auswertung der Ergebnisse bewertet.

Durchschnittliche Partie-Länge

Leute mögen es nicht, wenn Spiele zu kurz oder zu lang sind. Ein Erfinder kann Intervalle für die akzeptable Spiellänge vorgeben und auch, in welchem Ausmaß Fluktuationen der Spiellänge akzeptabel oder willkommen sind.

Remis-Quoten

Menschliche Spieler mögen es nicht, wenn ein Spiel zu oft unentschieden ausgeht. Auf Meister-Ebene sind Mühle und verschiedene Varianten des Damespiels sehr prominente Problemfälle. Schach könnte, wenn es noch besser verstanden wird, eines Tages auch problematisch werden. Ein Erfinder mag Intervalle für akzeptable Remisquoten vorgeben, beispielsweise zwischen 0 und 30 Prozent Unentschieden ist okay. Es kann übrigens auch sein, dass eine halbwegs große Remisquote gar nicht so schlecht ist: Manche Spieler mögen es gar nicht so sehr, wenn es immer einen Sieger und damit auch einen Verlierer geben muss.

Hat ein bestimmter Spieler einen Vorteil?

Schön ist es, wenn alle Beteiligten die gleichen Gewinnchancen haben. In einigen Spielen hat aber eine Seite, zum Beispiel der Spieler mit dem ersten Zug, einen entscheidenden Vorteil. Der Erfinder mag eine Schwelle M vorgeben und nur Spiele akzeptieren, in denen jede der Seiten in höchsten M Prozent der Fälle gewinnt. In einem Spiel mag es verschiedene Gewinnbedingungen geben, z.B. Spieler 1 siegt durch Matt, Spieler 1 siegt durch Ersticken, Spieler 2 siegt durch Erreichen der gegnerischen Brettseite usw. Hat man etliche Gewinnbedingungen, so mag der Erfinder eine Schranke T vorgeben und nur Spiele akzeptieren, bei denen jedes der Kriterien in höchstens T Prozent der Fälle für das Spielende verantwortlich ist.

Abwechslungs-Reichtum

Menschen mögen es nicht, wenn in einem Spiel immer die genau gleichen Züge erzwungen sind, oder wenn ein Computer-Gegner vollkommen deterministisch ist und auf die gleichen Züge immer identisch antwortet. In Programmen wie Morphling oder Zillions-of-Games lässt sich ein Parameter Variabilität des Computers einstellen. Nur Spiele mit einer gewissen Variabilität sind akzeptabel. Der Abwechslungs-Reichtum mag nicht so sehr durch Ausführen ganzer (automatischer) Testspielserien ermittelt werden, sondern eher durch wiederholte Computer-Suche in einzelnen Positionen.

Leistungsverlust durch großen Abwechslungs-Reichtum

Oft hat großer Abwechslungs-Reichtum seinen Preis in Form von verminderter Spielstärke. Ein Erfinder mag vorgeben, wie viel Leistungs-Verlust akzeptabel ist, wenn mit großer Variabilität gegen kleine Variabilität gespielt wird.

Mehr Leistung durch längeres Rechnen?

Aus der Computerschach-Praxis ist bekannt, dass längere und damit tiefere Spielbaumsuche zu besserer Leistung führt [Hei2000]. Dieses Phänomen ist bei fast allen “normalen” kombinatorischen Zwei-Personen-Spielen zu beobachten. Es mag Sinn machen, neue Spiele nur zu akzeptieren, wenn das bei ihnen auch der Fall ist. Natürlich hängt dieses Kriterium wesentlich von dem benutzten Programm X ab.

Glattheit der Zugkandidaten beim Iterativen Vertiefen

Normale Spielbaum-Suche benutzt einen iterativen Vertiefungs-Mechanismus. Dabei wird der Spielbaum in immer ausgedehnteren Schichten durchsucht; für Beschreibung und intensive Experimente siehe z.B. die Dissertation von Ernst Heinz [Hei2000]. Es kann passieren, dass die Zugkandidaten bei diesem Prozess häufig wechseln und auch, dass die Stellungs-Bewertungen zwischen den Iterationen stark hin und her schwingen. Typischerweise ist solch etwas ein Anzeichen, dass das Programm X das Spiel A nicht gut versteht.

In den einzelnen Punkten hieß es immer, dass das Spiel A (nur) akzeptabel sei, wenn der entsprechende Parameter in einem gewissen Intervall liege. Natürlich können die Daten aber auch benutzt werden, um verschiedene Varianten eines Spiels miteinander zu vergleichen. Dazu kann man zum Beispiel eine Interessantheits-Funktion als gewichtete Linearkombination aus einzelnen Kriterien zusammensetzen:

Interessantheit
     = 0,5 · Wert der Chancen-Ausgeglichenheit
     + 0,3 · Wert der durchschnittlichen Partielängen
     + 0,2 · Wert der Variabilität.

weiter

Referenzen

[Wer2002]

T. Werneck. Leitfaden für Spieleerfinder und solche, die es werden wollen. Ravensburger Spieleverlag, Ravensburg, 5. Auflage, 2002.
(Zu beziehen unter www.spiele-archiv.de)

[Hei2000]

Ernst A. Heinz: Scalable Search in Computer Chess.
Vieweg-Verlag, Braunschweig, 2000.