Kombinatorische-Spieltheorie/inputs/einige_spiele.tex

\vocab{Kombinatorische Spieltheorie} beschäftigt sich mit einer spezifischen Sorte an Spielen.
Etwas informell meinen wir mit \vocab{Spiel} im Folgenden immer Folgendes:

\begin{itemize}
  \item Es spielen zwei Parteien. Meistens heißen diese rot und blau
  \item Die Parteien sind abwechselnd am Zug und müssen einen der für sie legalen Züge ausführen
  \item Beide Parteien verfügen über absolutes Wissen über den Zustand und die Regeln des Spiels
  \item Das Spiel enthält keinen Zufall
\end{itemize}

Aus was ein \vocab{Zug} besteht, hängt natürlich davon ab, welches Spiel gerade gespielt wird.
Meistens verliert diejenige Partei, die zuerst nicht mehr ziehen kann.
Das nennt man dann \vocab{Normalspiel}, es gibt aber auch andere Varianten, wie wir sehen werden.

\begin{example}
  \gm{Schach}, \gm{Go}, \gm{Dame} und \gm{Mühle} sind kombinatorische Spiele.

  \gm{Uno} oder \gm{Schafkopf} sind keine kombinatorischen Spiele, denn sie enthalten Zufall.

  \gm{Wer bin ich?} ist kein kombinatorisches Spiel.
  Sieht man davon ab, dass es vermutlich schwer wäre,
  genau zu definieren, welche Fragen mit \enquote{ja} und \enquote{nein} beantwortet werden
  müssen, so gibt es in diesem Spiel keine absoluten Informationen für die Spieler:innen.
\end{example}

Eigentlich sollte man auch fordern, dass es kein \enquote{Unentschieden} in den Spielen gibt.
Das kann man aber dadurch umgehen, indem wir z.B.~einfach sagen, dass bei einem klassischen
\enquote{Unentschieden} eine vorher gewählte der beiden Parteien gewinnt.

\section{\gm{Subtraktionsspiel}}

Folgendes Spiel scheint recht verbreitet zu sein und hat eine nicht allzu schwere
Gewinnstrategie:

\begin{game}[\gm{Subtraktion}]
  Gegeben ist eine natürliche Zahl $n$.
  Ein Zug besteht daraus, von $n$ eine Zahl von $1$ bis $10$ abzuziehen.
  Wer nicht mehr ziehen kann, hat verloren.
\end{game}

\begin{talk}
  Hier das ganze mit den Schüler:innen ausprobieren und auf die Strategie kommen lassen.
\end{talk}

\begin{theorem}
  In \gm{Subtraktion} sind genau die durch $11$ teilbaren Zahlen die Verluststellungen.
\end{theorem}

\begin{proof}
  Ist eine Zahl durch $11$ teilbar, so führt jeder Zug zu einer Zahl,
  die nicht durch $11$ teilbar ist, weil $1, \dotsc, 10$ nicht durch $11$ teilbar sind.
  Ist eine Zahl $n$ nicht durch $11$ teilbar, so ist es eine der Zahlen
  $n-1, \dotsc, n-10$, weil unter den $11$ aufeinanderfolgenden Zahlen $n, n-1, \dotsc, n-10$
  ja eine durch $11$ teilbar ist.
  Es gibt also einen legalen Zug, der auf eine durch $11$ teilbare Zahl verkürzt.
\end{proof}

Man kann das ganze aber auch schwerer gestalten:

\begin{game}[Variante von \gm{Subtraktion}]
  Gegeben ist wieder eine natürliche Zahl $n$.
  In einem Zug darf man $2$, $3$ oder $5$ von ihr subtrahieren.
\end{game}

\begin{talk}
  Hier wieder viel ausprobieren lassen.
  Dann backtracking erklären und wie man das mit Tabellen hinbekommen kann.
  Vermutlich will man hier auch einmal die $8$-piece table von Schach als prominentes
  Beispiel nennen.
\end{talk}

\begin{remark}
  Diese Aufgabe wurde mal bei einer Bundesrunde der MO gestellt,
  allerdings weiß ich gerade nicht, welche das war.
  Ich vermute aber, dass das Klasse 9/10 war und eher eine der einfachen Aufgaben.
