Wie Mephisto III funktioniert:

By Benno Hartwig Date 2016-12-06 17:00 Edited 2016-12-06 17:05

Weiß nicht.

Aber ich meine, es war der Mephisto 3, der in einer toll getunten Version seinerzeit an einem Schachcomputerturnier teilnahm und mäßig abschnitt.
Sein Betreuer meinte hinterher: "Ja, er macht dieselben Fehler wie immer, nur eben viel schneller!"

Als ich begann, mich für die Thematik zu interessieren, war der Mephisto 2 im Verkauf, der immerhin so stark gewesen sein soll, dass er für einen Vereinsspieler (die Spielklasse wurde nicht genannt) ein ernstzunehmender Gegner sein kann.
Und ich meine, der Mephisto 3 spielte dann immerhin ein Stück weit erfolgreich gegen seinen älteren Brikett-Bruder.

Auf
http://www.schach-computer.info/wiki/index.php?title=Mephisto_III
sind noch einige weitere Stellungen/Zeit-Angaben für verschiedene Versionen des Rechners. (3,5 MHz bis 12 MHz)
Weiter unten in diesem Artikel findest du auch einige Informationen zu den programmgewordenen Konzepten und Ideen.

Benno

By Thorsten Czub Date 2016-12-06 20:49 Edited 2016-12-06 21:19

Da ist mir ja alles bekannt.

Das spannende ist ja
WIE Mephisto III seine spielstärke erreicht.

Während die Konkurrenten 500-1500 NPS machen macht Mephisto III 1-3 NPS.

Dennoch konnte das Programm in Glasgow einen WM Titel holen, ein geteilter Platz mit Gegnern die
Einen ganz anderen Ansatz verwendeten und deren Programme viel mehr NPS machten.

Darum geht es.
Thomas hat mir dazu ein paar erklärende Worte gemailt die ich gerne in diesem Thread statt in dem
anderen diskutieren würde, wo es vielleicht Off topic wäre.

Deswegen der Mephisto III Diskussionsbeitrag hier.

Ich habe selber mit meinem Mephisto III und meinem MM5 über die Zeit für jede neue iteration
Den BF gemessen und komme beim IIIer auf durchschnittlich 3.43 In der grundstellung nach 1.a4
Beim MM5 messe ich durchschnittlich 3.05.

Wenn man bedenkt das die Programme 7 Jahre unterscheiden ist das m.E. Ein beachtlicher wert.

Die Frage ist natürlich ob diese Messungen zulässig sind.
Denn meinen beide Programme in der Anzeige der tiefen dasselbe ?

hier meine Messung mit meinen originalgeräten:

Code:

bf=(t1-t2)/t2 
mit t1=gesamtzeit iteration n, t2=gesamtzeit iteration n-1

oder 

bf=(n1-n2)/n2 
n1=knoten iteration n, n2=knoten iteration n-1

Stellung nach:
1.a4       

MM1 aka mephisto III b 8 mhz                                                              
m2  15"
m3  56"  2.73
m4  194"  2.464
m5  1186"  5.11
    3.43

MM5
6  10"      
7  25"  1.5
8  110"  3.4
9  425"  2.863
10  2315"  4.45
    3.05

By Frank Brenner Date 2016-12-07 01:43

Zitat:

Code:


MM5
6  10"      
7  25"  1.5
8  110"  3.4
9  425"  2.863
10  2315"  4.45
    3.05

Ich glaube du berechnest den BF nicht so ganz richtig.

Um jetzt mal deine Messergebnisse herzunehmen

nach 10 Sekunden zeigt der MM-V 6.00 an - das bedeutet er hat für die Tiefen 1-5   10 Sekunden benötigt.

Nach 25 Sekunden zeigt der MM-V 7.00 an, d.h. für die Tiefe 6 hat der MMV   15 Sekunden benötigt.
Nach 110 Sekunden wird 8.00 angezeigt. d,h. für Tiefe 7 wurden 85 Sekunden benötigt.

Der BF ist also hier erstmalig berechenbar und beträgt 85/15 = 5,66

Nach 425 Sekunden wird 9.00 angezeigt, d.h. Tiefe 8 wurde in 425-110 = 315 Sekunden berechnet

Der BF ist also hier 315/85 = 3.705

Für die nächste Iteration braucht der MMV dann exakt 6 mal so viel Zeit wie für die vorhergehende Iteration.

Der durchschnittliche BF beträgt somit dritte_wurzel_aus( 5,66 * 3,705 * 6) =   (5,66*3,705*6) ^ (1/3)   =   5.01

Ich habe die Erfahrung beim MMV sowie beim Mep3 gemacht, daß wenn in einer Iteration der BF überdurchscnittlich hoch ist, daß dann die nächste Iteration überdurchschnittlich schnell erfolgt.
Daher ist es am besten immer eine gerade anzahl von Faktoren für den Mittelwert zu nehmen. Mit dem Windows Taschenrechner kann man die n-te Wurzel von x berechnen indem man x hoch (1/n) ausrechnet.

