Ist die Tiefe (Anzahl der Lagen) immer noch wichtig, wenn sie hoch genug ist?

10

Das ist nicht real, stellen Sie sich das vor.

Computer Aist Supercomputer. Es kann innerhalb von 20 Sekunden eine Tiefe von 30 Lagen berechnen.

Computer Bist Supercomputer. Es kann innerhalb von 20 Sekunden eine Tiefe von 15 Lagen berechnen.

Sie spielen gegeneinander Schach.

Sind diese 15 Tiefen wirklich wichtig? Ich vermute, dass es in diesen 15 Tiefen Billionen Möglichkeiten gibt, einem Schachmatt zu entkommen oder ein wichtiges Stück einzufangen. Klar, Computer Aweiß mehr. Kann Computer Baber meiner Meinung nach auch die Zukunft weit genug vorhersagen, um sich wirklich gut zu verteidigen.

RikTelner
quelle
In diesem Fall meinen Sie mit "Tiefe" die Anzahl der Lagen? Prost.
Rauan Sagit
Ja, ich meine Lagen.
RikTelner

Antworten:

13

Ja, diese 15 Tiefen sind sehr wichtig.

Betrachten Sie diese Position, die in Kasparovs Unsterblichem Spiel gegen Topalov aufgetreten ist .

Kasparov - Topalov

Ich habe diese Position mit mehreren Motoren getestet. Einige Motoren in Tiefe 15 konnten nicht erkennen, dass 24 ... cxd4 ein Verlust ist, und dachten, es würde gewinnen. Dieselben Motoren spielten in größerer Tiefe den richtigen Zug 24 ... Kb6!

Zum Beispiel hält selbst ein Motor, der anfangs in Tiefe 21 so stark ist wie Stockfish 4, den Verlustzug 24 ... cxd4 für richtig.

Stockfish DD 64 SSE4.2: 24...cxd4 25. Re7+ Kb6 26. Qxd4+ Kxa5 27. Qc3+ Kb6 
28. Qd4+ Qc5 29. Qxf6+ Bc6 30.Qxc6+ Qxc6 31. dxc6 Rd1+ 32. Ka2 f5 33. c7 Rc8 
34. Rxh7 Rxc7 35. Rh6 Rc6 36. g4 f4 37. g5 Rd2 38. c3 Rxc3 39. Rxg6+ Kc5 
40. Bg4 Rcc2 41. Rxa6 Rxb2+ 42. Ka1 Rbc2 43. Kb1 
(-1.45/21)

Der gleiche Motor zeigt, wenn er etwas tiefer eingeschaltet bleibt, 24 ... Kb6 für die richtige Bewegung.

Stockfish DD 64 SSE4.2: 24...Kb6 25. b4 Qxf4 26. Rxf4 Nxd5 27. Rxf7 cxb4 
28. axb4 Rhe8 29. Rxe8 Rxe8 30. Nb3 Re1+ 31. Kb2 Re2 32. Rxh7 Nxb4 
33. Kc3 Nd5+ 34. Kd3 Rxh2 35. Rh4 Ne7 36. Nd4 Nc6 37. Nxc6 Bxc6 38. f4 Kc5 
39. Be6 Rxh4 40. gxh4 Bd5 41. f5 gxf5 42. Bxf5 a5
(-0.78/26)

Auch Fritz 11 SE in Tiefe 15 scheiterte. Aber es fand die richtige Bewegung in Tiefe 16!

Fritz 11 SE: 24... cxd4 25. Qxd4+ Qb6 26. Re7+ Nd7 27. Qe5 f6 28. Qc3 Qg1+ 
29. Ka2 Bxd5+ 30. Nb3 f5 31. Qc7+ Ka8 32. Rxd7 Rxd7 33. Qxd7 Bxf3 34. Qd6 Qa7  
(-1.44/15) 

