Bewirkt Zugzwang im Schach eine Art Zeitdilatation?

By Thomas Hall Date 2009-10-05 09:20

Immer wieder scheitern auch (oder gerade) moderne
Schachengines an Zugzwangstellungen wie dem schon neulich
gesehenen Matt in 2:

Deswegen habe ich mich gefragt, was eigentlich am Zugzwang so
besonders ist.

Laut Wikipedia gilt:

"Mit Zugzwang wird in Spielen eine Situation bezeichnet, in
der ein nachteiliger Zug ausgeführt werden muss. Diese
Situation kann nur in Spielen eintreten, bei denen eine
Zugpflicht besteht, also beispielsweise beim Schach, nicht
aber beim Go."

Was in dieser Definition vielleicht nicht auf dem ersten Blick
deutlich wird, ist die Rolle der Zugpflicht. Durch diese wird
nämlich im Schach ein Phänomen eingeführt, das ich als
"Schachzeit" bezeichnen möchte.

Im Schach gibt es nämlich zweierlei Art von Zeiten. Da ist
einmal die reale Zeit, innerhab der eine Partie von zwei
Schachspielern gespielt wird. Die Dauer der Partie wird durch
die Bestimmungen der FIDE geregelt.

Dann gibt es aber auch die Zeit, die innerhalb des Schach-
spiels dafür sorgt, daß eine Partie voranschreitet, und diese
wird durch die Zugfolge definiert. Die Zugfolge ist unabhängig
von der Realzeit, wie man leicht feststellen kann, wenn man
sich z.B. die gedruckte Liste der Züge anschaut.

Phänomene der Schachzeit werden auch als "dynamisch"
bezeichnet, dazu gehören u.a. der Zugzwang und auch das
Gambit. Ein Gambit macht sich nämlich immer die Tatsache
zunutze, daß ein Spieler, der in der Eröffnung den Gambit-
bauern nimmt, "Schachzeit", in diesem Falle auch "Tempo"
genannt, verliert. Das verlorene Tempo hätte er nämlich
eigentlich dazu benutzen müssen, seine Eröffnung voran-
zutreiben, aber durch das Nehmen des Bauern fehlt ihm nun die
Zeit, das zu tun, und er kann nur hoffen, daß er später noch
Gelegenheit zum Ausgleich dieses Verlustes findet.

An diesem Beispiel wird deutlich, daß die Einheit der
"Schachzeit" das Tempo ist.

Während nun beim Gambit der Spieler, der das Gambit annimmt,
ein Tempo verliert, hat der Spieler, der im Zugzwang ist,
eigentlich ein Tempo zuviel, denn er möchte liebend gerne auf
einen Zug verzichten, aber die unerbittliche "Schachzeit"
treibt ihn voran, zunächst in einen ernsten Nachteil, danach
meist zur Niederlage.

Aber heißt das nicht auch, daß der Ablauf der Schachzeit
irgendwie aus dem Rhythmus gekommen ist, und könnte das nicht
auch der tiefere Grund sein, warum besonders moderne
"Alpha-Beta"-Varianten scheitern?

Denn schon der normale Minimax-Algorithmus basiert ja darauf,
daß alles, was ein Spieler tut, eigentlich schlecht für den
anderen ist und umgekehrt. Hier gibt es aber plötzlich eine
Situation, in der der im Zugzwang befindliche Spieler
praktisch FÜR den Gegner zieht, also könnte man fast
behaupten, der andere Spieler könnte genausogut zweimal
hintereinander ziehen.

Philosphisch betrachtet ist es schon sehr merkwürdig, daß man
den ABLAUF der "Schachzeit" durch Handlungen beeinflussen
kann, etwas, was zunächst einmal im realen Leben absolut
ungewöhnlich ist. Aber laut der speziellen Relativitätstheorie
wissen wir, daß für einen Reisenden, der sich mit seinem
Raumschiff nahe der Lichtgeschwindigkeit bewegt, die Zeit
langsamer als auf der Erde vergeht. Dieser Effekt wird
Zeitdilatation genannt.

