Direkt zum Inhalt

Lexikon der Mathematik: Spiel

im allgemeinen Sinn ein mathematisches Konzept zur Beschreibung von Entscheidungsvorgängen zwischen mehreren Parteien, bei denen jede Partei jeder Entscheidung eine gewisse Bewertung zuordnet.

Genauer ist ein Spiel (am Beispiel zweier Kontrahenten) wie folgt charakterisiert. Gegeben sind zwei Mengen S und T, die zwei Spielern \({\mathcal{S}}\) und \({\mathcal{T}}\) zugeordnet sind. Unter gewissen Kriterien sollen Paare (x, y) ∈ S × T ausgewählt werden. Die Mechanismen, nach denen diese Elemente von den Spielern bestimmt werden, nennt man Strategien. Ein derartiger Mechanismus ist durch Entscheidungsregeln für die Spieler gegeben. Für \({\mathcal{S}}\) ist eine solche Regel eine mengenwertige Abbildung CS von T nach S, die jeder Strategie yT mögliche Strategien xCS(y) für \({\mathcal{S}}\) zuordnet, wenn \({\mathcal{T}}\) weiß, daß \({\mathcal{T}}\) die Strategie y verwendet. I.allg. modelliert man Spiele unter Verwendung von Kostenfunktionen, mit denen jeder beteiligte Spieler die Paare (x, y) ∈ S × T bewertet. Ziel des Spiels ist dann für jede Partei die Optimierung ihres Gewinns. Dies liefert die sogenannte Normalform eines Spiels. Spiele in diesem allgemeinen Sinne werden im Rahmen der Spieltheorie mathematisch studiert.

Häufig wird der Begriff „Spiel“ auch als Synonym für Conway-Spiel verwendet. Dies ist ein mathematisches Spiel, wie es von John Horton Conway in [1] und zusammen mit Elwyn Ralph Berlekamp und Richard Kenneth Guy in [2] untersucht wird: Es gibt zwei Spieler, meist als linker Spieler oder einfach Links und rechter Spieler oder einfach Rechts bezeichnet. Das Spiel hat Positionen und wird so gespielt, daß die beiden Spieler abwechselnd Züge machen, die das Spiel aus der aktuellen Position in eine andere Position bringen. Zu jeder Position gibt es zulässige Züge für Links und zulässige Züge für Rechts. Die aus den zulässigen Zügen für Links bzw. Rechts folgenden Positionen nennt man linke Optionen bzw. rechte Optionen der Position. Wird beim Spielen des Spiels eine Position erreicht, in der es für den Spieler, der am Zug ist, keine Option gibt, so hat er verloren und der andere gewonnen, und das Spiel ist beendet. In einem Spiel darf es keine unendliche Folge von Positionen derart geben, daß jede Position eine Option ihrer Vorgängerin ist. Insbesondere endet jedes Spiel nach endlich vielen Zügen. (Die beiden Spieler wollen nicht ewig spielen, denn laut Conway sind sie beschäftigte Leute mit schwerwiegenden politischen Verpflichtungen.)

Jedes Spiel hat eine Anfangsposition, in der es begonnen wird, d. h. ein vereinbarter Spieler den ersten Zug macht. Dieser Spieler wird als erster Spieler und der andere als zweiter Spieler bezeichnet. Da jede Option eines Spiels sich als ein eigenes (verkürztes) Spiel sehen läßt, werden die Spiele mit ihren Anfangspositionen identifiziert.

Ist G ein Spiel, das die linken Optionen a, b, c, …und die rechten Optionen u, v, w, …hat, so schreibt man G = {a, b, c,… |u, v, w, …}. Aufgrund ihrer Struktur kann man Spiele auch als Bäume darstellen. Dabei ist jede Position ein Knoten, wobei die Anfangsposition als Wurzelknoten ganz unten und die Züge von Links bzw. Rechts als Äste nach links oben bzw. nach rechts oben gezeichnet werden.

Das einfachste Spiel ist das Spiel 0 := {|}, auch Endspiel genannt, in dem keiner der beiden Spieler einen Zug hat. Der erste Spieler verliert also, und der zweite Spieler gewinnt. Im Spiel 1 := {0 |} hat Links einen Zug, Rechts hat keinen. Links gewinnt daher, egal wer den ersten Zug hat. Entsprechend gewinnt im Spiel −1 := {| 0} immer Rechts. Im Spiel * := {0 | 0} schließlich gewinnt immer der erste Spieler.

