Kombinatorische Spieltheorie (CGT) ist ein Zweig der angewandten Mathematik und theoretischen Informatik, die folgende Spiele mit der vollkommenen Information, d. h. Zwei-Spieler-Spiele studiert, die eine Position haben, in die sich die Spieler abwechseln, sich auf definierte Weisen ändernd, oder sich bewegen, um eine definierte gewinnende Bedingung zu erreichen. CGT studiert Spiele mit der unvollständigen oder unvollständigen Information (manchmal genannt Glücksspiele, wie Schürstange) nicht. Es schränkt sich zu Spielen ein, deren Position beiden Spielern öffentlich ist, und in dem der Satz von verfügbaren Bewegungen auch (vollkommene Information) öffentlich ist. Kombinatorische Spiele schließen wohl bekannte Spiele wie Schach, Kontrolleure ein, Gehen Sie Arimaa, Hexe und Connect6. Sie schließen auch kombinatorische Ein-Spieler-Rätsel und sogar Automaten ohne Spieler wie das Spiel von Conway des Lebens ein. In CGT werden die Bewegungen in diesen Spielen als ein Spielbaum vertreten.

Spieltheorie schließt im Allgemeinen Glücksspiele, Spiele von unvollständigen Kenntnissen und Spiele ein, in denen sich Spieler gleichzeitig bewegen können, und sie neigen dazu, wahre Entscheidungsbilden-Situationen zu vertreten.

CGT hat eine verschiedene Betonung als "traditionelle" oder "wirtschaftliche" Spieltheorie, die am Anfang entwickelt wurde, um Spiele mit der einfachen kombinatorischen Struktur zu studieren, aber mit Elementen der Chance (obwohl es auch folgende Bewegungen denkt, sieh Spiel der umfassenden Form). Im Wesentlichen hat CGT neue Methoden beigetragen, um Spielbäume zum Beispiel mit surrealen Zahlen zu analysieren, die eine Unterklasse aller Zwei-Spieler-Spiele der vollkommenen Information sind. Der Typ von durch CGT studierten Spielen ist auch in der künstlichen Intelligenz, besonders für die automatisierte Planung und Terminplanung von Interesse. In CGT hat es weniger Betonung auf der Raffinierung praktischer Suchalgorithmen (wie das Alpha-Beta gegeben, das heuristisch, eingeschlossen in die meisten Lehrbücher der künstlichen Intelligenz heute beschneidet), aber mehr Betonung auf beschreibenden theoretischen Ergebnissen, wie Maßnahmen der Spielkompliziertheit oder Beweise der optimalen Lösungsexistenz, ohne einen Algorithmus notwendigerweise anzugeben (sieh Strategie stehlendes Argument zum Beispiel).

Ein wichtiger Begriff in CGT ist der des gelösten Spiels (der mehrere Geschmäcke hat), zum Beispiel bedeutend, dass man beweisen kann, dass das Spiel von tic-tac-toe auf eine Attraktion hinausläuft, wenn beide Spieler optimal spielen. Während das ein triviales Ergebnis ist, ist das Abstammen ähnlicher Ergebnisse für Spiele mit reichen kombinatorischen Strukturen schwierig. Zum Beispiel 2007 wurde es bekannt gegeben, dass Kontrolleure (schwach, aber nicht stark) gelöst gewesen sind - führt das optimale Spiel durch beide Seiten auch zu einer Attraktion - aber dieses Ergebnis war ein computergestützter Beweis. Andere echte Weltspiele werden größtenteils zu kompliziert, um ganze Analyse heute zu erlauben (obwohl die Theorie einige neue Erfolge im Analysieren gehabt hat, Gehen Schlussphasen). Die Verwendung von CGT zu einer Position versucht, die optimale Folge von Bewegungen für beide Spieler bis zu den Spielenden, und durch das Tun zu bestimmen, so entdecken Sie die optimale Bewegung in jeder Position. In der Praxis ist dieser Prozess gewunden schwierig, wenn das Spiel nicht sehr einfach ist.

Geschichte

