Gibt es einen perfekten Algorithmus für Schach? [geschlossen]

109

Ich war kürzlich in einer Diskussion mit einer Nicht-Codierer-Person über die Möglichkeiten von Schachcomputern. Ich bin theoretisch nicht gut versiert, aber ich glaube, ich weiß genug.

Ich argumentierte, dass es keine deterministische Turing-Maschine geben könne, die beim Schach immer gewann oder ins Stocken geriet. Ich denke, selbst wenn Sie den gesamten Raum aller Kombinationen von Spieler-1/2-Zügen durchsuchen, basiert der einzelne Zug, über den der Computer bei jedem Schritt entscheidet, auf einer Heuristik. Da es auf einer Heuristik basiert, schlägt es nicht unbedingt ALLE Züge, die der Gegner ausführen könnte.

Mein Freund dachte im Gegenteil, dass ein Computer immer gewinnen oder unentschieden spielen würde, wenn er niemals einen "Fehler" machen würde (aber definieren Sie das?). Als Programmierer, der CS genommen hat, weiß ich jedoch, dass selbst Ihre guten Entscheidungen - angesichts eines weisen Gegners - Sie am Ende dazu zwingen können, "Fehler" zu machen. Selbst wenn Sie alles wissen, ist Ihr nächster Schritt gierig darin, eine Heuristik zu finden.

Die meisten Schachcomputer versuchen, ein mögliches Endspiel an das laufende Spiel anzupassen, was im Wesentlichen ein dynamischer Programmier-Traceback ist. Auch hier ist das fragliche Endspiel vermeidbar.

Edit: Hmm ... sieht so aus, als hätte ich hier ein paar Federn gekräuselt. Das ist gut.

Wenn man noch einmal darüber nachdenkt, scheint es kein theoretisches Problem zu geben, ein endliches Spiel wie Schach zu lösen. Ich würde argumentieren, dass Schach etwas komplizierter ist als Dame, da ein Sieg nicht unbedingt durch numerische Erschöpfung der Figuren, sondern durch einen Partner erfolgt. Meine ursprüngliche Behauptung ist wahrscheinlich falsch, aber andererseits denke ich, dass ich auf etwas hingewiesen habe, das (formal) noch nicht zufriedenstellend bewiesen ist.

Ich denke, mein Gedankenexperiment war, dass der Algorithmus (oder die gespeicherten Pfade) immer dann, wenn ein Zweig im Baum genommen wird, einen Pfad zu einem Partner finden muss (ohne sich zu paaren), damit sich ein möglicher Zweig des Gegners bewegt. Nach der Diskussion werde ich kaufen, dass bei mehr Gedächtnis, als wir uns nur erträumen können, all diese Wege gefunden werden könnten.

Überflogen
quelle
1
+1: ausgezeichnetes Thema. Ich würde jedoch denken, dass dies Wiki-fied sein sollte, wie die Vielfalt und das Volumen der Antworten zeigen.
IAbstract
1
"Ich glaube, ich habe auf etwas hingewiesen, das noch nicht zufriedenstellend bewiesen ist"? Worauf haben Sie hingewiesen, was formal nicht bewiesen ist?
S.Lott
2
ack! Wie kann es 20 verschiedene Antworten auf eine solche Schwarz-Weiß-Frage geben? (kein Wortspiel beabsichtigt).
Peter Recore
5
Auch ich bin erstaunt über die Anzahl der Personen, die ihre spekulativen Antworten veröffentlichen, ohne zu wissen, dass die Antwort tatsächlich mathematisch bestimmt wurde - Antwort in dem Sinne, dass bewiesen wurde, dass Schach eine Lösung hat - es ist einfach nicht praktikabel, sie zu berechnen.
DJClayworth
3
Erinnert mich an den Witz über den Perfect Chess Playing Computer. Weiß spielen, es denkt und denkt und denkt und dann ... tritt zurück!

Antworten:

104

"Ich habe argumentiert, dass es keine deterministische Turing-Maschine geben kann, die beim Schach immer gewonnen oder ins Stocken geraten ist."

Du hast nicht ganz recht. Es kann eine solche Maschine geben. Das Problem ist die Größe des Staatsraums, den er durchsuchen müsste. Es ist endlich, es ist einfach WIRKLICH groß.

Deshalb greift Schach auf Heuristiken zurück - der Staatsraum ist zu groß (aber endlich). Selbst aufzuzählen - viel weniger nach jedem perfekten Zug in jedem Verlauf eines möglichen Spiels zu suchen - wäre ein sehr, sehr großes Suchproblem.

Eröffnungen werden per Skript erstellt, um Sie zu einer Spielmitte zu bringen, die Ihnen eine "starke" Position gibt. Kein bekanntes Ergebnis. Selbst Endspiele - wenn es weniger Teile gibt - sind schwer aufzuzählen, um den besten nächsten Zug zu bestimmen. Technisch sind sie endlich. Aber die Anzahl der Alternativen ist riesig. Sogar ein 2 Türme + König hat ungefähr 22 mögliche nächste Züge. Und wenn es 6 Züge dauert, um sich zu paaren, sehen Sie 12.855.002.631.049.216 Züge.

Rechnen Sie beim Öffnen von Zügen. Während es nur etwa 20 Eröffnungszüge gibt, gibt es ungefähr 30 zweite Züge. Beim dritten Zug sehen wir uns also 360.000 alternative Spielzustände an.

Aber Schachspiele sind (technisch) endlich. Riesig, aber endlich. Es gibt perfekte Informationen. Es gibt definierte Start- und Endzustände. Es gibt keine Münzwürfe oder Würfelwürfe.

S.Lott
quelle
22
Alle Endspiele mit 6 oder weniger Teilen wurden aufgezählt und gelöst. Siehe Tabellenbasis und Bitbasis hier: en.wikipedia.org/wiki/Tablebase . Zum Beispiel gibt es ein KQNKRBN-Endspiel, bei dem 517 Züge erforderlich sind, um einen Partner zu zwingen! Die Gesamtzahl der Schachpartien liegt jedoch bei (10 ^ (10 ^ 50)).
HTTP 410
2
Ein Skript zum Gewinnen ist eine Sache. Vollständig aufgezählt ist eine andere Sache. In jedem Fall sind die Informationen perfekt - alles ist bekannt - das Spiel ist per Definition deterministisch.
S.Lott
11
@ RoadWarrior: nicht einverstanden. Zufällig gilt für das Wetter. Gott würfelt. Zufall gilt nicht für Schach - per Definition. Schach hat vollständige Informationen. Wetter hat Quanteneffekte - es kann nicht vollständig sein.
S.Lott
3
Was die Vorhersage des Wetters schwierig macht, sind die chaotischen nichtlinearen Faktoren, keine Quanteneffekte. Bei ausreichender Rechenleistung und ausreichendem Wissen könnten wir theoretisch eine "korrekte" Wettervorhersage erstellen.
HTTP 410
3
@monojohnny: Die Regeln verbieten drei Wiederholungen derselben Position. Schach ist einfach endlich. Es ist groß aber endlich.
S.Lott
72

Ich weiß so gut wie nichts darüber, was tatsächlich über Schach entdeckt wurde. Aber als Mathematiker hier meine Argumentation:

Zuerst müssen wir uns daran erinnern, dass Weiß zuerst gehen darf und dies ihm vielleicht einen Vorteil verschafft; Vielleicht gibt es Schwarz einen Vorteil.

Nehmen wir nun an, dass es für Schwarz keine perfekte Strategie gibt , mit der er immer gewinnen / in eine Pattsituation geraten kann. Dies bedeutet, dass Weiß unabhängig davon, was Schwarz tut, eine Strategie verfolgen kann, um zu gewinnen. Warten Sie eine Minute - das heißt, es gibt eine perfekte Strategie für Weiß!