\end{remark}

\begin{theorem}
  In dieser Variante von \gm{Subtraktion} sind genau die Zahlen $\equiv 0,1 \mod 7$
  die Verluststellungen.
\end{theorem}

\begin{proof}
  Sei $n \not \equiv 0,1 \mod 7$.
  Dann können wir nach folgendem Schema subtrahieren, um in eine Verluststellung zu
  überführen:

  \begin{center}
    \begin{tabular}{c | c | c | c | c | c }
      $n \mod 7$ & 2 & 3 & 4 & 5 & 6 \\
      \hline
      Zug & 2 & 3 & 3 & 5 & 5
    \end{tabular}
  \end{center}

  Außerdem erkennen wir gleichzeitig, dass wir stets weniger abziehen als der Siebenerrest der
  aktuellen Zahl, also gelangen wir auch nicht unter Null und all diese angegeben Züge sind legal.

  Ist umgekehrt $n \equiv 0,1 \mod 7$, so unterscheiden wir zwei Fälle:
  Für $n=0,1$ gibt es keine legalen Züge, das sind also Verluststellungen.
  Für alle größeren $n$ sind alle $3$ potenziellen Züge legal,
  allerdings führen diese wegen $0 - 5 \equiv 2 \mod 7$ und $1 - 2 \equiv 6 \mod 7$
  immer zu einem neuen Siebenerrest zwischen einschließlich $2$ und $6$,
  also genau zu den behaupteten Verluststellungen.
\end{proof}

\begin{proof}
  
\end{proof}


\section{\gm{Dim}}

\begin{game}[\gm{Dim}]
  Ein Spielzustand besteht aus einer natürlichen Zahl $n$.
  Ein Zug besteht daraus, von $n$ einen seiner Teiler zu subtrahieren.
  Wer auf $0$ subtrahiert, verliert.
\end{game}

\begin{remark}
  Das ist nicht die von Conway gegebene Definition von \gm{Dim},
  weil wir hier eigentlich die misère Konvention anwenden.
  Wenn man wie üblich Normalform des Spiels will,
  dürfte man durchaus auf $0$ subtrahieren und die jeweils andere Person
  verliert, weil sie nicht mehr ziehen kann.
  Dann ist aber trivialerweise jede Stellung außer $0$ eine Gewinnstellung
  und das Spiel für uns (erstmal) uninteressant.
  Wir kommen später darauf zurück.
\end{remark}

\begin{theorem}
  In \gm{Dim} sind genau die geraden Zahlen Gewinnstellungen.
\end{theorem}

\begin{proof}
  Ungerade Zahlen haben nur ungerade Teiler.
  Jede ungerade Stellung führt also zu einer geraden.
  Potenziell führt diese zu Null, dann endet das Spiel entsprechend sofort.
  In jeder geraden Stellung subtrahieren wir $1$ und gelangen zu einer ungeraden.
  Insbesondere haben wir damit noch nicht verloren, weil $0$ gerade ist.
\end{proof}

\section{\gm{Prim}}

\begin{game}{\gm{Prim}}
  Eine Stellung besteht wieder aus einer natürlichen Zahl $n$.
  In einem Zug darf man eine zu $n$ teilerfremde Zahl von $n$ subtrahieren.
\end{game}

\begin{theorem}
  In \gm{Prim} sind die Gewinnstellungen genau die ungeraden Zahlen.
\end{theorem}

\begin{proof}
  Wir verfahren analog wie im Fall von \gm{Dim}:
  Ist $n$ ungerade, so können wir von $n$ einfach $1$ subtrahieren und landen
  bei einem geraden Zustand, insbesondere hatten wir noch einen legalen Zug.
  Ist $n$ gerade, so ist jede Zahl, die zu $n$ teilerfremd ist, ungerade
  und jeder Zug führt somit zu einer ungeraden Zahl.
\end{proof}

\section{\gm{Nim}}
\label{sec:nim-einfuehrung}

\gm{Nim} ist vermutlich eines der bekanntesten Spiele der kombinatorischen Spieltheorie.
Auch hier wollen wir zunächst ein bisschen selber spielen und dann eine allgemeine Theorie aufbauen.

