Ruhesuche: gewählter oder aufgezwungener Abtausch

By Ernst Happe Date 2010-09-10 14:14

hi benno,

also, bevor wir hier diskutieren, wäre es meiner meinung nach sinnvoll, dass du hier mehrere partien zum vergleich vorstellst,
damit wir sehen können, wie sich deine ideen in den partien auswirken.

Ernst

p.s.

gleiche eröffnung, 1 kern, ohne egtb`s, gleiche farbverteilung...

By Benno Hartwig Date 2010-09-11 13:42

[quote="Ernst Happe"]also, bevor wir hier diskutieren, wäre es meiner meinung nach sinnvoll, dass du hier mehrere partien zum vergleich vorstellst,
damit wir sehen können, wie sich deine ideen in den partien auswirken.

[/quote]Natürlich könnte ich solche Partien liefern.
Mache ich natürlich auch, wenn sie jemand betrachten möchte.
Ich zumindest könnte sicher überhaupt nicht sehen, wo sich das auswirkt, denn bei den auch schon verschlechternden

sehr zurückhaltenden Implementierungen, bei denen ich nur sehr streng und auch nur einen seehr kleinen Bonus gewährte, gibt es halt immer irgendwo in den Ruhesuchen (also in Tiefen 14 und ggf. sehr weit darüber) Stellungen, die nun einen kleinen Bruchteil eines Bauern besser oder schlechter bewertet werden gemäß original-Stockfish.
Und das pflanzt sich dann über 15 bis 20 plys minimax-mäßig letztlich zum gewählten Zug durch. Die eigentliche Suche arbeitet ja unverändert.
Das im letztlich gewählten Zug zu erkennen und zu verstehen, wäre zumindest mir gänzlich unmöglich.

Benno

By Rudolf Rohs Date 2010-09-10 14:40

Hallo Benno,

also ich möchte mal sagen, es kommt drauf an.

Ich selber passe mich mit meinem Spielstil häufig dem Gegner an. Halte ich ihn für stärker haue ich das Material vom Brett (Was nicht da ist kann nicht schaden
und ist das Brett leer kann auch ein besserer Spieler nicht mehr/kaum noch gewinnen).
Halte ich mich für den besseren Spieler versuche ich das Material auf dem Brett zu lassen, solange mir ein Abtausch nicht direkt nutzt. Schließlich halte ich meine Figuren aufgrund des besseren Spiels dann für wertvoller als die "schlechtgeführten" Figuren des Gegners. Somit nutzen mir die Figuren auf dem Brett dann mehr, da sie meinen
"eingebildeten" Vorteil erhöhen.

Also einfach ausgedrückt. Stärkerer Gegner (wenn gefahrlos möglich) abtauschen und die Partie (und die Fehlermöglichkeiten) verkürzen. Schwächerer Gegner die Partie lang anlegen um die kleinen rausgespielten Vorteile addieren zu können und möglichst sicher zu gewinnen.

Gruß

Rudolf

By Benno Hartwig Date 2010-09-10 20:04

Thanx für die Einschätzung, aber vergleiche bitte mal folgende Situationen (an sowas dachte ich genauer. Und gehe bitte von einem gleichstarken Gegner aus.):
Du kannst in etwas Tiefe zwei Stellungen erreichen, bei denen du jeweils in einen Schlagabtausch kommst, der normalerweise jeweils zu Wert 0,00 führt.
Schlagabtausch-1 bedeutet vielleicht, dass du aus Stellung mit Wert -0,20 durch dein Schlagzüge immer zunächst zu Werten 3,00 oder so kommst, nur dass dein Gegner zurückschlagen kann, sodass am Ende 0,00 herauskommt.
Schlagabtausch-2 bedeutet vielleicht, dass du aus Stellung mit Wert -3,00 durch dein Schlagzüge immer zunächst zu Werten 0,20 oder so kommst, nur dass dein Gegner zurückschlagen kann, sodass am Ende 0,00 herauskommt.

Ich habe so den Eindruck, dass es meist sinnvoll sein kann, in solch einer Situation lieber den Schlagabtausch-1 anzustreben, also dieser Stellung dann nicht den normalen Wert 0 sondern vielleicht +0,05 (oder auch nur +0,01) zuzuweisen.
Die Idee dabei ist, dass ich, wenn ich wirklich zu solchen Stellungen komme, dann vielleicht mit etwas größerer Wahrscheinlichkeit unter den anderen Zügen eine noch bessere Möglichkeit finde.
Schlagabtausch-1 bietet gute Chancen, dass einer der anderen Züge bei näherem Hinsehen noch besser ist. Schlagabtausch-2 lässt mir wahrscheinlich nur die Wahl zuzuschlagen.
Das war meine Idee.

Benno

By Rudolf Rohs Date 2010-09-10 20:56

Hallo Benno,

ich denke schon das Engines die reinen Schlagabtäusche schon ziemlich genau durchrechnen. Erst hinter dem Horizont (ein Halbzug zuviel) ändert sich dies manchmal schlagartig.
Kommt also auf den Zeithorizont an. Ist der kurz und evtl. noch innerhalb einer möglichen Kombination kann es klappen, endet der Horizont erst weit hinter dem Schlagabtausch
würde ich es nicht so sehen.

Einen Schlagabtausch selbst anzustreben kann ein Vorteil sein, den im Schach gewinnt ja häufig derjenige der angreift. Selbst die Vereinfachung anzustreben kann also richtig sein,
aber nicht zwingend, da der Gegner dann den letzten Zug hat, also diese Figur evtl. entwickelt, während deine überlebenden Figuren so stehen wie sie vorher standen. Dann hast
Du evtl. durch den Erstschlag nur ein Tempo verloren.

Auch steigt beim Zurückschlagenden, wenn mehrere Antwortzüge möglich sind die erreichbare Rechentiefe zuerst, da der weniger Figuren ausrechnen muß. Auch dies kann ein Vorteil für den
Nachschlagenden sein.

Es gibt also auch Gründe die gegen einen Erstschlag sprechen können.

Hängt also wieder einmal von der Stellung und vom eigenen Schachvermögen ab, die Stellung richtig einzuschätzen.

Größere Gewinnmöglichkeiten bieten warscheinlich das Buch auf die Stärken der eigenen Engine einzustellen und auf die Programmierkünste des Programmierers zu hoffen.

Gruß

Rudolf

By Benno Hartwig Date 2010-09-11 13:30

[quote="Rudolf Rohs"]ich denke schon das Engines die reinen Schlagabtäusche schon ziemlich genau durchrechnen.[/quote]Sorry, hier drückte ich mich vielleicht schlecht aus, denn mehrere verstanden mich so wie du.
Der Schlagabtausch wird natürlich korrekt durchgerechnet.
Nur ist die Bewertung daraus deutlich unzuverlässiger, als wenn man im tatsächlichen Spiel bei dieser Stellung ankommt und hier eine volle Suche durchführt.
Darin sah ich die Ungenauigkeit der Ruhesuche.
Kommt man näher, sieht man mehr.

[quote="Rudolf Rohs"]Einen Schlagabtausch selbst anzustreben kann ein Vorteil sein, den im Schach gewinnt ja häufig derjenige der angreift.[/quote]An sowas dachte ich.
Wenn ich wählen soll zwischen einer ausgeglichen Stellung, in der ich die Damen tauschen kann, und einer Stellung, in der ich eine Dame zurück liege, nun aber zurückschlagen kann, dann ist mir irgendwie die erste Stellung lieber, denn da kann ich, wenn die Stellung auf dem Brett ist, immer noch überlegen, ob ich abtausche, während ichbei der anderen Stellung vermutlich kaum eine Wahl habe.
In der Mehrzahl der Fälle zumindest. (oder nicht?)

[quote="Rudolf Rohs"]Es gibt also auch Gründe die gegen einen Erstschlag sprechen können. [/quote]
OK, das müsste dann vermutlich genauer betrachtet werden.

Benno

By Rudolf Rohs Date 2010-09-14 17:10

Hallo Benno,

[url]Nur ist die Bewertung daraus deutlich unzuverlässiger, als wenn man im tatsächlichen Spiel bei dieser Stellung ankommt und hier eine volle Suche durchführt.
Darin sah ich die Ungenauigkeit der Ruhesuche.
Kommt man näher, sieht man mehr.[/url]

Absolut richtig. Die Engine ist ein paar Halbzüge weiter und darüber hinaus sind einige Figuren vom Brett verschwunden. Deshalb dürfte der Rechenhorizont
steigen und daraus logischerweise sieht/rechnet die Engine in der gleichen Zeit weiter als vorher. Daraus kann sich die Bewertung ändern, weil die Engine jetzt
neue Möglichkeiten berechnen kann die vorher außerhalb des Rechenhorizontes lagen.

Gruß

Rudolf

By Peter Martan Date 2010-09-10 16:09 Edited 2010-09-10 16:15

[quote="Benno Hartwig"]
Wenn ich in der Ferne einen Schlagabtausch sehe, den ich positionell noch nicht so ganz bewerten kann, dann bin ich doch lieber derjenige, der dann ggf. entscheidet, ob er den Abtausch beginnt, als derjenige, dem er aufgezwungen wird. Oder ist das grundsätzlich falsch?
[/quote]

Hallo Benno!

ich weiß nicht, ob das grundsätzlich falsch ist, grundsätzlich richtig finde ich es nicht, beziehungsweise hab deinen Gedankengang wahrscheinlich noch nicht ganz verstanden.
Wenn du einen entfernt liegenden und daher (?) noch nicht in der aktuellen Stellung exakt durchrechenbaren Schlagabtausch mit einem Bonus bewertest, wieso nimmst du an, dass das in mehr als der Hälfte der Fälle richtig sein wird?
Ich meine, ihn herbeizuführen, ohne konkrete Pluspunkte, die dafür sprechen, mag ebenso oft von Vorteil wie von Nachteil sein, nein?
Dementsprechend kann ich auch Rudolfs Überlegungen zum eigenen Spiel relativ zu dem des Gegners nicht ganz nachvollziehen, sosehr ich das psychologische Moment Vereinfachung starken Gegnern gegenüber kenne und verstehen kann, es bleiben einem dadurch vielleicht Verwicklungen erspart.
Schachlich logisch wäre es nur dann, wenn ich aber durch die Vereinfachung, die das Abtauschen ja schon meistens bewirken wird, nicht nur in eine einfachere, sondern auch eine einfach besserere Stellung komme.
Ansonsten bewirkt sie nur eines sicher, dass es schneller aus ist, für wen das besser endet, hat damit meinem Spielverständnis nach noch nichts zu tun, oder?

Wie gesagt, ich konzidiere, wahrscheinlich noch nicht alles ganz verstanden zu haben, was du dir da so alles gedacht haben wirst, gebe damit auch Ernst recht, der meint, du solltest konkrete Stellungsbeispiele bringen, anhand derer man das betrachten könnte.
Und dann wäre natürlich vor Allem die Umsetzung mit code anhand von Beispielen die zu diskutierende, da könnte ich aber wieder nicht so viel mitreden, was ich, wie du merkst, gern täte.

Weil: die Frage, wie soll das Schachprogramm denken, anhand derjenigen, wie denkt man selbst, sich zunächst mal selbst zu stellen, ist faszinierend. Vom Schachjournalisten gefragt, weiß Botwinnik, wie Botwinnik denkt, soll der ja angeblich auch keine wirklich gute Antwort gehabt haben, oder sie wurde nicht überliefert (von böswilligen oder die Antwort nicht verstehenden Journalisten

).

Und jetzt dann zu guter Letzt doch noch eine konkrete Frage: haben Rudolf und ich das überhaupt ríchtig verstanden?

"1) das ich bei A schon bei Bewertung annähernd w erreiche, während ich bei
2) zunächst in der Bewertung weit zurück liege, und erst durch das Schlagen wieder zu w komme.
Sollte einem dann nicht die Stellung A die willkommenere Stellung sein?"

heißt doch vielleicht eigentlich, dass du in so einem Fall das Schlagen eher vermeiden willst?
Wie gesagt, es fehlt einfach zum Verständnis noch was Wesentliches, mir zumindest.

By Rudolf Rohs Date 2010-09-10 20:38

Hallo Peter,

[url]Dementsprechend kann ich auch Rudolfs Überlegungen zum eigenen Spiel relativ zu dem des Gegners nicht ganz nachvollziehen, sosehr ich das psychologische Moment Vereinfachung starken Gegnern gegenüber kenne und verstehen kann, es bleiben einem dadurch vielleicht Verwicklungen erspart.
Schachlich logisch wäre es nur dann, wenn ich aber durch die Vereinfachung, die das Abtauschen ja schon meistens bewirken wird, nicht nur in eine einfachere, sondern auch eine einfach besserere Stellung komme.
[/url]

Nein, wenn ich einen stärkeren Gegner habe bin ich meist schon mit einem Remis zufrieden. Wenn ich denke, daß mein Gegner ca. 0,02 Bauerneinheiten pro Zug besser denkt, erreiche ich mit einer
30-zügigen Partie noch ein Remis. Bei 100 Zügen dürfte die Partie weg sein.

Gruß

Rudolf

By Benno Hartwig Date 2010-09-11 12:23

Zitat:

Wenn du einen entfernt liegenden und daher (?) noch nicht in der aktuellen Stellung exakt durchrechenbaren Schlagabtausch mit einem Bonus bewertest,

Sorry, hier war ich vielleicht missverständlich. Der Schlagabtausch wird auf jeden Fall sauber durchgerechnet. Es werden aber die Positionsbewertungen direkt an diese Schlussstellungen geknüpft, es werden 'keine' ruhigen Züge mehr betrachtet. Dadurch hat diese Ruhesuche eine gewisse Aussagekraft, diese ist aber schwächerwie wenn ich hier eine volle Suche gestartet hätte oder wenn ich gar nch tiefer gerechnet hätte. Das meinte ich mit " den ich positionell noch nicht so ganz bewerten kann".
Nur-Ruhesuche in einer Stellung gibt natürlich keine sehr verlässliche Bewertung dieser Stellung.
Der Abtausch wird sicher sauber durchgerechnet.

Ich versuche mal ein sehr konkretes Beispiel:
Angenommen, in meiner Suche sehe ich in großer Tiefe zwei Stellungen, die minimax-mäßig zu einem gleichen Stellungswert führen:
also:
Stellung-1: ich liege 4 Bauerneinheiten zurück, kann aber mit einem Turm die Dame Schlagen, der Gegner kann dann nur den Turm zurückerobern.
und
Stellung-2: ich liege 4 Bauerneinheiten im plus, sehe mich aber gezwungen mit meiner Dame einen Gegnerturm zu schlagen, der Gegner kann dann aber meine Dame schlagen.
Weitere Schlagzüge sollen nicht bestehen.

Rein nach minimax und auch der klassischen Ruhesuche würde beides ungefähr zu ausgleich führen.
Die Stellungen wären also ungefähr gleichwertig.
Und trotzdem vermute ich irgendwie, dass es ohne weitere Kenntnisse eher von Vorteil wäre, lieber Stellung-1 anzustreben, einfach, weil sich vielleicht aus der +4-Bauern-Stellung heraus doch noch bessere Chancen bieten, währnd ich aus der -4-Bauern-Stellung heraus einfach gezwungen sehe, erstmal den Ausgleich wieder herbeizuführen.
Darum war ich geneigt, Stellung-1 etwas besser zu bewerten.
Aber vielleicht ist diese Vermutung bei einiger Schacherfahrung ja auch Blödsinn und es interessiert mich eure Meinung.

Benno

By Jörg Oster Date 2010-09-10 19:41

Hallo Benno,

meinst du mit Ruhesuche Quiescence search?

Darunter versteht man, soweit ich das verstanden habe, etwas anderes.
Wenn die Berechnungen für eine bestimmte Tiefe abgeschlossen sind, wird geschaut, ob noch Schlagzüge möglich sind.
Wenn ja, werden diese noch berechnet, bis man eine ruhige Stellung erreicht. (Vereinfacht ausgedrückt)
Dadurch mindert man etwas den Horizont-Effekt.

Schau mal in die Chess Programming Wikis.

Gruß,
Jörg.

By Benno Hartwig Date 2010-09-10 19:52

[quote="Jörg Oster"]meinst du mit Ruhesuche Quiescence search?
Darunter versteht man, soweit ich das verstanden habe, etwas anderes.
Wenn die Berechnungen für eine bestimmte Tiefe abgeschlossen sind, wird geschaut, ob noch Schlagzüge möglich sind.
Wenn ja, werden diese noch berechnet, bis man eine ruhige Stellung erreicht. (Vereinfacht ausgedrückt)
Dadurch mindert man etwas den Horizont-Effekt.[/quote]
Ja ich meine Quiescence search, und ich denke, ich habe sie richtig verstanden.
Man untersucht hier nicht nur alle Schlagzüge (ggf. auch nur bis zum Cut), sondern auch den aktuellen Stellungswert, und man geht (optimistisch?) davon aus, dass dieser sich meist halten lässt durch einen eventuell ruhigen Zug.
Es wäre ja auch sehr unpassend, in jeder Stellung nur alle Schlagabtäusche zu betrachten, denn es könnte ja sein, dass die alle nur Nachteile bringen.

Benno

By Benno Hartwig Date 2010-09-10 20:41

[quote="Jörg Oster"]Schau mal in die Chess Programming Wikis.[/quote]
Recht gut ist, was ich zur Ruhesuche sagte, zu sehen auf
http://chessprogramming.wikispaces.com/Quiescence+Search

Code:

int Quiesce( int alpha, int beta ) {
    int stand_pat = Evaluate();
    if( stand_pat >= beta )
        return beta;
    if( alpha < stand_pat )
        alpha = stand_pat;
 
    until( every_capture_has_been_examined )  {
        MakeCapture();
        score = -Quiesce( -beta, -alpha );
        TakeBackMove();
 
        if( score >= beta )
            return beta;
        if( score > alpha )
           alpha = score;
    }
    return alpha;
}

stand_pat wird zunächst bestimmt (Bewertung der aktuellen Stellung ohne weitere Suche)
und dieser Wert wird alpha zugewiesen, kann duch die Schlagzüge nur verbessert werden.
Und alpha ist dann der Stellungswert.

Benno

By Wilfried Arheit Date 2010-09-10 21:43

Hier fehlen mir die Worte.
Solch einen Unsinn habe ich noch nie gehört.
Oder bin ich schon vollkommen verblödet?
MfG
Wilfried

By Benno Hartwig Date 2010-09-11 06:29

[quote="Wilfried Arheit"]Hier fehlen mir die Worte. Solch einen Unsinn habe ich noch nie gehört. Oder bin ich schon vollkommen verblödet?[/quote]
Ich bin mir sicher, dass dies im Databecker-Computerschachbuch, wo ein ganz interessantes BASIC-Schachprogramm im Detail mit jeder Source-Zeile vorgestellt wird, und welches ich seinerzeit durcharbeitete, so erklärt wird.
Und wenn ich die Stockfish-Sourcen nicht total falsch verstehe, ist dies auch da das (dann kräftig erweiterte) Grundprnzip der Ruhesuche.
Dumpfe Erinnerung: Toga macht es auch genau so.

Benno

By Benno Hartwig Date 2010-09-11 06:43 Edited 2010-09-11 06:47

Hier noch kurz die Skizzierung der Ruhesuche aus "Computerschachbuch" von Datebecker von Bartel, Kraas und Schüfer, welches für den Schachprogrammier-Einsteiger meiner Meinung nach ein sehr gutes Lehrbuch ist:

"In allen Stellungen jenseits des Suchhorizonts wird zunächst die Bewertungsfunktion aufgerufen. Nun wird angenommen, daß der am Zug befindliche Spieler deren Wert sicher hat, aber es wird noch geprüft, ob er sich durch Schagzüge oder Bauernumwandlungen verbessern kann. Deren Züge werden nacheinander untersucht. Liefern sie Werte, die besser sind, so werden diese zum Stellungswert, sonst die Bewertung." (Seite 132)
Im Weiteren wird die Routine noch erweitert für eine angemessene Behandlung von z.B. "im Schach stehen", weil in solchen Fällen dieses "als sicher annehmen" nicht gerechtfertigt wäre.

Doch, ich bin mit sicher, dass ich die Ruhesuche richtig skizzierte.
Was für eine Vorstellung hattest denn du?

Benno

By Urs Maier Date 2010-09-11 14:01

theoretisch sollte das stimmen und praktisch zumindest keine negativen auswirkungen haben.
allerdings solltest du vielleicht grob bestimmen, in wie vielen fällen ein echter effekt eintritt, denn die engines rechnen ja eh alle "schlagzug-varianten" bis zum ende.

um wie viel schlechter schnitt stockfish denn ab? war das überhaupt messbar?

By Benno Hartwig Date 2010-09-13 10:23

[quote="Urs Maier"]um wie viel schlechter schnitt stockfish denn ab? war das überhaupt messbar? [/quote]Das hing ab von der Schärfe, mit der ich es implementierte.
Als ersten Test nehme ich einen Satz von 74 Anfangsstellungen und lasse den mit Farbvertauschung gegen Rybka3 und Rybka4 spielen. 1m+1s, 1 Kern, kein ponder
(OK, nur diese Gegner, nur (naja, vielleicht auch: immerhin) 296 Partien. Da kann man kritisieren. Auch sehr kurze Zeiten. Aber so als 1. Test fand ich es OK.
Und wenn ich nach 40 Partien schon sah, dass die neue Engine nur Mist macht, breche ich auch früher ab.)
Original-Stockfish_18 kommt knapp meist positiv gegen R3 raus und ein Stück negativ gegen R4, insgesamt knapp negativ.
Das habe ich auch auf mehreren Rechner bei verschiedenen Zeiten gespielt, sodass ich ein ganz verlässliches Bild habe (muss ich mal raussuchen).

Sehr zurückhaltend war meine Implementierung, die so lief:
Wenn die Ruhesuche feststellt, dass die Bewertung der aktuellen Stellung nur um 1 (Stockfisch-Wertung, ich glaube das ist weniger als ein Centibauer, muss ich noch genauer ansehen) schlechter der beste Schlagzug (also wirklich schon fast gleich gut ist), dann erhöhe ich den Stellungswert um 1. Ich belohne, dass sich der Wert ggf. erreichen lässt durch Schlagabtausch und vermutlich durch ruhige Züge. Sollte ich in die Stellung wirklich kommen, dann habe ich vermutlich mehrere gute Optionen, unter denen ich wählen kann.
Das tritt wohl nur sehr selten auf, und die Spielstärke unterscheidet sich kaum. Ich sah aber auch keine Ahnung von einer Verbesserung.

Etwas mutiger kann ich auch sagen, ich gewähre diesen 1-Bonus bereits, wenn die aktielle Stellungesbewertung nur höchstens 5 schlechter ist als der beste Schlagzug.
Dann brach die Stärke aber schon deutlich ein.
'meine' Engine kamm nur noch auf 1/3 der Punkte.
Hatte ich nciht erwartet (Falsche Erwartung? fehlerhafte Implementierung?)

Und gedacht hatte ich eigentlich sogar an eine 'rasante' gestaffelte Lösung:
Wenn Stellungsbewertung=bester_Schlagzug - 1   =>   value=value+3
sonst
Wenn Stellungsbewertung>=bester_Schlagzug - 3   =>   value=value+2
sonst
Wenn Stellungsbewertung>=bester_Schlagzug - 7   =>   value=value+1

Aber bei sowas bricht die Spieltsärke total ein

'meine' Engine holt nur noch vereinzelt Punkte.

Gehofft hatte ich, dass ich 'meine' Engine so zu Stellungen führen kann, die sehr nahe am Optimum liegen, die aber mehrere Chancen bieten, unter denen dann (kommt man näher, sieht man mehr) die bessere gewählt werden kann. Und sie soll den Gegner in Stellungen bringen, in denen er nur weniger Möglichkeiten hat, ggf. sogar nur die eine Chance zu nutzen hat, für die er sich schon früher, bei weit schlechterem Durchblick, entschieden hat.
So meine Idee, die nun in der Praxis aber entschieden strauchelt.

Benno

By Urs Maier Date 2010-09-13 15:05

ich kann mir schon vorstellen, daß du bei der implementierung keinen fehler gemacht, den effekt aber weit überschätzt hast.
wenn du die engines z.B. auf 3 ply gegeneinaderspielen lassen würdest, sollte es aber klappen

.
man bräuchte erstmal statistisch auswertbares material als grundlage für deine idee.

By Reinhard Scharnagl Date 2010-09-13 18:14

Die Frage "gewählter oder aufgezwungener Abtausch" allein zeigt schon, dass m. E. hier das eigentliche Kernproblem übersehen wird. Auch wenn sich sonst kaum jemand für meine theoretischen Überlegungen erwärmt, so möchte ich hier mal versuchen, das Problem aus meiner Sicht zu beleuchten.

Wenn eine Position einer anderen via Zug nachfolgt, so denkt man leicht, dass es natürlich sei, die ursprüngliche Position als DEN Vorgänger zu betrachten. Das ist natürlich ein ziemlicher Irrtum. Durch die verschiedensten Zugumstellungen kann die letztere Position auf mancherlei Wegen erreicht werden. Wahrscheinlich wäre es grundsätzlich sinnvoll, jene Zugfolge als charakteristisch anzusehen, welche insgesamt mit den jeweils stärksten Zügen zu dieser Endposition führte. Diese ist aber nicht einfach ad hoc zu bestimmen.

Die Bewertung einer Position von dem temporär vorhergehenden Zug abhängig zu machen führt dagegen zu unterschiedlichen Bewertungen für dieselbe Position, je nachdem welcher Zweig des Suchbaumes gerade durchgesehen wird. Eine sinnvolle Entscheidung wird hiermit also eher erschwert.

Man sollte also Bewertungen grundsätzlich NIE vom "vorhergehenden" Zug abhängig machen.

By Benno Hartwig Date 2010-09-14 08:18

[quote="Reinhard Scharnagl"]Die Bewertung einer Position von dem temporär vorhergehenden Zug abhängig zu machen führt dagegen zu unterschiedlichen Bewertungen für dieselbe Position, je nachdem welcher Zweig des Suchbaumes gerade durchgesehen wird.[/quote]Ja? Hmmm...
Gemäß reinem alpha-beta werden relevante Positionen eigentlich immer gleich bewertet, ganz egal, über welche Zugfolge diese Position errreicht wird.
Das ist die klassische Methode. (OK, für modernere Implementierungen halte ich nicht unbedingt meine Hand ins Feuer)

Und ich überlege manchmal, ob es nicht klug wäre, entgegen dieser klassischen Methode, und entgegen deiner Ansicht, doch den Zugpfad dorthin mitzubewerten. Wenn ich aus meiner Ausgangsstellung zwei eigentlich gleichwertige Stellungen erreichen (erzwingen) kann, dann gibt es ggf. Gründe, doch bewusst die eine der Abwicklungen zu wählen, weil sie dem Gegner vielleicht Fallen stellt, für den Gegner schwer zu durchschauen ist, wiel ich zwischendurch mehre gleichwertige Zugmöglichkeiten habe (und wenn sich bei näherer Betrachtung eine als schlechter erweist, taugt ggf. ja doch die andere), wenn ich Material verliere, dann lieber später, denn vielleicht sieht es mein Gegner ja nicht (klingt billig, hätte aber z.B. bei den Rybka-Vorgabe-Begegnungen eine Rolle gespielt)...

Mancher wird kritisieren "Für das Spiele-Gewinnen könnte das nützlich sein. Aber nicht für eine korrekte Bewertung der Stellung!"
Mag sein. Wenngleich: Gehört ein "stellt dem Gegner eine Falle" oder "Hat wegen größerer Auswahl guter Züge mehr Potential" nicht auch zu einer 'korrekten Stellungsbewertung'?

Zumindest meine Überlegungen gehen jetzt mehr in diese Richtung.
Benno

By Reinhard Scharnagl Date 2010-09-14 14:33

[quote="Benno Hartwig"]
[quote="Reinhard Scharnagl"]Die Bewertung einer Position von dem temporär vorhergehenden Zug abhängig zu machen führt dagegen zu unterschiedlichen Bewertungen für dieselbe Position, je nachdem welcher Zweig des Suchbaumes gerade durchgesehen wird.[/quote]Ja? Hmmm...
Gemäß reinem alpha-beta werden relevante Positionen eigentlich immer gleich bewertet, ganz egal, über welche Zugfolge diese Position errreicht wird.
Das ist die klassische Methode. (OK, für modernere Implementierungen halte ich nicht unbedingt meine Hand ins Feuer)[/quote]Wenn das zu 100% so wäre, dann wären die Analyse-Ergebnisse einer Engine immer determiniert, was insbesondere beim Multithreading aber eher die Ausnahme ist. Es gibt eine Reihe von Tricks bei Vorbewertungen zur Zugsortierung wie etwa Vorrang für das Zurückschlagen der "soeben" gezogenen Figur, was bei nicht vollständig expandierten Knoten zu Unterschieden führen kann, ähnliches gilt für History Heuristiken.

[quote="Benno Hartwig"]Und ich überlege manchmal, ob es nicht klug wäre, entgegen dieser klassischen Methode, und entgegen deiner Ansicht, doch den Zugpfad dorthin mitzubewerten. ...[/quote]Leider gibt es DEN Zugpfad nicht, denn je mehr Plies zurückgelegt werden, um so mehr wirken sich Zugumstellungen aus.

By Benno Hartwig Date 2010-09-14 20:00

[quote="Reinhard Scharnagl"]Wenn das zu 100% so wäre, dann wären die Analyse-Ergebnisse einer Engine immer determiniert, was insbesondere beim Multithreading aber eher die Ausnahme ist.[/quote]Da magst du irgendwie auch Recht haben. Weiß ich bei modernen Engines nicht.
Gewisse Undeterminiertheiten lasse ich mir aber gefallen, wenn aufgrund der anderweitigen Rechnerbelastungen 1 Minute Rechenzeit paktisch doch etwas andere und unterschiedliche Rechenzeiten bedeuten kann. Und auch wenn aufgrund unterschiedlicher Belastungen der Threads die Reihenfolge der Teil-Rechenergebnisse der Threads und dann auch die Entscheidung, wie danach konkret in den Threads weitergemacht wird, durchaus unterschiedlich sein kann, lasse ich mir etws unterschiedliche Geschwindigkeiten bei der Lösung gefallen, was dann bei gegebenen Zeiten auch zu unterschiedlichen Ergebnissen führen würde. Aber vielleicht reicht das als Erklärung auchnicht.
Interessant wäre es, die Unterschiedlichkeit der Ergebnisse zu bewerten, wenn eine feste Suchtiefe vorgegeben ist.
Hast du da Erfahrungen?

[quote="Reinhard Scharnagl"]Leider gibt es DEN Zugpfad nicht, denn je mehr Plies zurückgelegt werden, um so mehr wirken sich Zugumstellungen aus. [/quote]Klar, es gibt nicht den Zugpfad. Ich will letztlich aber auch nicht eigentlich eine Stellung in der Tiefe des Suchbaumes bewerten, sondern die mir zur Verfügung stehenden Züge. Das läuft dann über Minimax und die Bewertungen in der Tiefe, und (so möchte ich es) die (ggf. mehreren) Zugpfade, die dorthin führen.

Benno

By Reinhard Scharnagl Date 2010-09-14 22:01

[quote="Benno Hartwig"]
...Interessant wäre es, die Unterschiedlichkeit der Ergebnisse zu bewerten, wenn eine feste Suchtiefe vorgegeben ist.
Hast du da Erfahrungen?[/quote]Mit SMIRF ist mir einiges klarer geworden, auch wenn ich hierbei keine Affinität zu fester oder variabler Suchtiefe sehe. Insbesondere habe ich versucht, einen situationsbezogenen Anzugsvorteil heraus zu rechnen, indem ich Feinbewertungen zwischen Situation und Vorgängersituation verglichen habe. Dabei bin ich auf genau das Problem gestoßen, dass es schwer ist, den "optimalen" Vorgänger zu identifizieren. Inzwischen habe ich aber ein gar nicht rechenintensives Konzept für ein solches Vorgehen gefunden. Mangels Interesse an einem Nachfolgeprojekt zu SMIRF und an eigenständiger Entwicklungsarbeit überhaupt habe ich dieses Konzept und zahlreiche andere, vermutlich massive Verbesserungen nicht mehr in eine neue Engine umgesetzt.

[quote="Benno Hartwig"]Klar, es gibt nicht den Zugpfad. Ich will letztlich aber auch nicht eigentlich eine Stellung in der Tiefe des Suchbaumes bewerten, sondern die mir zur Verfügung stehenden Züge. Das läuft dann über Minimax und die Bewertungen in der Tiefe, und (so möchte ich es) die (ggf. mehreren) Zugpfade, die dorthin führen.[/quote]Es macht keinen wirklichen Sinn, Züge zu bewerten, sondern nur, zwischen Zügen zu entscheiden. Dazu etwa bewertet man Positionen. Ist eine solche einmal erreicht worden, ist der Weg, der dahin führte, momentan komplett irrelevant. Um zwischen Zügen zu wählen, reicht es aus, sie nach Qualität ordnen zu können, ja sogar schon, einen Zug vor allen übrigen stehend zu erkennen. Das über die Bewertung nachfolgender Bäume bzw. derer Knoten zu erreichen, ist nur EINE Möglichkeit hierzu, die wahrscheinlich oft sehr ineffizient ist. Die ersten Schachprogramme haben z.B. auch lange überlegt, wenn es nur einen einzigen Zug gab, oder nur einen, der ein Matt vermied. Das beweist, dass die Baumsuche eigentlich primär ein Entscheidungsproblem und kein Bewertungsproblem ist, Bewertungen sind nur EIN Hilfsmittel für Entscheidungen. Man könnte komplett auf Bewertungsfunktionen verzichten, hätte man ein treffsicheres Verfahren, zwischen zwei beliebigen Positionen nach Qualität zu entscheiden. Das könnte eine interessante Aufgabe für neuronale Netzwerke sein.

Wenn schon ein Bezug zu einem Vorgängerzug Sinn machen sollte, dann nur der, welcher bei einer Retro-Analyse einer zuvor optimal gespielt gedachten Partie ausgewählt worden wäre. Das wird man kaum mit wenig Rechenaufwand schaffen. Aber es gibt hierzu eine gangbare Alternative, die dem sehr nahe kommt.

By Benno Hartwig Date 2010-09-15 06:58

[quote="Reinhard Scharnagl"]Dabei bin ich auf genau das Problem gestoßen, dass es schwer ist, den "optimalen" Vorgänger zu identifizieren.[/quote]Ich verstehe nicht, warum willst du dies den überhaupt?
Und was konkret macht denn einen Vorgänger zu einem 'optimalen' Vorgänger?

[quote="Reinhard Scharnagl"]Es macht keinen wirklichen Sinn, Züge zu bewerten, sondern nur, zwischen Zügen zu entscheiden.[/quote]Da werden vermutlich die Interessen unterschiedlich sein. Viele Anwender wollen wohl nicht nur eine Engine, die sehr gute Züge ausspuckt, sie wollen auch eine Information darüber, wie gut die so erreichte Stellung ist/sein mag. Du wirklich nicht?

Benno

By Benno Hartwig Date 2010-09-15 08:19 Edited 2010-09-15 08:23

Ergänzung:
Engines versuchen den stärksten Zug zu bewerten, bei den anderen versuchen sie es dabei zu belassen, dass sie nachweisen, dass diese nicht besser als der stärkste Zug sind, dass ihr Wert nicht höher als der des besten Zuges ist.
Insofern ist schon richtig was du sagst: Der Wert all dieser nicht optimalen Züge interessiert normalerweise nicht.
Benno

By Benno Hartwig Date 2010-09-15 08:48

Sorry, noch ein Ergänzung:
Bei den Zügen mitten drin im Suchbaum interessiert meist noch nicht mal der Wert des besten Zuges in einer Stellung.
Es reicht vollkommen aus zu erkennen und zu 'beweisen', dass es überhaupt einen Zug in der Stellung gibt, der genügend gut ist, um einen beta-cut herbeizuführen.
Benno

By Reinhard Scharnagl Date 2010-09-15 17:10

[quote="Benno Hartwig"]
[quote="Reinhard Scharnagl"]Dabei bin ich auf genau das Problem gestoßen, dass es schwer ist, den "optimalen" Vorgänger zu identifizieren.[/quote]Ich verstehe nicht, warum willst du dies den überhaupt?
Und was konkret macht denn einen Vorgänger zu einem 'optimalen' Vorgänger?[/quote]Jeder Zug transformiert eine Spielsituation in eine andere. Es ist wichtig, entscheiden zu können, ob ein solcher Zug mindestens den Anzugsvorteil realisiert, um den bisherigen Positionswert zu konservieren. Hier hilft es, wenn man den Anzugsvorteil, der zur Folgeposition führt, herausrechnen kann. SMIRF hat das versucht und kann so leicht sogar Knoten aus verschiedenfarbiger Plies wertmäßig miteinander vergleichen. Sich dabei auf die dem Zug vorausgehende Position zu beziehen, hat sich jedoch als ein leicht randomisierender Irrweg herausgestellt, weil es eben mehrere Zugfolgen zu einem Knoten gibt, und soche Bezüge zur vorherigen Situationen eben schwankende Einschätzungen für den mindestens abzudeckenden Anzugsvorteil hervorbringen. Das führt zu Bewertungen, die von der Reihenfolge der Betrachtungen der Knoten des Suchbaums abhängen, und damit leider zu Instabilitäten führen.

Der "optimal" zu betrachtende Vorgängerzug entstünde durch jene der möglichen Zugfolgen, bei dem der betragmäßig kleinste Unterschied zwischen einer absolut gedachten Bewertung der gemachten und der denkbar besten Züge minimal ist. Das wäre aber eine rechnerisch nicht zu schaffende Utopie. Es gibt aber eine fast gleichwertige Lösung hierzu.

Wie man sieht, arbeiten nicht alle Schachprogramme in gleicher Weise. SMIRF war für meinen ersten Versuch schon ganz brauchbar, und hat mir im Rückblick viele neue Ideen gebracht.