Dies sagt uns , dass zumindest einer der beiden Spieler hat eine perfekte Strategie hat , die diese Spieler können immer Sieg oder Unentschieden.

Es gibt also nur drei Möglichkeiten:

  • Weiß kann immer gewinnen, wenn er perfekt spielt
  • Schwarz kann immer gewinnen, wenn er perfekt spielt
  • Ein Spieler kann gewinnen oder unentschieden spielen, wenn er perfekt spielt (und wenn beide Spieler perfekt spielen, geraten sie immer in eine Pattsituation)

Aber welche davon tatsächlich richtig ist, wissen wir vielleicht nie.

Die Antwort auf die Frage lautet ja : Es muss einen perfekten Algorithmus für Schach geben, zumindest für einen der beiden Spieler.

Artelius
quelle
2
+1, das ist eine großartige Möglichkeit, es zu erklären. Ich kann nicht glauben, dass ich nie daran gedacht habe!
Zifre
2
Warum bedeutet Schwarz ohne perfekte Strategie, dass Weiß eine perfekte Strategie hat? Was ist mit beiden Spielern, die keine perfekte Strategie haben? Wenn Ihre Implikation wahr wäre, würde es nicht für jedes 2-Spieler-Spiel zutreffen, was bedeutet, dass jedes Spiel eine perfekte Strategie hat?
John M Naglick
8
@john: Da Schach perfekte Informationen und keine zufälligen Elemente enthält (im Gegensatz zu vielen, vielen anderen 2-Spieler-Spielen), ist es nur möglich, dass keine perfekte Strategie für Schwarz existiert, wenn Weiß trotz eines Versuchs von einen Sieg erzwingen kann schwarz - mit anderen Worten, wenn es eine perfekte Strategie für Weiß gibt.
Dave Sherohman
2
Eigentlich gilt diese Logik nicht immer , aber in diesem Fall ist sie wahr.
BlueRaja - Danny Pflughoeft
4
@john "warum so viel Diskussion hier" - weil einige Leute die Antwort nicht kennen, aber trotzdem hier posten.
DJClayworth
30

Für das Dame-Spiel wurde bewiesen, dass ein Programm das Spiel immer gewinnen oder binden kann. Das heißt, es gibt keine Auswahl an Zügen, die ein Spieler ausführen kann, um den anderen Spieler zum Verlieren zu zwingen.

Die Forscher haben fast zwei Jahrzehnte damit verbracht , die 500 Milliarden Milliarden möglichen Dame-Positionen zu durchlaufen, was übrigens immer noch ein unendlich kleiner Bruchteil der Anzahl der Schachpositionen ist. Zu den Bemühungen der Prüfer gehörten Top-Spieler, die dem Forschungsteam dabei halfen, die Faustregeln der Prüfer in Software zu programmieren, die Bewegungen als erfolgreich oder erfolglos einstufte. Dann ließen die Forscher das Programm auf durchschnittlich 50 Computern täglich laufen. An manchen Tagen lief das Programm auf 200 Maschinen. Während die Forscher den Fortschritt überwachten und das Programm entsprechend anpassten. Tatsächlich schlug Chinook die Menschen, um 1994 die Dame-Weltmeisterschaft zu gewinnen.

Ja, Sie können Schach lösen, nein, Sie werden es nicht so bald tun.

BCS
quelle
6
"[Y] du wirst nicht so bald" ist eine Untertreibung. Neben der Begrenzung der erwarteten Dauer des Universums gibt es ein Speicherproblem: Die Anzahl der Staaten im Schach übersteigt die 500 Milliarden Milliarden Kontrolleure bei weitem. Tatsächlich überschreitet es die Anzahl der Teilchen im Universum.
Michael Dorfman
30
"[...] tatsächlich übersteigt es die Anzahl der Teilchen im Universum." Solange es die Anzahl der Zustände der Teilchen im Universum nicht überschreitet, gibt es noch Hoffnung ;-)
Carsten
1
Was passiert, wenn das Programm, das den Gegner immer zum Verlieren zwingt, gegen sich selbst spielt?
John Demetriou
1
@BCS hmm, was ist, wenn es eine Vorhersage gibt, in der, wenn ich als zweiter Spieler spiele und der andere dieselbe Heuristik wie ich verwendet, dieser Heuristik folgt, um zu gewinnen, und wenn der erste Spieler eine ähnliche Heuristik hat ???? ?
John Demetriou
1
Ich sage, wenn es einen perfekten Algorithmus gibt und beide Spieler ihn haben, wird es eine unbestimmte Anzahl von Wahrscheinlichkeiten geben, die der Algorithmus ändern kann, damit er perfekt ist
John Demetriou
15

Hier geht es nicht um Computer, sondern nur um das Schachspiel.

Die Frage ist, gibt es eine ausfallsichere Strategie, um das Spiel niemals zu verlieren? Wenn es eine solche Strategie gibt, kann ein Computer, der alles weiß, sie immer verwenden, und sie ist keine Heuristik mehr.

Zum Beispiel wird das Spiel Tic-Tac-Toe normalerweise basierend auf Heuristiken gespielt. Es gibt jedoch eine ausfallsichere Strategie. Was auch immer der Gegner bewegt, Sie finden immer einen Weg, um zu vermeiden, dass Sie das Spiel verlieren, wenn Sie es von Anfang an richtig machen.

Sie müssten also beweisen, dass eine solche Strategie auch für Schach existiert oder nicht. Es ist im Grunde das gleiche, nur der Raum möglicher Bewegungen ist weitaus größer.

ypnos
quelle
Also, wer hatte den Drang, meine Antwort abzulehnen? Stimmt etwas nicht? Willst du dich nach vorne bringen?
Ypnos
@ypnos, ich habe deine Antwort überhaupt nicht abgelehnt. Ich habe nur kommentiert, um zu sagen, dass zufällige Down-Wähler Sie nicht unterkriegen sollen. Sie haben 30 Wiederholungen gewonnen und nur 1 verloren. Auch +1;)
mmcdole
1
Mehrere Gründe für eine Ablehnung. 1) Es ist bekannt, dass es einen Algorithmus zum Lösen des Spiels gibt. Es ist nur unpraktisch, den Algorithmus unter Verwendung einer denkbaren Technologie zu berechnen. 2) Das Lösen des Spiels bedeutet NICHT, dass es eine ausfallsichere Strategie gibt. Tic-Tac-Toe ist gelöst, aber es gibt keine Strategie für den zweiten Spieler, die einen Verlust vermeidet.
DJClayworth
2
"Hier geht es nicht um Computer, sondern nur um das Schachspiel." In der Informatik geht es eigentlich nicht um Computer. Sie sind nur ein Werkzeug. Die Informatik arbeitet ohne Computer.
Janus Troelsen
1
Es ist eigentlich eine Frage über Computer, da die Frage ist, ob eine Turing-Maschine (= Computer) existieren könnte, die Schach löst.
SDwarfs
14

Ich komme sehr spät zu diesem Thread und dass Sie einige der Probleme bereits erkannt haben. Aber als Ex-Meister und Ex-Profi-Schachprogrammierer dachte ich, ich könnte ein paar nützliche Fakten und Zahlen hinzufügen. Es gibt verschiedene Möglichkeiten, die Komplexität des Schachs zu messen :

  • Die Gesamtzahl der Schachpartien beträgt ungefähr 10 ^ (10 ^ 50). Diese Zahl ist unvorstellbar groß.
  • Die Anzahl der Schachpartien mit 40 Zügen oder weniger liegt bei 10 ^ 40. Das ist immer noch eine unglaublich große Zahl.
  • Die Anzahl der möglichen Schachpositionen liegt bei 10 ^ 46.
  • Der vollständige Schach-Suchbaum (Shannon-Nummer) liegt bei 10 ^ 123, basierend auf einem durchschnittlichen Verzweigungsfaktor von 35 und einer durchschnittlichen Spieldauer von 80.
  • Zum Vergleich wird die Anzahl der Atome im beobachtbaren Universum üblicherweise auf etwa 10 ^ 80 geschätzt.
  • Alle Endspiele mit 6 oder weniger Teilen wurden zusammengestellt und gelöst .