Ich bin gespannt was Thomas Nitsche über sein Programm und über die winzige Knotenfrequenz sagt.

Ich glaube, dass hier nicht alle Knoten gezählt werden die bei den anderen Mitbewerbern gezählt wurden . Nur so kommt die winzige Knotenfrequenz zustande.

Mit Sicherheit kann ein Schachprogramm durch 100 fach so langes Angucken einer einzelnen Position keine "magischen" Erkenntnisse erzielen um plötzlich mit 3 Knoten/S noch richtig ordentlich Schach zu spielen.

Die fähigkeit auch Matts in 9 zu finden kommt weil die Ruhesuche ganz schön lange Pfade durchläuft und nicht - so wie bei den meisten Mitbewerbern - irgendwann einfach abgeschätzt werden um zeit zu sparen und sich nicht zuuuu lange an der stelle aufzuhalten.

In einem Bericht zu deep Blue hat Feng-hsiung Hsu einmal gesagt, daß Singular Extensions verwendet werden, dank derer in der Ruhesuche auch mal eben so ein matt in 30 gefunden wird.

Im ccc hat dann einer der damaligen Schachprogrammierer von PC Schachprogrammen geschrieben (leider weiß ich nicht mehr wer das gesagt hat), das es leicht möglich ist das eigene Programm auch mit Singular Extensions auszurüsten die dann bis ins halleluja weitersuchen und ebenso dann ratzefatz ein matt in 30 finden ... aber im Duchschnitt würde das Schachprogramm dann schwächer spielen.

Im Durchschnitt spielt das Programm besser, wenn nicht bis in ungeahnte Tiefen gesucht wird, sondern wenn nach einer bestimmten Tiefe einfach bestmöglich abgeschätzt wird.

By Thorsten Czub Date 2016-12-08 21:32 Edited 2016-12-08 21:37

So wie ich das Programm bzw. Thomas verstanden habe, hat es keine Ruhesuche wie du sie bezeichnest.
Es hat die von Thomas und Elmar beschriebene 3 geteilte suche.
Bitte lies dazu das Papier das die beiden herausgebracht haben mit Beispielen.
Sascha hat ja den Link hier angegeben der auf die Schachcomputer.info Seite verweist.

Die knotenzahl ist echt. Da gibt es keine versteckten oder zusätzlichen, nicht gezählten Knoten.

Ein Großteil der Zeit geht bei Mephisto III für die statische Abschätzung von schlagzügen und einigen Vokabeln drauf die
Mephisto III wie ein Mensch "kennt". Sie sind im Papier explizit genannt und mit Beispielen angezeigt.
Mephisto III kann alle diese "Vokabeln" statisch erkennen ohne eine Stellung generieren oder Züge vor und zurücknehmen zu müssen.

Durch dieses Vokabel-Wissen substituiert (ersetzt) Mephisto III erkenntnisse die es ansonsten über die Suche und das vor und nachspielen und bewerten der endstellungen vornehmen müsste. Daher kann es schon mit einer sehr flachen Tiefe Erkenntnisse bekommen die sehr viel tiefer im Baum sind, und die normale Programme erst durch höhere rechentiefen ausspielen würden im Baum.

Wenn man bedenkt das Nitsche/Henne das alles KOMMERZIELL und bis zum Weltmeistertitel bereits 1983 realisiert haben, kann man heute nur Respekt und Achtung für diese Leistung zollen.

Es ist mir vollkommen unverständlich das du die Programme als graduell unterschiedlich ausgeprägte A-Strategie Programme bezeichnest.

Mephisto III hat dies damals alles realisiert, also nicht nur drüber gesprochen, sondern es in der Praxis als Massenprodukt für jeden Kunden der wollte kommerziell auf den Markt gebracht, mit nur 6-8 MHz bei 32 KB ROM und 8 KB RAM.

Sicherlich ist das Programm später von anderen konkurrenzprogrammen überholt worden. Die mit herkömmlicheren Methoden ein stärkeres Ergebnis gebracht haben. Aber das macht ja den von Thomas und Elmar verfolgten Ansatz nicht weniger wertvoll.

Sie haben gezeigt das es möglich ist. Und wir wissen nicht wie das Programm sich entwickelt hätte, wenn sie weiter daran gearbeitet hätten.

By Frank Brenner Date 2016-12-10 01:11

Code:


Es ist mir vollkommen unverständlich das du die Programme als graduell unterschiedlich ausgeprägte A-Strategie Programme bezeichnest.

Dabei habe ich das doch mehrfach begründet.

Du hast übrigens am Ende von dem was du geschrieben hast das "Amen" vergessen.

By Thorsten Czub Date 2016-12-10 09:56

Ich kann nicht mehr machen als den Programmierer danach fragen.

