Montag, 7. November 2016

Jass-Spielpläne ohne Wiederbegegnung

Das Jass ist ein im alemannischen Sprachraum verbreitetes Kartenspiel mit vier Spielern. Es erfreut sich in der Schweiz großer Beliebtheit, und häufig werden Jass-Turniere organisiert, bei denen in jeder Runde an mehreren Tischen gleichzeitig gespielt wird. In der folgenden Runde wechseln die Teilnehmer nach einem vorgegebenen Spielplan ihre Plätze und spielen somit gegen andere Teilnehmer.

Dabei soll der Spielplan gewährleisten, dass eine maximale Durchmischung stattfindet. Die Spieler sollen idealerweise in jeder Runde gegen andere Spieler antreten. Eine Frage, die man sich hierbei stellen kann, ist:

Wieviele Runden kann ein Spielplan maximal vorsehen, so daß sich keine zwei Teilnehmer in mehr als einer Runde an einem Tisch begegnen?
Nehmen wir ein Turnier in mittlerer Größe an, mit 24 Teilnehmern, die somit an sechs Tischen miteinander spielen.

Eine Obergrenze für die Rundenzahl ergibt sich natürlich aus der Gesamtzahl der Spieler: da jeder Spieler in jeder Runde gegen drei andere Teilnehmer antritt, kann es nicht mehr als sieben solcher Runden geben: denn in einer achten Runde gäbe es nur noch zwei Spieler, gegen die er noch nicht gespielt hat – nicht genug, um einen Tisch vollzubekommen. Nun ist dies eine sehr theoretische Obergrenze. Ich kann zeigen:

Ein Spielplan kann maximal genau M=5 Runden enthalten, in denen jeder Spieler in jeder Runde gegen andere Leute spielt.
Obwohl ich das dringende Gefühl habe, dass es einen sehr einfachen Beweis geben muss, um M=6 und M=7 auszuschließen, habe ich einen solchen nicht gefunden. Ich kann im folgenden nur einen Computerbeweis angeben, und diese haben die unschöne Eigenschaft, daß sie von einigen sehr puristischen Mathematikern nicht anerkannt werden – im Grunde mit dem gleichen Argument, das vor über zweitausend Jahren schon zum Ausschluß von Archimedes aus der Akademie der Wissenschaften von Alexandria geführt hat: daß nämlich durch Beweise dieser Art – ebenso wie durch die damaligen Wasserverdrängungsmessungen des Archimedes – "der reine Geist der Mathematik mit schmutziger Materie befleckt wird". Wer es also schafft, einen rein geistigen Unmöglichkeitsbeweis für die Fälle M=6 oder wenigstens M=7 zu führen, ist herzlich eingeladen, mir diesen mitzuteilen.

Doch nun zur Beweisführung. Sämtliche möglichen Spielpläne maschinell durchzurechnen, sprengt sehr schnell die Leistungsgrenzen von Computern. Eine einzelne Runde bietet ja bereits 24! = 6.2045·1023 Möglichkeiten, die Spieler aufzuteilen. Mit allzu brutaler brute force geht es also nicht. Wir müssen ein paar Symmetrie- oder Äquivalenzüberlegungen voranstellen, um die Zahl der zu prüfenden Möglichkeiten signifikant zu verringern.

Schauen wir uns einmal einen Spielplan mit zwei Runden an, der die gewünschte Bedingung erfüllt:

Wie man an den Farben direkt sieht, sitzt jeder Spieler in der zweiten Runde tatsächlich nur mit Spielern an einem Tisch, die in der ersten Runde an anderen Tischen saßen. Dieses Beispiel beweist also durch seine bloße Existenz: M≥2.

Hinter diesem Übergang von der ersten zur zweiten Runde verbirgt sich eine Struktur, die ich (4,4)-Relation nenne: wenn wir uns die Sache auf Tischebene anschauen, steht jeder Tisch der ersten Runde mit genau vier Tischen der zweiten Runde in Beziehung: nämlich mit den vier Tischen, an denen seine Spieler in der zweiten Runde Platz nehmen. Umgekehrt steht jeder Tisch der zweiten Runde mit genau vier Tischen der ersten Runde in Beziehung: nämlich den vier Tischen der ersten Runde, von denen die Spieler des Tisches in der zweiten Runde herkommen.

Wir haben also dem Übergang von der ersten zur zweiten Runde eine Relation R auf der Menge mit 6 Elementen zugeordnet, mit der Eigenschaft |R-1(x)| = |R(x)| = 4 für alle x = 1,...,6. Eine solche Relation läßt sich – wie jede Relation – als eine nur mit Nullen und Einsen besetzte quadratische Matrix darstellen. In diesem Beispiel hat die Matrix die Gestalt

Relation der beschriebenen Art sind dadurch charakterisiert, dass ihre darstellende Matrix in jeder Spalte und in jeder Zeile genau vier Einsen (und somit genau zwei Nullen) enthält. Die Menge solcher Matrizen bildet eine Teilmenge aus der Menge aller Relationen. Hat letztere 236 Elemente (klar: auf jedem Platz der Matrix kann eine Eins oder eine Null stehen), enthält erstere nur noch 67950 Elemente. Das kann man durch simples Durchzählen ermitteln, etwa in einem kleinen JavaScript-Programm. Es ist aber auch eine in der Mathematik bekannte Zahl aus der relativ gut erforschten OEIS-Zahlenfolge A001499. Nennen wir diese Menge R64;4