Mein Fazit: Während Schach theoretisch lösbar ist, werden wir niemals das Geld, die Motivation, die Rechenleistung oder den Speicher haben, um es jemals zu tun.

HTTP 410
quelle
3
Komm schon. Sie müssen das Problem anders sehen. Denken Sie nicht an die Anzahl der Spiele, denn Transpositionen und Alpha-Beta-Algorithmen und solche reduzieren das immens. Denken Sie an Brettpositionen (10 ^ 60) oder Kombinationen von Schachfiguren (100 Millionen). Mit Quantum Computing ist das trivial.
lkessler
2
Alpha-Beta in diesem Zusammenhang (Schach lösen) würde eine perfekte Bewertungsfunktion erfordern. So auch Brettpositionen und Stückkombinationen. Wir haben keine perfekte Bewertungsfunktion, daher hilft uns das Quantencomputing nicht.
HTTP 410
1
Immer wenn ich denke, dass etwas "trivial" ist und ich sicher bin, dass es noch niemand getan hat, bin ich mir auch sicher, dass ich mich mindestens einmal geirrt habe.
Dean J
2
@lkessler: Vorstandspositionen erzählen nicht die ganze Geschichte. Zumindest ein Teil des Spielverlaufs ist erforderlich, um zu erobern oder en passant zu erobern oder zu ziehen, da es an Eroberung oder Bauernbewegung mangelt, und der gesamte Verlauf, um durch Wiederholung gezogen zu werden. Da es kürzlich ein bemerkenswertes Forschungsergebnis für einen Quantencomputer war, Faktor 15 zu erreichen, würde ich sagen, dass Quantencomputer derzeit nichts Triviales sind.
David Thornley
2
Zum Vergleich: Wenn Sie hier alle möglichen Schachpositionen generieren können, können Sie jede Verschlüsselung mit einem 128-Bit-Schlüssel trivial brutal erzwingen, da 10 ^ 46 ungefähr 2 ^ 152 oder 2 ^ 153 ist. Es gibt gute Gründe zu der Annahme, dass dies vor dem Hitzetod des Universums unmöglich ist.
David Thornley
9

Einige Spiele wurden tatsächlich gelöst. Tic-Tac-Toe ist sehr einfach, um eine KI zu bauen, die immer gewinnt oder unentschieden spielt. Vor kurzem wurde auch Connect 4 gelöst (und es hat sich gezeigt, dass es dem zweiten Spieler gegenüber unfair ist, da ein perfektes Spiel dazu führt, dass er verliert).

Schach wurde jedoch nicht gelöst, und ich glaube, es gibt keinen Beweis dafür, dass es sich um ein faires Spiel handelt (dh ob das perfekte Spiel zu einem Unentschieden führt). Aus theoretischer Sicht hat Schach eine begrenzte Anzahl möglicher Stückkonfigurationen. Daher ist der Suchraum endlich (wenn auch unglaublich groß). Daher gibt es eine deterministische Turing-Maschine, die perfekt spielen könnte. Ob man jemals gebaut werden könnte, ist eine andere Sache.

Cybis
quelle
8

Der durchschnittliche 1000-Dollar-Desktop kann bis zum Jahr 2040 Checkers in nur 5 Sekunden lösen (5x10 ^ 20 Berechnungen).

Selbst bei dieser Geschwindigkeit würden 100 dieser Computer ungefähr 6,34 x 10 ^ 19 Jahre brauchen , um Schach zu lösen. Immer noch nicht machbar. Nicht annähernd.

Um 2080 werden unsere durchschnittlichen Desktops ungefähr 10 ^ 45 Berechnungen pro Sekunde haben. Ein einzelner Computer verfügt über die Rechenleistung, um Schach in etwa 27,7 Stunden zu lösen. Es wird definitiv bis 2080 fertig sein, solange die Rechenleistung weiter wächst wie in den letzten 30 Jahren.

Bis 2090 wird auf einem 1000-Dollar-Desktop genügend Rechenleistung vorhanden sein, um Schach in etwa 1 Sekunde zu lösen. Bis zu diesem Datum wird dies also völlig trivial sein.

Angesichts der Tatsache, dass die Kontrolleure 2007 gelöst wurden und die Rechenleistung, um sie in 1 Sekunde zu lösen, um etwa 33 bis 35 Jahre zurückbleiben wird, können wir wahrscheinlich grob schätzen, dass Schach irgendwo zwischen 2055 und 2057 gelöst wird. Wahrscheinlich früher, wenn mehr Rechenleistung verfügbar ist (was in 45 Jahren der Fall sein wird), kann mehr für solche Projekte aufgewendet werden. Ich würde jedoch frühestens 2050 und spätestens 2060 sagen.

Im Jahr 2060 würde es 100 durchschnittliche Desktops 3,17 x 10 ^ 10 Jahre dauern, um Schach zu lösen. Stellen Sie fest, dass ich einen 1000-Dollar-Computer als Benchmark verwende, während größere Systeme und Supercomputer wahrscheinlich verfügbar sein werden, da sich auch das Preis-Leistungs-Verhältnis verbessert. Außerdem nimmt ihre Größenordnung der Rechenleistung schneller zu. Stellen Sie sich vor, ein Supercomputer kann jetzt 2,33 x 10 ^ 15 Berechnungen pro Sekunde und ein 1000-Dollar-Computer etwa 2 x 10 ^ 9 ausführen. Zum Vergleich: Vor 10 Jahren betrug der Unterschied 10 ^ 5 statt 10 ^ 6. Bis 2060 wird der Unterschied in der Größenordnung wahrscheinlich 10 ^ 12 betragen, und selbst dieser kann schneller als erwartet zunehmen.

Vieles davon hängt davon ab, ob wir als Menschen den Antrieb haben, Schach zu lösen, oder nicht, aber die Rechenleistung wird es um diese Zeit möglich machen (solange unser Tempo anhält).

Außerdem hat das viel einfachere Spiel Tic-Tac-Toe 2.653.002 mögliche Berechnungen (mit offenem Brett). Die Rechenleistung zur Lösung von Tic-Tac-Toe in ungefähr 2,5 (1 Million Berechnungen pro Sekunde) Sekunden wurde 1990 erreicht.

Im Jahr 1955 hatte ein Computer die Fähigkeit, Tic-Tac-Toe in etwa einem Monat zu lösen (1 Berechnung pro Sekunde). Dies basiert wiederum auf den 1000 US-Dollar, die Sie erhalten würden, wenn Sie sie in einen Computer packen könnten (ein 1000-Dollar-Desktop gab es 1955 offensichtlich nicht), und dieser Computer wäre der Lösung von Tic-Tac-Toe gewidmet gewesen Dies war 1955 einfach nicht der Fall. Die Berechnung war teuer und wurde nicht für diesen Zweck verwendet, obwohl ich nicht glaube, dass es ein Datum gibt, an dem Tic-Tac-Toe von einem Computer als "gelöst" eingestuft wurde, aber ich bin es sicher, dass es hinter der tatsächlichen Rechenleistung zurückbleibt.

Berücksichtigen Sie außerdem, dass 1000 US-Dollar in 45 Jahren etwa viermal weniger wert sind als jetzt, sodass viel mehr Geld in Projekte wie dieses fließen kann, während die Rechenleistung weiterhin billiger wird.