By Mythbuster Date 2016-12-10 12:30 Upvotes 2

Thorsten Czub schrieb:

Ich kann nicht mehr machen als den Programmierer danach fragen.

Doch, eine Diskussion lassen, wenn sich zeigt, dass das Gegenüber nicht verstehen will. Manchmal ist es besser, einen Thread durch Nichtbeachtung in der Versenkung verschwinden zu lassen.

Schade, dass die Aussagen von absoluten "Helden" der Schachprogrammierung (von TN&EH bis zu RL) öffentlich als Lügen und Unwahrheit dargestellt wird ...

By Frank Rahde (Mod.) Date 2016-12-10 15:40

Als echte Lüge seitens Frank Brenner habe ich das Ganze jetzt nicht verstanden, sondern als andere Meinung/Sicht, als Bezweifeln, als Nicht-Glauben. Wofür ist denn Diskussion da, wenn nicht zum Versuchen des Gegeneinander Überzeugens mit Argumenten und Beispielen, zur Klärung und zum Wissensammeln!?

Schade, dass der bisher sachlich geführte Disput wieder zu persönlich wird. Wenn das so weitergeht, muss ich den Thread (wenn auch sehr ungern) sperren.

By Mythbuster Date 2016-12-10 16:33 Upvotes 1

Frank, alles Ansichtssache.

Sehen wir es mal so: A und B diskutieren über ein Programm und können sich nicht einigen. A behauptet, das Programm würde alle Züge aus einer Endspieldatenbank spielen und B sagt, das Programm würde alles selbst errechnen. Dann wird von B der Autor zitiert, der die Aussage von B bestätigt. Wenn A nun bei seiner "Meinung" bleibt (trotz klarer Aussage des Autors), so bezichtigt meiner bescheidenen Meinung nach A den Autor indirekt der Lüge.

Aber gut, ist halt wie auf der Autobahn, wo im Radio vor einem Falschfahrer gewarnt wird und sich einer fragt "wieso ein Falschfahrer" ...

Man kann ja über viel diskutieren, aber speziell bei den alten Programmen ist schon recht eindeutig bekannt, welches Programm selektiv rechnete und welches Brute Force ...

Und spätestens, wenn jemand öffentlich schreibt, dass die Angaben vom Programm zur Knotenzahl "falsch" seien, dann ist das nicht mehr und nicht weniger, als dass behauptet wird, dass die Autoren die Kunden verarscht haben ... und sorry, das finde ich schon ziemlich befremdlich!

Mehr werde ich dazu nicht schreiben ... und keine Sorge, auf Diskussionen mit dem Schreiber werde ich mich gewiss nicht einlassen.

By Frank Rahde (Mod.) Date 2016-12-10 17:28

Mythbuster schrieb:

... A und B diskutieren über ein Programm und können sich nicht einigen. A behauptet, das Programm würde alle Züge aus einer Endspieldatenbank spielen und B sagt, das Programm würde alles selbst errechnen. Dann wird von B der Autor zitiert, der die Aussage von B bestätigt. Wenn A nun bei seiner "Meinung" bleibt (trotz klarer Aussage des Autors), so bezichtigt meiner bescheidenen Meinung nach A den Autor indirekt der Lüge.

Vielleicht kann uns ja Frank noch erklären, weshalb er der direkten Quelle (dem Autoren) nicht glaubt/traut. Dies wüsste ich auch gern.

Gruß, F.

By Thorsten Czub Date 2016-12-10 20:12 Edited 2016-12-10 20:20

Ich fände es sehr schade wenn man diesen Thread wegen Beleidigungen schließen müsste. Ich habe ihn initiiert weil ich
die Diskussion in dem anderen Thread Off topic und auch zu versteckt fand.

Frank schließt auf die Programme indem er INDIREKT die Zeit misst die das Programm benötigt um eine Iteration
tiefer zu kommen.
Das sagt es doch schon. Er misst INDIREKT über die Zeit. Er könnte ja auch konkret die NPS zählen, aber da gibt es
bei den Schachcomputern ja kaum Angaben. Bei Mephisto III gibt es Angaben. Aber den schenkt er keinen Glauben.
Also bleibt ihm nur, INDIREKT zu messen, zumal MM5 und Mephisto Amsterdam (um mal konkret einen Lang zu benennen)
gar keine knotenangaben machen.

Thomas Nitsche meinte, das Mephisto III einen grossen Anteil seiner zur Verfügung stehenden Zeit für die statische Analyse der Stellung aufwendet. Wissen das statisch gesehen wird, also ohne das ein Zug generiert werden muss.
Er meinte das Mephisto III keine ruhesuche hätte (und, wie Frank vermutet dort die Knoten nicht mitzählt). Im Gegenteil. Stattdessen würde es alle schlagabtäusche und viele andere "Vokabeln"
statisch sehen. Dadurch könnte Mephisto III auch bei der geringen knotenzahl und dem kleinen Baum den es mit den wenigen Knoten erstellt, mehr erkennen als andere Programme mit einem viel größeren Baum, weil sie dynamische suchen haben.

