Wie soll ich würfeln?

(Stephan Valkyser, GM in der Abseitsfalle)

Einleitung und Motivation

Nahezu jedem von uns ist es wohl schon einmal passiert, daß er gegen einen ungefähr gleich starken Gegner antreten mußte. Da helfen auch keine taktischen Überlegungen mehr; am Ende läuft es immer auf folgendes (bekanntes) Problem hinaus:

  1. Spiele ich Mittelfeld, dann stürmt er.
  2. Stürme ich, dann mauert er mich aus.
  3. Mauere ich, dann spielt er garantiert Mittelfeld.

Einmal in diese Zwickmühle geraten (die umso grausamer wird, wenn sich die beiden Manager auch noch gut kennen und beide wissen, zu welchen Überlegungen der andere fähig ist) behelfen sich viele Manager mit dem Würfel, z. B.: Bei 1-3 Sturm, bei 4-5 Mittelfeld und bei 6 Mauern. Dies ist im Prinzip gar nicht so schlecht - der Haken an der Sache ist nur die Verteilung der Würfelzahlen auf die einzelnen Taktiken.

Dieses Problem kann man auch mathematisch lösen. Im folgenden liefere ich den Ansatz für das allgemeine Problem und die exakte Lösung für zwei 130-WP-Teams.

Die mathematische Problemformulierung / ein bißchen Spieltheorie

Gehen wir von zwei 130-WP-Teams aus (lauter 10er-Spieler, ohne Heimvorteil und Härte), so gibt es nach allgemeinen Erkenntnissen nur vier sinnvoll erscheinende Aufstellungen (im folgenden reine Strategien genannt):

  1. 10-10-20-20-50 (Sturm)
  2. 10-10-20-50-20 (Mittelfeld)
  3. 10-10-30-40-20 (Rasenschach)
  4. 10-10-40-30-20 (Verteidigung)

United-Experten werden hier schon einwerfen, daß die Rasenschach-Taktik nur gegen schwächere Teams mit (insbesondere) schwächerer Hintermannschaft ihren vollen Effekt erzielt. Nun, wir werden gleich sehen, warum die Rasenschach-Taktik hier minderwertig ist.

Beide Gegner verfügen über dieselbe Strategienmenge {S, M, R, V}. Was jetzt noch fehlt, ist die Auszahlungmatrix A. Sinnvollerweise erhalten die Elemente von A die Punkt-Erwartungswerte der einzelnen Begegnungen, wie sie z. B. UNITED/ST in der Glückswürfeldatei berechnet.

A =
    S M R V  
S ( 1.000 1.206 1.000 0.606 )
M 0.794 1.000 1.144 1.291
R 1.000 0.856 1.000 1.185
V 1.394 0.709 0.815 1.000

Den Eintrag im Feld "S gegen M" berechnet man dabei wie folgt:

Bei Sturm gegen Mittelfeld gibt es 48.892% Siegchance für Team 1, 22.844% Remischance und 28.265% Siegchance für Team 2. Daraus folgt als Erwartungswert für Team 1 (Anzahl der erzielten Punkte mal Wahrscheinlichkeit dafür): (2 * 0.48892) + (1 * 0.48892) = 1.206.

Der Eintrag für "M gegen S" entspricht dann natürlich (2 - 1.206) = 0.794, da ja (nur genau) zwei Punkte in jedem Spiel zu vergeben sind.

Wie man leicht sieht, dominiert keine reine Strategie eine andere, d. h. ist unter allen Eventualitäten besser (das weiß jedoch schon jeder United-Anfänger). Was wir nun suchen, ist eine gemischte Strategie (p1, p2, p3, p4), das heißt die Wahrscheinlichkeiten, mit denen man die reinen Strategien 1-4 auswählt. Dabei sind alle pk ≥ 0 und ∑(pk) = 1.

Beispiel:
Die gemischte Strategie (0, 0.5, 0, 0.5) bedeutet dabei, daß ich mich zu je 50% für die Strategien M und V entscheide.

Die Auszahlung dieser Strategie ist dabei natürlich 0.5 * a(M) + 0.5 * a(V).