\begin{game}[Nim]
  Gespielt wird mit einer Menge an (nicht zwingend gleich großen) Stapeln von Münzen.
  Ein Zug besteht daraus, von einem der Stapel eine beliebige, positive Anzahl an Münzen
  zu entfernen (potenziell alle).
  Verloren hat, wer keinen Zug mehr ausführen kann.
\end{game}

Wir versuchen nun, für eine beliebige Position zu klären, wer den Sieg erzwingen kann.
Hierzu benötigen wir:

\begin{definition}
  Die \vocab{Nim-Summe} von zwei natürlichen Zahlen $a$ und $b$ ist definiert als die
  Summe ohne Übertrag der beiden Zahlen $a$ und $b$ in ihrer Binärdarstellung.
\end{definition}

\begin{example}
  Es ist $3 \nimsum 7 = 11_{(2)} \nimsum 111_{(2)} = 100_{(2)} = 4$.
\end{example}

\begin{fact}
  $(\mathbb{N}, \nimsum)$ ist eine abelsche Gruppe.
  Insbesondere ist $\nimsum$ kommutativ und assoziativ.
\end{fact}

\begin{theorem}
  In Nim sind genau diejenigen Positionen Gewinnpositionen,
  bei denen die Nimsumme der Anzahl der Münzen in den einzelnen Stapeln \emph{nicht}
  Null ist.
\end{theorem}

\begin{proof}
  Umgekehrt behaupten wir natürlich, dass genau diejenigen Positionen Verluststellungen
  sind, bei denen die entsprechende Nimsumme Null \emph{ist}.
  Wie immer zeigen wir, dass jede Verlustposition zwangsweise in eine Gewinnposition übergeht
  und dass es in jeder Gewinnposition einen Zug gibt, der in eine Verluststellung führt.

  Sei zunächst eine Verluststellung gegeben, d.h.~$a_1 \nimsum a_2 \nimsum \dotsb \nimsum a_n = 0$.
  Ein beliebiger Zug ändert nur einen der Summanden, OBdA $a_1$ zu $a_1'$.
  Wäre die Summe danach immer noch $0$, so würde $a_1 = a_1'$ folgen, das ist aber kein legaler Zug.

  Sei nun $a_1 \nimsum \dotsb \nimsum a_n = x \neq 0$.
  Es genügt ein $i$ zu finden mit $a_i \nimsum x < a_i$,
  solch einen Stapel nennen wir dann \vocab{aktiv}:
  Dann können wir vom Stapel $a_i$ so viele Münzen wegnehmen,
  dass $a_i \nimsum x$ viele übrig bleiben.
  Die neue Nimsumme ist dann
  \[
    a_1 \nimsum \dotsb (a_i \nimsum x) \dotsb a_n
    =
    a_1 \nimsum \dotsb a_n \nimsum x
    =
    x \nimsum x
    =
    0
    .
  \]
  Hierzu betrachte die vorderste Stelle $j$ von $x$ in der Binärdarstellung.
  Weil $x\neq 0$ ist, handelt es sich um eine $1$.
  Es gibt dann mindestens ein $a_i$, das an Stelle $j$ ebenfalls eine $1$ hat.
  Dann stimmt aber $x \nimsum a_i$ mit $a_i$ in allen Stellen $>j$ überein
  und hat an Stelle $j$ eine $0$ statt einer $1$.
  Damit ist $x \nimsum a_i < a_i$ wie gewünscht.
\end{proof}

\section{\gm{Hackenbush}}

\begin{game}[\gm{Hackenbush (beherrscht)}]
  Gespielt wird mit einer Anordnung von \vocab{Stäben} (Kanten),
  die an ihren Enden miteinander verbunden sein können.
  Jeder Stab ist (direkt oder indirekt) mit dem \vocab{Boden} verbunden und trägt
  eine der Farben blau und rot (korrespondierend zu den beiden Spielerinnen).
  Ein Zug besteht darin, eine Kante der eigenen Farbe zu entfernen.
  Alle Kanten, die danach nicht mehr mit dem Boden verbunden sind, werden ebenfalls entfernt.
  Wie immer verliert diejenige, die nicht mehr ziehen kann.
\end{game}