Welche Vokabeln das neben den abtäuschen sind, erklärte ja schon das alte Papier.

Ich muss sagen das mir das einleuchtet weil wir das beim Chess System Tal genauso gemacht haben.
Chess System Tal konnte auch matt und viele angriffsmotive statisch sehen, die bewertungsfunktion hatte das einfach drauf und daher
musste an vielen Stellen keine baumsuche eingesetzt werden.

Wenn also Frank Brenner INDIREKT die Zeit misst die Mephisto III benötigt um eine iteration tiefer zu kommen,
misst er auch de Zeit mit, die das Programm benötigt um statisch Sachverhalte zu klären, weniger den suchbaum, der zeitlich
nur einen kleinen Anteil der Rechenzeit benötigt.

Das ist der Grund warum Mephisto III nur so wenige Knoten pro Sekunde berechnet.
Weil die meiste Zeit mit dem Erstellen der statischen bewertungsfunktion abgearbeitet wird.

Wie die Suche im einzelnen funktioniert, die 3 geteilte suche, haben Thomas Nitsche und Elmar Henne ja im Papier erläutert.
Das kann man sehr schön hier nachlesen:
http://www.schach-computer.info/wiki/index.php?title=Mephisto_III

In diesem Sinne ein schönes Wochenende.

By Frank Brenner Date 2016-12-11 04:01

Zentraler Punkt ist, daß wenn jede weitere Iteration beim Mephisto 3 ebenfalls im Durchschnitt Faktor 5 an Zeit benötigt, also einen vergleichbaren Wert wie bei MM5, dann ist der Grad an Bruteforce beim Mep3 identisch zum MMV.

Mephisto ist also gar kein Programm welches in besonderer Weise menschliches denken abbildet mit einem sehr kleinen BF. Großmeister haben einen BF von unter 2.

Diese Argumentation ist unabhängig davon gültig auf welche Art und Weise die Blätter bewertet werden, ob nun durch eine Ruhesuche, statisch , oder selbst dann wenn die Bewertung vom einer Datenbank oder von einem allwissenden Orakel zugeflüstert wird.

Man kann also eine Engine in eine BLAXBOX sperren und allein durch die Zeitmessung der einzelnen Iterationsstufen den Grad an Bruteforce ableiten mit dem die Engine rechnet.

Eine 100%ige Brute Force engine erzielt einen BF der mit wurzel(n) übereinstimmt, wobei n die Durchschnittliche Anzahl an Züge in einer Stellung entspricht.

Eine 100%ige Super Intelligente Engine hat einen BF von 1.0 - nämlich eine Datenbank.

Zu den Knotenzahlen:

Grundsätzlich hat natürlich jeder Programmierer das Recht alles zu zählen was er gerne möchte.
Er braucht auch keine umgangssprachliche Formulierung abzugeben was genau gezählt wird und was nicht.

Selbst die Begriffe was ein Blatt ist und was eine Ruhesuche ist, kann ein Programmierer individuell so definieren wie er gerne möchte. So kann es dann durchaus passieren dass man sagt "Mein Schachprogramm hat keine Ruhesuche"

Man müsste schon das Programm vom Mephisto 3 angucken was da gezählt wird und was nicht.

By Thorsten Czub Date 2016-12-11 10:35 Edited 2016-12-11 10:45

Tut mir leid aber hier irrst du. Du willst den branchingfaktor einer Black Box ermitteln.
Das Programm benötigt aber sehr viel Zeit um die Züge zu differenzieren.
Der suchbaum und die knotenzahl ist klein.
Du misst also gar nicht die Zeit die für den suchbaum anfällt, du misst die Zeit
Die das Programm aufwendet diesen geringen branchingfaktor möglich zu machen.

Und dann folgerst du das es einen hohen branchingfaktor hat anhand der Zeit.

Der Clou ist ja gerade das Mephisto III fähig ist zu unterscheiden welche Äste man weiterrechnen
soll und welche nicht. Für diese Bestimmung geht viel Zeit drauf.

Fakt bleibt aber das die knotenzahl und der suchbaum klein ist. Und DAS widerspricht ja deiner
Annahme die du aus der Zeit gefolgert hast.

Mephisto III ist anders als andere Programme. Es verwendet einen großen Teil der Zeit darauf
zu entscheiden welche Züge weiterverfolgt werden. Die wenigen Züge die es berechnet, also der eigentliche suchbaum,
Sind klein. Und dennoch kann es mit den wenigen berechneten stellungen ordentliches Schach spielen.
Ja es gewann sogar in Glasgow einen WM Titel.

Natürlich ist dies ein radikaler Ansatz.
Und manchmal macht Mephisto III auch Fehler. Und übersieht etwas.

