Computer Chess Club Archives


Search

Terms

Messages

Subject: Re: Different Hydra personalities against Rybka

Author: Thorsten Czub

Date: 08:03:15 12/13/05

Go up one level in this thread


On December 13, 2005 at 08:35:07, Chrilly Donninger wrote:

>One big error - publishing NullMove - is
>enough. But NullMove was anyway known in the community.
>
>Chrilly

Mephisto III and Colossus chess had nullmove.

Mephisto III was made 1981 and published 1983. and Colossus X was 1989 for
several hardware e.g.
PC and ATARI ST.

Thomas Nitsche tried to publish his concept in ICCA journal. but tony marsland
or another sherriff did not get it, or surpressed the info or whatever PROBLEM
was there.

so i guess it never came into the official archives.


here some text about the mephisto III program:

Das Mephisto 3-Projekt
von Thomas Nitsche

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 Hegener + Glaser eng im Bereich der MEPHISTO
Schachcomputer-Entwicklung zusammen. E.Henne und T.Nitsche haben dabei von
Anfang an die Programme MEPHISTO 1, 2 und 3 entworfen und realisiert, wobei z.B.
die Eröffnungsbibliothek mit Hilfe von Ossi Weiner entstand.
Neuerdings zeichnet P1 in Zusammenarbeit mit R.D.KIein, 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
Sommer '81 standen wir vor der Notwendigkeit ein neues MEPHISTO Schachprogramm
zu konzipieren. Zwar war 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 3 aussehen könnte, hatten wir bereits;-er
sollte noch mehr dem Menschen vergleichbar Schach spielen.
Sorgfältig begannen wir, MEPHISTO 3 zu planen. Alles, was uns einfiel, wurde
aufgeschrieben. Insbesondere hatten wir eine 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 200mal schneller rechnet, als
der 1806-Micro-Prozessor des MEPHISTO.

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:
In Verbindung mit der Ziel-Vorgabe war ein weiteres Problem zu lösen.-Die Wahl
der Progammiersprache. 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 3 gleichzeitig in der jeweils neuesten Programm-Version auf 3
verschiedenen Ziel-Prozessoren läuft: DECPDP11 (alsTest-undTrace-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 3 im Vergleich zu
der schachlichen Seite stark in den Hintergrund getreten; schließlich wußten wir
nach M1 und M2 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 derZieleinengung:
"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 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 sub-sumieren lassen.

Die "Kopec-7-Teststellung"


http://www.thorstenczub.de/sf6.jpg

Zur Klarheit wird an folgendem Beispiel, welches sicherlich vielen bereits aus
Bild der Wissenschaft bekannt ist, die Arbeitsweise von 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 bisherschnellste Brute-Force Programm,
schafft im Mittelspiel etwa die Tiefe 7).

3.) Für uns war es diejenige Stellung, in der MEPHISTO 3 das erste Mal sein
ganzes Können unter Beweis stellen konnte.

Zusammenspiel der Figuren:
Druck auf unbewegliche Figuren (gefesselt, direkt unbeweglich,
überlastet).Deckung, Fesselung, Eröffnungstempi, spezielle Endspielregeln, etc.

2.) 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 Springer
  geopfert. Es werden nur noch Züge angeschaut,
  die diesen Springer oder mehr zurückgewinnen.



"Utopischer Zug":
MEPHISTO 3 opfert zwar den Springer, erwartet aber bei "Nichtstun" die Qualität.

"Optimistischer Zug":
MEPHISTO 3 steht zwar 2 Bauern schlechter, erwartet aber bei "Nichtstun" einen
Springer als Gewinn.

"Realistischer Zug":
Das Ergebnis der Gabel am Schluß Ist bei Springer-Wegzug 2 Bauern, sonst 1
Bauer.

http://www.thorstenczub.de/loesung_sf6.gif

Die Knotenentscheidung:
In einer gegebenen Stellung findet 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).

http://www.thorstenczub.de/knotenentscheidung.gif
http://www.thorstenczub.de/suchbaum.jpg



This page took 0 seconds to execute

Last modified: Thu, 15 Apr 21 08:11:13 -0700

Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.