Nun ja, der Vergleich scheint vielleicht etwas weit hergeholt,
aber trotzdem ist jetzt klarer, daß z.B. die Nullmove-Technik,
die wahrscheinlich in fast allen modernen Engines zum Einsatz
kommt und die es bei der Zugberechnung einer Seite ermöglicht,
zwei Züge auszuführen, beim Zugzwang von der falschen
Voraussetzung ausgeht, nämlich daß das Zugrecht einen Vorteil
darstellt. So ist es kein Wunder, daß immer wieder Engines am
Zugzwang scheitern.

Was meint Ihr?

Grüße, Thomas.

By Werner Mueller Date 2009-10-05 11:12

Dieser Effekt wird Zeitdilatation genannt.

So habe ich zukünftig wenigstens eine wissenschaftliche Erklärung, wenn ich in einer Partie ganz alt aussehe.

By Benno Hartwig Date 2009-10-05 13:45 Edited 2009-10-05 13:48

Zitat:

Philosphisch betrachtet ist es schon sehr merkwürdig, daß man
den ABLAUF der "Schachzeit" durch Handlungen beeinflussen
kann

Aus diesem Grunde finde ich die Assoziation mit 'Zeit' oder 'Schachzeit' irgendwie unpassend.
Schachstellungen sind Zustände des Spiels, die halt gemäß den Regeln in Zusammenhang miteinander stehen.
'Schachzeit' würde ich ansonsten nur strickt mit der Zugnummer identifizieren (und dann lohnt natürlich die Einführung dieses Begriffs nicht).

Die Wendung 'ein Tempo verlieren' mag ja noch angehen.
"Ich habe weniger Züge für die Entwicklung nutzen können"
wird halt bildhaft formuliert mit
"Ich habe Zeit bei der Entwicklung verloren"

Zugzwang
Natürlich ist es technisch überhaupt kein Problem, Engines total unempfindlich zu machen ggü. solchen Zugzwang-Fehlern!
Indem man hier aber eine nassforsche Implementierung einbaut (spekulierend), gewinnt man in der weit überwiegenden Zahl der Fälle erheblich an Performance, und nur ganz selten übersieht man was. Das wird dann halt in Kauf genommen.
"Das Programm hat 100 ELO mehr!" wirkt halt verkaufsfördernder als "Es lässt sich nicht durch Zugzwangstellungen verwirren!"
Aber fallen denn alle Engines auf jede Zugzwang-Problematik herein? Da hat sich doch (wohl dank Mischstrategien) einiges getan, oder?

Benno

By Michael Scheidl Date 2009-10-05 16:20

So ist es, man findet ja Engines die oben das #2 sehen, und zwar starke Engines die zweifellos Nullmove enthalten. "Verified nullmove" war in den letzten Jahren oft bei techn. Enginebeschreibungen zu lesen und ist (wie auch Wikipedia ausführt) eine verbesserte Technik, die Probleme in Zugzwangstellungen umgeht.

Etwas anderes an das ich mich erinnere ist, daß manche Engines (möglicherweise Crafty) Nullmove einfach unterhalb eines gewissen Materialstandes abschalten, weil ja Zugzwang typischerweise erst bei wenigen Steinen wirklich wichtig wird. Echter Zugzwang im Mittelspiel ist so extrem selten daß man ihn vernachlässigen kann, aber in manchen Wenigsteiner-Positionen kann er entscheidend sein.

Daß Nullmove ein prinzipielles Problem mit Zugzwang hat, wissen Computerschachfans seit mindestens 10 Jahren. Bald nachdem man Engines hatte, die an sich durch Nullmove deutlich verstärkt worden waren, wurden solche Beispiele ähnlich obigem gefunden. Aber es ist ein Randproblem und wurde dann, allgemein gesagt, abgemildert. Vielleicht ist das nicht bei allen Engines gleich gut gelungen.

Man sollte allerdings Fälle wo nur ein längeres Matt gespielt wird (nur ein Schönheitsfehler), von solchen unterscheiden wo das richtige Erkennen eines Zugzwanges über einen halben oder ganzen Punkt entscheidet.

By Roland Rösler Date 2009-10-05 18:40