CGT ist in Bezug auf die Theorie von gerechten Spielen entstanden, in denen jedes für einen Spieler verfügbare Spiel für den anderen ebenso verfügbar sein muss. Ein sehr wichtiger solches Spiel ist nim, der völlig gelöst werden kann. Nim ist ein gerechtes Spiel für zwei Spieler und Thema der normalen Spiel-Bedingung, was bedeutet, dass ein Spieler, der sich nicht bewegen kann, verliert. In den 1930er Jahren hat der Sprague-Grundy Lehrsatz gezeigt, dass alle gerechten Spiele zu Haufen in nim gleichwertig sind, so zeigend, dass Hauptvereinigungen in Spielen möglich sind, die an einem kombinatorischen Niveau (in der ausführlich berichtete Strategie-Sache, nicht nur Belohnungen) betrachtet sind.

In den 1960er Jahren haben Elwyn R. Berlekamp, John H. Conway und Richard K. Guy gemeinsam die Theorie eines Parteispiels eingeführt, in dem die Voraussetzung dass ein für einen Spieler verfügbares Spiel, für beide verfügbar sein, entspannt wird. Ihre Ergebnisse wurden in ihrem Buch veröffentlicht, Wege für Ihre Mathematischen Spiele 1982 Gewinnend. Jedoch war das erste auf dem Thema veröffentlichte Buch Conway Auf Zahlen und Spielen, auch bekannt als ONAG, der das Konzept surrealer Zahlen und der Generalisation zu Spielen eingeführt hat. Auf Zahlen und Spielen war auch eine Frucht der Kollaboration zwischen Berlekamp, Conway und Guy.

Kombinatorische Spiele sind allgemein durch die Tagung, die in eine Form gestellt ist, wo ein Spieler gewinnt, wenn der andere keine restlichen Bewegungen hat. Es ist leicht, jedes begrenzte Spiel mit nur zwei möglichen Ergebnissen in ein gleichwertiges umzuwandeln, wo diese Tagung gilt. Eines der wichtigsten Konzepte in der Theorie von kombinatorischen Spielen ist das der Summe von zwei Spielen, die ein Spiel ist, wo jeder Spieler beschließen kann, sich entweder in einem Spiel oder in anderem an jedem Punkt im Spiel zu bewegen, und ein Spieler gewinnt, wenn sein Gegner keine Bewegung in jedem Spiel hat. Diese Weise, Spiele zu verbinden, führt zu einer reichen und starken mathematischen Struktur.

John Conway stellt in ONAG fest, dass die Inspiration für die Theorie von Parteispielen auf seiner Beobachtung des Spieles darin basiert hat, gehen Schlussphasen, die häufig in Summen von einfacheren Schlussphasen zersetzt werden können, die von einander in verschiedenen Teilen des Ausschusses isoliert sind.

Beispiele

Der einleitende Text, Wege Gewinnend, hat eine Vielzahl von Spielen eingeführt, aber der folgende wurde als das Motivieren von Beispielen für die einleitende Theorie verwendet:

• Blau-roter Hackenbush - Am begrenzten Niveau erlaubt dieses kombinatorische Parteispiel Aufbauten von Spielen, deren Werte dyadische rationale Zahlen sind. Am unendlichen Niveau erlaubt es, alle echten Werte, sowie viele unendliche zu bauen, die innerhalb der Klasse von surrealen Zahlen fallen.

• Blauer Roter Grüner" Hackenbush - Berücksichtigt zusätzliche Spielwerte, die nicht Zahlen im traditionellen Sinn, zum Beispiel, Stern sind.
• Kröten und Frösche - Erlauben verschiedene Spielwerte. Verschieden von den meisten anderen Spielen wird eine Position durch eine kurze Reihe von Charakteren leicht vertreten.
• Tyrannisierend - erscheinen Verschiedene interessante Spiele wie heiße Spiele, als Positionen im Tyrannischen, weil es manchmal einen Ansporn gibt, sich, und manchmal nicht zu bewegen. Das erlaubt Diskussion einer Temperatur eines Spiels.
• Nim - Ein gerechtes Spiel. Das berücksichtigt den Aufbau des nimbers. (Es kann auch als ein grün-einziger spezieller Fall "Blauen Roten Grünen" Hackenbush gesehen werden.)