Bei CSTAL war es ähnlich. Aber was den suchbaum angeht eher umgekehrt,
Die knotenzahl war durch das viele schachwissen geringer. Aber durch die "interesting" Funktion hat CSTAL
Äste und Opfer weiterverfolgt, die andere schachprogramme abgeschnitten und nicht vertieft hatten.
D.h. CSTAL hat da wo die Tal Funktion griff, extrem große suchbäume gehabt.

Der eine hat ein Schlüsselbund und steckt einfach jeden Schlüssel mal ins Schloss um zu sehen ob die Tür aufgeht.
Der andere schaut die Schlüssel an. Und steckt nur die Schlüssel ins Schloss die nach seinem Wissen über Schlösser und Schlüssel, Sinn machen. Nun ist doch klar das man beim betrachten und analysieren der Schlüssel mehr Zeit braucht als wenn man die Schlüssel einfach ins Schloss steckt und einmal umzudrehen versucht.

Und der branching Faktor ist wieviele Schlüssel man ausprobiert.
Und nicht wie lange man die Schlüssel anschaut.

Wie öffnest du denn deine Haustür und deine Wohnungstür.
Probierst du einfach irgendwelche kleinen oder großen Schlüssel aus ? Oder guckst du auf dein Schlüsselbund
Und steckst gleich den richtigen Schlüssel rein (vielleicht hast du den markiert )? oder aus einer Auswahl von 2 gleich aussehenden Schlüsseln aus 8 probierst du die 2 dann aus ?

By Frank Brenner Date 2016-12-11 12:49

Code:


Du misst also gar nicht die Zeit die für den suchbaum anfällt, du misst die Zeit
Die das Programm aufwendet diesen geringen branchingfaktor möglich zu machen.

Ich messe die Zeit die für die Knoten im Suchbaum anfallen multipliziert mit der Zeit T,
wobei T die Zeit ist, die das Programm benötigt um eine einzelne Stellung zu bewerten (meinetwegen statisch) zuzüglich der zeit die das Programm benötigt um den Zug zu selektieren.

Die Gesamtzeit die ich pro Iteration messe ist also Anzahl_Knoten_im_Suchbaum_Iteration_n * T

Und wenn diese Gesamtzeit pro Iteration um den Faktor 5 ansteigt, so bedeutet dies, daß die Anzahl der Knoten im Suchbaum pro Iterationsstufe ebenfalls um den faktor 5 ansteigen, denn wenn man die beiden Zahlenwerte für aufeinanderfolgende Suchtiefen (n-1,n) teilt dann kürzt sich das T weg !!

Und da dieser Faktor bei Mephisto 3 und MMV in etwa identisch ist, bedeutet dies, daß der Mephisto 3 den gleichen Grad an Selektivität/Bruteforce erzielt wie der MM5.

Wäre der Mephisto 3 in der Baumsuche im Durschnitt selektiver als der MMV , so würde der Mephisto 3 nach langer Rechenzeit eine immer größer werdende Suchtiefe erzielen die dann irgendwann am MMV vorbeirauscht und ab da an würde der MMV immer weiter ins hintertreffen gelangen, weil der Mephisto 3 den aAbstand sogar ständig vergrößert.
Dies würde selbst dann der Fall sein, wenn der Mephisto 3 eine Stunde pro Stellungsbewertung benötigt und eine Stunde für die Zugauswahl pro Stellung.

Dies ist aber in der realität absolut nicht der Fall wie du leicht sehen kannst anhand beliebiger beispiele: Die Suchtiefendifferenz ist im wesentlichen gleich.

By Thorsten Czub Date 2016-12-11 15:17

Bei Mephisto III ersetzt die statische Berechnung in Kombination mit einer z.B. 2 ply suche in etwa einer normalen Berechnung von 4-5 Halbzügen.
Der verzweigungsfaktor beträgt 1 , selten auch 2.

Damit kann das "langsame Programm" dann schon mal 8-12 halbzüge tief geschaut (maximal 19).

Beim branching Faktor misst man die Verzweigung des suchbaums.

D.h. Wie viele Schlüssel steckst du in einer gegebenen Zeit ins Schloss und probierst ob die Tür aufgeht wenn du umdrehen kannst.
Der eine probiert ganz viele Schlüssel (Novag constellation / super constellation: 1000-1500 NPS)
etwas schlauere Programme schaffen nicht ganz soviele Schlüssel (Rebell Versionen vielleicht 500 NPS)
Saitek Kaplan Programme 350 bis 800 NPS, und ganz doofe Programme sogar 1500-2500 NPS (quest).

Manche schauen aufs Schlüsselbund und WISSEN das sie die dicken Schlüssel nicht ausprobieren müssen weil die physisch nicht ins Schloss passen wenn es ein Sicherheitsschloss ist.

Die probieren die dicken Schlüssel also NICHT aus.

