Das Mephisto-Konzept

DAS MEPHISTO-KONZEPT

Ein "menschenähnlich" denkendes Schachprogramm
von Thomas Nitsche (Programmautor der MEPHISTO-Schachcomputer) März 1982

In dem folgenden Artikel werde ich zum ersten Mal einer breiteren Öffentlichkeit das MEPHISTO-Konzept vorstellen. MEPHISTO (Autoren: E.HENNE, T.NITSCHE) stellt kein starres Programm dar, sondern besteht vielmehr aus einer Menge von Ideen, die wir laufend weiterentwickeln.

Im Gegensatz zur allgemeinen Anschauung liegt die Grundproblematik der Schachprogrammierung nicht darin, möglichst schnell jeden noch so schlechten Zug durchzurechnen, sondern in der möglichst genauen Bewertung einer Schachstellung. Alle unsere Ideen im taktischen und positionellen Bereich sind unter diesem Gesichtspunkt zu betrachten.

Ich möchte den Leser nicht mit technischen Einzelheiten langweilen, wie etwa 'Schnelle Zuggenerierung', 'Genaues statisches Abschätzen von Schlagfolgen' etc., da dies- den Rahmen des Artikels bei weitem sprengen würde. Weiterhin ist es mir aus naheliegenden Gründen nicht möglich, letzte Einzelheiten dort anzugeben, wo eine vorzeitige Veröffentlichung unseren technologischen Vorsprung gefährden würde. Bevor ich genauer auf das MEPHISTO-Konzept eingehe, werde ich für diejenigen Leser, die sich mit dem Fachgebiet noch nicht beschäftigt haben, die wichtigsten Grundbegriffe kurz definieren.

Im Folgenden bezeichne ich mit 'Zug' immer den (Halb-) Zug einer Seite. Der 'Entscheidungsbaum' stellt die möglichen Zugkombinationen ausgehend von einer Ausgangsstellung ('Wurzel') dar, in der ein Zug' gefunden werden soll. Die Astgabeln werden 'Knoten' genannt und entsprechen Stellungen. Knoten sind durch 'Äste' verbunden, die den Zügen entsprechen. Die Tiefe gibt an, wie viele Züge man benötigt, um einen Knoten von der Wurzel aus zu erreichen. Zu jedem Knoten (außer der Wurzel) führt genau ein Ast hin und je nachdem kein, ein oder mehrere Äste weg. Führt kein Ast aus dem Knoten weg, so heißt er 'Endknoten'.

'Gute' Züge sind bei MEPHISTO solche Züge, bei denen die Zugfigur nicht mit Gewinn für den Gegner geschlagen werden kann, d.h. kein Materialverlust droht.

I.A. wird zwischen zwei Konzepten oder auch Typen von Schachprogrammen unterschieden:

SHANNON-A Strategie:

Diese Methode ist auch unter dem Namen 'Brute Force' (Rohe-Gewalt) bekannt. Bis zu einer festen Tiefe werden alle Zugkombinationen angeschaut. Zusätzlich schauen sich manche 'Brute Force'-Programme in den Endknoten noch alle Schlagzüge an.

SHANNON-B Strategie:

Hier wird in einem Knoten eine Vorauswahl unter den möglichen Zügen getroffen und es werden nur vorausgewählte Züge weiter-analysiert. Dieses Konzept ist flexibler als Typ A, hat jedoch den entscheidenden Nachteil, dass bei einer Vorauswahl unter Umständen sinnvolle Opfer bzw. feindliche Drohungen übersehen werden können.

Mit Shannon A oder B werden die heutigen Schachprogramme nur sehr unzureichend charakterisiert. Viele Programme, wie etwa MEPHISTO, sind Mischformen. Folgende Kriterien sind hilfreicher um Schachprogramme zu beschreiben:

Wie lauten die Auswahlkriterien für Züge in einem Knoten (in Abhängigkeit von z.B. der Tiefe)?
Wie lauten die Abbruchkriterien für Zugfolgen (z.B. Zugziel kann potentiell nicht mehr erreicht werden)?
Wieviel 'Schach' wird in einem Knoten gemacht, d.h. wie umfangreich wird eine Stellung schachlich beurteilt? Wird in jedem Endknoten eine umfangreiche Bewertung vorgenommen, oder etwa nur in Knoten der Tiefe 1?