Abbildung 1 zum Lexikonartikel Spiel
© Springer-Verlag GmbH Deutschland 2017
 Bild vergrößern

Als einfache weitere Spiele, in denen immer Links gewinnt, erhält man 2 := {1 |}, 3 := {2 |} usw., und als Spiele, in denen immer Rechts gewinnt, −2 := {| − 1} und −3 := {| − 2} usw., während etwa im Spiel {* | *} immer der zweite Spieler gewinnt.

Abbildung 2 zum Lexikonartikel Spiel
© Springer-Verlag GmbH Deutschland 2017
 Bild vergrößern

Zwar muß jedes Spiel nach endlichen vielen Zügen beendet sein, aber es sind durchaus Spiele mit unendlich vielen Positionen möglich. Beispielsweise ist ω := {0, 1, 2, 3, …|} ein Spiel, in dem immer Links gewinnt.

Abbildung 3 zum Lexikonartikel Spiel
© Springer-Verlag GmbH Deutschland 2017
 Bild vergrößern

Im allgemeinen hat ein Spieler in einer Position mehrere Optionen, und es hängt von seiner Auswahl der Züge im Spielverlauf ab, ob ein Spieler gewinnt oder verliert. Hat ein Spieler die Möglichkeit, durch geschickte Wahl seiner Züge den Gewinn zu erzwingen, so sagt man, es gebe für ihn eine Gewinnstrategie. Man schreibt für ein Spiel G

G > 0 und nennt G positiv, wenn es eine Gewinnstrategie für Links gibt,

G < 0 und nennt G negativ, wenn es eine Gewinnstrategie für Rechts gibt,

G = 0 und nennt G Null, wenn es eine Gewinnstrategie für den zweiten Spieler gibt,

G || 0 und nennt G unklar, unscharf oder verwirrt, wenn es eine Gewinnstrategie für den ersten Spieler gibt.

Jedes Spiel liegt in genau einer der hierdurch definierten Ergebnisklassen. Weiter definiert man: \begin{eqnarray}\begin{array}{rl}G\ge 0 & :\iff G\gt 0\vee G=0\\ G\le 0 & :\iff G\lt 0\vee G=0\\ G\parallel \gt 0 & :\iff G\gt 0\vee G\parallel 0\\ G\lt \parallel 0 & :\iff G\lt 0\vee G\parallel 0\end{array}\end{eqnarray}G ≥ 0 bedeutet z. B. gerade, daß es im Fall, daß Rechts beginnt, eine Gewinnstrategie für Links gibt, und G ||> 0 bedeutet, daß es im Fall, daß Links beginnt, eine Gewinnstrategie für Links gibt.

Eine entscheidende Entdeckung Conways war, daß man mit Spielen rechnen kann. Er stellte nämlich fest, daß etwa das Spiel Go gegen Spielende häufig in voneinander getrennte Teile zerfällt, die sich als unabhängige Spiele betrachten lassen. Die (disjunktive) Summe G1 + … + Gn von gegebenen Spielen G1, …, Gn ist definiert als das simultane Spielen von G1, …, Gn, wobei der Spieler, der am Zug ist, einen Zug in einem Spiel seiner Wahl machen kann. Das Negative −G eines Spiels G ist definiert als das gleiche Spiel mit vertauschten Rollen von Links und Rechts, was einer Spiegelung der Baumdarstellung an einer vertikalen Achse entspricht. Für Spiele G und H definiert man \begin{eqnarray}G-H:=G+(-H)\end{eqnarray} und damit \begin{eqnarray}G \circ H:\iff (G-H) \circ 0\end{eqnarray} für ○ ∈ {>, < , =, ||, ≥, ≤, ||>, < ||}. Insbesondere ist auch die Gleichheit = eine definierte Äquivalenzrelation. Modulo dieser Gleichheit bildet die Klasse der Spiele mit der Addition +, der Null 0, der Negation – und den Relationen >, < , ≥, ≤ eine partiell geordnete Gruppe. Die Aussage G || H bedeutet gerade die Nichtvergleichbarkeit von G und H.