Frank
quelle
9
"Wussten Sie, dass die Verkäufe von Disco-Rekorden zum Jahresende 1976 um 400% gestiegen sind? Wenn sich diese Trends fortsetzen ... AAY!" - Disco Stu
Jeremy Friesner
2
Moores Gesetz - die Rechenleistung verdoppelt sich alle 18 Monate - wird voraussichtlich um 2015 scheitern. Andernfalls muss das Design des Computerprozessors radikal anders sein. 2080 ist also kein realistisches Ziel.
Philip Smith
3
@Philip: Die Prozessortaktraten von Desktop-Computern sind seit 2003 nur geringfügig gestiegen, und die Verbesserungen seitdem wurden hauptsächlich durch Cache und mehrere Kerne erhöht. Da ein 3-GHz-Prozessor einen Taktzyklus in der Zeit hat, die Licht benötigt, um sich 10 cm zu bewegen, kann nicht erwartet werden, dass die Taktrate auf unbestimmte Zeit ansteigt. Darüber hinaus ist Parallelität typischerweise schwierig. Eine exponentielle Zunahme für fünfzig Jahre zu prognostizieren, als sie vor sieben Jahren zusammenbrach, scheint keine sichere Sache zu sein.
David Thornley
1
@ David - das ist alles wahr. Aber verfehlt den Punkt. Wenn Sie die Hälfte der Komponenten auf dem Chip haben, werden die Elektronen bei gleicher Taktrate doppelt so viel erledigt. Dies ist es, was Moores Gesetz antreibt.
Philip Smith
3
@Philip: Die Halbierung kann natürlich nicht ewig dauern. Ein Siliziumatom hat einen Durchmesser von etwa einem Viertel Nanometer, und die Herstellung von Chips ist bereits auf zehn Nanometer beschränkt. Darüber hinaus gehorchen Teilchen auf Quantenebene statistischen Regeln, nicht absoluten Regeln, so dass es notwendig ist, sich gleichzeitig um genügend Elektronen zu bewegen, um das Gesetz der großen Zahlen aufzurufen. Bisher lag Moores Gesetz irgendwo zwischen einem Gesetz und einer sich selbst erfüllenden Prophezeiung, aber das endet irgendwann ziemlich bald.
David Thornley
7

Es ist tatsächlich möglich, dass beide Spieler Gewinnstrategien in unendlichen Spielen ohne gute Reihenfolge haben. Schach ist jedoch gut geordnet. In der Tat gibt es aufgrund der 50-Züge-Regel eine Obergrenze für die Anzahl der Züge, die ein Spiel haben kann, und daher gibt es nur endlich viele mögliche Schachspiele (die aufgezählt werden können, um genau zu lösen .. theoretisch, wenigstens :)

BlueRaja - Danny Pflughoeft
quelle
4
Technisch gesehen führt die Fünfzig-Züge-Regel, wie die Drei-Züge-Wiederholung (die auch die Dinge einschränkt - es gibt eine endliche Anzahl möglicher Positionen, so dass das Multiplizieren dieser Zahl mit drei eine Obergrenze ergibt) nicht zu einem Unentschieden. Vielmehr gibt es jedem Spieler die Möglichkeit, ein Unentschieden zu fordern . Normalerweise wird der verlierende Spieler dies tun, aber es ist nicht erforderlich. Daher ist das Folgende ein völlig legales Spiel: 1. Sc3 Sc6 2. Sc1 Sb8 3. Sc3 Sc6 4. Sc1 Sb8, für immer wiederholt. Und wenn ich mich nicht irre, wurde nicht widerlegt, dass dies nicht das Ergebnis von zwei perfekten Algorithmen ist, die als Weiß und Schwarz spielen.
Lenoxus
6

Ihr Ende des Arguments wird durch die Art und Weise unterstützt, wie moderne Schachprogramme jetzt funktionieren . Sie arbeiten so, weil es viel zu ressourcenintensiv ist, ein Schachprogramm zu codieren, um deterministisch zu arbeiten. Sie werden nicht unbedingt immer so funktionieren. Es ist möglich, dass Schach eines Tages gelöst wird , und wenn dies passiert, wird es wahrscheinlich von einem Computer gelöst.

Bill die Eidechse
quelle
5

Für die Aufzeichnung gibt es Computer, die bei Dame gewinnen oder binden können . Ich bin mir nicht sicher, ob das auch für Schach möglich ist. Die Anzahl der Züge ist viel höher. Außerdem ändern sich die Dinge, weil sich Teile in jede Richtung bewegen können, nicht nur vorwärts und rückwärts. Ich denke, obwohl ich nicht sicher bin, dass Schach deterministisch ist, aber dass es einfach zu viele mögliche Züge gibt, als dass ein Computer derzeit alle Züge in angemessener Zeit bestimmen könnte.

Kibbee
quelle
1
Es kann gemacht werden, aber kann es auf einem Computer gemacht werden, den wir wahrscheinlich jemals sehen werden?
BCS
1
Wahrscheinlich nicht in unserem Leben. Alle wirklich interessanten Forschungen auf diesem Gebiet werden im Spiel Go durchgeführt. :)
Bill the Lizard
IIRC die meisten 6-Jährigen können jeden Computer bei Go sein.
BCS
2
@BCS: Nicht mehr. Die besten Go-Programme schlagen jetzt Dan (professionelle) Level-Spieler.
Bill the Lizard
1
@BlueRaja: Das war im Jahr 2008. Ich weiß nicht, was der aktuelle Rekord ist, aber MoGo hat Profis mit 6 und 7 Steinen auf einem 19x19 geschlagen. ireport.cnn.com/docs/DOC-214010
Bill the Lizard
5

Ich denke du bist tot auf. Maschinen wie Deep Blue und Deep Thought sind mit einer Reihe vordefinierter Spiele und cleveren Algorithmen programmiert, um die Bäume bis zum Ende dieser Spiele zu analysieren. Dies ist natürlich eine dramatische Vereinfachung. Es besteht immer die Möglichkeit, den Computer im Laufe eines Spiels zu "schlagen". Damit meine ich eine Bewegung, die den Computer dazu zwingt, eine Bewegung auszuführen, die nicht optimal ist (was auch immer das ist). Wenn der Computer vor dem Zeitlimit für den Umzug nicht den besten Pfad finden kann, kann er einen Fehler machen, indem er einen der weniger wünschenswerten Pfade wählt.

Es gibt eine andere Klasse von Schachprogrammen, die echtes maschinelles Lernen oder genetische Programmier- / Evolutionsalgorithmen verwenden. Einige Programme wurden entwickelt und verwenden neuronale Netze, um Entscheidungen zu treffen. In einem solchen Fall würde ich mir vorstellen, dass der Computer "Fehler" macht, aber dennoch einen Sieg erringt.

Es gibt ein faszinierendes Buch über diese Art von GP namens Blondie24 , das Sie vielleicht lesen werden. Es geht um Dame, aber es könnte für Schach gelten.

Jason Jackson
quelle
So schlagen Sie die heutigen Computer beim Schach. Morgen wird es besser. Ich stimme Ihnen jedoch zu, dass Blondie24 faszinierend ist.
Bill the Lizard
Wieder abgestimmt. Dieser Beitrag verdient keine negative Bewertung.
Cybis
Leider ist das Schachspielproblem zu groß, als dass maschinelles Lernen funktionieren könnte. Sie könnten niemals ein Lernschachprogramm bekommen, um auch ohne Fehler neu zu spielen. Heuristiken sind besser. Aber Brute Force war noch besser. Das Gebiet des maschinellen Lernens lernte nur aus seinem Scheitern beim Schach.
lkessler
Schachprogramme machen keine kurzfristigen Fehler, und die besten Programme spielen besser als Weltmeister. Ich denke, die neueste Version von Rybka 64-Bit ist wie 3200 ELO
Alex
5

Aus der Spieltheorie, um die es in dieser Frage geht, lautet die Antwort: Ja, Schach kann perfekt gespielt werden. Der Spielraum ist bekannt / vorhersehbar und ja, wenn Sie die Quantencomputer Ihres Enkels hätten, könnten Sie wahrscheinlich alle Heuristiken eliminieren.