[quote="Michael Scheidl"]Daß Nullmove ein prinzipielles Problem mit Zugzwang hat, wissen Computerschachfans seit mindestens 10 Jahren. Bald nachdem man Engines hatte, die an sich durch Nullmove deutlich verstärkt worden waren, wurden solche Beispiele ähnlich obigem gefunden. Aber es ist ein Randproblem und wurde dann, allgemein gesagt, abgemildert. Vielleicht ist das nicht bei allen Engines gleich gut gelungen.[/quote]
Nullmove hat kein Problem mi Zugzwang, sondern blendet den Zugzwang einfach aus. Und Zugzwang ist auch kein Randproblem, sondern fundamental in Endspielen (okay, möglicherweise ist für Dich ja das Endspiel ein Randproblem!

).
Wer keine Ahnung von Zugzwang hat, kann auch keine Endspiele spielen; so einfach ist das! Und in Engine-Matches gewinnt heutzutage der Einäugige das Endspiel. Und Zugzwang hat auch nicht unmittelbar was mit der Anzahl der Figuren auf dem Brett zu tun. Hat man es mit einer blockierten Stellung auf einem Flügel des Bretts zu tun, können auf der anderen Seite des Bretts leicht Zugzwangstellungen entstehen (siehe die meistdiskutierte Studie in diesem Forum).
"Verified nullmove" ist ein schönes Schlagwort! Bei Fritz 11 und 12 hat der Anwender die Zugzwangerkennung manuell! zuzuschalten (Nullmove abschalten)! Rybka erkennt Zugzwang meist viel zu spät (immerhin erkennt er jetzt, wenn er den Gegner im nächten Halbzug in Zugzwang setzen kann)! Gute Zugzwangerkenner sind Fritz 10 und Shredder (bis einschliesslich Version 12)!

By Michael Scheidl Date 2009-10-05 20:38

Bitte genauer lesen anstatt mich über Endspiel & Zugzwang belehren zu wollen, als wäre ich ein Schachanfänger.

Was schrieb ich denn oben im zweiten Absatz? Um mich zu wiederholen, "(...) weil ja Zugzwang typischerweise erst bei wenigen Steinen wirklich wichtig wird. Echter Zugzwang im Mittelspiel ist so extrem selten daß man ihn vernachlässigen kann, aber in manchen Wenigsteiner-Positionen kann er entscheidend sein."

Darüber wieviel Bedeutung man Zugzwang im Schachspiel insgesamt ganz genau beimessen sollte, möchte ich nicht diskutieren.

By Thomas Hall Date 2009-10-05 18:18

Hallo Benno,

[quote="Benno Hartwig"]
Aus diesem Grunde finde ich die Assoziation mit 'Zeit' oder 'Schachzeit' irgendwie unpassend.
Schachstellungen sind Zustände des Spiels, die halt gemäß den Regeln in Zusammenhang miteinander stehen.
'Schachzeit' würde ich ansonsten nur strickt mit der Zugnummer identifizieren (und dann lohnt natürlich die Einführung dieses Begriffs nicht).

Ja, aber diese Zustände stehen nicht nur in einem rein
numerischen Zusammenhang wie in einer mathematischen Folge.
Nein, man kann jedem dieser Zustände einen Zeitpunkt in der
Realzeit zuordnen, und wenn eine Zugliste nicht nur die Züge,
sondern auch die Bedenkzeiten enthält, kann man diese
Zuordnung auch noch im Nachhinein wieder herstellen.

Dafür, daß man in diesem Zusammenhang eigentlich immer von
"Zeit" (vielleicht nicht explizit von "Schachzeit") gesprochen
hat und nicht nur von einer einfachen Zugabfolge, spricht
auch der Begriff "Tempo" (Wortherkunft aus dem Italienischen,
tempo = Zeit), der nach allgemeinen Verständnis ein Maß für
den Faktor Zeit im Schachspiel ist.

Du gibst ja auch selbst zu, daß man ein Tempo verlieren kann,
und das bedeutet "greifbare" Zeit, nicht nur ein Bild. Ferner
ergibt sich die Zugabfolge auch aus einem inneren Kausalzu-
sammenhang, denn Züge können ja nicht beliebig umgeordnet
werden. Die kausale Abfolge von Ereignissen ist ein wichtiges
Kennzeichen eines Zeitablaufs.