Manche Aussagen über Spiele sind anschaulich sofort einsichtig. Die Aussage GG = 0 für jedes Spiel G etwa bedeutet, daß beim simultanen Spielen von G und −G der zweite Spieler gewinnen kann. Immer wenn der erste Spieler einen Zug in G oder −G gemacht hat, braucht der zweite Spieler einfach nur den entgegengesetzten Zug im jeweils anderen Spiel zu machen (Tweedledum-Tweedledee-Stτategie, benannt nach den Zwillingen aus Alice im Wunderland).

Für einen etwas formaleren Zugang zu Spielen sind folgende Notationen recht nützlich: Der Ausdruck {L | R} ist eine Schreibweise für ein Paar (L, R) von Mengen L und R. Man nennt L linke Menge, R rechte Menge, Elemente von L linke Optionen und Elemente von R rechte Optionen von {L | R}. Sind a, b, c,… und u, v, w, … Elemente, so schreibt man unter Weglassung der Mengenklammern auch {a, b, c, … | u, v, w, …} anstelle von {{a, b, c, …}|{u, v, w, …}}.

Für ein solches x = {L | R} bezeichnet xL ein typisches (d. h. irgendein) Element von L und xR ein typisches Element von R, und man schreibt damit auch x = {xL | xR}. Schreibt man eine Aussage für xL bzw. xR, so soll dies bedeuten, daß sie für alle linken bzw. rechten Optionen von x gilt, und entsprechend auch für Aussagen in mehreren Variablen.

Damit lassen sich Spiele einfach durch folgende Regel definieren:

  • Sind L und R Mengen von Spielen, dann ist {L | R}

ein Spiel. Alle Spiele entstehen auf diese Weise. Durch die Vorschrift „Alle Spiele entstehen auf diese Weise“ und das Fundierungsaxiom der Mengenlehre wird gewährleistet, daß jedes Spiel nach endlich vielen Zügen endet, daß Relationen und insbesondere Funktionen von Spielen sich rekursiv definieren und geeignete Aussagen über Spiele sich induktiv beweisen lassen. Ist etwa P(x) eine Aussageform für Spiele, und folgt aus der Gültigkeit von P(xL) und P(xR) die Gültigkeit von P(x), dann gilt P(x) für alle Spiele x.

Die Relation ≥ für Spiele x, y wird durch die rekursive Definition \begin{eqnarray}x\ge y:\iff y\ngeqq {x}^{R}\wedge {y}^{L}\ngeqq x\end{eqnarray} erklärt, und damit die übrigen Relationen wie folgt: \begin{eqnarray}\begin{array}{rl}x\le y & :\iff y\ge x\\ x=y & :\iff x\ge y\wedge y\ge x\\ x\parallel y & :\iff x\ngeq y\wedge y\ngeq x\\ x\gt y & :\iff x\ge y\wedge y\ngeq x\\ x\lt y & :\iff y\gt x\\ x\parallel \gt y & :\iff x\nleq y\\ x\lt \parallel y & :\iff x\ngeq y\end{array}\end{eqnarray} Die Gleichheit = von Spielen ist also eine definierte Äquivalenzrelation. Die Relation ≥ ist eine partielle Ordnung auf den Spielen.

Gilt x = y für zwei Spiele x und y, so sagt man, x und y hätten den gleichen Wert, oder auch, x habe den Wert y. Stärker als die Gleichheit ist die Identität: Man bezeichnet zwei Spiele x und y genau dann als identisch, schreibt x = y und sagt, sie hätten die gleiche Form, wenn x und y identische linke und rechte Optionen haben.

Die Addition von Spielen x, y ist ebenfalls rekursiv durch \begin{eqnarray}x+y:=\{{x}^{L}+y,x+{y}^{L}|{x}^{R}+y,x+{y}^{R}\}\end{eqnarray} definiert. Man vergleiche dies mit der obigen mehr umgangssprachlichen Definition. Daß das Summenspiel x + y die linken Optionen xL + y und x + yL hat, spiegelt z. B. gerade die Tatsache wider, daß Links bei einem Zug in x + y entweder im Teilspiel x oder im Teilspiel y ziehen kann.