Fritz 11 SE: 24... Kb6 25. b4 Qxf4 26. Rxf4 Nxd5 27. Rxf7 cxb4 28. axb4 Nxb4 
29. Nb3 Bd5 30. Rf6+ Nc6 31. Nd4 Rdf8 32. Rd6 Kc5 33. Rxc6+ Bxc6 34. Ne6+ Kd6 
35. Nxf8 
(-0.59/16)

Betrachten Sie auch dieses unglaubliche Problem wie die Position, die ich hier gefunden habe .

Stockfish konnte die Gewinnlinie 1 nicht finden. Be2 +! bis zur Tiefe 31 und bis dahin dachte es, es sei ein schlechter Schachzug. Ich zeige hier den Sieg. Der Punkt ist, dass Schwarz wegen der Bedrohung durch Partner in Zugswang ist und entweder die Königin aufgeben oder den Bauern bewegen muss, wodurch Weiß einen übergebenen Bauern erstellen und gewinnen kann.

NN - NN, 1-0
1. Be2 +! Kf5 2. Sd5! Dxe6 3. Ld3 + Kg4 4. Be4 !! Dh6
( 4 ... Dxe4 5. Sf6 + )
5. Sf4 Dg7 6. Sd3! Dxd4 7. c6! a5
( 7 ... Dxe4 8. Sf2 + Kf3 9. Sxe4 Kxe4 10. Kg2 Kd4 11. g4 hxg4 12. h5 Ke5 13. h6 Kf6 14. Kg3 Kg6 15. Kxg4 Kxh6 16. Kf5 Kg7 17. Ke6 Kf8 18. Kd7 Kf7 19. Kxc7 )
8. b5! a4 9. b6 cxb6 10. c7 Dxe4
( 10 ... Dc3 11. Sf2 # )
11. Sf2 + Kf3 12. Sxe4 1-0

Hier ist das Motorprotokoll von Stockfish 4. Wie Sie sehen können, erkennt es, dass 1. Be2 + gewinnt, nur in Tiefe 31!

Stockfish DD 64 SSE4.2: 1. Be2+ Kf5 2.Bc4 c6 3. Ne2 Qf6 4. Kg2 Kg4 5. Nf4 Qxd4 
6. Bd3 Qe3 7. Be2+ Kf5 8. Bf3 Qd2+ 9. Kh3 Qxb4 10. e7 Qe1 11. Ne2 Qf1+ 12. Kh2 Qf2+
13. Kh3 Qe3 (-1.05/22) 

Stockfish DD 64 SSE4.2: 1. Be2+ Kf5 2. Bc4 Qf6 3. Ne2 c6 4. Bxa6 Qxe6 5. Bd3+ Kf6 
6. Nf4 Qe1 7. d5 Qxb4 8. dxc6 Qxc5 9. Be4 Ke7 10. c7 Kd7 11. Nd5 Kd6 12. Kh3 Qc4 
13. Bg2 Qg4+ 14. Kh2 Qc8 15. Be4 (-1.15/26) 

Stockfish DD 64 SSE4.2: 1. Be2+ Kf5 2. Bc4 Qf6 3. Ne2 c6 4. d5 cxd5 5. Bxd5 Qb2 
6. Bc4 Kf6 (-1.01/28) 

Stockfish DD 64 SSE4.2:  1. Be2+ Kf5 2. Nd5 Qxe6 3. Bd3+ Kg4 4. Be4 Qh6 5. Nf4 Qf6 
6. Nd3 Qxd4 7. c6 Qxe4 8. Nf2+ Kf3 9. Nxe4 Kxe4 10. Kg2 Ke5 11. Kf3 Kf5 12. g4+ Kf6
13. gxh5 Kg7 14. Kf4 Kf6 15. h6 Kg6 16. h5+ Kh7 17. Kg5 Kg8 18. h7+ Kxh7 19. Kf5 Kg7
20. Ke6 Kh6 21. Kd7 Kxh5 22. Kxc7 Kg5 23. Kd7 (6.06/31) 
Wir s
quelle
Aber ich meine 15 Züge pro Zug. Nicht nur am Anfang.
RikTelner
4
Ja, bei jeder Bewegung. Wenn es beim ersten Zug in Tiefe 15 berechnet und einen Fehler macht, wird es bei der Berechnung von 15 Tiefen bei jedem weiteren Zug nicht gespeichert.
Wes
4

Die Beziehung zwischen Leistungssteigerungen und Suchtiefe ist in den Computerschach-Programmiergemeinschaften seit geraumer Zeit ein aktives Forschungsgebiet. Es gab eine Theorie, dass eine Zunahme der Suchtiefe zu einer Abnahme der Stärke führte ... dies schien in experimentellen Ergebnissen bestätigt zu werden.

Aus meiner Sicht gibt es dafür eine intuitive Grundlage. Stellen Sie sich Ihre hypothetische Übereinstimmung zwischen zwei Supercomputern vor, beginnend mit den Tabellenpositionen der Endspiele. Die meisten erzwungenen Gewinne in Tabellenbasen erfolgen an einem Horizont von weniger als (zum Beispiel) 50 Lagen. Die Mehrheit der verbleibenden Positionen wird gezogen, nur ein kleiner Bruchteil beschließt, in einer höheren Tiefe zu gewinnen. Ein Computer, der mit 100 Lagen sucht, hätte einen begrenzten Vorteil gegenüber einem 50-Lagen-Computer, da (wie Sie erwähnen) das schwächere Programm durch fast alle verlorenen Linien navigieren kann, die alle in begrenzterer Tiefe auftreten. Ein 50-lagiges Programm hätte tatsächlich einen viel größeren Vorteil gegenüber einem 25-lagigen Programm ... ebenso wie ein 4-lagiges Programm einen noch größeren Vorteil gegenüber einem 2-lagigen Programm hätte.

Ich bin vor ungefähr 15 Jahren zum ersten Mal auf dieses Konzept gestoßen, als ich in einer Reihe von Artikeln über Dark Thought experimentierte. Diese sind eine gute Lektüre, wenn Sie sich für Computerschach interessieren.

Obwohl ich keine Online-Referenz finden konnte, gibt es ein Papier aus dem letzten Jahr zu diesem Thema ...

Diogo R. Ferreira (2013). Der Einfluss der Suchtiefe auf die Schachspielstärke. ICGA Journal, Vol. 36, Nr. 2

tbischel
quelle
1

Die Frage ist: Meinen Sie 15/30 Lagen erschöpfender Suche oder eine nominelle Tiefe / Iteration von 15/30 einer modernen Schachmaschine wie Stockfish?

Wenn Sie letzteres gemeint haben, bedeutet 15-lagig nicht unbedingt viel. Moderne Schach-Engines beschneiden und reduzieren Bewegungen, die angeblich schlecht sind, stark, so dass es sein kann, dass ein Opfer, das auf den ersten Blick schlecht erscheint, bei einer nominalen Tiefe / Iteration von 15 tatsächlich nur bis zu einer Tiefe von z. B. 5-10 gesucht wird. Bei Tiefe / Iteration 30 wird die Bewegung wahrscheinlich immer noch nur bis zu einer reduzierten Tiefe gesucht, aber dann kann es sich um eine effektive Tiefe von 15 bis 20 handeln, die ausreichen könnte, um festzustellen, dass das Opfer tatsächlich gut ist, und sobald der Motor stellt fest, dass die Bewegung vielversprechend ist, verringert sie die Reduzierung, so dass die Bewegung bis zu einer Tiefe gesucht wird, die näher an 30 Lagen liegt (oder aufgrund von Erweiterungen und Ruhesuche sogar noch tiefer). Also ja, ich denke, es kann einen Unterschied machen, selbst wenn die Kombination innerhalb des nominalen Horizonts von 15 Lagen liegt.

Wenn Sie sich auf eine umfassende Suche beziehen würden, wäre eine Engine mit einer Tiefe von 15 meiner Meinung nach sehr stark, vorausgesetzt, sie verfügt über eine gute Bewertungsfunktion und eine Art Ruhesuche (nach dem Verlassen der Knoten in Tiefe 15). Aufgrund der sinkenden Renditen denke ich, dass der Gewinn durch Verdoppelung der Tiefe viel geringer wäre als der, den Sie für ein Match zwischen zwei modernen Motoren mit Tiefe 15 gegen Tiefe 30 erhalten würden. Aber das ist natürlich nur theoretisch, da eine erschöpfende Suche nach Die Tiefe 15 würde mehrere Größenordnungen länger dauern als die Motoren normalerweise benötigen, um die Tiefe / Iteration 15 zu erreichen, so dass ein solches Experiment nur in niedrigeren Tiefen möglich wäre.

Fabian Fichter
quelle
0

FWIW Als der ARM neu war, schrieb ich ein optimiertes ARM-Vollständig-Suchprogramm mit einer Positionsbewertung nur für Material nach Lage 1.

Ich habe Tricks mit optimiertem Maschinencode, iterativer Vertiefung, Alpha-Beta-Fensterung bei sortierten Zügen (fast alle Positionen hatten den Wert 0, also nahezu optimales Alpha-Beta-Bereinigen) verwendet - und Hash-Tabellen, die den Verzweigungsfaktor auf viel weniger als den reduzierten theoretische Quadratwurzel für Alpha-Beta, normalerweise um die 4 im schlechtesten Teil des Spiels.

In einem Wettbewerb gegen die damaligen Standardprogramme geriet mein E6P-Programm in schreckliche Positionen, jedoch mit ein oder zwei zusätzlichen Lagen im Vergleich zu Pro-Software zu der Zeit (dh normalerweise 6 Lagen erschöpfende + ruhende Suche im schlimmsten Stadium mit Bis zu 12 Lagen, als das Spiel vereinfacht wurde, zappelte es trotz des Vertrauens seiner Gegner immer wieder davon ab, tatsächlich zu verlieren. Fast alle Spiele wurden nach vielen Stunden entschieden, weil die gegnerischen Programme nicht wirklich gewinnen konnten.

Später habe ich es für StrongARM optimiert, wo es auf 10 Lagen verschoben wurde. Diese Version könnte leicht alle Nicht-Schachspieler schlagen, obwohl es offensichtlich an Strategiebewusstsein mangelte, so dass der berühmte Kommentar zutraf: Ja, es sind Schachzüge - aber es ist kein Schach!

Dies war vor einigen Jahren, aber ich bin versucht, es mit einer strategischeren Positionsbewertung auf Schicht 1 noch einmal ausführlich zu versuchen - und mit einem Intel XEON, der theoretisch 10.000-100.000x schneller (und mit 30.000 Mal mehr Hash-Tabellenspeicher) als ein 4MIPS ist ARM2 Acorn Archimedes.

Zugegeben, kein Mainstream, aber es macht Spaß zu spielen.

Stephen Streater
quelle
-2

+1 Lage wird geschätzt + 55..70 ELO-Gewinn (viele Untersuchungen zu diesem Thema)

Ich vermute, dass es in diesen 15 Tiefen Billionen Möglichkeiten gibt, einem Schachmatt zu entkommen oder ein wichtiges Stück einzufangen.

Die Sache ist, dass all diese "Billionen" mit A @ D = 30 berechnet wurden, und wenn A einen Zug mit Gewinnauswertung wählt, bedeutet dies, dass er all diese "Billionen" berechnet hat und egal welche der "Billionen" die Antwort des Gegners bewegt - Antwort gewinnt immer noch

Yuriy Pylypenko
quelle
Willkommen zur Diskussion. Haben Sie etwas, um Ihre Aussage zu beweisen? Ich glaube nicht, dass es eine konkrete Beziehung gibt.
SmallChess