Wir werden hier (erstmal) nicht das Ziel haben, alle Positionen von Hackenbush zu klassifizieren.

\begin{example}
  Positionen $0$, $1$.
\end{example}

\begin{definition}
  Das Negative einer Hackenbush-Position entsteht durch Vertauschen der Farben
  aller Stäbe.
\end{definition}

\begin{example}
  $-1 = -(1)$.
  Das mag erstmal sehr verwirrend aussehen, ist aber dem Fakt geschuldet,
  dass wir das Negativ der Position \enquote{$1$} bereits mit $-1$ benannt haben,
  wobei hier das \enquote{$-$} ein \emph{Vorzeichen} ist,
  wohingegen bei $-(1)$ tatsächlich das \emph{Negative} des Spiels $1$ gemeint ist.
  Unsere Notation ist also so suggestiv, dass wir nicht mehr zwischen den beiden
  Dingen unterscheiden müssen/\allowbreak{}wollen/\allowbreak{}können.
\end{example}

\begin{definition}
  \label{def:spiele-vorzeichen-0-fuzzy}
  Sei $G$ ein Spiel. Dann sagen wir, dass
  \begin{enumerate}[p]
    \item $G$ \vocab{positiv} ist, wenn die linke Spielerin eine Gewinnstrategie hat.
      Wir schreiben hierbei $G>0$.
    \item $G$ \vocab{negativ} ist, wenn die rechte Spielerin eine Gewinnstrategie hat.
      Wir schreiben $G<0$.
    \item $G$ \vocab{Null} ist, wenn es eine Gewinnstrategie für die zweite Spielerin gibt.
      Wir schreiben $G=0$.
%    \item $G$ \vocab{fuzzy} ist, wenn es eine Gewinnstrategie für die erste Spielerin gibt.
%      Wir schreiben $G \fuzzy 0$.
  \end{enumerate}
\end{definition}

\begin{notation}
  Wir schreiben $\equiv $ für die Übereinstimmung von Spielen.
  Das heißt, $G \equiv H$ bedeutet,
  dass die legalen Züge von $G$ und $H$ in Bijektion stehen.
\end{notation}

\begin{remark}
  Noch haben wir keine genaue Definition von Spiel gesehen, mehr dazu später.
\end{remark}

\begin{example}
  Wir können also feststellen, dass $-1 < 0$ und $0 < 1$.
  Beachte, dass die \enquote{$0$}, die in dieser Schreibweise auftaucht,
  erstmal rein formal ist, und nicht das Nullspiel, das wir auch definiert hatten.
\end{example}

\begin{definition}
  Die Summe von zwei Hackenbush-Positionen entsteht durch deren Vereinigung.
\end{definition}

\begin{example}
  $G + 0 \equiv 0$, denn das Nullspiel hat keine legalen Züge.
  In $G + 0$ wird also letztendlich auch nur in der Position von $G$ gezogen,
  das Spiel läuft also gleich ab.
\end{example}

\begin{lemma}
  \label{lm:addition-respektiert-groessergleich-null}
  Ist $G \geq 0$ und $H \geq  0$, dann ist auch $G + H \geq 0$.
\end{lemma}

\begin{proof}
  Fängt die rechte Spielerin an,
  so kann die linke beide Spiele gewinnen, indem sie immer in dem Teilspiel mit einem
  Zug antwortet, in dem die rechte Spielerin gerade gezogen hat.
  Weil sie beide Teilspiele gewinnt, hat sie dadurch immer einen legalen Zug und gewinnt
  somit letztendlich auch die Summe.
  Fängt die linke Spielerin an, so gibt es nichts zu zeigen.
\end{proof}

\begin{definition}
  Wir sagen, dass zwei Hackenbush Positionen \vocab{gleich} sind,
  wenn sie sich spieltechnisch gleich verhalten.
  Das heißt, $G = H$ steht für $G + (-H) = 0$
  im Sinne von 
  \autoref{def:spiele-vorzeichen-0-fuzzy}.
\end{definition}

\begin{example}
  $ 1 + (-1) = 0$
\end{example}