Gesucht wird nun die optimale gemischte Strategie, die mir eine gewisse Mindestauszahlung, den sogenannten Spielwert w sichert! "Sichern" heißt dabei "egal, was für eine Strategie mein Gegner wählt".

Die untere Schranke der Auszahlung für jede Strategie ist sicherlich das Minimum der folgenden vier Werte:

a(p|S) = 1.000 * p1 + 0.794 * p2 + 1.000 * p3 + 1.394 * p4 (bedingte Auszahlung, falls er S spielt)
a(p|M) = 1.206 * p1 + 1.000 * p2 + 0.856 * p3 + 0.709 * p4 (bedingte Auszahlung, falls er M spielt)
a(p|R) = 1.000 * p1 + 1.144 * p2 + 1.000 * p3 + 0.815 * p4 (bedingte Auszahlung, falls er R spielt)
a(p|V) = 0.606 * p1 + 1.291 * p2 + 1.185 * p3 + 1.000 * p4 (bedingte Auszahlung, falls er V spielt)

Die optimale Strategie ist nun sicherlich das p*, für das gilt:

min { a(p*|S); a(p*|M); a(p*|R); a(p*|V) } = maxp { min { a(p|S); a(p|M); a(p|R); a(p|V) } }

p* nennt man deswegen auch eine Minimax-Strategie.

Mannomann, wer bis hier durchgehalten hat, kann von mir einen Schein über Grundlagen der Spieltheorie anfordern. Ein Trost: Ab jetzt wird es konkreter!

Erste Ergebnisse

Nun, wie versprochen, die Begründung dafür, warum die Rasenschach-Strategie minderwertig ist.

Die gemischte Strategie q = (0, 0.65, 0, 0.35) dominiert die Rasenschach-Strategie, denn:

a(q|S)=(0.650 * 0.794) + (0.35 * 1.394)=1.004 >1.000=a(R|S)
a(q|M)=(0.650 * 1.000) + (0.35 * 0.709)=0.898 >0.856=a(R|M)
a(q|R)=(0.650 * 1.144) + (0.35 * 0.815)=1.029 >1.000=a(R|R)
a(q|V)=(0.650 * 1.291) + (0.35 * 1.000)=1.189 >1.185=a(R|V)

Ein Mischen zwischen M und V (mit den obigen Wahrscheinlichkeiten) ist also in jedem Falle besser als die reine Strategie R.

Das bedeutet, daß wir die dritte Zeile und die dritte Spalte aus der Matrix A streichen können und erhalten die neue Matrix

B =
    S M V  
S ( 1.000 1.206 0.606 )
M 0.794 1.000 1.291
V 1.394 0.709 1.000

Gesucht ist nun die Minimax-Strategie p**, die man aus folgendem Maximierungsproblem erhält:

maxp { min { (p1 + 0.794 * p2 + 1.394 * p3); (1.206 * p1 + p2 + 0.709 * p3); (0.606 * p1 + 1.291 * p2 + p3) } }

Diese erhält man nun allgemein durch Methoden des Operations Research (speziell Lineare Optimierung) oder man läßt einfach seinen Rechenknecht alle Möglichkeiten durchprobieren (eine Differenzierung in Tausendstel macht ihm dabei keine Mühe und sollte schon eine sehr gute Näherung liefern, da die zu maximierende Funktion in allen Komponenten linear ist und einem deswegen das wahre Maximum kaum durch die Lappen geht).

Die versprochene exakte Lösung

Da wir es aber hier mit United zu tun haben, verfügen wir über eine zusätzliche Information, die der normale Spieltheoretiker nicht hat. Wir kennen nämlich schon den Spielwert w = 1 (mehr als ein Punkt ist bei optimaler Strategiewahl beider Spieler nicht zu erreichen).

Das bedeutet:

a(p**|S) = a(p**|M) = a(p**|V) = 1

Dies ist äquivalent zur Lösung des folgenden Gleichungssystems:

( 1.000 1.206 0.606 )   ( p1 )   ( 1.000 )
0.794 1.000 1.291 * p2 = 1.000
1.394 0.709 1.000   p3   1.000

Der Gauß-Algorithmus (der aus der Schule bekannt sein sollte und auf den ich hier nicht näher eingehen möchte) liefert:

p1 = 0.3266 p2 = 0.4422 p3 = 0.2312