Sie können heutzutage eine perfekte Tic-Tac-Toe-Maschine in jeder Skriptsprache schreiben, die sich in Echtzeit perfekt abspielen lässt.

Othello ist ein weiteres Spiel, das aktuelle Computer problemlos perfekt spielen können, aber der Speicher und die CPU des Computers benötigen ein wenig Hilfe

Schach ist theoretisch möglich, aber praktisch nicht möglich (2008)

i-Go ist knifflig, der Raum der Möglichkeiten geht über die Anzahl der Atome im Universum hinaus, sodass wir möglicherweise einige Zeit brauchen, um eine perfekte i-Go-Maschine herzustellen.

Robert Gould
quelle
Dies ist keine Spieltheorie
BlueRaja - Danny Pflughoeft
4
Technisch gesehen ist es eine kombinatorische Spieltheorie.
Anaphory
5

Schach ist ein Beispiel für ein Matrixspiel, das per Definition ein optimales Ergebnis erzielt (denken Sie an das Nash-Gleichgewicht). Wenn Spieler 1 und 2 jeweils optimale Züge ausführen, wird IMMER ein bestimmtes Ergebnis erzielt (ob es sich um einen Gewinn-Verlust-Verlust handelt, ist noch nicht bekannt).

Jon Smock
quelle
5

Als Schachprogrammierer aus den 1970er Jahren habe ich definitiv eine Meinung dazu. Was ich vor ungefähr 10 Jahren geschrieben habe, ist heute noch im Grunde wahr:

"Unvollendete Arbeit und Herausforderungen für Schachprogrammierer"

Damals dachte ich, wir könnten Schach konventionell lösen, wenn es richtig gemacht würde.

Checkers wurde kürzlich gelöst (Yay, Universität von Alberta, Kanada !!!), aber das wurde effektiv Brute Force getan. Um konventionell Schach zu spielen, muss man schlauer sein.

Es sei denn natürlich, Quantum Computing wird Realität. In diesem Fall ist Schach genauso einfach zu lösen wie Tic-Tac-Toe.

In den frühen 1970er Jahren gab es in Scientific American eine kurze Parodie, die meine Aufmerksamkeit auf sich zog. Es war eine Ankündigung, dass das Schachspiel von einem russischen Schachcomputer gelöst wurde. Es wurde festgestellt, dass es einen perfekten Zug für Weiß gibt, der einen Sieg mit perfektem Spiel beider Seiten garantiert, und dieser Zug lautet: 1. a4!

lkessler
quelle
3

Viele Antworten hier machen die wichtigen spieltheoretischen Punkte:

  1. Schach ist ein endliches, deterministisches Spiel mit vollständigen Informationen über den Spielstatus
  2. Sie können ein endliches Spiel lösen und eine perfekte Strategie identifizieren
  3. Schach ist jedoch groß genug, dass Sie es mit einer Brute-Force-Methode nicht vollständig lösen können

Diese Beobachtungen übersehen jedoch einen wichtigen praktischen Punkt: Es ist nicht notwendig, das gesamte Spiel perfekt zu lösen, um eine unschlagbare Maschine zu schaffen .

Es ist in der Tat sehr wahrscheinlich, dass Sie eine unschlagbare Schachmaschine schaffen könnten (dh niemals verlieren und immer einen Gewinn oder ein Unentschieden erzwingen), ohne auch nur einen winzigen Bruchteil des möglichen Zustandsraums zu durchsuchen.

Die folgenden Techniken reduzieren beispielsweise den erforderlichen Suchraum massiv:

  • Baumschnitttechniken wie Alpha / Beta oder MTD-f reduzieren den Suchraum bereits massiv
  • Nachweisbare Gewinnposition. Viele Endungen fallen in diese Kategorie: Sie müssen beispielsweise nicht nach KR gegen K suchen, es ist ein bewährter Gewinn. Mit etwas Arbeit ist es möglich, viel mehr garantierte Siege zu beweisen.
  • Fast sichere Siege - für ein "gut genug" Spiel ohne dumme Fehler (etwa ELO 2200+?) Sind viele Schachpositionen fast sichere Gewinne, zum Beispiel ein anständiger materieller Vorteil (z. B. ein zusätzlicher Ritter) ohne kompensierenden Positionsvorteil. Wenn Ihr Programm eine solche Position erzwingen kann und über genügend Heuristiken verfügt, um Positionsvorteile zu erkennen, kann es davon ausgehen, dass es mit einer Wahrscheinlichkeit von 100% gewinnt oder zumindest unentschieden spielt.
  • Heuristiken für die Baumsuche - Mit einer ausreichend guten Mustererkennung können Sie sich schnell auf die relevante Teilmenge der "interessanten" Bewegungen konzentrieren. So spielen menschliche Großmeister, es ist also eindeutig keine schlechte Strategie ... und unsere Mustererkennungsalgorithmen werden ständig besser
  • Risikobewertung - Eine bessere Vorstellung von der "Risikobereitschaft" einer Position ermöglicht eine wesentlich effektivere Suche, indem die Rechenleistung auf Situationen konzentriert wird, in denen das Ergebnis ungewisser ist (dies ist eine natürliche Erweiterung der Ruhesuche ).

Mit der richtigen Kombination der oben genannten Techniken würde ich gerne behaupten, dass es möglich ist, eine "unschlagbare" Schachspielmaschine zu schaffen. Mit der aktuellen Technologie sind wir wahrscheinlich nicht allzu weit weg.

Beachten Sie, dass es mit ziemlicher Sicherheit schwieriger ist zu beweisen, dass diese Maschine nicht zu schlagen ist. Es wäre wahrscheinlich so etwas wie die Reimann-Hypothese - wir wären ziemlich sicher, dass es perfekt spielt und empirische Ergebnisse hätten, die zeigen, dass es nie verloren hat (einschließlich einiger Milliarden Straight Draws gegen sich selbst), aber wir hätten tatsächlich nicht die Fähigkeit dazu Beweise es.

Zusätzlicher Hinweis zu "Perfektion":

Ich achte darauf, die Maschine nicht als "perfekt" im spieltheoretischen Sinne zu bezeichnen, da dies ungewöhnlich starke zusätzliche Bedingungen impliziert, wie zum Beispiel:

  • Immer gewinnen in jeder Situation, in der es möglich ist, einen Sieg zu erzwingen, egal wie komplex die Gewinnkombination sein mag. Es wird Situationen an der Grenze zwischen Gewinn / Unentschieden geben, in denen es äußerst schwierig ist, dies perfekt zu berechnen.
  • Nutzen Sie alle verfügbaren Informationen über mögliche Unvollkommenheiten im Spiel Ihres Gegners, um daraus zu schließen, dass Ihr Gegner möglicherweise zu gierig ist und absichtlich eine etwas schwächere Linie als gewöhnlich spielt, da dies ein größeres Potenzial hat, Ihren Gegner zu einem Fehler zu verleiten. Gegen unvollkommene Gegner kann es in der Tat optimal sein, eine Niederlage zu machen , wenn Sie schätzen, dass Ihr Gegner den erzwungenen Sieg wahrscheinlich nicht erkennt und Sie dadurch eine höhere Wahrscheinlichkeit haben, selbst zu gewinnen.

Perfektion (insbesondere bei unvollkommenen und unbekannten Gegnern) ist ein viel schwierigeres Problem als einfach unschlagbar zu sein.