\begin{abuse}
  Wir können jetzt außerdem feststellen,
  dass wir die \enquote{$0$} in $G < 0$ jetzt sowohl als die formale Null
  als auch das Nullspiel verstehen können.
  Denn $G + (-0) \equiv G$, und damit ist $G < 0$ (mit Nullspiel) genau als $G < 0$
  (mit formaler Null) definiert.
  In Zukunft werden wir also nicht mehr zwischen den beiden unterscheiden.
\end{abuse}

\begin{proposition}
  \label{prop:hackenbush-kleinergleich-respektiert-gleichheit}
  Die Relation \enquote{$=$} ist eine Äquivalenzrelation auf den \gm{Hackenbush}-Spielen,
  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{proof}
  TODO
\end{proof}

Außerdem können wir jetzt unsere Definition von $<$ ausweiten:

\begin{definition}
  Sind $G$ und $H$ zwei Hackenbush Spiele, so schreiben wir $G < H$ für $G - H  < 0$,
  wenn also die rechte Spielerin eine Gewinnstrategie in $G - H$ hat.
\end{definition}

An dieser Stelle sollten wir uns davon überzeugen,
dass sich $\leq $ mit Addition und Subtraktion so verhält,
wie man es erwarten würde:


\begin{proposition}
  \label{prop:hackenbush-bildet-geordnete-abelsche-gruppe}
  Die \gm{Hackenbush}-Spiele bilden 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}

\begin{proof}
  Dass die Addition kommutativ und assoziativ ist, ist bildlich sofort klar.

  Wir zeigen als nächstes, dass $P + (-P)$ ein Nullspiel ist,
  als Gewinnstrategie für die zweite Spielerin kann sie einfach die Züge der ersten
  Spielerin im jeweils anderen Spiel kopieren:
  Zieht die erste Spielerin in $P$, so zieht die zweite in $-P$ und umgekehrt.
  Damit garantiert sie, dass nach ihrem Zug immer wieder zwei zueinander negative Positionen
  vorhanden sind, und sie diese Strategie fortsetzen kann.
  Die zweite Spielerin verliert also nicht, und gewinnt somit, weil das Spiel endlich%
  \footnotemark
  ist.

  Ist $G \leq H$, so gilt $G = H$ (und wir sind fertig) oder $G < H$.
  Analog sind wir fertig oder es gilt $H < G$.
  $H < G$ und $G < H$ können aber nicht gleichzeitig eintreten,
  denn es können natürlich nicht beide Spielerinnen eine Gewinnstrategie haben.

  Zunächst wollen wir nun zeigen, dass die Ordnung überhaupt \enquote{$=$} respektiert.
  Sei hierzu $G \leq H$ und $G = G'$, Dann ist $G - H \geq 0$ und $G ' - G = 0$,
  also nach \autoref{lm:addition-respektiert-groessergleich-null} $G' - H \geq 0$,
  also $G' \geq H$.

  Jetzt ist $G_1 + H \leq G_2 + H$ nach Definition äquivalent zu $G_1 + H - (G_2 + H) \leq 0$,
  also wegen (i) zu $G_1 - G_2 \leq 0$, was genau $G_1 \leq G_2$ entspricht.
\end{proof}
\footnotetext{Mehr dazu später, momentan wollen wir das einfach annehmen}

\begin{remark}
  Wir behaupten an dieser Stelle nur, dass die Ordnung partiell ist.
  In der Tat handelt es sich hier um eine Totalordnung, aber das ist nicht trivial
  und liegt am konkreten Spiel, lässt sich also nicht wie unsere allgemeinen Ergebnisse
  später verallgemeinern, wie wir noch sehen werden.
\end{remark}


\section{\gm{Hackenbush Mischmasch}}


\begin{game}[\gm{Hackenbush Mischmasch}]
  Dieses Spiel verhält sich grundsätzlich wie Hackenbush,
  allerdings gibt es jetzt auch grüne Stäbe,
  die von beiden Spielerinnen entfernt werden dürfen.
\end{game}

\begin{talk}
  Jetzt darüber diskutieren, dass wir \enquote{komische} Positionen erhalten werden:
  \begin{itemize}
    \item Nim ist eine Teilmenge von Hackenbush geworden
    \item $\nimber 1 \fuzzy 0$
    \item up, down schon einführen?
  \end{itemize}
\end{talk}