Ein paar wenige , die nach dem Wissen in Frage kämen, werden aber ausprobiert.

Thomas spricht von einem branching Faktor zwischen 1-2.

By Frank Brenner Date 2016-12-12 02:14

Code:

Thomas spricht von einem branching Faktor zwischen 1-2.

Messen tue ich aber ganz Eindeutig ca Faktor 5 - so wie bei den Schröder Programmen!

Faktor 1-2 könnte bei der Ruhesuche (oder wie auch immer man das nennen will) durchaus plausibel sein, nur so kann ein Matt in 9 in kurzer Zeit gefunden werden. Bei Deepblue wurden mit so einem schmalen BF in der Ruhesuche durch die "singular extensions" sogar Matts in 32 gefunden.

Die Ruhesuche in einem Blatt dauert aber im Durchschnitt immer gleich lang, daher wird diese Zeitdauer hierfür bei der Berechnung des BF der Hauptsuche weggekürzt und es bleibt für den BF die 5 übrig

By Thorsten Czub Date 2016-12-30 00:48 Upvotes 1

Hier erklärt Thomas Nitsche Mephisto III, Vortrag auf Video:

https://media.ccc.de/v/vcfb2016_-_45_-_de_-_medientheater_-_201610021400_-_die_entwicklung_des_ersten_mephisto-schachcomputers_-_thomas_nitsche#video&t=964

By Michael Scheidl Date 2016-12-30 02:20

Danke für diesen Link, aber Du wirst mir hoffentlich nicht böse sein, daß ich diese Darbietung nicht länger als fünf Minuten ertragen konnte.

By Thorsten Czub Date 2016-12-30 09:46

By Klaus S. Date 2016-12-30 21:33 Upvotes 1

Michael Scheidl schrieb:

Danke für diesen Link, aber Du wirst mir hoffentlich nicht böse sein, daß ich diese Darbietung nicht länger als fünf Minuten ertragen konnte.

Ab minute 43:30 wird sehr Interessantes über Hegener&Glaser, Sid Samole ect. erzählt!

Sollte sich jeder mal ansehen - finde ich.
.

By Michael Scheidl Date 2016-12-30 23:33

Ein Sittenbild der besonderen Art

By Thorsten Czub Date 2016-12-30 10:55

Hier haben wir nun also mal alles erklärt vom Programmierer selber.

By Frank Brenner Date 2016-12-30 15:54

Danke für den Link.

Ich finde solche Dokumentationen immer sehr spannend.

Warst du der Fragesteller im Publikum ?

Mir wären auch ein paar Fragen eingefallen. Toller Vortrag.

By Thorsten Czub Date 2016-12-30 19:27

Nein ich war nicht dabei. Thomas hatte mir nur davon berichtet.
Aber jemand anderes aus der Szene war dabei.

By Benno Hartwig Date 2016-12-30 20:08

> Die Ruhesuche in einem Blatt dauert aber im Durchschnitt immer gleich lang

Zwangsläufig muss das aber nicht bei jeder Engine so sein.
Der Programmierer könnte durchaus auf die Idee kommen, die in der Ruhesuche wirksamen Parameter unterschiedlich zu setzen, je nachdem wie tief die Hauptsuche inzwischen ist.
Ich weiß nicht, ob ggf. auch sowas gemacht wird.

Benno

By Thomas Plaschke Date 2016-12-30 13:18

Reizvolle Fragestellung: Wo wäre Stockfish 8 unter den Schachcomputern der Mitte-80er Jahre gelandet?

Ich habe das mal in Relation zu Mephisto III im Mephisto-S mit Motorola 68000 bei 7,2 MHz versucht zu berechnen. Für Stockfish habe ich die Knotenleistung von Pedantfish genommen - also die schnellste Stockfishversion überhaupt. In einer CSS wurde der Begriff Chess Instructions Per Second =CIPS eingeführt, den jemand von Saitek ins Spiel gebracht hatte, um CPUs von Schachcomputern vergleichen zu können. Eine chess instruction sollte die durchschnittliche Zahl von Taktimpulsen zur Verarbeitung eines typischen CPU-Befehls darstellen.
Für den 68000 wurde der Wert 9 angegeben - den ich vorsichtig für optimistisch halte (mit dem 68000 kenne ich mich etwas aus). Den modernen Intel-Prozessorkern habe ich mit 3 eingeschätzt - mit dem kenne ich mich weniger gut aus. Die modernen Prozessoren habe aber Befehle, die in einem Takt ausgeführt werden und können manches sogar parallel bearbeiten. Dagegen benötigen viele Adressierungsarten mehr Zeit und der RAM-Zugriff ist beim cache-miss vergleichweise besonders zeitintensiv (gemessen am CPU-Takt).
Lässt man sich aber auf dieses Gedankenspiel ein, erhält man dieses Ergebnis:

Code:

    CPU    Takt (MHz)  Hz/CI  MCIPS/Takt         N/s     N/MHz         CI/N