mikera
quelle
Unvollkommene Gegner zu haben ist kein wirkliches Problem. Dadurch gewinnt / zieht der perfekte Spieler (was auch immer das perfekte Ergebnis ist) in weniger Zügen. Eine optimale Bewegung in jeder Position ist immer besser oder gleich den anderen möglichen Bewegungen (per Definition). Ein suboptimaler Zug ermöglicht es Ihrem Gegner, früher einen optimalen Endzustand (Gewinn / Unentschieden) zu erreichen oder sogar ein besseres Ergebnis zu erzwingen. Wenn beispielsweise Schwarz immer verlieren würde, wenn Weiß perfekt spielt, ist es möglich, dass Schwarz gewinnt, wenn Weiß nur einen einzigen suboptimalen Zug spielt. Aber ja, dies sollte die Komplexität der Analyse etwas erhöhen.
SDwarfs
@Stefan - unvollkommene Gegner sind ein großes Problem, wenn Sie sich für ein optimales Spiel interessieren . Insbesondere können Sie sich Situationen vorstellen, in denen es tatsächlich vorzuziehen ist, einen verlorenen Zug zu spielen (dh einen Zug, bei dem ein perfekter Gegner Sie definitiv schlagen würde), wenn Sie wissen, dass die Wahrscheinlichkeit, dass Ihr Gegner einen Fehler macht, ausreichend hoch ist.
Mikera
Ein optimales Spiel bedeutet meiner Meinung nach, das bestmögliche Ergebnis ohne Risiko zu erzielen. Ihr Gegner ist wahrscheinlich "schwach", aber wenn Sie diesen verlorenen Zug spielen, kann er / sie leider versehentlich einen guten Zug spielen. Die Sorge um suboptimale Gegner ist nur relevant, wenn nur die Wahl zwischen verlorenen Zügen besteht, bei denen einer von ihnen eine höhere Wahrscheinlichkeit für einen Fehler des (suboptimal spielenden) Gegners hat, der tatsächlich zu einem Unentschieden oder Gewinn führt.
SDwarfs
1
Das ist nicht die übliche Definition von optimal in der Spieltheorie. Optimal bedeutet normalerweise, das erwartete Ergebnis zu maximieren . In diesem Fall geht ein optimaler Spieler ein gewisses Risiko ein, sofern er im Durchschnitt ein besseres Ergebnis erzielt .
Mikera
In diesem Fall haben Sie vollkommen recht!
SDwarfs
2

Wenn Sie den gesamten Bereich aller Kombinationen von Spieler-1/2-Zügen durchsuchen, basiert der einzelne Zug, über den der Computer bei jedem Schritt entscheidet, auf einer Heuristik.

Dort gibt es zwei konkurrierende Ideen. Zum einen suchen Sie jede mögliche Bewegung, zum anderen entscheiden Sie sich anhand einer Heuristik. Eine Heuristik ist ein System, um eine gute Vermutung anzustellen. Wenn Sie jede mögliche Bewegung durchsuchen, raten Sie nicht mehr.

Joel Coehoorn
quelle
Eigentlich ist das Zitat richtig. Programme untersuchen alle möglichen Bewegungen für beide Seiten in der aktuellen Position und verwenden Heuristiken, um eine gute Bewegung zu finden, um das Spiel in Richtung einer für den Computer günstigen Position zu steuern.
Bill the Lizard
1
Nein, sie sehen sich nicht alle möglichen Bewegungen an. Sie verwenden eine Null-Move-Heuristik, um den Baum zu beschneiden.
Alex
2

"Gibt es einen perfekten Algorithmus für Schach?"

Ja da ist. Vielleicht muss Weiß immer gewinnen. Vielleicht muss Schwarz immer gewinnen. Vielleicht ist es für beide immer mindestens zu binden. Wir wissen nicht welche, und wir werden es nie erfahren, aber es existiert auf jeden Fall.

Siehe auch

Polygenschmierstoffe
quelle
1
Als ziemlich anständiger Schachspieler und nachdem ich das Problem im Laufe der Jahre ausgiebig untersucht habe, bin ich mir zu 99,9% sicher, dass die Präfektenstrategie im Schach für beide Spieler zu einem Unentschieden führt (wie es bei Dame bewiesen wurde). Es gibt auch Hinweise darauf, dass mit zunehmender Stärke des Spielers auch der Prozentsatz der Unentschieden zunimmt.
Mikera
2

Ich fand diesen Artikel von John MacQuarrie , der auf Arbeiten des "Vaters der Spieltheorie" Ernst Friedrich Ferdinand Zermelo verweist . Es zieht die folgende Schlussfolgerung:

Im Schach kann entweder Weiß einen Sieg erzwingen oder Schwarz kann einen Sieg erzwingen, oder beide Seiten können mindestens ein Unentschieden erzwingen.

Die Logik scheint mir vernünftig.

Ben Gartner
quelle
2

Es ist perfekt lösbar.

Es gibt 10 ^ 50 ungerade Positionen. Nach meiner Einschätzung erfordert jede Position mindestens 64 runde Bytes zum Speichern (jedes Quadrat hat: 2 Zugehörigkeitsbits, 3 Stückbits). Sobald sie zusammengestellt sind, können die Positionen, die Schachmatt sind, identifiziert und Positionen verglichen werden, um eine Beziehung zu bilden, die zeigt, welche Positionen zu anderen Positionen in einem großen Ergebnisbaum führen.

Dann muss das Programm nur die niedrigsten nur eine Seite Schachmattwurzeln finden, wenn so etwas existiert. In jedem Fall wurde Schach am Ende des ersten Absatzes ziemlich einfach gelöst.

Solomon
quelle
1

Ich bin nur zu 99,9% von der Behauptung überzeugt, dass die Größe des Staatsraums es unmöglich macht, auf eine Lösung zu hoffen.

Sicher, 10 ^ 50 ist eine unglaublich große Zahl. Nennen wir die Größe des Zustandsraums n.

Wie hoch ist die Anzahl der Züge im längsten Spiel? Da alle Spiele mit einer endlichen Anzahl von Zügen enden, gibt es eine solche Grenze, nennen Sie es m.

Können Sie ausgehend vom Ausgangszustand nicht alle n Bewegungen im O (m) -Raum aufzählen? Sicher, es dauert O (n) Zeit, aber die Argumente aus der Größe des Universums sprechen das nicht direkt an. O (m) Raum könnte nicht einmal sehr viel sein. Könnten Sie für O (m) -Raum während dieser Durchquerung nicht auch verfolgen, ob die Fortsetzung eines Zustands entlang des von Ihnen durchquerten Pfades zu EntwederMayWin, EntwederMayForceDraw, WhiteMayWin, WhiteMayWinOrForceDraw, BlackMayWin oder BlackMayWinOrForceDraw führt? (Es gibt ein Gitter, je nachdem, wer an der Reihe ist. Kommentieren Sie jeden Zustand in der Geschichte Ihrer Durchquerung mit dem Gittertreffen.)