Man kommt also eigentlich um die Dimension "Zeit" im Schach
nicht herum, und hier ist nicht die Wettkampfzeit gemeint.

Zitat:

Zugzwang
Natürlich ist es technisch überhaupt kein Problem, Engines total unempfindlich zu machen ggü. solchen Zugzwang-Fehlern!

Ja, das bestreite ich auch nicht, aber es wird schwierig, wenn
man als Programmierer Techniken wie "Nullmove" benutzt, und
kann man darauf in heutiger Zeit verzichten, wo es mehr denn
je darauf ankommt, möglichst schnell in große Tiefen des
Variantenbaumes zu kommen? Manche Engines verzichten im
Endspiel auf "Nullmove", da hier Zugzwang häufiger auftritt,
aber das Ganze bleibt ein Kompromiss. Es ist für den Benutzer
halt nur ärgerlich, wenn eine Top-Engine, für die er einen
Batzen Geld ausgegeben hat, noch nicht einmal alle "Matt in 2"-
Aufgaben lösen kann.

Wir werden sehen, wie die Entwicklung hier weitergeht.

Grüße, Thomas.

By Benno Hartwig Date 2009-10-05 19:48

[quote="Thomas Hall"]Nein, man kann jedem dieser Zustände einen Zeitpunkt in der
Realzeit zuordnen, und wenn eine Zugliste nicht nur die Züge,
sondern auch die Bedenkzeiten enthält, kann man diese
Zuordnung auch noch im Nachhinein wieder herstellen.

Deiner Auffassung der Sinnhaftigkeit von 'Zeit' folge ich nicht.
Schachspiel ist eher vergleichbar einem Automaten aus der Informatik mit seiner Zustandsmenge.
Die Unterschiede zu dem üblichen Begriff 'Zeit' empfinde ich als zu gravierend.
Aber darüber lohnt sicher kein Streit.

Zitat:

Es ist für den Benutzer
halt nur ärgerlich, wenn eine Top-Engine, für die er einen
Batzen Geld ausgegeben hat, noch nicht einmal alle "Matt in 2"-
Aufgaben lösen kann.

Das stimmt natürlich.
Ich dachte auch daran, dass vielleicht ein Kompromiss darin bestehen könnte, dass Nullmove immer in z.B. 33% der Nominaltiefe nicht gemacht wird. Dass würde vielleicht die Suche nicht so schrecklich verlangsamen, aber die Engine würde die Zugzwang-matt-in-2 finden in der Tiefe, in der sie ansonsten die matt-in-6 findet.
Matt-in-3, wo sonst schon matt-in-9 gefunden wird.
Immerhin.
Schon leichter verzeihbar, finde ich.
(Und nun sollte ich mich doch mal mit deiner Stellung beschäftigen, dachte ich doch eigentlich, dass jett bereits derartige Kompromisslösungen Standard sind. Aber dan kann ich mich täuschen!)

Benno

By Thomas Hall Date 2009-10-07 11:25 Edited 2009-10-07 11:30

Hallo Peter,

Du sprichst ein interessantes Problem an:

Welche Beziehung zwischen dem Fortschritt der Zeit in einer
Schachpartie und dem Fortschritt dieser Schachpartie selbst
gibt es?

Ganz allgemein könnte man hier vom "Altern" einer Schachpartie
reden, und laut Spielregeln strebt sie wie alles Vergängliche
auch auf ein Ziel zu, das ja im allgemeinen das Schachmatt
sein sollte, aber sehr oft, wie wir wohl wissen, nur ein Remis
ist.

Dabei kann man einem zwischenzeitlichen Spielstand oft nicht
genau ansehen, wie "alt" die zugehörige Partie ist, d.h.
wieviel Züge zu diesem Zustand geführt haben, besonders, wenn
es Zugwiederholungen gab. Diese können ja, solange es hinrei-
chend wenige sind, die zu derselben Stellung führen, auch
schon mal in Großmeisterpartien auftreten und werden dann oft
genug dazu benutzt, um "Zeit zu schinden", denn Menschen
brauchen manchmal etwas länger, um sich zu einem entschei-
denden Zug aufzuraffen.

