Rechnerisch begrenzte Version des Nash-Gleichgewichts?

Ich frage mich, ob es eine rechnerisch begrenzte Version des Nash-Gleichgewichtskonzepts gibt, etwa in der folgenden Richtung.

Stellen Sie sich eine Art perfektes Zwei-Spieler-Informationsspiel vor, das auf einem Brett gespielt wird und in dem Sinne komplex ist, dass ein optimales Spiel EXPTIME-schwer ist. Nehmen wir auch der Einfachheit halber an, dass Zeichnungen nicht möglich sind. Stellen Sie sich ein Paar zufälliger Polynom-Zeit-Turing-Maschinen vor, die dieses Spiel gegeneinander spielen. Für jeden , lassen die Wahrscheinlichkeit , dass schlägt an dem auftrags- - Spiel. (Der Vollständigkeit halber nehmen wir an, dass mit einer Wahrscheinlichkeit von 0,5 zuerst spielt.) Ich halte es für cool, wenn man die Existenz eines Paares nachweisen könnte( A , B ) n p A , B ( n ) A B n A ( A , B $n\times n$$(A, B)$$n$$p_{A,B}(n)$$A$$B$$n$$A$$(A,B)$mit der Eigenschaft , daß kein Polynom-Zeitturingmaschine randomisiert dominiert (wobei " vorherrscht " bedeutet für alle hinreichend großen ) und in ähnlicher Weise kein Polynom-Zeitturingmaschine randomisiert dominiert (wobei " dominiert " bedeutet für alle hinreichend großen ).$A'$ $A$$A'$$A$$p_{A',B}(n) > p_{A,B}(n)$$n$$B'$$B$$B'$$B$$p_{A,B'}(n) < p_{A,B}(n)$$n$

Irgendwie vermute ich, dass das zu viel ist, um es zu hoffen, aber gibt es irgendeine Hoffnung, dass so etwas wahr ist, vielleicht für eine eingeschränkte Klasse von Spielen?

Eine Motivation für diese Frage ist, dass ich nach einer Möglichkeit suche, die Vorstellung zu formalisieren, dass eine gegebene Schachposition "vorteilhaft für Weiß" ist. Klassischerweise ist eine Position entweder ein Gewinn für Weiß oder nicht. Schachspieler, sowohl Menschen als auch Computer, haben jedoch ein intuitives Verständnis dafür, was es für Weiß bedeutet, einen Vorteil zu haben. Es scheint etwas mit der Wahrscheinlichkeit zu tun zu haben, dass Weiß gewinnt, vorausgesetzt, die Spieler sind rechenintensiv und müssen den besten Zug erraten. Für ein bestimmtes Paar randomisierter Algorithmen kann man natürlich über die Wahrscheinlichkeit sprechen, dass Weiß gewinnen wird, aber ich frage mich, ob es in gewissem Sinne eine kanonische geben kann Paar rechnerisch begrenzter Spieler, deren Gewinnwahrscheinlichkeiten einen Wert für die Position ergeben, der nur vom Spiel selbst und nicht von den Eigenheiten der Spieler abhängt.

Ich kann mir auf keine Weise vorstellen, dass es eine einfache, völlig elegante / befriedigende Antwort auf diese Frage geben könnte, insbesondere weil die Endauszahlung so schwer zu berechnen ist. Meine Gedanken sind jedoch zu lang, um sie als Kommentar zu veröffentlichen.

Die beste Idee, die ich habe, ist folgende: Versuchen Sie im Fall von Schach, die Wahrscheinlichkeit, dass Weiß gewinnt, basierend auf dem materiellen Vorteil von Weiß (dh zusätzliche Bauern, Ritter usw.) für eine bestimmte Position zu schätzen, indem Sie Positionen mit genau diesem Betrag zufällig auswählen -Konfiguration. Vielleicht könnten wir im Fall von "All-Rooks-Schach" sagen: "Wie wahrscheinlich ist es, dass Weiß mit 8 Rooks gegen die 17 Rooks von Schwarz gewinnt?" Vielleicht beträgt diese Wahrscheinlichkeit 4%; Um dies zu berechnen, müssten wir 1000 verschiedene zufällig generierte Schachpositionen untersuchen, die 8 weiße und 17 schwarze Türme haben, und dann in jedem Fall 10 Züge tief nach vorne schauen, um zu sehen, wie die neue Materialkonfiguration aussieht . Nehmen Sie dann die erwarteten Gewinnchancen basierend auf der Materialkonfiguration am Ende.

Natürlich wäre es notwendig, die Materialkonfiguration für jede relevante Möglichkeit ( M , N ) von M weißen Türmen zu N schwarzen Türmen zu finden ... vermutlich beginnend mit dem Paar niedrigster Ordnung ( M = 1, N = 1) und arbeitend von dort oben.

Gehen Sie für die ursprüngliche Position nicht einfach von der Statistik aus, die Sie erhalten (dh, wenn die ursprüngliche Position Türme hat ( M = 6, N = 7), gehen Sie nicht einfach davon aus, dass Weiß eine Gewinnchance von 25% hat, weil das so ist die erwarteten Gewinnchancen für (6,7)); Stattdessen, weil Sie präziser sein können, schauen Sie mit nur dieser einen Position wie gewohnt 10 Züge tief und finden Sie jede mögliche Endposition. Suchen Sie dann den richtigen Pfad (der ein optimales Spiel beider Seiten beinhaltet) zu einer Konfiguration mit 10 Zügen und wählen Sie die erwarteten Quoten dieses Pfades als die erwarteten Quoten der ursprünglichen Position aus.

Ich denke, dass dieser Prozess in polynomialer Zeit durchgeführt werden kann. Wenn Sie im Schach nach einem festen k suchen, ist k in der Größe des Bretts polynomisch, und die Gesamtzahl der weißen und schwarzen Türme wird (in gewisser Weise) als unär ausgedrückt, da diese Zahl kleiner als die Größe des Bretts sein muss.

Wenn das kompliziert und schwer zu erklären klingt, dann ist es so. Eine prägnantere Zusammenfassung dessen, was ich beschreibe, ist: Verwenden Sie Rekursion und grundlegende Statistiken, um die Gewinnchancen für Weiß bei M weißen Türmen und N schwarzen Türmen auf dem Brett zu berechnen . Verwenden Sie dann diese Werte, um zu sehen, wie tief sich k bewegt, und um die Gewinnchancen für Weiß in der ursprünglichen Position zu ermitteln.

Abschließender Kommentar: Ich denke, dieses Problem ist auch für Spiele interessant, die nicht EXPTIME-vollständig sind, wie Tic-Tac-Toe, das laut Wikipedia PSPACE-vollständig ist. Außerdem glaube ich, dass ein Prozess wie der oben beschriebene auch dort nützlich sein könnte, obwohl es offensichtlich unmöglich wäre, einen "materiellen" Vorteil in Tic-Tac-Toe zu haben. Es müsste eine andere Grundlage für die Beurteilung der Überlegenheit der X- oder O-Position geben.