Das taktische MEPHISTO-Konzept:

Gegeben ist stets eine Mindestrechentiefe Min.T (in Abhängigkeit von z.B. der Spielstufe). In der Turnierstufe erreicht MEPHISTO eine Min.T von 3-4.

Es gelten die folgenden Auswahlkriterien und Regeln für den Abbruch der Analyse in den Knoten: Falls für einen Knoten die Rechentiefe kleiner oder gleich Min.T ist, so gilt: Analysiere jeden möglichen Zug weiter.

Bis zu einer gewissen Tiefe arbeitet MEPHISTO als 'Brute Force'-Programm, um nicht, wie andere selektiv rechnende Programme, einfache Opfer beider Seiten zu übersehen. Bei Knoten, die in einer Tiefe größer der Min.T liegen, ergeben sich verschiedene Möglichkeiten:

1. Existieren in einem Knoten eigene hängende Figuren oder hängende Figuren des Gegners, so werden Züge betrachtet, welche die Stellung 'beruhigen' (z.B. Wegziehen oder Deckungszüge, bzw. die hängenden Figuren des Gegners schlagen).
2. Sind 'gute' Schachzüge möglich, so werden diese weiter-analysiert. Im besten Fall ergibt sich daraus ein Mattangriff. MEPHISTO 2 ist in der Lage, im Mittelspiel auf Turnierstufe ein bis zu 4-zügiges Matt zu erkennen (im Endspiel auch bis zu 5-zügig).
3. Bei einem Bauern auf der 7. Reihe wird die Bauernumwandlung weiter analysiert.
4. Falls ein Knoten in der Tiefe Min.T + 1 liegt, und es sind 'gute' Schlagzüge möglich, so werden diese Varianten weiter analysiert.

Die Grundüberlegung bei diesen 4 Regeln lautet: Stabilisierende Züge (z.B. Deckungszüge) oder destabilisierende Züge (z.B. Schachzüge) sollen möglichst genau durchgerechnet werden. Eine statische Analyse (Keine Züge werden weiterverfolgt, die Stellung wird direkt bewertet) liefert für Stellungen, in denen etwa Figuren hängen, oft sehr ungenaue Werte. Die Folge sind ungenaue Zugentscheidungen, sprich 'schlechte Züge'.

MEPHISTO besitzt eine Reihe zeitsparender Abbruchregeln, z.B. lautet eine davon:

Kann MEPHISTO auch bei optimistischster Stellungseinschätzung (Alle eigenen hängenden Figuren können gerettet werden und alle gegnerischen hängenden Figuren können geschlagen werden) den Wert des bisher besten Zuges nicht erreichen, so wird diese Zugkombination abgebrochen. Das heißt in der Praxis: Ist z.B. bereits eine Dame geopfert und hat MEPHISTO nur noch die Möglichkeit einen Turm zu schlagen, so wird die Zugfolge abgebrochen. Besteht dagegen die Möglichkeit eines 'guten' Schachs, so wird dieser Zug weiteranalysiert.

Selbstverständlich benützt MEPHISTO auch eine Reihe exakter Techniken (Alfa-Beta-Algorithmus, Fenstertechnik, Killerheuristik etc.), mit deren Hilfe nicht jede sinnlose Kombination angeschaut werden muss. Mit exakt bezeichne ich die Tatsache, dass das Ergebnis der Zugauswahl durch solche Techniken nicht berührt wird. Der Zeitaufwand für die Zugauswahl wird dadurch erheblich verkürzt (exponentiell für Alfa-Beta-Algorithmus).

Alles bisher Gesagte bezieht sich lediglich auf den taktischen Aspekt des MEPHISTO-Programms. Um aber eine Partie zu gewinnen, ist es nicht damit getan, nur Figurenverluste zu vermeiden oder einen Bauerngewinn zu sehen.

Aus diesem Grund besitzen neuere Spitzen-Schachprogramme eine Reihe von aufwendigen Einzelbewertungen, 'Heuristiken' genannt, mit deren Hilfe sie langfristig nach Materialvorteil streben, kurzfristig aber 'nur' nach positionellem Übergewicht.

Das positionelle MEPHISTO Konzept:

Im Gegensatz zu reinen 'Brote Force'-Programmen kann sich MEPHISTO den Luxus erlauben, ein umfangreiches positionelles Konzept zu entwickeln. Für die einzelnen Figuren auf dem Brett werden dabei unterschiedliche Heuristiken berücksichtigt, von denen ich die wichtigsten aufzähle:

Bauer: Tempo, Vormarsch, Zentrum, sowie neuerdings auch Doppel- und Freibauern. In Zukunft werden noch Muster von Bauernstrukturen, sowie Isolani und rückständige Bauern folgen.
Springer: Tempo, Zentralisierung.
Läufer: Tempo, lange Diagonalen, sowie Fianchetto. Dadurch behandelt MEPHISTO 2 bestimmte Eröffnungen (z.B. Indische Systeme) wesentlich besser als MEPHISTO 1.
Turm: Halboffene und offene Linien, Verdoppelung, hinter Freibauern.
Dame: Zurückhaltung in der Eröffnung, Aktivierung im Mittelspiel.
König: Anstreben einer sicheren Rochadestellung, Rochade-Bauern-Muster, Annäherung an eigene Bauern, Zentralisierung im Endspiel.

Beim allgemeinen Zusammenspiel der Figuren gibt es weiterhin Prioritäten für den Angriff auf den feindlichen König bzw. Deckung der eigenen Stellung und Figuren. Viel gebracht hat für die Spielweise von MEPHISTO 2 das Erkennen von Fesselungen. Das Programm ist jetzt in der Lage, auch komplexe Drohungen im Mittelspiel aufzubauen und zu erkennen. Zur Zeit werden eine Reihe spezieller Endspiel-Heuristiken entwickelt, welche in Zukunft sehr verstärkt an 'Bedeutung gewinnen werden, wie z.B. Opposition, Quadratregel und kritische Felder im Bauernendspiel, richtige Turmpostierung in Turmend-spielen, oder auch Springer-Läufer-Matt-Setzunq.

Selbstverständlich unterscheidet MEPHISTO bei der Anwendung dieser Heuristiken nach Eröffnung, Mittelspiel und Endspiel. In der Eröffnung wird z.B. auf das Tempo (d.h. schnelle Entwicklung) viel Wert gelegt, während der Angriff noch keine Rolle spielt.

Die Einteilung in die Spielphasen ist bei MEPHISTO keine starre Angelegenheit (10 Züge Eröffnung, Endspiel ab Zug 30), sondern richtet sich nach dem Partiestand. Während das Mittelspiel nach etwa 8 Eröffnungstempi einsetzt, ist das Endspiel vom Material abhängig.

In den Heuristiken unterscheiden sich die auf dem Markt angebotenen Schachprogramme z.T. sehr erheblich und entwickeln oft einen eigenen 'Schachstil'. Dies scheint für den Interessenten die Auswahl unter mehreren gleichstarken Mikroschachcomputern fast zu einer persönlichen Geschmacksfrage zu machen. Der begeisterte Computerschach-Spieler, der sich heute für ein bestimmtes System entscheidet, möchte jedoch gerne wissen, wie sich die zukünftige Entwicklung gestalten wird.

Nach meiner Auffassung sind die auf der A-Strategie basierenden Programme weitgehend an einer Schwelle angelangt; sie können wohl noch schneller, aber kaum noch 'besser' werden. Man bedenke dabei, dass selbst eine Geschwindigkeitssteigerung um den Faktor 5 bei dieser Strategie noch nicht einmal einen Halbzug mehr in der Rechentiefe einbringt!

In der Zeitschrift 'DM' (Heft 11/81) habe ich die Voraussage gewagt, dass wir mit unserem Großrechner-Programm 'ORWELL' (Sprache: PASCAL / MODULA 2, Rechner: PDP 11, LILITH, IBM 3033 / 3081) eine Spielstärke (je nach Rechner) von zumindest über 2000 ELO-Punkten erreichen könnten. Bis Ende 1983 hoffen wir dies auch für MEPHISTO realisieren zu können, und damit dem 'menschenähnlich' denkenden Schachprogramm endgültig den Durchbruch zu ebnen.

Links

s.h. auch, Zusammen mit Elmar Henne - Das Mephisto 3-Projekt