Objektiv gesehen halten Zugwiederholungen eine Partie länger
jung, und wie es aussieht, kann man auch hier von Zeitdila-
tation reden, denn man darf ja nicht vergessen, daß das
Zeitmaß hier das Tempo ist und nicht die reale Zeit, die man
auf der Uhr ablesen kann. Aber vielleicht kommt es hier, wie
auch oft in der Relativitätstheorie, auf den Standpunkt des
Betrachters an, denn ein neutraler Beobachter (im Schach oft
Kibitz genannt), der zu einem beliebigen Zeitpunkt die Partie
betrachtet, mag das anders sehen als jeder der beiden Spieler.

Wo diese Problematik gerade hinsichtlich der Schachengines am
deutlichsten wird, ist das Phänomen der Festung, denn hier
können beide Seiten noch viele Züge machen, aber die Partie
"altert" eigentlich nicht weiter, und was nicht weiter altert,
ist endweder tot oder unsterblich.

Engines, die einen solchen Zustand erkennen wollen, müssen
also quasi einen Sinn für den "Fortschritt" einer Partie
haben. Wenn das einfach zu realisieren wäre, gäbe es schon
Engines, die so etwas können. Ob Pruning-Techniken, egal ob
Nullmove oder Futility-Pruning, dabei helfen, ist in diesem
Zusammenhang mehr als fraglich.

Grüße, Thomas.

By Michael Scheidl Date 2009-10-07 12:11

[quote="Thomas Hall"]
Engines, die einen solchen Zustand erkennen wollen, müssen
also quasi einen Sinn für den "Fortschritt" einer Partie
haben. Wenn das einfach zu realisieren wäre, gäbe es schon
Engines, die so etwas können. [/quote]
Das ist - jedenfalls im Verlauf einer Partie - einfach zu realisieren, die Programmierer interessieren sich dafür nur nicht. Denn sie sagen, dann ist es eh schon zu spät. Sie wollen gewinnen. Das Erkennen einer Festung ist ihnen dann kein Trost mehr.

Natürlich muß man argumentieren, daß zumindest die richtige Bewertung einer solchen Situation ein "gutes Service" für die User wäre.

Die Engine bräuchte nur eine ganz primitive Liste der (dann vorerst irrigen) Bewertungen zu führen, die sie bei den gespielten Zügen im Verlauf der Partie jeweils hatte. Normalerweise beweist sich eine große Plus-Bewertung dadurch, daß sie wächst. Habe ich aber beispielsweise +4.x und nach 20 Zügen immer noch nur +4.x, dann ist etwas faul. Anhand dessen könnte die Engine ablesen, daß kein Fortschritt eintritt. Das heißt nicht daß sie panikartig auf 0.00 korrigieren muß, sondern das könnte schrittweise und abhängig von irgendwelchen Faktoren intelligenter gestaltet werden. Vielleicht läßt sich die Festung mit einem Opfer knacken, ohne daß man selber in Verlustgefahr kommt usw.usf.

(In der Analyse natürlich nicht, wenn die Bewertungshistory fehlt.)

By Thomas Hall Date 2009-10-07 16:26

Hallo Michael,

Ja, wie Du schon richtig sagst, die Engines wollen gewinnen,
also kommt es auch darauf an, einen möglichen Festungszustand
zu vermeiden, denn es mag ja sein, daß man den Festungszustand
erkennen kann, wenn man ihn erreicht hat, aber dann ist es eh
zu spät, wie Du schon richtig sagst. Irgendwann wird dann die
50-Züge-Regel die Bewertung sowieso auf Null bringen.

Vor ein paar Jahren habe ich einmal mit DF 8 ein Experiment
gemacht, ich habe bei der Analyse einer Festung die Engine
soweit analysieren lassen, bis die Bewertung auf Null sprang
und bin danach mit der Rückwärtsanalyse in der Variante
zurückgegangen, habe dann, wenn die Engine einen anderen Zug
vorschlug, diesen verfolgt und so weiter. Dabei stellte sich
heraus, daß ich immer weiter zurückgehen konnte und die Engine
immer früher die Bewertung 0 anzeigte, ganz klar, weil die
Hashtabelle mit relevanten Stellungen gefüllt worden war. Auf
diesen Effekt hatte ich gebaut, und ich konnte tatsächlich im
Variantenbaum soweit zurückgehen, bis ich an eine Stellung vor
dem Auftreten der Festung ankam, und siehe da, DF 8 fand einen
Zug, der die Festung vermied. Die ganze Prozedur war zwar
mühselig und zeitraubend, aber als Experiment erfolgreich.