Nun ist klar, dass die Lösung eine Lösung bliebe, wenn man die Tische in der ersten oder zweiten Runde einfach nur umstellen würde. Mathematisch gesprochen, bedeutet dies, dass die Gruppe 𝔖6 der 6!=720 Permutationen (möglichen Umstellungen) der Tische von links und von rechts auf R64;4 operiert. Lösungen, die bis auf Anordnung der Tische gleich sind, wollen wir als äquivalent betrachten.

In welche Äquivalenzklassen (Orbits) zerfällt die Menge R64;4 bezüglich dieser Relation?

Auch dies lässt sich rechnerisch ermitteln: ich habe es hier getan. Das Ergebnis:

  1. Orbit mit 1350 Elementen
  2. Orbit mit 16200 Elementen
  3. Orbit mit 7200 Elementen
  4. Orbit mit 43200 Elementen

Hier sind Repräsentanten für die vier Orbits, wobei ich jeweils eine symmetrische Matrix als Repräsentant gewählt habe:

Da die Umordnung der Tische in jedem Schritt keine "neue" Lösung generiert, kann man sich nun darauf beschränken, für jeden Übergang von einer Runde zur nächsten genau eine aus diesen vier konkreten Relationen zugrundezulegen. Man hat damit eine Vorschrift, an welchen Tischen die Spieler eines Tischs in der nächsten Runde gelangen, wobei automatisch sichergestellt ist, dass keine zwei Spieler desselben Tischs wieder an einem Tisch landen - denn die vier Spieler eines Tischs der neuen Runde kommen ja immer auch von vier verschiedenen Tischen der vorherigen Runde. Ob die Spieler allerdings in irgendwelchen davor liegenden Runden gegeneinander spielten, kann man damit natürlich nicht ausschliessen.

Es gibt nun noch einen weiteren Freiheitsgrad: man kann nicht nur für den Übergang von einer Runde zur nächsten eine der vier o.a. Relationen verwenden, sondern darüberhinaus auch die vier Spieler, die an einem Tisch landen, beliebig permutieren. Das scheint auf den ersten Blick genauso irrelevant wie das Umordnen der Tische - ist es aber nicht: denn die Reihenfolge der Spieler am Tisch entscheidet darüber, an welchen vier Folgetischen sie jeweils landen (wenn die Konvention ist, dass der erste Spieler des Tischs am am weitesten links liegenden Tisch landet, zu dem sein Tisch in Relation steht, der zweite dann am zweiten usw. - dies nur, um für die (4,4)-Relationen eine eindeutige Vorschrift für den Übergang zur nächsten Runde einzurichten). Da wir an jedem Tisch eine solche Permutation vornehmen können, haben wir weitere (4!)6 = 191'102'976 Möglichkeiten pro Runde.

Das ist immer noch gewaltig viel, möchte man meinen – zumal sich die Möglichkeiten ja pro Runde multiplizieren müssten. Nun fallen aber viele Möglichkeiten weg – die meisten Spielpläne verletzen die Anforderung, dass keine Wiederbegegnung mit Spielern aus früheren Runden stattfinden darf: diese brauchen dann natürlich auch nicht mehr fortgesetzt zu werden. Ebenso gibt es terminale, nicht mehr erweiterbaren Spielpläne, bei denen jede mögliche nächste Runde zu Wiederbegegnungen führt.

Diese Überlegung gab mir Anlaß zu einem Backtracking-Verfahren: ich versuche, einen bereits bis zu einer bestimmten Runde aufgebauten Plan weiter zu ergänzen, indem ich die Tischpermutationen und die Übergangsmatrizen der Reihe nach anwende und schaue, ob eine begegnungsfreie Runde entstanden ist. Wenn ja, versuche ich, noch weiter fortzufahren (also weitere Runden anzufügen). Wenn nein, melde ich den bis dahin aufgebauten Spielplan als "terminalen" (nicht mehr erweiterbaren) Spielplan an das Hauptprogramm und setze dann auf der letzten Runde auf, um weitere Kombinationen zu finden (pro Runde habe ich mir den "Zustand" gemerkt: den aktuell verwendeten Vektor von sechs Permutationen, und die aktuell verwendete Übergangsmatrix).

Hier ist eine terminale Lösung mit fünf Runden – zugleich der Beweis für M≥5 (ich habe die Tischanordnungsfreiheit noch genutzt, um die Spieler 1 bis 4 ab der zweiten Runde an den Tischen 1 bis 4 sitzen zu lassen):

Der Algorithmus ist alle Möglichkeiten durchgegangen und hat keine Spielpläne mit mehr als fünf Runden gefunden. Das ist der Computerbeweis für M=5.

Wer es selbst überprüfen möchte (ich finde zwar keinen Fehler im Algorithmus, aber Menschen machen Fehler): der Algorithmus ist hier als Worker implementiert und wird von der Webseite http://ruediger-plantiko.net/jass/ aufgerufen.

Keine Kommentare :