242 lines
9.4 KiB
TeX
242 lines
9.4 KiB
TeX
\section{Ein abstrakter Blickpunkt auf Spiele}
|
|
|
|
Ziel dieses Kapitels soll es sein, einen formalen Standpunkt auf Spiele zu entwickeln
|
|
und unsere Beobachtungen über die bisherigen Spiele, insbesondere Hackenbush,
|
|
auf standfesten Boden zu bekommen.
|
|
|
|
\begin{definition}
|
|
Ein \vocab{Spiel} $G$ besteht aus einer Menge von Positionen
|
|
und einer ausgezeichneten Startposition.
|
|
Jeder Position $P$ des Spiels sind seine \vocab{linken Züge} und seine
|
|
\vocab{rechten Züge} zugeordnet, die ebenfalls Positionen von $G$ sind.
|
|
$2$ Spielerinnen sind abwechselnd an der Reihe und führen einen für sie legalen Zug aus
|
|
und überführen damit das Spiel in eine neue Position.
|
|
Mit der \vocab{Normalspielkonvention} sagen wir,
|
|
dass eine Spielerin verloren hat, wenn sie keinen legalen Zug mehr hat.
|
|
\end{definition}
|
|
|
|
\begin{remark}
|
|
Natürlich können wir aus jeder Position $P$ eines Spiels $G$ einfach ein (sehr ähnliches)
|
|
Spiel $G'$ machen, indem $G'$ in $P$ startet und nur noch die Positionen von $G$ enthält,
|
|
die man von $P'$ aus \enquote{erreichen} kann.
|
|
|
|
Deswegen werden wir meistens auch Spiele und Positionen einfach gleich behandeln.
|
|
Es sollte jedoch darauf Wert gelegt werden, dass die bloße Angabe von \gm{Prim} noch \emph{nicht}
|
|
ein Spiel darstellt, weil wir keine Startposition haben.
|
|
Eigentlich handelt es sich hier um eine Menge von Spielen, die über die jeweilige Startposition
|
|
charakterisiert werden.
|
|
|
|
Umgangssprachlich werden wir aber natürlich auch weiterhin sagen, dass \gm{Prim} ein Spiel ist.
|
|
\end{remark}
|
|
|
|
\begin{notation}
|
|
Für eine Position $P$ schreiben wir $P = \set{ L_1, L_2, \dotsc \suchthat R_2, R_2, \dotsc } $,
|
|
wenn die $L_i$ die Menge der linken Züge von $P$ und die $R_i$ die Menge der rechten
|
|
Positionen von $P$ aufzählen.
|
|
Oft schreiben wir auch $P = \set{ P^L \suchthat P^R } $ und meinen dann mit $P^L$ und $P^R$
|
|
wahlweise alle entsprechenden Züge oder einen \enquote{generischen} Zug für die entsprechende
|
|
Spielerin.
|
|
\end{notation}
|
|
|
|
\begin{remark}[Mengentheorie]
|
|
Wir wollen hier nicht zu genau mit den Begriffen Menge und Klasse umgehen,
|
|
weil diese meist nicht relevant für uns sind.
|
|
Eigentlich könnte man erlauben, dass ein Spiel aus einer \emph{Klasse} von Positionen
|
|
besteht, jede Position aber tatsächlich \emph{Mengen} an linken und rechten Positionen
|
|
hat.
|
|
|
|
Für die Notation $P = \set{ L_1, L_2, \dots \suchthat R_1, \dotsc } $ muss man natürlich
|
|
i.A.~dann auch eine beliebige Indexmenge für die Aufzählen zulassen, weil die Menge
|
|
der linken Züge natürlich keineswegs abzählbar sein muss.
|
|
Auch das ist aber für uns erstmal irrelevant.
|
|
\end{remark}
|
|
|
|
\begin{example}
|
|
Wir haben bereits \gm{Hackenbush}-Positionen gesehen, die wir mit natürlichen Zahlen
|
|
benannt haben.
|
|
Wir stellen fest, dass
|
|
\begin{gather*}
|
|
0 = \set{ \suchthat }, \quad
|
|
1 = \set{ 0 \suchthat }, \quad
|
|
2 = \set{ 0, 1 \suchthat }, \quad
|
|
n = \set{ 0, 1, \dotsc, n-1 \suchthat }
|
|
\\
|
|
\frac{1}{2} = \set{ 0 \suchthat 1 }, \quad
|
|
\frac{1}{2^n} = \set{ 0 \suchthat \frac{1}{2^{n-1}} }
|
|
\end{gather*}
|
|
etc.
|
|
\end{example}
|
|
|
|
\begin{remark}
|
|
In den bisherigen Positionen beobachtet man noch Folgendes:
|
|
\begin{itemize}
|
|
\item Alle Positionen für die linke Spielerin sind stets strikt kleiner als die der rechten
|
|
\item Der Name einer neuen Position ist immer zwischen den Werten der Positionen links und rechts
|
|
\end{itemize}
|
|
Wie wir bald sehen werden, muss dem im Allgemeinen überhaupt nicht so sein.
|
|
Spiele, die sich so verhalten, sind allerdings besonders, wir werden später nochmal auf sie
|
|
zurückkommen.
|
|
\end{remark}
|
|
|
|
\begin{example}
|
|
Betrachten wir \gm{Dim} und bezeichnen die Spielzustände mit Zahlen $\Dim{n}$.
|
|
Dann ist z.B.
|
|
$\Dim{0} = \set{ \suchthat } $,
|
|
$\Dim 1 = \set{\suchthat } $,
|
|
$\Dim 2 = \set{ \Dim 1 \suchthat \Dim 1 } $,
|
|
$\Dim 3 = \set{ \Dim 2 \suchthat \Dim 2 } $,
|
|
$\Dim 4 = \set{ \Dim 2, \Dim 3 \suchthat \Dim 2, \Dim 3 } $,
|
|
$\Dim 5 = \set{ \Dim 4 \suchthat \Dim 4 } $,
|
|
\end{example}
|
|
|
|
Weil die Notation offensichtlich Redundanz enthält, stellen wir Folgendes fest:
|
|
|
|
\begin{definition}
|
|
Ein Spiel $G$ heißt \vocab{neutral},
|
|
wenn in jeder Position beide Spieler (sofern sie am Zug sind)
|
|
die gleichen legalen Züge haben.
|
|
Mit anderen Worten: Für jede Position $P = \set{ L \suchthat R } $ von $G$ ist $L = R$.
|
|
\end{definition}
|
|
|
|
\begin{question}
|
|
Welche der bisher angetroffenen Spiele sind neutral?
|
|
\end{question}
|
|
|
|
\begin{notation}
|
|
Ist $G$ ein neutrales Spiel, so schreiben wir für Positionen $P$ von $G$ im Folgenden nur noch
|
|
$P = \set{ Z_1, Z_2, \dotsc } $ und unterscheiden nicht zwischen $P^L$ und $P^R$.
|
|
\end{notation}
|
|
|
|
Wir wollen nun erste Schritte unternehmen, um Spiele ganz \emph{formal} zu klassifizieren:
|
|
|
|
|
|
\begin{notation}
|
|
Schreibe $G \geq 0$ für $G = 0$ oder $G > 0$, analog $G \leq 0$.
|
|
Ebenfalls führen wir $G \lfuzzy 0$ für $G < 0$ oder $G \fuzzy 0$ ein,
|
|
analog $G \gfuzzy 0$.
|
|
\end{notation}
|
|
|
|
Relevant ist nun Folgendes:
|
|
|
|
\begin{theorem}
|
|
\label{thm:vergleichbarkeit-von-spielen}
|
|
Für jedes Spiel $G$ gilt genau eines von $G>0$, $G<0$, $G = 0$ und $G \fuzzy 0$.
|
|
\end{theorem}
|
|
|
|
\begin{proof}
|
|
Klarerweise können nicht zwei der vier Fälle gleichzeitig eintreten.
|
|
Wir gehen induktiv vor, sei $G$ also ein Spiel,
|
|
sodass wir die Aussage für alle linken und rechten Position von $G$ bereits kennen.
|
|
Sei also $G$ beliebig und nimm zunächst an,
|
|
die linke Spielerin ist am Zug.
|
|
Gibt es ein $G^L$ mit $G^L \geq 0$, so kann $L$ gewinnen, indem es diese Position wählt.
|
|
Ist $G^L \lfuzzy 0$ für jedes $G^L$, so gewinnt $R$, indem er danach die Gewinnstrategie
|
|
in der von links gewählten Position verfolgt.
|
|
Analoges gilt für eine Fallunterscheidung nach $G^R \leq 0$,
|
|
wenn die rechte Spielerin beginnt.
|
|
Damit ergibt sich zusammen folgende Tabelle:
|
|
|
|
\begin{center}
|
|
\begin{tabular}{c | c | c}
|
|
& $\exists G^L \geq 0$ & $\forall G^L \lfuzzy 0$
|
|
\\
|
|
\hline
|
|
$\exists G^R \leq 0$ & $G \fuzzy 0$ & $G < 0$
|
|
\\
|
|
\hline
|
|
$\forall G^R \gfuzzy 0$ & $G > 0$ & $ G = 0$
|
|
\end{tabular}
|
|
\end{center}
|
|
|
|
Das zeigt insbesondere, dass $G$ in einem der vier Fälle liegt.
|
|
\end{proof}
|
|
|
|
\begin{talk}
|
|
Hier etwas darüber sagen, dass wir hier mengentheoretisch etwas gehackt haben,
|
|
dass das eigentlich formal transfinite Induktion ist, was wir hier brauchen,
|
|
und dass man etwas vorsichtig sein muss, was das definieren von Spielen angeht,
|
|
weil wir eigentlich darüber reden müssen, dass wir alle Spiele über ihre Geburtstage
|
|
\enquote{generieren}, oder zumindest, wie wir gedenken, die Rekursion aus der Definition
|
|
ein bisschen wegzubekommen.
|
|
|
|
Spezifisch sollte über die folgenden Spiele geredet werden:
|
|
\[
|
|
\on \coloneqq \set{ \on \suchthat },
|
|
\qquad
|
|
\off \coloneqq \set{ \suchthat \off },
|
|
\qquad
|
|
\dud \coloneqq \on + \off = \set{ \dud \suchthat \dud }
|
|
\]
|
|
Hierbei steht \enquote{$\dud$} für \enquote{deathless universal draw}.
|
|
\end{talk}
|
|
|
|
|
|
\section{Addition und Negative von Spielen}
|
|
|
|
Wir wollen uns jetzt in etwas allgemeinerem Kontext nochmal ansehen,
|
|
wie wir Spiele addieren und negieren konnten,
|
|
so wie wir das bei Hackenbush getan haben.
|
|
|
|
\begin{definition}[Addition von Spielen]
|
|
Seien $G$ und $H$ zwei Spiele.
|
|
Die (disjunkte) \vocab{Summe} von $G$ und $H$ entsteht als neues Spiel wie folgt:
|
|
Eine Position von $G + H$ ist ein Paar von Positionen aus $G$ und $H$.
|
|
Ein Zug besteht nun daraus, eine der beiden Positionen zu wählen und in ihr
|
|
einen (für die entsprechende Spielerin) legalen Zug zu machen.
|
|
In jedem Zug ändert sich also nur eine der beiden Positionen des Paars.
|
|
Verloren hat (wie immer), wer keinen Zug mehr machen kann,
|
|
wer also in \emph{beiden} Positionen des Paares keinen Zug mehr machen kann.
|
|
\end{definition}
|
|
|
|
\begin{sanity-check}
|
|
Überzeuge dich, dass das mit unserer bisherigen Definition im Falle von Hackenbush übereinstimmt.
|
|
\end{sanity-check}
|
|
|
|
\begin{remark}
|
|
Es kann jetzt vorkommen,
|
|
dass in $G + H$ in der Position von $G$ zweimal hintereinander die gleiche Spielerin zieht.
|
|
\end{remark}
|
|
|
|
\begin{definition}[Negatives eines Spiels]
|
|
Ist $G$ ein Spiel, so ist das Negative von $G$,
|
|
notiert $-G$ dasjenige Spiel $G$, in dem die legalen Züge der beiden Spielerinnen
|
|
vertauscht werden.
|
|
\end{definition}
|
|
|
|
\begin{sanity-check}
|
|
Überzeuge dich auch hier, dass das mit der bisherigen Position übereinstimmt.
|
|
\end{sanity-check}
|
|
|
|
Wir können nun
|
|
\autoref{prop:hackenbush-kleinergleich-respektiert-gleichheit}
|
|
und
|
|
\autoref{prop:hackenbush-bildet-geordnete-abelsche-gruppe}
|
|
unmittelbar verallgemeinern.
|
|
|
|
\begin{proposition}
|
|
\label{prop:kleinergleich-respektiert-gleichheit}
|
|
Die Relation \enquote{$=$} ist eine Äquivalenzrelation auf der Klasse der Spiele,
|
|
das heißt:
|
|
\begin{enumerate}[p]
|
|
\item $G = G$ für jedes Spiel $G$
|
|
\item Ist $G = H$, so ist auch $H = G$
|
|
\item Ist $G = H$ und $H = I$, so auch $G = I$
|
|
\end{enumerate}
|
|
\end{proposition}
|
|
|
|
\begin{proposition}
|
|
\label{prop:games-bildet-geordnete-abelsche-gruppe}
|
|
Die Klasse der Spiele bildet mittels \enquote{$+$} und \enquote{$\leq $}
|
|
eine (partiell) geordnete, abelsche Gruppe.
|
|
Das heißt:
|
|
\begin{enumerate}[p]
|
|
\item \enquote{$+$} ist kommutativ und assoziativ
|
|
\item Jede Position $P$ hat eine negative Position $-P$ mit $P + (-P) = 0$.
|
|
\item Aus $G \leq H$ und $H \leq G$ folgt $G = H$.
|
|
\item Die Ordnung ist mit $\leq $ verträglich, d.h.
|
|
\[
|
|
G_1 \leq G_2 \qquad \iff \qquad G_1 + H \leq G_2 + H
|
|
\]
|
|
\end{enumerate}
|
|
\end{proposition}
|