Eine automatische Vermeidung einer Festung ist allerdings
immer noch schwierig, das hängt ganz einfach mit dem Such-
horizont zusammen.

Grüße, Thomas

By Michael Scheidl Date 2009-10-07 18:36

Ich glaube, daß Programierer eine "Festungs-Gefahr" (sowohl vom Blickpunkt des Angreifers als des Verteidigers) über typische Strukturen und Materialverteilungen definieren könnten. Das kann sicher nicht alle, aber möglicherweise 90% der Festungen abdecken. Ich rechne damit daß Programmierer in naher Zukunft Maßnahmen ergreifen werden, damit ihre Engines in solchen Situationen nicht wie die letzten Trotteln dastehen! Soviel Ehrgeiz traue ich den guten Programmieren sicherlich zu.

By Benno Hartwig Date 2009-10-07 11:46

[quote="Peter Martan"]Das Problem ist umso gravierender, als man den Nullzug, den es durch die Stellungswiederholung ja auch real gibt[/quote]Ich denke, mit solch einer Formulierung verwirrst du mehr als dass du erklärst.
Es mag Züge im Schach geben, die keinerlei Fortschritt bringen (naturgemäß zum Beispiel in Remis-Stellungen). Hier aber den Begriff 'Nullzug' zu nutzen muss irritieren.
Manche Stellung ist ja bisweilen gerade deshalb remis, weil Nullzüge keine legalen Züge sind. (Anderenfalls gäbe es kein Patt und dafür etwas später ein Matt)

Benno

By Peter Martan Date 2009-10-07 12:30

[quote="Benno Hartwig"]
Es mag Züge im Schach geben, die keinerlei Fortschritt bringen (naturgemäß zum Beispiel in Remis-Stellungen). Hier aber den Begriff 'Nullzug' zu nutzen muss irritieren.
Manche Stellung ist ja bisweilen gerade deshalb remis, weil Nullzüge keine legalen Züge sind. (Anderenfalls gäbe es kein Patt und dafür etwas später ein Matt)
[/quote]

Ich finde zwar nicht, dass Nullzug hier irritieren muss, weil wenn eine Seite einen Zug durch einen folgenden rückgängig macht, hat sie de facto einen Nullzug ausgeführt, nein?
Nein, weil sie dafür 2 Züge braucht, du hast recht.

By Benno Hartwig Date 2009-10-07 12:55 Edited 2009-10-07 13:01

[quote="Peter Martan"]Ich finde zwar nicht, dass Nullzug hier irritieren muss, weil wenn eine Seite einen Zug durch einen folgenden rückgängig macht, hat sie de facto einen Nullzug ausgeführt, nein?[/quote]Ich denke: nein!

Nullzug bedeutet, ich lasse testweise einen Spieler einen Zug A machen, der Gegner B antwortet nicht (Nullzug) und der erste Spieler A zieht noch einmal (obwohl er nach Schachregel gar nicht dran ist) Spieler A zieht, obwohl Spieler B dran ist.
Nullzug bedeutet nicht: A macht einen Zug, B antwortet, und dadurch ist eigentlich nichts passiert!
Bei Zugwiederholungen hast du aber in der Regel gleiche Figurenaufstellungen nur dann, wenn auch derselbe Spieler wieder am Zug ist. Spieler A zieht in Stellung, die Spieler A bereits einmal hatte.

Ich denke, diese beiden Situationen haben wirklich nichts miteinander zu tun.
Während Nullmoves vermutlich meist hochgespannte Situationen hervorrufen, werden bei Zugwiederholungen eher Remis-Situationen vorliegen.

Viele typische Remissituationen, die heute sofort in Stellungswiederholungen münden, würden sofort eine scharfe Angriffsvariante, wenn einer der Spieler, oder vermutlich auch beide Spieler dem Gegner einen Nullmove aufzwingen könnten.

Benno