Die Addition ist verträglich mit der Gleichheitsrelation: Für alle Spiele x1, x2, y1, y2 mit x1 = x2 und y1 = y2 hat man x1 + y1 = x2 + y2. Mit der Null 0 := {|} ist die Addition eine kommutative Halbgruppenoperation auf den Spielen, und zwar sowohl bzgl. der Gleichheit als auch bzgl. der Identität. Wenn man noch das Negative eines Spiels x durch \begin{eqnarray}-x:=\{-{x}^{R}|-{x}^{L}\}\end{eqnarray} definiert, werden die Spiele zu einer kommutativen Gruppe bzgl. der Gleichheit gemacht, jedoch nicht bzgl. der Identität: Mit 1 :={0 |} gilt beispielsweise 1 + (−1) = 0, aber 1 + (−1) ≢ 0.

Mittels der Addition und der Negation definiert man wie gewohnt durch \begin{eqnarray}x-y:=x+(-y)\end{eqnarray} die Subtraktion von Spielen x, y. Schließlich wird durch \begin{eqnarray}xy:=\{{x}^{L}y+x{y}^{L}-{x}^{L}{y}^{L},{x}^{R}y+x{y}^{R}-{x}^{R}{y}^{R}|{x}^{L}y+x{y}^{R}-{x}^{L}{y}^{R},{x}^{R}y+x{y}^{L}-{x}^{R}{y}^{L}\}\end{eqnarray} die Multiplikation von Spielen x, y erklärt mit den Eigenschaften \begin{eqnarray}\begin{array}{l}\begin{array}{lll}x0\equiv 0, & x1\equiv x, & xy\equiv yx\end{array}\\ (-x)y\equiv x(-y)\equiv -(xy) \\ (x+y)z=xz+yz,\,\,\,\,\,\,(xy)z=x(yx)\end{array}\end{eqnarray} für alle Spiele x, y, z. Die Multiplikation ist jedoch nicht verträglich mit der Gleichheitsrelation, denn es gibt Spiele x und y = z mit xyxz. Für * := {0 | 0} und 2 := {1 |} etwa hat man 0 = {| 2}, aber *0 = *{| 2}.

In diesem Sinne ‚schönere‘ Eigenschaften haben die surrealen Zahlen, die sich als diejenigen Spiele x einführen lassen, deren Optionen allesamt Zahlen sind mit xLxR. Die Spiele 0 und 1 sind Zahlen, nicht aber etwa das Spiel *. Summe, Negatives und Produkt von Zahlen sind Zahlen, und zu jeder von Null verschiedenen Zahl gibt es eine reziproke Zahl. Die Zahlen sind im Gegensatz zu den Spielen total geordnet, und sie bilden einen nichtarchimedischen Körper.

Von besonderem Interesse sind Spiele, die eine Zahl als Wert haben, weil dieser sich als Quantifizierung des Vorteils bzw. Nachteils von linkem und rechtem Spieler deuten läßt. In einem Spiel mit dem Wert 2 etwa hat der linke Spieler zwei Züge Vorteil, in einem Spiel mit dem Wert \(-\frac{1}{4}\) hat der rechte Spieler einen Viertelzug Vorteil.

Für weiteres sei verwiesen auf Conways ONAG [1] und insbesondere auf das mehrbändigen Werk [2], das 2001 in einer Neubearbeitung erschien und eine Vielzahl konkreter Spiele vorstellt.

[1] Conway, J. H.: On Numbers and Games. AK Peters Natick, Massachusetts, 2001.
[2] Berlekamp, E. R.; Conway, J.H.; Guy, R. K.: Gewinnen, Strategien für mathematische Spiele, Band 1-4. Vieweg Braunschweig, 1986.
[3] Berlekamp, E. R.; Conway, J. H.; Guy, R. K.: Winning Ways for Your Mathematical Plays, Vol. 1. A K Peters Natick, Massachusetts, 2001.

Lesermeinung

Wenn Sie inhaltliche Anmerkungen zu diesem Artikel haben, können Sie die Redaktion per E-Mail informieren. Wir lesen Ihre Zuschrift, bitten jedoch um Verständnis, dass wir nicht jede beantworten können.

  • Die Autoren
- Prof. Dr. Guido Walz

Partnerinhalte