i5-3570         4200       3        1400   2.250.000    535,71        622,2
M68000           7,2       9         0,8         5,5      0,76     145454,5
               583,3              1750,0                              233,8

1.750 wäre demnach der Faktor, um den Mephisto III auf moderner Hardware schneller laufen würde.
Er käme auf ca. 10.000 N/s und würde in einer Sekunde berechnen, wofür das "echte" Gerät eine halbe Stunde brauchen würde. Beim Blitzen mit rund 5 s pro Zug müsste man ihn zum Vergleich pro Zug 2,5 Stunden rechnen lassen. Aber wer lässt sich auf so was ein?

Umgekehrt würde Stockfish 8 mit rechnerisch ca. 1.285 N/s laufen und mit der Mephisto III Hardware ( +reichlich RAM (Speicherverbrauch laut Taskmanager >8 MBytes), (-) Konversion auf 32 Bit und (-) ca. 30% der Leistung (vermutlich noch mehr, da 32 Bit-Befehle auf dem 68000 (gemessen an der Ausführungszeit) quasi als zwei 16 Bit-Befehle ausgeführt werden)) zu den schnelleren Rechnern gehören. Ich schätze, dass er auch mit einem Malus von 50 % einsam an der Spitze wäre.

Viele Grüße
Th. Plaschke

By Frank Brenner Date 2016-12-30 15:52

Zitat:

. Beim Blitzen mit rund 5 s pro Zug müsste man ihn zum Vergleich pro Zug 2,5 Stunden rechnen lassen. Aber wer lässt sich auf so was ein?

der cbemu emulitert auf meinem (langsamen) pc den 68000 mit 12 MHZ mit dem Faktor 11.

Der Faktor 1750 kann also um den Faktor 11 verkürzt werden.

Darüberhinaus ist es für einen fairen Vergleich notwendig, die Spielstärke bei ständig größer werdenden Bedenkzeiten zu berechnen um so den Spielstärkezuwachs bei größeren Bedenkzeiten mit in die Wertung einzubeziehen.

Hier profitiert die hocheffiziente (superintelligente) Suche von Stockfish bedeutend mehr (BF etwa 2) als die noch sehr ineffiziente und für heutige Verhältnisse "dumme" Suche des mephisto 3. (BF etwa 5)

By Thorsten Czub Date 2016-12-30 19:26

Naja ich weiß nicht.
Damals gab es keine MB.
32 KB rom und 8 KB RAM.
Und da kann meine auch keine MB im Speicher belegen.

Es wird sehr schwer sein stockfish soweit runterzubrechen das es ein sinnvoller Vergleich ist.

Was nützt es wenn ich das von der Taktfrequenz fair habe. Aber stockfish einen erheblich größeren Teil des Rams bekommt.
Nix mit MB. KB !!

Und maximal 32 KB inklusive bibi haben in das ROM gepasst.
Nix mit großer bibi.

Kein Hash beim Rechnen.

By Thomas Plaschke Date 2016-12-30 20:47

Ich hatte nicht vor, die beiden Programme gegeneinander zu stellen. Auch scheint mir die Thematik nicht durch moralische Wertungen erfassbar (Stichwort: Fairness). Schließlich hatte man beim Stockfish-Projekt auch nicht vor Augen, das Programm für einen Schachcomputer zu bauen, geschweige denn die Vorgabe, mit 32 kB für Code und 8 kB freiem Speicher auszukommen. Ein nicht unerheblicher Teil des Speicherverbrauchs geht bei Stockfish zu Lasten der Zugdarstellung. Ich erzähle da nichts neues. Bitboards sind im Vergleich zur mailbox-Brettdarstellung Speicherfresser. In den 80er Jahren nur auf Großrechnern realisiert, wenn ich mich richtig erinnere. Wer mag, kann ja Stockfish ohne Bitboards zu realisieren versuchen ...

Außerdem benutzt Stockfish mindestens 1 MB für Hashtabellen. I.Ü. kann der M68000 16 MB adressieren. Und PCs mit 16 MB waren ab Mitte der 80er kein Ding der Unmöglichkeit und sogar bezahlbar gewesen ...

Das ist mir aber alles so unwichtig, dass ich mich darüber nicht weiter ereifern möchte. Denn vor allem reizte mich der Vergleich der Programme auf identischer Hardware. Nicht zuletzt deswegen habe ich diesen Vergleich gemacht: Mephisto III würde auf modernen PCs gerade mal Züge im Bereich kilo-Knoten-pro-Sekunde bewerten und umgekehrt der heutige Stockfish durchaus mit damaligen Schachcomputern vergleichbare Knotenleistungen bringen. Ob das im Fall Mephisto III sinvoll ist, wenn die Suche auf 19 Hz beschränkt ist, oder ob sich Stockfish überhaupt auf dem M68000 realisieren lässt, bleibt dabei außen vor. Was Thomas Nitsche damals mit den heutigen Möglichkeiten gemacht hätte, wäre auch interessant zu erfahren