Das klassische Spiel Geht war auf die frühe kombinatorische Spieltheorie einflussreich, und Berlekamp und Wolfe haben nachher eine Schlussphase und Temperaturtheorie dafür entwickelt (sieh Verweisungen). Bewaffnet damit sind sie im Stande gewesen, plausibel zu bauen, Gehen Schlussphase-Positionen, von denen sie Experten geben konnten, Gehen Spieler eine Wahl von Seiten und vereiteln sie dann jeder Weg.

Übersicht

Ein Spiel, in seinen einfachsten Begriffen, ist eine Liste von möglichen "Bewegungen", die zwei Spieler, genannt link und Recht, machen können. Wie man betrachten kann, ist die Spielposition, die sich aus jeder Bewegung ergibt, ein anderes Spiel. Diese Idee, Spiele in Bezug auf ihre möglichen Bewegungen zu anderen Spielen anzusehen, führt zu einer rekursiven mathematischen Definition von Spielen, die in der kombinatorischen Spieltheorie normal ist. In dieser Definition hat jedes Spiel die Notation {LR}. ist der Satz von Spielpositionen, die der linke Spieler dazu bewegen kann, und der Satz von Spielpositionen ist, zu denen sich der richtige Spieler bewegen kann; jede Position in L und R wird als ein Spiel mit derselben Notation definiert.

Verwenden Sie Tyrannisch als ein Beispiel, etikettieren Sie jeden der sechzehn Kästen vier durch vier Ausschuss durch A1 für das obere leftmost Quadrat, C2 für den dritten Kasten vom links auf der zweiten Reihe von der Spitze und so weiter. Wir verwenden z.B (D3, D4), um für die Spielposition einzutreten, in der ein vertikales Domino in die Ecke unten rechts gelegt worden ist. Dann kann die anfängliche Position in der kombinatorischen Spieltheorie-Notation als beschrieben werden

Bemerken Sie, dass, im Standardquer-Gedränge-Spiel, die Spieler Umdrehungen abwechseln lassen, aber dieser Wechsel wird implizit durch die Definitionen der kombinatorischen Spieltheorie behandelt, anstatt innerhalb der Spielstaaten verschlüsselt zu werden.

Das obengenannte Spiel (ist ein irrelevantes offenes Quadrat an C3 aus dem Diagramm weggelassen worden), beschreibt ein Drehbuch, in dem es nur eine Bewegung abgereist jeder Spieler gibt, und wenn jeder Spieler das sich dieser Spieler Gewinne bewegen lässt.

: 1 = {0 |}, 2 = {1 |}, 3 = {2 | }\

:-1 = 0\,-2 =-1},-3 =-2 }\

Das Nullspiel ist ein Verlust für den ersten Spieler.

Die Summe von Zahlenspielen benimmt sich wie die ganzen Zahlen, zum Beispiel 3 +-2 = 1.

Stern

Stern, schriftlich als * oder {0|0}, ist ein Gewinn des ersten Spielers, da jeder Spieler muss (wenn man sich zuerst im Spiel bewegt), bewegen sich zu einem Nullspiel, und gewinnen deshalb.

: * + * = 0, weil der erste Spieler eine Kopie * zu 0, und dann drehen muss, wird der andere Spieler die andere Kopie * zu 0 ebenso drehen müssen; an diesem Punkt würde der erste Spieler verlieren, seitdem 0 + 0 lässt keine Bewegungen zu.

Das Spiel, *, ist weder positiv noch negativ; wie man gesagt wird, ist es und alle anderen Spiele, in denen der erste Spieler gewinnt (unabhängig von dem Partei ergreifen, ist der Spieler auf), damit kraus oder mit 0 verwirrt; symbolisch schreiben wir * || 0.

Oben, schriftlich als , ist eine Position in der kombinatorischen Spieltheorie. In der Standardnotation,  = {0 |*}.

: − =  (unten)

ausschließlich positiv (> 0), aber ist unendlich klein. Wird im Gewinnen von Wegen für Ihre Mathematischen Spiele definiert.

Unten

Unten, schriftlich als , ist eine Position in der kombinatorischen Spieltheorie. In der Standardnotation,  = {* |0}.

: − = 

Unten ist ausschließlich negativ (