Wer also bei 130-WP-Teams zu 32.66% stürmt, zu 44.22% Mittelfeld spielt und zu 23.12% mauert, sichert sich (zumindest stochastisch gesehen) mindestens den Spielwert w = 1.

Anwendung

Probiert es einmal aus! Setzt euch mit einem anderen United-Manager an einen Tisch und spielt mit den Strategien 10-10-20-20-50, 10-10-20-50-20, 10-10-40-30-20 einige Spiele gegeneinander, wobei ihr so tut, als ob ihr jedesmal über eure Strategie grübelt (in Wirklichkeit würfelt ihr 'unter dem Tisch' nach obigem Schema), und euer Gegner ebenfalls versuchen soll, 'eine Ecke weiter zu denken'. (Er wird z. B. mauern, wenn ihr öfter hintereinander gestürmt habt.)

Der 'Würfler' wird auf die Dauer garantiert besser abschneiden, egal wie viel Kopfzerbrechen sich der 'Denker' auch machen wird. Sobald der allerdings merkt, daß ihr nach obigem Schema würfelt, wird er auch seine Aufstellung auswürfeln, und dann sind die Chancen wieder gleich!

Anmerkungen zur Spieltheorie

(Michael Schröpl)

Ich habe die interessante Analyse von Stephan Valkyser mit einiger Spannung gelesen. Dann habe ich ein wenig nachgerechnet - und bin erstaunt.

Zunächst einmal: Die Zahlenwerte stimmen natürlich. Mit der angegebenenen Minimax-Strategie erreicht man tatsächlich gegen ein gleichwahrscheinliches Gemisch aus S, V und M jeweils einen Erwartungswert von 1.0 Punkten.

Dann habe ich die angegebenen Zahlen mit der Auszahlungsmatrix-Spalte für Rasenschach multipliziert und einen Wert von 1.0209 erhalten. Tatsächlich ist die gewählte Strategie im direkten Vergleich der Rasenschach-Strategie überlegen. Rasenschach lebt von der 7:5-Feldüberlegenheit gegen den Gegner und ist bei kleinen WP-Zahlen wirkungsvoller.

Gegen die sonstigen Ausführungen von Stephan habe ich allerdings diverse Einwände, die ich im folgenden darlegen will.

Das Ausmultiplizieren der Werte für die übrigen Matrix-Spalten ergibt nämlich, wie nicht anders zu erwarten, jeweils 1.0. Und dabei bleibt es auch. Von "mindestens", wie Stephan am Ende seines Artikels ausführt, und von "auf die Dauer häufiger gewinnen" kann keine Rede sein. Es wird ein Erwartungswert von 1.0 Punkten gegen jeden der drei möglichen Gegner garantiert. Das klingt ganz nett - mir ist das aber zu wenig.

Wenn beide Manager aus allen Strategien einige wenige auswählen und innerhalb dieser Strategien gleichwahrscheinlich würfeln, dann erreichen sie im Schnitt ebenfalls beide 1.0 Punkte. Ohne jegliches Nachdenken!

Daraus schließe ich: Es sollten doch irgendwie mehr als 1.0 Punkte zu erreichen sein! Die grundsätzliche Annahme von Stephan, daß bei beiderseitiger optimaler Strategie nur 1.0 Punkte zu erreichen seien, ist zwar richtig, aber wir nehmen ja gerade vom Gegner keine optimale Strategie an, sondern irgendwas aus S, M und V (eventuell auch noch R).
Was also möglich erscheint, ist, die Umwelt zwar nicht genau, aber doch wenigstens im Modell zu erraten. Wenn ich nicht weiß, was der Gegner macht, ihm aber nur die reinen Strategien zutraue, dann behaupte ich zunächst einmal, daß alle diese Strategien gleichwahrscheinlich sind. (In der United-Realität werde ich mir natürlich wenigstens das Torverhältnis des Gegners ansehen und einige Strategien für wahrscheinlicher als andere halten.) De facto setze ich also eine Strategie für den Gegner an und versuche, dieser eine möglichst wirkungsvolle Gegenstrategie entgegenzusetzen.

