Einzelnen Beitrag anzeigen
  #24  
Alt 01.07.2015, 13:56
Benutzerbild von spacious_mind
spacious_mind spacious_mind ist offline
Schachcomputer Koryphäe
 
Registriert seit: 29.06.2006
Ort: Alabama, USA
Land:
Beiträge: 1.927
Abgegebene Danke: 47
Erhielt 327 Danke für 197 Beiträge
Aktivitäten Langlebigkeit
0/20 18/20
Heute Beiträge
0/3 sssss1927
Re: AW: Warum Fidelity scheiterte!

 Zitat von Solwac Beitrag anzeigen
Hast Du Dir schon mal den Quellcode (oder auch Pseudocode) angeschaut? Dann siehst Du, dass die Grundidee unabhängig von der Zugfolge ist und nur den aktuellen Zug der Variante betrachtet.

Könntest Du das mal bespielsweise formulieren? Ich sehe da nämlich keine Chance für eine Spezifikation.
Erst im nächsten Schritt der Entwicklung, der Konstruktion, könnte so etwas kommen.

Dafür gibt es genug Quellen, hier noch einmal ein Link: https://chessprogramming.wikispaces....lar+Extensions
Ich habe das erste Mal über den Einsatz bei Deep Thought im Artikel im Scientific American/Spektrum der Wissenschaft (keine Ahnung ob deutsch oder englisch) gelesen. Da war von der deutlichen Steigerung bei Stellungstests und beim Selbstspiel die Rede. Erst später habe ich dann mitbekommen (das könnte nach dem 1997er Match gegen Kasparow gewesen sein), dass der Effekt doch nicht so groß wie zuerst gedacht war. Erfahrungen mit Singular Extensions haben noch die Teams von Hitech und Cray Blitz gemacht und veröffentlicht, von den Schachprogrammen von Mikros gibt es hingegen kaum Infos über die ursprüngliche Version (die Profis waren da immer schon verschlossen) und ab Mitte der 90er haben dann etliche mit Varianten experimentiert.

Zum Aufwand: Von Deep Thought kenne ich keine exakten Zahlen, aufgrund der Mischstruktur (die ersten paar Halbzüge wurden in Software auf einer Workstation berechnet, die letzten 4-6 Halbzüge in Hardware auf den Spezialchips) wäre es aber auch nicht so einfach übertragbar. Deep Thoughts Suchgeschwindigkeit wurde immer relativ merkwürdig beschrieben, die Spezialchips könnten durch die Wiederholungssuche also eventuell besser ausgenutzt werden und damit den Mehraufwand reduzieren.
Von Hitech kenne ich (ich glaube u.a. von Berliner "Oral History" http://archive.computerhistory.org/p....103630824.pdf) die Aussage, dass es einen Halbzug in der Suchtiefe kostet, ähnlich ist die Aussage von Bob Hyatt für Cray Blitz (bis zum Faktor 10).
Ed Schröder und Jonathan Schaeffer meinten 1996, dass sie aufgrund des enormen Mehraufwands andere Versionen testen würden.
Was bedeutet das? Für Hitech und Cray Blitz sind ein Halbzug tiefer etwa ein Faktor 6 in der Rechenzeit. Die Erfahrungen waren, dass ca. 9 Halbzüge tief brute force (also jede Variante wird mindestens 9 Halbzüge tief berechnet, einzelne Züge dann aber tiefer) ungefähr vergleichbar sind mit 8 Halbzügen brute force und zusätzlichen Vertiefungen durch die singular extensions. Letztere finden zwar einige spektakuläre Kombinationen, über das ganze Spiel niweg würde es sich aber ungefähr ausgleichen. Dies passt auch zu den Erfahrungen von Hsu, wie er sie z.B. in seinem Buch über Deep Blue (Hsu, F.: Behind Deep Blue: Building the Computer that Defeated the World Chess Champion. (Paperback)) beschrieben hat.
Mikrocomputer kamen damals eher auf 6 Halbzüge brute force, hätten also mit singular extensions nur noch etwa 5 Halbzüge tief suchen können. Der Verlust an Qualität ist dabei aber größer als beim Rückgang von 9 auf 8, vor allem wenn die Konkurrenz ungefähr die gleiche Rechenleistung zur Verfügung hat (Deep Thought sowieso, aber auch Hitech und Cray Blitz gehörten immer zu den jeweils rechenstärksten Teilnehmern).
Außerdem sind die Programme auf Mikrorechnern schon früh vom reinen brute force abgegangen. Dadurch erhöhten sich die Suchtiefen und der Verzweigungsfaktor sank (zu Lasten eines Risikos etwas zu übersehen stieg so auch die Spielstärke). Allerdings bedeutet ein um den Faktor 6 erhöhter Aufwand jetzt nicht mehr nur die Verringerung der Suchtiefe um 1 sondern ist größer. Auch sind die selektiven Techniken der letzten 25 Jahre teilweise ähnlich im Effekt auf den Suchbaum, d.h. die zusätzliche Verwendung von singular extensions bringen weniger Erfolg und werden damit unattraktiver.
Um etwas zu verstehen da muss ich das problem erst zerbrechen in kleine Stufen um ueberhaupt es zu verstehen. Hier versuche ich es mal zu verstehen.

Angenommen es Spielt ein 6502 1 MHz. Er schafft ca wie folgt:

3 Ply = @ 1 Minute
4 Ply = @ 3 Minutes

In ein spiel von 3 minute pro zug wuerde er dann mit Brute Force vielleicht 4 Ply schaffen.

1) Mit selektiv wo er nur den besten Zug weiter rechnet, damit koennte er vielliecht + 3 Ply gewinnen bei 3 Minuten pro Zug = 6 Ply

Problem = nur 1 Zug wird laenger gerechnet = sehr viele fehl entscheidungen.

2) Aber theoretisch geht auch mit diesen 6502 1 Mhz die besten 2 Zuege ab 3 Ply weiter zu rechnen bis auf 6 Ply. = 3 Minuten fuer 2 hochgerechnete Zuege.

Problem = nur 2 Zuege werden laenger gerechnet = wieder sehr viele fehl entscheidungen.

Das koennte vielleicht nur einigermassen ok klappen wenn man die besten 5 oder 6 zuege weiter rechnet aber dafuer waere als besipiel ein 6502 1 MHz sehr viel zu langsam.

Die Frage ist ab welcher geschwindigkeit waere es ein Akzeptabler weg?

Oder ist die Theorie anders wo ZB:

- alle zuege auf ZB 3 Ply gerechnet sind
- 9 Besten + 2 Ply weiter gerechnet sind
- 5 besten + weitere 2 Ply
- 2 besten + weitere 2 ply

= ca 9 Ply fuer die 2 besten zuege.

Gruss

Nick

Gruss
Mit Zitat antworten