Wenn mir nichts fehlt, ist dies ein O (n) Zeit / O (m) Raum-Algorithmus, um zu bestimmen, in welche der möglichen Kategorien Schach fällt. Wikipedia zitiert eine Schätzung für das Alter des Universums zu ungefähr 10 ^ 60. Planck-Zeiten. Lassen Sie uns raten, dass vor der Hitze / Kälte / dem Tod des Universums noch so viel Zeit verbleibt, ohne auf ein kosmologisches Argument einzugehen. Daher müssen wir alle 10 bis 10 Planck-Zeiten oder alle 10 bis 34 Sekunden einen Zug auswerten. Das ist eine unglaublich kurze Zeit (ungefähr 16 Größenordnungen kürzer als die kürzesten jemals beobachteten Zeiten). Lassen Sie uns optimistisch sagen, dass wir mit einer Super-Duper-Good-Implementierung, die über der Linie der gegenwärtigen oder vorausgesehenen Nicht-Quanten-P-ist-eine-richtige-Teilmenge der NP-Technologie läuft, hoffen könnten, sie zu bewerten (nehmen Sie eine Einzelschritt vorwärts, Kategorisieren Sie den resultierenden Zustand als Zwischenzustand oder als einen der drei Endzustände mit einer Rate von 100 MHz (einmal alle 10 ^ -8 Sekunden). Da dieser Algorithmus sehr parallelisierbar ist, benötigen wir für jedes Atom in meinem Körper 10 bis 26 solcher Computer oder etwa einen, zusammen mit der Fähigkeit, ihre Ergebnisse zu sammeln.

Ich nehme an, es gibt immer einen Hoffnungsschimmer für eine Brute-Force-Lösung. Wir könnten Glück haben und wenn wir nur einen der möglichen Eröffnungszüge von Weiß untersuchen, wählen beide einen mit einem unterdurchschnittlichen Fanout und einen, bei dem Weiß immer gewinnt oder gewinnt oder unentschieden spielt.

Wir könnten auch hoffen, die Definition von Schach etwas zu verkleinern und alle davon zu überzeugen, dass es moralisch immer noch dasselbe Spiel ist. Müssen wir wirklich Positionen benötigen, die vor einem Unentschieden dreimal wiederholt werden müssen? Müssen wir die weglaufende Gruppe wirklich dazu bringen, die Fähigkeit zu demonstrieren, für 50 Züge zu fliehen? Versteht jemand überhaupt, was zum Teufel mit der En-Passant- Regel los ist? ;) Im Ernst, müssen wir einen Spieler wirklich zwingen, sich zu bewegen (im Gegensatz zum Ziehen oder Verlieren), wenn sein einziger Zug nur der Kontrolle entgeht oder eine Pattsituation eine en passant Gefangennahme ist? Könnten wir die Auswahl der Teile einschränken, auf die ein Bauer befördert werden kann, wenn die gewünschte Beförderung ohne Königin nicht zu einem sofortigen Scheck oder Schachmatt führt?

Ich bin mir auch nicht sicher, inwieweit das Zulassen eines Hash-basierten Zugriffs auf eine große Datenbank mit späten Spielzuständen und deren möglichen Ergebnissen (die auf vorhandener Hardware und mit vorhandenen Endspieldatenbanken relativ machbar sein könnten) dazu beitragen könnte, die Suche früher zu bereinigen. Natürlich können Sie sich nicht die gesamte Funktion ohne O (n) -Speicher merken, aber Sie könnten eine große Ganzzahl auswählen und sich so viele Endspiele merken, die von jedem möglichen (oder sogar nicht leicht nachweisbar unmöglichen) Endzustand rückwärts aufgezählt werden.

Doug McClean
quelle
1
Ihr m = 5898. Die FIDE-Schachregeln definieren, dass Sie mindestens alle 50 Züge (die als 50-Züge-Regel bezeichnet werden) einen Bauern bewegen oder eine Figur nehmen müssen (etwas, das das Spiel irreversibel verändert), oder einer der Spieler kann ein Unentschieden beanspruchen. Es wurde berechnet, dass das längste Spiel 5898 Züge lang ist, wenn beide Spieler zusammenarbeiten und so schnell wie möglich ein Unentschieden fordern. Es macht keinen Sinn, weiterzuspielen, wenn beide Spieler ein Unentschieden fordern können. Wenn ein Spieler bemerkt, dass er verliert, kann er die Auslosung beanspruchen und das gleiche Ergebnis erzielen. Siehe: chess.com/blog/kurtgodden/the-longest-possible-chess-game
SDwarfs
1
Hinweis: m = 5898 ist die Anzahl der "Züge". Die maximale Anzahl von halben Zügen beträgt (118-3) * 100 + 3 * 99 = 11797. Den Beweis finden Sie hier (deutsch!): De.wikipedia.org/wiki/50-Z%C3%BCge-Regel# Schachmathematik
SDwarfs
1

Ich weiß, dass dies eine kleine Beule ist, aber ich muss meine 5 Cent hier reinstecken. Es ist möglich, dass ein Computer oder eine Person jedes einzelne Schachspiel, an dem er / sie / es teilnimmt, entweder in einem Sieg oder in einer Pattsituation beendet.

Um dies zu erreichen, müssen Sie jedoch jede mögliche Bewegung und Reaktion usw. bis hin zu jedem einzelnen möglichen Spielergebnis genau kennen und dies visualisieren oder eine einfache Möglichkeit zur Analyse dieser Informationen finden es als Mind Map, die sich ständig verzweigt.

Der Mittelknoten wäre der Start des Spiels. Jeder Zweig aus jedem Knoten würde eine Bewegung symbolisieren, wobei sich jeder von seinen bretheren Bewegungen unterscheidet. Die Präsentation in diesem Herrenhaus würde viel Ressourcen in Anspruch nehmen, insbesondere wenn Sie dies auf Papier tun würden. Auf einem Computer würde dies möglicherweise Hunderte von Terrabyte an Daten erfordern, da Sie sehr viele Wiederholungsbewegungen ausführen würden, es sei denn, Sie hätten die Zweige zurückgebracht.

Das Speichern solcher Daten wäre jedoch unplausibel, wenn nicht unmöglich. Es wäre möglich, aber nicht plausibel, einen Computer die optimalste Bewegung erkennen zu lassen, um aus den (höchstens) 8 sofort möglichen Bewegungen herauszukommen. Da dieser Computer in der Lage sein müsste, alle Zweige nach dieser Bewegung zu verarbeiten, Zählen Sie bis zu einer Schlussfolgerung alle Schlussfolgerungen, die zu einem Sieg oder einer Pattsituation führen, und reagieren Sie dann auf diese Anzahl von Gewinn-Schlussfolgerungen, um Schlussfolgerungen zu verlieren. Dies würde RAM erfordern, das Daten in den Terrabytes oder mehr verarbeiten kann! Und mit der heutigen Technologie würde ein solcher Computer mehr als das Bankguthaben der 5 reichsten Männer und / oder Frauen der Welt erfordern!

Nach all diesen Überlegungen konnte es also getan werden, aber niemand konnte es tun. Eine solche Aufgabe würde 30 der klügsten Köpfe erfordern, die heute leben, nicht nur im Schach, sondern auch in der Wissenschaft und Computertechnologie, und eine solche Aufgabe könnte nur auf einer (lassen Sie es uns ganz in die grundlegende Perspektive bringen) ... extrem letztendlich hyper erledigt werden Super-Duper-Computer ... der möglicherweise seit mindestens einem Jahrhundert nicht mehr existieren könnte. Es wird gemacht! Nur nicht in diesem Leben.

MrDeeJayy
quelle
1