Wenn man den Gegner exakt zu erraten versucht, dann lautet für einen Maurer die zu schlagende Gegner-Strategie (1, 0, 0, 0). Das ganze geht aber auch mit einer gemischten Strategie des Gegners. Der Gegner, der bei dem angesprochenen Würfel-Experiment angesprochen wird, darf auf meine Aufstellung reagieren, wenn er sie gesehen hat. In United sieht man aber nur das Ergebnis und kann nur selten exakt sehen, was ich aufgestellt habe. Also nehme ich an, daß der Gegner gleichwahrscheinlich würfeln wird, z. B. also eine Strategie der Art (0.25, 0.25, 0.25, 0.25) wählen könnte. Gegen diese kann ich mühelos eine Strategie angeben, die einen Erwartungswert größer als 1.0 besitzt. Man braucht sich nur die Auszahlungsmatrix anzusehen, um zu erkennen, daß man gegen einen solchen Gegner mit einer reinen M-Strategie 4.229/4 = 1.0573 Punkte, mit der so gescholtenen R-Strategie immerhin 4.041/4 = 1.0100 Punkte, mit der V-Strategie auch noch 3.918/4 = 0.9790 Punkte und nur mit der S-Strategie schlappe 3.812/4 = 0.9503 Punkte erhält. Dabei ist in dieser Umwelt die reine M-Strategie eindeutig am besten, da jeder Wechsel auf eine andere Strategie sofort einen Teil der Erwartungspunkte-Überlegenheit kostet.
Der Trick dabei ist lediglich, daß der Gegner nicht sieht, was man macht, und demzufolge nicht selbst eine Strategie gegen die reine M-Aufstellung entwirft, sondern brav gleichwahrscheinlich weiterwürfelt.

Stephans Strategie ist eine Schadensbegrenzung gegen mehrere als möglich angesehene gegnerische Aufstellungen, nicht eine Strategie zur Optimierung des eigenen Erfolges. Es ist nicht möglich, eine gemischte Strategie aus den 4 angegebenen reinen Strategien anzugeben, die gegen die berechnete Strategie mehr als 1.0 Erwartungspunkte erzielen wird. Mehr noch: Solange ich nicht gerade selbst Rasenschach spiele, kann ich gegen Stephans Strategie würfeln, wie ich will - es werden immer genau 1.0 Erwartungspunkte herauskommen.

Gerade die aktive Optimierung ist in United aber notwendig, wenn man erfolgreich sein will. Mit der berechneten Strategie kann man in einer geeigneten Umwelt einen Schnitt von 22 Punkten pro Saison auch gegen unberechenbare Gegner erhoffen - gegen Rasenschachspieler sogar etwas mehr.
Was man nicht kann, ist es, mit einer solchen Strategie Meister zu werden. Das kann man übrigens auch mit keiner anderen Strategie, dazu ist der langfristige Aspekt von United zu entscheidend - und es wäre auch schlimm, wenn es anders wäre. Wenn man allerdings in einzelnen Spielen gut sein will, muß man ein konkretes Modell des Gegners ansetzen und dann die prinzipiell gleiche Optimierungsaufgabe berechnen.

Stephan hat gleich eine ganze Klasse gegnerischer Aufstellungen angenommen und gegen diese im Schnitt nur eine Remis erreicht. Allerdings gegen jede einzelne von ihnen ebenfalls ein Remis - das ist beachtlich. Wenn man nun mehr WP besitzt (z. B. daheim), dann kann man mit einer entsprechenden Berechnung garantieren, daß man "besser ist" als der Gegner. Wenn auch nur nur ein kleines bißchen.

Dazu gehört übrigens auch, alle Strategien (nicht nur die reinen Strategien) in diese Berechnung mit aufzunehmen. Denn mit den genannten Strategien ist der berechneten Strategie tatsächlich nicht beizukommen! Das ist übrigens das Geheimnis der hinten offenen Anti-Rasenschach-Strategie 2-5-4, die in Turnierfußball zuletzt große Erfolge feierte: Gegen eine Mischung aus Rasenschach, Mittelfeld, Mauern und Sturm (allesamt mit Hintermannschaft) kommt ein ziemlich guter Schnitt heraus, sofern nicht auffallend viele Stürmer dabei sind. Um das Torverhältnis darf man sich dabei natürlich nicht kümmern.