Quelltext der Seite Das Mephisto 3-Projekt
← Das Mephisto 3-Projekt
Das '''[[Mephisto III|MEPHISTO 3]]'''-Projekt von Thomas Nitsche aus der Schach Zeitschrift '''"Schach-Echo" 7/{{Erscheinungsjahr|1984}}''' eingescannt und aufbereitet. [[Bild:SchachEcho.jpg|thumb|left|'''Schach-Echo 7/1984''']] == Die Autoren == '''Elmar Henne''' (29 Jahre, Diplom Informatiker) und '''Thomas Nitsche''' (31 Jahre, Diplom Mathematiker) sind Mitbegründer der Münchner Software Firma '''P1 GmbH'''. Seit einigen Jahren befassen sie sich intensiv mit der Entwicklung von Schachprogrammen. Unter anderem haben sie 1980-1982 Experimentalprogramme für den BTX-Einsatz, sowie den Parallelrechner SMS 201 von Siemens entwickelt. Seit 1980 arbeiten P1 und [[Mephisto|Hegener + Glaser]] eng im Bereich der Mephisto Schachcomputer-Entwicklung zusammen. [[Nitsche, Thomas & Henne, Elmar|E.Henne und T.Nitsche]] haben dabei von Anfang an die Programme [[Mephisto]] [[Mephisto I|1]], [[Mephisto II|2]] und [[Mephisto III|3]] entworfen und realisiert, wobei z.B. die Eröffnungsbibliothek mit Hilfe von '''Ossi Weiner''' entstand. Neuerdings zeichnet P1 in Zusammenarbeit mit '''R.D. Klein''', vielen aus der NDR-Informatik-Serie und von seinen Büchern her bekannt, auch für die Entwicklung der "schnellen"-bzw. der Mephisto-Experimental-Hardware, verantwortlich. == Der Anfang == [[Bild:Mephisto_III.jpg|thumb|250px|right|Mephisto 3, das '''Brikett''']] Sommer '[[1981|81]] standen wir vor der Notwendigkeit ein neues Mephisto Schachprogramm zu konzipieren. Zwar war [[Mephisto II|MEPHISTO 2]] ein gutes Programm, aber erstens geht die Entwicklung weiter und zweitens hatten wir das Gefühl, daß trotz laufender Verbesserungen eine Grenze absehbar war. Etwas Neues mußte passieren. Vorstellungen davon, wie [[Mephisto III|MEPHISTO 3]] aussehen könnte, hatten wir bereits: * er sollte noch mehr dem Menschen vergleichbar Schach spielen. Sorgfältig begannen wir, [[Mephisto III|MEPHISTO 3]] zu planen. Alles, was uns einfiel, wurde aufgeschrieben. Insbesondere hatten wir eine [[Mephisto III|MEPHISTO 3]] Eigenschaftsliste aufgestellt, die all das enthalten sollte, was wir uns für die Zukunft unter einem guten Schachprogramm vorstellten. Sicherlich waren und sind die Ziele hochgesteckt, doch mit weniger wollten wir uns nicht zufrieden geben. Uns war klar, daß die Brute-Force-Programme nur noch minimal zu steigern seien. * Der jetzige Weltmeister Cray-Blitz verlor erst kürzlich 4Partien klar gegen David Levy (etwa 2300 Elo). Anzumerken ist, daß Cray-Blitz mit einem Rechner arbeitet, der etwa 200 mal schneller rechnet, als der [[1806]]-Micro-Prozessor des Mephisto. == [[Mephisto III|MEPHISTO 3]] Ziele == * Klare Unterscheidung zwischen einer ruhigen und einer dynamischen Stellung. * Das Programm soll in der Lage sein zu planen und zielgerichtet zu handeln (z.B. Bauerndurchmarsch). * Die Stellungsbewertung soll Feinheiten in jeder Tiefe des Baumes erkennen (z.B. rückständige Bauern). * Taktisch erzwungene Zugfolgen sollen durchgerechnet werden. Taktische Wendungen am Ende einer solchen Zugfolge sollen erkannt werden. Insbesondere sollen lange Mattkombinationen gesehen werden. * Abspiele in positionell vorteilhafte Stellungen sollen erkannt werden (z.B. gewonnenes Endspiel). * Opferkombinationen der eigenen Seite wie des Gegners sollen gesehen werden. * Bei Abspielen (erzwungene Zugfolgen) soll der Baum nicht exponentiellen Charakter haben. * Der [[Horizonteffekt]] soll weitgehend eliminiert werden. == Die technischen Aspekte == [[Bild:MM_I_innen.jpg|thumb|left|Mephisto MM I Modul von innen]] In Verbindung mit der Ziel-Vorgabe war ein weiteres Problem zu lösen. - Die Wahl der Programmiersprache. Assemblerprogrammierung kam nicht in Frage, denn unsere Zielvorgaben enthalten insbesondere die Forderung nach viel Schachwissen, welches aber in adäquater Zeit nur mit einer angepaßten höheren Sprache zu lösen ist. PASCAL, von uns in anderen Bereichen bevorzugt, schied aus, dazu ineffiziente ablauffähige Programme entstehen (Faktor 5-6 gegenüber Assembler), ebenso "Nicht-Sprachen" wie BASIC, FORTRAN etc. In einem kleinen Fachzeitungs-Artikel stießen wir auf '''CDL2''', das unseren Forderungen sehr nahe kam: === Effizienz === nur Faktor 1,5-2,0 langsamer als Assembler. === Möglichkeit der '''angepaßten Formulierung''' === hohe Sprach-Konstrukte, wie etwa Freibauer, rückständiger Bauer etc. sind direkt und bequem, nach einmaliger Definition, im Programm als Begriffe verfügbar. === '''Portabilität''' === Die Anpaßbarkeit an neue Prozessoren ist mit vertretbarem Aufwand möglich, so daß [[Mephisto III|MEPHISTO 3]] gleichzeitig in der jeweils neuesten Programm-Version auf 3 verschiedenen Ziel-Prozessoren läuft: DEC '''PDP11''' (als Test-und Trace-Version), RCA '''[[1806]]''' (als Markt-Normal-Version) und Motorola '''[[68000]]''' (als Spitzen-Version). Einige Sätze zu den mehr technischen Teilen des Programms. Sicherlich stellt die Art der legalen Zuggenerierung mit all ihren Facetten (schnell/langsam, legal/pseudolegal) ein Problem dar. Dies ist aber bei [[Mephisto III|MEPHISTO 3]] im Vergleich zu der schachlichen Seite stark in den Hintergrund getreten; schließlich wußten wir nach M1 und M 2 ziemlich genau, wie ein effizienter Zuggenerator auszusehen hat. Etwas aufwendiger war da schon die EA-Konzeption. Der Ruf nach Systematik, Klarheit und Einfachheit wurde laut. === Folgende gänzlich neue Zielvorgaben waren zu beachten === * Die Information über das Spielgeschehen ist jederzeit, (unabhängig, ob der Computer am Zug ist oder nicht) abrufbar. * Die Benutzereingaben sind durch eine Menüwahl gekennzeichnet, die klar unterschiedene Bereiche des Programms ansprechen. :'''MEMO:''' Spielhistorie, Züge vor und zurück etc. :'''POS:''' Kontrolle der aktuellen Spielsituation, neue Stellung aufsetzen etc. :'''LEV:''' Kontrolle der Spielweise Level, Problem, Zufall, Zeitverhalten etc. :'''INFO:''' Information über die aktuelle Zugentscheidung, Hauptvariante, Wert, Zeit, Knoten, Tiefe etc. == Menschliche Spielweise und der erste Blick == Stellen Sie sich vor, Sie rechnen eine Schach-Kombination durch. Sie haben einen netten Schlüsselzug gefunden, etwa eine Gabel mit Opfer, und der Gegner hat nur wenige Antworten. Bei ihnen und bei Mephisto wird jetzt vor allen Dingen eine Fähigkeit gefordert: * Auf einen '''"ersten Blick"''' zu entscheiden, welche vernünftigen Züge es für den Gegner gibt und was es darauf lohnt, weiterzuspielen. Gibt es in einer Stellung lohnende Züge, so müssen diese weiterverfolgt werden, gibt es keine, so muß die Stellung bewertet werden und damit die hinzuführende Zugfolge. Man hat dafür nur wenig Zeit. Nach '''De Groot''' bewerten Großmeister etwa 180 Stellungen pro Zug, haben also für diesen ersten Blick jeweils nur eine Sekunde Zeit. Das Problem des ersten Blickes ist nicht trivial. Werden in einer Stellung systematisch zu viele "interessante" Züge ausgewählt, so verliert man sich im Dschungel der Kombinationen, werden aber zu wenige ausgesucht, so übersieht man evt. eine gewinnversprechende Variante. D.h. die ausgewählten Züge sollen möglichst exakt bewertet werden und sollte ein Zug mit interessanten Möglichkeiten vorkommen, so sollte er auch mit hoher Sicherheit gefunden und entsprechend bewertet werden. == Die Zieleinengung == Wesentlich beim Erfolg dieser Idee ist das Konzept der Zieleinengung: "Je tiefer man sich in einer Kombination befindet, desto weniger wird nach sensationellen Zügen gesucht." Es gilt jedoch der Grundsatz, daß ein Zug, der den Gegner zu einer einzigen klar definierten Reaktion zwingt, immer angeschaut wird. - Der Entscheidungsbaum (Darstellung der untersuchten Varianten) wird durch solche Züge '''nicht''' wesentlich ('''exponentiell''') größer. == [[Mephisto III|MEPHISTO 3]] unterteilt den Entscheidungsbaum in 3 Abschnitte == * '''Utopische''' Züge (gut, falls der Gegner nichts tut): Eine Stellung kommt in einer '''Tiefe''' von etwa '''1-3''' vor. Der Beginn einer Kombination. Fast jeder irgendwie erfolgversprechende Zug wird selektiert, auch wenn die Wahrscheinlichkeit des Erfolges recht gering ist. Der Mensch nennt manche dieser Züge Opfer. * '''Optimistische''' Züge (gut, falls der Gegner nur die zweitbeste Antwort hat): Die Kombination hat eine '''Tiefe''' von '''4-8''' erreicht. Nur noch Züge mit einer Trefferwahrscheinlichkeit von größer als 30% werden selektiert. I.A. sind dies Züge, bei denen hohe Figuren angegriffen werden, Schach gedroht wird, etc. Diese Züge sollen aber selbst nichts opfern. * '''Realistische''' Züge (gut, falls der Gegner den besten Gegenzug wählt): Die Stellung kommt in einer '''Tiefe größer als 8''' vor. Nur noch klare Abwicklungen werden untersucht. D.h. das Programm greift nicht mehr auf Verdacht an, sondern verfolgt Züge mit hoher Trefferrate. Etwa eine angegriffene Figur in Sicherheit bringen, d.h. realisieren, daß die Figur auch wirklich sicher ist und nicht etwa gefesselt oder überlastet ist. == Noch eine kurze Bemerkung zum Wesen der Kombination beim Schachspiel == "Finde einen Schlüsselzug, der dem Gegner zu einer oder zu wenigen Antworten zwingt; setze 1-2 Züge mit Druck fort; rechne sie i.A. klare Abwicklung durch." Wenn Sie als Leser die mehr oder weniger berühmten Kombinationen unter diesem Gesichtspunkt betrachten, so werden Sie feststellen, daß sich 90%-95% unter diesem Schema subsumieren lassen. == Die "Kopec-7-Teststellung" == Zur Klarheit wird an folgendem Beispiel, welches sicherlich vielen bereits aus Bild der Wissenschaft bekannt ist, die Arbeitsweise von [[Mephisto III|MEPHISTO 3]] verdeutlicht. 2-3 Gründe machen das Beispiel interessant. 1.) Als die Stellung etwa 30 menschlichen Schachspielern vorgelegt wurde (es war nicht klar, ob die Lösung taktischer oder positioneller Natur sei), war nur ein einziger, ein Großmeister, in der Lage, den Schlüsselzug innerhalb der vorgegebenen Zeit zu finden. 2.) Alle mir bisher bekannten Brute-Force Programme scheitern an dieser Stellung wegen eines interessanten '''"Horizonteffektes"'''. Der Zwischenzug - La4xc2 (Horizont) schiebt den für dei Kombination entscheidenden Zug - Bf6-f7 (Gabel- und kein Schlagzug) in die Tiefe 7 und das Ansetzen der Schlagfolgen in dieTiefe9. Ein Brute-Force Programm braucht somit eine Tiefe von 8, um den Schlüsselzug zu finden (BELLE, das bisher schnellste Brute-Force Programm, schafft im Mittelspiel etwa die Tiefe 7). 3.) Für uns war es diejenige Stellung, in der [[Mephisto III|MEPHISTO 3]] das erste Mal sein ganzes Können unter Beweis stellen konnte. '''Partie: Golyak - Gaiduk''' [[Bild:M3-Kopec-7.png]] Sh5-f6 Bg7xf6 Be5xf6 Se7-g6 Bf6-f7 0,53 -0,54 Se7-c6 Bf6-f7 0,53 -0,54 La4xc2 Dd1xc2 Se7-g6 Bf6-f7 -0,53 -0,54 Se7-c6 Bf6-f7 -5,70 -0,54 0,53 -5,70 Sb8-c6 Bf6-f7 2,14 0,53 -2,14 La3-b4 -0,14 -0,54 Sb8-d7 Sf6xe8 0,53 -0,54 La4xc2 La3xe7 Lc2xd1 Ta1xa5 Ld1xe2 Sf6xg8 Le2xf3 Ta5-c5 Kc8-d7 -0,35 0,34 -0,35 0,34 Sf6xe8 Tg8xe8 Tf3-e3 0,12 Tf3-f2 0,00 0,34 -0,35 0,34 -0,35 Le2xd1 Da5xa1 -0,35 0,34 -0,35 0,34 Sf6xe8 Lc2xd1 -0,35 0,34 Dd1xc2 Bg7xf6 Be5xf6 Se7-g6 Bf6-f7 0,53 -0,54 Se7-c6 Bf6-f7 5,70 -0,54 0,53 -0,54 0,53 -5,70 Bh7-h6 Sf6xe8 0,53 -0,54 Te8-f8 Sf6xg8 0,53 -0,54 Tg8-h8 Sf6xe8 0,53 -0,54 Tg8-f8 Sf6xe8 0,53 0,53 -0,54 h5xf6 g7f6 e5f6 Le2xc4 d5xc4 La3-b4 Da5-b5 -0,54 0,53 La3xe7 Te8xe7 -0,54 Baum: 1 127.194 0,53 0287 === Folgendermaßen findet [[Mephisto III|MEPHISTO 3]] die Lösung === * '''"Utopischer Zug":''' [[Mephisto III|MEPHISTO 3]] opfert zwar den Springer, erwartet aber bei "Nichtstun" die Qualität. [[Bild:M3-U.png]] * '''"Optimistischer Zug":''' [[Mephisto III|MEPHISTO 3]] steht zwar 2 Bauern schlechter, erwartet aber bei "Nichtstun" einen Springer als Gewinn. [[Bild:M3-O.png]] * '''"Realistischer Zug":''' Das Ergebnis der Gabel am Schluß ist bei Springer-Wegzug 2 Bauern, sonst 1 Bauer. [[Bild:M3-R.png]] == Die Knotenentscheidung == In einer gegebenen Stellung findet [[Mephisto III|MEPHISTO 3]] unabhängig von der Tiefe folgende taktisch motivierten Züge in etwa einer halben Sekunde ([[1806]]-Modular) bzw. einer zehntel Sekunde ([[68000]]-Excalibur). === Gabel === [[Bild:M3-1.png]] === Abzugsangriff === [[Bild:M3-2.png]] === Angriff auf eingesperrte Figur === [[Bild:M3-3.png]] === Gegenpläne: "Gegen-Bauern-durchmarsch" === [[Bild:M3-4.png]] === Angriff auf überlastete Figur === [[Bild:M3-5.png]] === Angriff auf gefesselte Figur === [[Bild:M3-6.png]] === Schlagzug mit rückschlagen einer unbeweglichen Figur === [[Bild:M3-7.png]] === Bauern aufhalten === [[Bild:M3-8.png]] === Schach mit "0 Antworten" === [[Bild:M3-9.png]] === Schach mit "1 Antwort" === [[Bild:M3-10.png]] === [[Mephisto III|MEPHISTO 3]]-Endspielpläne: Plan: Bauerndurchmarsch === [[Bild:M3-11.png]] === König ins Quadrat === [[Bild:M3-12.png]] == Weitere Kriterien == Zusätzlich zum prinzipiellen Finden dieser taktischen Züge muß [[Mephisto III|MEPHISTO 3]] aber noch einiges mehr bewältigen: === Stellungsbewertung === Die Stellung wird nach '''positionellen Kriterien''' bewertet (Stellungsbewertung) In jeder Tiefe, aber in Abhängigkeit von Eröffnung, Mittel- und Endspiel: * Bauer: Zentrum, Doppel, isoliert, Frei, Duo, rückständig, Vorposten, Hebel, blockiert, etc. * Springer: Zentrum, Vorposten, Entwicklung, etc. * Läufer: Lange Diagonalen, Fianchetto, Vorposten, Entwicklung, Paar, etc. * Turm: Offene-, Halboffene-Linien, Verdoppelung, hinter Frei-Bauern, hinter potentielle Hebel, 7.Reihe etc. * Dame: Aktivität, siehe partiell Turm, etc. * König: Sichere Rochadenstellung (Muster der Bauern, Kontrolle der Umfelder durch Figuren), Angriff auf den König, etc. * Zusammenspiel der Figuren: Druck auf unbewegliche Figuren (gefesselt, direkt unbeweglich, überlastet),Deckung, Fesselung, Eröffnungstempi, spezielle Endspielregeln, etc. === Suche === Für jeden einzelnen Zug muß neu entschieden werden, ob er weiterverfolgt werden soll oder ob dies keinen Sinn mehr macht. Einige Fälle sind vorstellbar: * Bis jetzt ist noch nichts passiert, :- alle taktisch interessanten Züge werden weiter analysiert. * Eine nette Kombination ist gefunden, mit der dem Gegner z.B. die Qualität abgenommen wird. :- Nur Züge, die mehr als diese Qualität erwarten lassen, z.B. einen Bauerndurchmarsch oder eine Mattdrohung, werden selektiert. * Das Programm hat bereits z.B. einen Springergeopfert. :- Es werden nur noch Züge angeschaut, die diesen Springer oder mehr zurückgewinnen. [[Bild:GlasgowS.jpg|thumb|left|240px|[[WMCCC|Weltmeister]] [[1984]] in Glasgow]] [[Kategorie:Stellungstests]] [[Kategorie:Schachcomputer]] [[Kategorie:Glossar]] [[Kategorie:Nitsche, Thomas]] [[Kategorie:Henne, Elmar]]
Vorlage:Erscheinungsjahr (Quelltext anzeigen)
Zurück zur Seite Das Mephisto 3-Projekt.