In Ihrem Gedankenexperiment gibt es zwei Fehler:

  1. Wenn Ihre Turing-Maschine nicht "begrenzt" ist (Speicher, Geschwindigkeit, ...), müssen Sie keine Heuristiken verwenden, aber Sie können die Endzustände (Gewinn, Verlust, Unentschieden) berechnen. Um das perfekte Spiel zu finden, müssten Sie nur den Minimax-Algorithmus (siehe http://en.wikipedia.org/wiki/Minimax ) verwenden, um die optimalen Züge für jeden Spieler zu berechnen, was zu einem oder mehreren optimalen Spielen führen würde.

  2. Der Komplexität der verwendeten Heuristik sind ebenfalls keine Grenzen gesetzt. Wenn Sie ein perfektes Spiel berechnen können, gibt es auch eine Möglichkeit, daraus eine perfekte Heuristik zu berechnen. Bei Bedarf ist es nur eine Funktion, die Schachpositionen wie folgt abbildet: "Wenn ich in dieser Situation bin, ist mein bester Zug M".

Wie andere bereits betont haben, wird dies zu drei möglichen Ergebnissen führen: Weiß kann einen Sieg erzwingen, Schwarz kann einen Sieg erzwingen, einer von ihnen kann ein Unentschieden erzwingen.

Das Ergebnis eines perfekten Dame-Spiels wurde bereits "berechnet". Wenn sich die Menschheit vorher nicht selbst zerstören wird, wird es eines Tages auch eine Berechnung für Schach geben, wenn sich die Computer so weit entwickelt haben, dass sie über genügend Speicher und Geschwindigkeit verfügen. Oder wir haben einige Quantencomputer ... Oder bis jemand (Forscher, Schachexperten, Genie) einige Algorithmen findet, die die Komplexität des Spiels erheblich reduzieren. Um ein Beispiel zu geben: Was ist die Summe aller Zahlen zwischen 1 und 1000? Sie können entweder 1 + 2 + 3 + 4 + 5 ... + 999 + 1000 berechnen oder einfach berechnen: N * (N + 1) / 2 mit N = 1000; Ergebnis = 500500. Stellen Sie sich vor, Sie wissen nichts über diese Formel, Sie wissen nichts über mathematische Induktion, Sie wissen nicht einmal, wie man Zahlen multipliziert oder addiert, ... Also, Es ist möglich, dass es einen derzeit unbekannten Algorithmus gibt, der letztendlich die Komplexität dieses Spiels verringert, und es würde nur 5 Minuten dauern, um den besten Zug mit einem aktuellen Computer zu berechnen. Vielleicht wäre es sogar möglich, es als Mensch mit Stift und Papier einzuschätzen, oder sogar in Ihrem Kopf, wenn Sie etwas mehr Zeit haben.

Die schnelle Antwort lautet also: Wenn die Menschheit lange genug überlebt, ist es nur eine Frage der Zeit!

SDwarfs
quelle
0

Es ist vielleicht lösbar, aber etwas stört mich: Selbst wenn der gesamte Baum durchquert werden könnte, gibt es immer noch keine Möglichkeit, den nächsten Zug des Gegners vorherzusagen. Wir müssen unseren nächsten Zug immer auf den Zustand des Gegners stützen und den "besten" Zug zur Verfügung stellen. Dann machen wir es basierend auf dem nächsten Zustand erneut. Unser optimaler Zug könnte also optimal sein, wenn sich der Gegner auf eine bestimmte Weise bewegt. Für einige Züge des Gegners war unser letzter Zug möglicherweise nicht optimal.

Ich sehe einfach nicht ein, wie es in jedem Schritt zu einem "perfekten" Zug kommen kann.

Damit dies der Fall ist, muss es für jeden Zustand [im aktuellen Spiel] einen Pfad im Baum geben, der zum Sieg führt, unabhängig vom nächsten Zug des Gegners (wie bei Tic-Tac-Toe), und ich habe es schwer Zeit, das herauszufinden.

E Dominique
quelle
5
Der perfekte Zug wird durch die 'Minmax'-Strategie entschieden: Es ist der Zug, der Ihre minimal mögliche Punktzahl maximiert (angesichts aller möglichen Züge, die der Gegner machen könnte). Oder anders ausgedrückt, es wird davon ausgegangen, dass der Gegner auch perfekt spielt.
Nick Johnson
Dies ist jedoch ein interessanter Punkt. Könnte eine Situation entstehen, in der eine Reaktion auf den bestmöglichen Zug Sie benachteiligen würde, wenn Ihr Gegner nicht den bestmöglichen Zug macht? Welche Auswirkungen hat dies?
Nona Urbiz
Ich bin kein Mathematiker und kein sehr guter Schachspieler. Ich nahm auch an, dass theoretisch (sollte der gesamte Spielbaum bekannt sein) die Antwort darauf "Ja" lautet. Bedeutet dies nun, da Sie dieses Problem [die Wahl des anderen Spielers] erwähnen, dass das System möglicherweise unvorhersehbar ist? Gibt es eine Mitte im Spiel, in der der andere Spieler einen Nachteil erzwingen könnte? Ist das ein bisschen wie die Tatsache, dass das Perceptron (Neuronales Netz) 'ODER' und 'UND' lernen kann, aber niemals 'XOR' erfassen kann? Ist Schach ein Beispiel für ein "chaotisches" System? FWIW, IMHO Ich denke, die Antwort scheint an dieser Stelle "keine Ahnung" zu sein.
Monojohnny
@Nona Per Definition wäre dieser Zug der beste Zug. Es gibt keine Annahme.
Piccolbo
@piccolbo: Besser einer der besten Moves. Es gibt Positionen im Schach, an denen mehrere Züge zum gleichen Ergebnis führen (Gewinn, Unentschieden oder Verlust bei der gleichen Anzahl von Zügen).
SDwarfs
0

Mathematisch wurde Schach durch den Minimax-Algorithmus gelöst , der bis in die 1920er Jahre zurückreicht (entweder von Borel oder von Neumann gefunden). Somit kann eine Turingmaschine tatsächlich perfektes Schach spielen.

Die rechnerische Komplexität des Schachs macht es jedoch praktisch unmöglich. Aktuelle Motoren verwenden verschiedene Verbesserungen und Heuristiken. Die heutigen Top-Motoren haben die besten Menschen in Bezug auf die Spielstärke übertroffen, aber aufgrund der von ihnen verwendeten Heuristik spielen sie möglicherweise nicht perfekt, wenn sie unendlich lange Zeit haben (z. B. können Hash-Kollisionen zu falschen Ergebnissen führen).

Die nächsten, die wir derzeit in Bezug auf perfektes Spiel haben, sind Endgame-Tabellen . Die typische Technik, um sie zu erzeugen, heißt retrograde Analyse . Derzeit sind alle Positionen mit bis zu sechs Teilen gelöst.

Philipp Claßen
quelle
-1

Ja , in der Mathematik wird Schach als entschlossenes Spiel klassifiziert, das heißt, es hat einen perfekten Algorithmus für jeden ersten Spieler. Dies gilt nachweislich auch für unendliche Schachbretter. Eines Tages wird wahrscheinlich eine Quanten-KI die perfekte Strategie finden. und das Spiel ist weg

Mehr dazu in diesem Video: https://www.youtube.com/watch?v=PN-I6u-AxMg

Es gibt auch Quantenschach, bei dem es keinen mathematischen Beweis dafür gibt, dass es sich um ein bestimmtes Spiel handelt. Http://store.steampowered.com/app/453870/Quantum_Chess/

und dort gibt es ein detailliertes Video über Quantenschach https://chess24.com/en/read/news/quantum-chess

Dhia Hassen
quelle
-2

Natürlich gibt es nur 10 hoch fünfzig mögliche Kombinationen von Teilen auf dem Brett. In Anbetracht dessen müssten Sie, um bei jeder Berechnung zu spielen, weniger als 10 hoch fünfzig machen (einschließlich Wiederholungen multiplizieren Sie diese Zahl mit 3). Es gibt also weniger als zehn hoch hundert Schachzüge. Wählen Sie einfach diejenigen aus, die zu Schachmatt führen, und Sie können loslegen

Alex
quelle
-3

64-Bit-Mathematik (= Schachbrett) und bitweise Operatoren (= nächste mögliche Züge) sind alles, was Sie brauchen. Also einfach. Brute Force findet normalerweise den besten Weg. Natürlich gibt es keinen universellen Algorithmus für alle Positionen. Im wirklichen Leben ist die Berechnung auch zeitlich begrenzt, das Timeout stoppt sie. Ein gutes Schachprogramm bedeutet schweren Code (bestanden, doppelte Bauern usw.). Kleiner Code kann nicht sehr stark sein. Das Öffnen und Beenden von Datenbanken spart nur Verarbeitungszeit, eine Art vorverarbeiteter Daten. Das Gerät, meine ich - das Betriebssystem, das Threading, die Umgebung und die Hardware definieren die Anforderungen. Programmiersprache ist wichtig. Auf jeden Fall ist der Entwicklungsprozess interessant.

AI-Entwickler
quelle