Kombinatorische Spieltheorie
Die kombinatorische Spieltheorie, auch als CGT bekannt, ist ein Zweig der angewandten Mathematik und der theoretischen Informatik, der sich mit kombinatorischen Spielen befasst und sich von der "traditionellen" oder "ökonomischen" Spieltheorie unterscheidet. CGT entstand im Zusammenhang mit der Theorie der unparteiischen Spiele, insbesondere dem Zwei-Spieler-Spiel von Nim, mit dem Schwerpunkt auf dem "Lösen" bestimmter Arten von kombinatorischen Spielen.
Ein Spiel muss mehrere Bedingungen erfüllen, um ein kombinatorisches Spiel zu sein. Diese sind:
- Das Spiel muss mindestens zwei Spieler haben.
- Das Spiel muss sequentiell ablaufen (d.h. die Spieler wechseln sich ab.)
- Das Spiel muss über perfekte Informationen verfügen (d.h. es dürfen keine Informationen versteckt sein, wie beim Poker).
- Das Spiel muss deterministisch (d.h. chancenlos) sein. Glück ist nicht Teil des Spiels.
- Die Partie muss eine bestimmte Anzahl von möglichen Zügen haben.
- Das Spiel muss irgendwann enden.
- Das Spiel muss beendet werden, wenn ein Spieler nicht mehr ziehen kann.
Die kombinatorische Spieltheorie beschränkt sich weitgehend auf die Untersuchung einer Teilmenge von kombinatorischen Spielen, die zwei Spieler haben, endlich sind und einen Gewinner und einen Verlierer haben (d.h. nicht unentschieden enden).
Diese kombinatorischen Partien können durch Bäume dargestellt werden, von denen jeder Scheitelpunkt die Partie ist, die sich aus einem bestimmten Zug aus der Partie direkt unter dem Baum ergibt. Diesen Partien können Spielwerte zugeordnet werden. Das Auffinden dieser Spielwerte ist für CG-Theoretiker von großem Interesse, ebenso wie das theoretische Konzept der Partieaddition. Die Summe von zwei Partien ist die Partie, in der jeder Spieler an seinem Zug nur in einer der beiden Partien ziehen muss, während die andere unverändert bleibt.
Elwyn Berlekamp, John Conway und Richard Guy sind die Begründer der Theorie. Sie arbeiteten in den 1960er Jahren zusammen. Ihre veröffentlichte Arbeit wurde Winning Ways for Your Mathematical Plays genannt.
Definitionen
In der Theorie gibt es zwei Spieler, die links und rechts genannt werden. Eine Partie ist etwas, das es links und rechts ermöglicht, Züge zu anderen Partien zu machen. Zum Beispiel gibt es beim Schachspiel eine übliche Startaufstellung. Man könnte sich eine Schachpartie jedoch auch nach dem ersten Zug als eine andere Partie mit einem anderen Aufbau vorstellen. Jede Stellung wird also auch als Partie bezeichnet.
Spiele haben die Notation {L|R}. L {\Anzeigeart L}
sind die Spiele, zu denen der linke Spieler ziehen kann. R {\Anzeigestil R}
sind die Partien, zu denen der rechte Spieler sich bewegen kann. Wenn Sie die Schachnotation kennen, dann ist die übliche Schachaufstellung die Partie
| { a 3 , a 4 , N a 3 , b 3 , b 4 , c 3 , c 4 , N c 3 , ... | a 6 , a 5 , N a 6 , b 6 , b 5 , c 6 , c 5 , N c 6 , ... } {\Anzeigestil \{a3,a4,Na3,b3,b4,c3,c4,Nc3,\Punkte |a6,a5,Na6,b6,b5,c6,c5,Nc6,\Punkte \} |
Die Punkte "..." bedeuten, dass es viele Züge gibt, es werden also nicht alle angezeigt.
Schach ist sehr komplex. Es ist besser, sich einfachere Partien auszudenken. Nim, zum Beispiel, ist viel einfacher zu denken. Nim wird so gespielt:
- Es gibt null oder mehr Stapel von Zählern.
- In einem Spielzug darf ein Spieler so viele Spielsteine von einem Stapel nehmen, wie er möchte.
- Der Spieler, der keinen Zug machen kann, verliert.
Das einfachste Spiel von Nim beginnt ganz ohne Konter! In einem solchen Fall kann keiner der beiden Spieler ziehen. Das wird als {|} angezeigt. Beide Seiten sind leer, weil keiner der Spieler ziehen kann. Der erste Spieler, der geht, kann nicht ziehen und verliert somit. Im CGT schreibt man oft {{|} als Symbol 0 (Null).
Das nächst leichtere Spiel hat nur einen Stapel mit nur einem Konter. Wenn der linke Spieler zuerst geht, muss dieser Spieler den Spielstein nehmen und rechts ohne Zug ({|}, oder 0) zurückbleiben. Wenn stattdessen die Rechte zuerst zieht, gibt es für die Linke keine Züge mehr. Also können sowohl links als auch rechts einen Zug auf 0 machen, was als {{{{{|}|{|}} oder {0|0} angezeigt wird. Der erste Spieler, der einen Zug macht, gewinnt. Spiele mit {0|0} sind sehr wichtig. Sie werden mit dem Symbol * (Stern) geschrieben.
Fragen und Antworten
F: Was ist die Kombinatorische Spieltheorie?
A: Die Kombinatorische Spieltheorie (CGT) ist ein Zweig der angewandten Mathematik und der theoretischen Informatik, der sich mit kombinatorischen Spielen befasst und sich von der "traditionellen" oder "wirtschaftlichen" Spieltheorie unterscheidet.
F: Welche Bedingungen muss ein Spiel erfüllen, um als kombinatorisches Spiel zu gelten?
A: Damit ein Spiel als kombinatorisches Spiel angesehen werden kann, muss es mindestens zwei Spieler haben, es muss sequentiell sein (d.h. die Spieler sind abwechselnd am Zug), es muss perfekte Informationen haben (d.h. es gibt keine versteckten Informationen), es muss deterministisch sein (d.h. kein Zufall), Glück darf nicht Teil des Spiels sein, es muss eine bestimmte Anzahl möglicher Züge geben, das Spiel muss schließlich enden, und das Spiel muss enden, wenn ein Spieler nicht mehr ziehen kann.
F: Auf welche Art von Spielen konzentriert sich die Kombinatorische Spieltheorie?
A: Die kombinatorische Spieltheorie konzentriert sich hauptsächlich auf endliche Spiele mit zwei Spielern, bei denen es Gewinner und Verlierer gibt (d.h. die nicht unentschieden enden).
F: Wie werden diese Arten von Spielen dargestellt?
A: Diese Arten von Spielen können durch Bäume dargestellt werden, wobei jeder Scheitelpunkt das Ergebnis eines bestimmten Zuges des direkt darunter liegenden Spielers im Baum darstellt.
F: Was sind einige Ziele für CG-Theoretiker?
A: Zu den Zielen der CG-Theoretiker gehört es, Werte für diese Art von Spielen zu finden und das Konzept der "Spieladdition" zu verstehen, bei dem jeder Spieler in zwei verschiedenen Spielen nur einen Zug macht, während das andere Spiel unverändert bleibt.
F: Wer hat die CGT gegründet?
A: Elwyn Berlekamp, John Conway und Richard Guy wird die Gründung der CGT in ihrem in den 1960er Jahren veröffentlichten Werk Winning Ways for Your Mathematical Plays zugeschrieben.