Es ist halt nur so ein Gedankenspiel gewesen.

Viele Grüße
Th. Plaschke

By Thorsten Czub Date 2016-12-30 22:54 Edited 2016-12-30 22:56

Man darf nicht vergessen das die 68000 Hardware 1984 noch sehr sehr teuer war.
Viel wichtiger: Mephisto III lief ja auch auf den 1802 CPUs im Brikett mit 6.1 MHz.

Und dann später im modular/exklusive/München Brett als moduleinschub als MMI mit 8 MHz im 1806.

Und ich korrigiere mich mal: es waren 32 KB ROM bei 4 KB RAM.

Das war schon sehr minimalistisch !!

Der Mephisto III S Glasgow kostete als moduleinschub für die Bretter 3000 DM !!!
Noch teurer die 50 hergestellten Excalibur Geräte im alten ESB Brett.
5000 DM wollte man dafür sehen.

By Michael Scheidl Date 2016-12-31 00:04

Ich hatte seinerzeit ein Mephisto III-Modulset 8 MHz, gebraucht gekauft. Schon erstaunlich daß es bei dieser niedrigen Knotenleistung - so denn stimmte was angzeigt wurde? - vernünftig Schach spielen konnte. Ungefähr so stark wie Onkel Otto der dreimal im Jahr sonntags spielt und keine Ahnung hat. Leute wo man sich nicht sicher ist ob sie überhaupt die Rochaderegel kennen. Auf diesem Niveau spielte Mephisto III. Ich begreife nicht worüber wir hier reden.

By Peter Martan Date 2016-12-31 07:05 Edited 2016-12-31 07:12 Upvotes 1

Michael Scheidl schrieb:

so denn stimmte was angzeigt wurde?

Naja, das war und ist offenbar die Frage, die Alle beschäftigt. Wie ich dem Vortrag entnehme, hat man das damals, als es rauskam auch von verschiedener Seite sehr angezweifelt, in erster Linie von Seiten der Konkurrenz natürlich. Und das war das, was mich auch am Video am meisten belustigt hat, was für eine Geheimniskrämerei da damals stattfand. Eh klar, es wussten nur ein paar Leute überhaupt etwas und das bisschen zählte dafür enorm.

Und jetzt, weil ich mir das habe im Vortrag "erklären" lassen, was der wesentliche Unterschied zu den anderen Programmen gewesen sein soll, versteh' ich's natürlich auch nach wie vor nicht, aber vorstellen kann ich mir schon, dass da eine Knotenzahl noch einmal eine völlig andere Bedeutung und einen anderen Aussagewert hat, wenn z.B. selbst Schlagzüge gar nicht generiert werden müssen, um in ihrer Abfolge schon "statisch" beurteilt werden zu können, und jeder Figur und jedem Feld, das von Figuren besetzt, angegriffen oder gedeckt wird, Werte angerechnet werden je nach der Stellung, die sonst erst dynamisch mit Varianten berechnet werden müssten.

Wenn ich das alles richtig verstanden habe, arbeitete das Programm dadurch auch automatisch mit sehr viel Nullzug ("utopischer" Figuren- Felderwert oder so ähnlich habe ich in Erinnerung, Eval, die für den Fall zustande kommt, dass der Gegner nicht zieht, zum Unterschied von einem realistischen und einem optimistischen solchen) und konnte auf der anderen Seite mit wenig Rechenleistung in einzelnen (z.B. Mattsuche) Richtungen in große Tiefen kommen. Ob da jetzt schon ein wesentlicher Unterschied zu den später sogenannten Singular Extensions bestand oder besteht und oder ob es nicht doch einfach eines der ersten wesentlich auf eingprogrammierten "Wissen" beruhendes Programm war mit sehr aufwendiger statischer Eval und dadurch wenig (Zeit für) brute force- Rechnen, kann ich natürlich auch nicht sagen, und wird wohl weiter eine Frage der Definitionen für die Fachleute bleiben. Wenn die sich da weiter drüber streiten wollen, ob man die Knoten, die da angegeben werden vom Programm und den Branching Factor überhaupt irgendwie sinnvoll mit dem vergleich kann und soll, was heutzutage ja auch immer noch recht umstritten und verschieden von verschiedenen engines ausgewiesen wird, ist mir das eigentlich auch ziemlich schnuppe. Dass Knoten/Zeit und auch time to depth nach wie vor für jedes Programm etwas anderes bedeutet, ist ja ohnehin auch schon ein ziemlich alter Hut.

Michael Scheidl schrieb:

Ich begreife nicht worüber wir hier reden.

Über Schachprogramm- Geschichte, glaube ich, Michael. Ich hab den Link zum Video schon dankenswert gefunden.
Rutsch gut rüber!