Branching-Faktor 2 wird anno 2013 klar unterschritten

By Kurt Utzinger Date 2013-06-16 11:04

Hallo Michael
Ist dieser B.F. von irgendwelcher Relevanz?
Mfg
Kurt

By Ingo Bauer Date 2013-06-16 12:12 Edited 2013-06-16 12:17

[quote="Kurt Utzinger"]
Hallo Michael
Ist dieser B.F. von irgendwelcher Relevanz?
Mfg
Kurt
[/quote]

Ja und das ist hochspannend!

In der Grundstellung hat man 20 mögliche Züge. Wenn man alle Untersucht wären das also 20 Positionen zu Untersucehn oder ein BF (branching = verzweigen) von 20. Obiges Bsp sind Mittelspielstellugnen. Wieviele Positionen da ca abgehen ist mir jetzt nicht ganz klar, aber mit Sicherheit mehr als 2. Ein BF von unter 2 bedeutet, das moderne Engines im Mittelspiel praktisch alles wegschneiden und nur noch <2 Positionen weiterverfolgen ...

Durchschnitt wie gesagt, dicht an der Root wird das mehr sein, nach hinten in der PV weniger aber trotzdem, sehr bemerkenswert.

Brute Force würde zwar nichts übersehen, aber eben genau deswegen nicht auf Tiefe kommen ...

Gruß
Ingo

PS: Hoffentlich habe ich jetzt nicht totalen Mist verzapft

By Michael Scheidl Date 2013-06-16 13:26

Das wird schon stimmen bzw. ich sehe es genauso. Die engl. Wikipedia nimmt unter dem Stichwort branching factor für Schach einen Durchschnitt von 35 an, chessprogramming.wikispaces 35...38. Den Beschreibungen zufolge erreicht pures Alpha-Beta - also ohne sonstige Tricks - durch gute Zugsortierung einen Faktor von ca. der Quadratwurzel der Zuganzahl, das wären also um 6 herum. Doch wir stehen jetzt bei <2.

Was das Pruning heute leistet, ist also enorm - umso mehr, da man ja nicht den Eindruck hat es würde mehr übersehen als früher. Offensichtlich wird trotz kleinerem B.F. weniger übersehen, sonst wären die Engines dadurch ja schwächer und nicht stärker. Natürlich spielen die viel größeren Tiefen auch eine große Rolle.

http://chessprogramming.wikispaces.com/Branching+Factor

@Kurt, wenn wir davon ausgehen daß im allgemeinen der Branchingfaktor über den zusätzlichen Zeitverbrauch für einen Ply mehr entscheidet, so zeigt uns das, warum gute Engines heute kaum doppelt so lange für Tiefe X brauchen als für X-1. Allerdings im Durchschnitt, Einzelfälle können mitunter stark abweichen.

In der Schachcomputer-Steinzeit war ja die fünf- bis sechsfache Rechenzeit nötig... und zweistellige Tiefen eine sehr seltene Erscheinung.

By Ingo Bauer Date 2013-06-16 14:10

[quote="Michael Scheidl"]
Das wird schon stimmen bzw. ich sehe es genauso. Die engl. Wikipedia nimmt unter dem Stichwort branching factor für Schach einen Durchschnitt von 35 an, chessprogramming.wikispaces 35...38. Den Beschreibungen zufolge erreicht pures Alpha-Beta - also ohne sonstige Tricks - durch gute Zugsortierung einen Faktor von ca. der Quadratwurzel der Zuganzahl, das wären also um 6 herum. Doch wir stehen jetzt bei <2.

Was das Pruning heute leistet, ist also enorm - umso mehr, da man ja nicht den Eindruck hat es würde mehr übersehen als früher. Offensichtlich wird trotz kleinerem B.F. weniger übersehen, sonst wären die Engines dadurch ja schwächer und nicht stärker. Natürlich spielen die viel größeren Tiefen auch eine große Rolle.

http://chessprogramming.wikispaces.com/Branching+Factor

@Kurt, wenn wir davon ausgehen daß im allgemeinen der Branchingfaktor über den zusätzlichen Zeitverbrauch für einen Ply mehr entscheidet, so zeigt uns das, warum gute Engines heute kaum doppelt so lange für Tiefe X brauchen als für X-1. Allerdings im Durchschnitt, Einzelfälle können mitunter stark abweichen.

In der Schachcomputer-Steinzeit war ja die fünf- bis sechsfache Rechenzeit nötig... und zweistellige Tiefen eine sehr seltene Erscheinung.

[/quote]

Ein interessanter Gedanke ist, dass auch der Mensch nicht alle 35 Züge durchdenkt. Engines sind im Schnitt bei <2 wie viele Züge erscheinen dem Menschen sinnvoll? Vielleicht ist das gerade ähnlich, nur vergisst der Rechner nichts und kommt dabei viel tiefer ... sieht nicht gut aus für den Menschen

Gruß
Ingo

By Stefan Pohl Date 2013-06-17 06:04

[quote="Ingo Bauer"]
[quote="Michael Scheidl"]
Das wird schon stimmen bzw. ich sehe es genauso. Die engl. Wikipedia nimmt unter dem Stichwort branching factor für Schach einen Durchschnitt von 35 an, chessprogramming.wikispaces 35...38. Den Beschreibungen zufolge erreicht pures Alpha-Beta - also ohne sonstige Tricks - durch gute Zugsortierung einen Faktor von ca. der Quadratwurzel der Zuganzahl, das wären also um 6 herum. Doch wir stehen jetzt bei <2.

Was das Pruning heute leistet, ist also enorm - umso mehr, da man ja nicht den Eindruck hat es würde mehr übersehen als früher. Offensichtlich wird trotz kleinerem B.F. weniger übersehen, sonst wären die Engines dadurch ja schwächer und nicht stärker. Natürlich spielen die viel größeren Tiefen auch eine große Rolle.

http://chessprogramming.wikispaces.com/Branching+Factor

@Kurt, wenn wir davon ausgehen daß im allgemeinen der Branchingfaktor über den zusätzlichen Zeitverbrauch für einen Ply mehr entscheidet, so zeigt uns das, warum gute Engines heute kaum doppelt so lange für Tiefe X brauchen als für X-1. Allerdings im Durchschnitt, Einzelfälle können mitunter stark abweichen.

In der Schachcomputer-Steinzeit war ja die fünf- bis sechsfache Rechenzeit nötig... und zweistellige Tiefen eine sehr seltene Erscheinung.

Gruß
Ingo
[/quote]

Ich habe mal vor langer Zeit ein Referat zum Schachprogramm Pionier von Botwinnik gehalten, was ja menschliches Denken simulieren sollte - und grandios gescheitert ist. Damals hatte Botwinnik postuliert, daß gute Schachspieler nur 2-5 Züge in einer Stellung überhaupt in Erwägung ziehen. Insofern sind die Engines heutzutage schon ziemlich menschlich in ihrer Suche, nur das Meta-Verständnis für Stellungstypen und dazugehörige Pläne ist noch sehr rudimentär...aber das kompensieren sie mit der immensen Suchgeschwindigkeit.

Stefan

By Benno Hartwig Date 2013-06-16 19:47 Edited 2013-06-16 19:54

[quote="Michael Scheidl"]Das wird schon stimmen bzw. ich sehe es genauso. Die engl. Wikipedia nimmt unter dem Stichwort branching factor für Schach einen Durchschnitt von 35 an, chessprogramming.wikispaces 35...38. Den Beschreibungen zufolge erreicht pures Alpha-Beta - also ohne sonstige Tricks - durch gute Zugsortierung einen Faktor von ca. der Quadratwurzel der Zuganzahl, das wären also um 6 herum...[/quote]Als ich anfing, mich in den 80er für Computerschach zu interessieren, war dies auch noch ein praktisch beobachtbarer Wert.
(Auf Colossus-C64: Matt in 2 fast sofort, Matt in 3 noch recht zügig, Matt in 4 nicht immer in 3 Minuten erreichbar)

Und was existiert da so an Cuts:
- alpha-beta schneidet verlustlos.
- Verbesserung der Zugsortierung, Killerzüge: verlustlos
(hier würde ich eigentlich gern nicht nur eine sehr wahrscheinliche Widerlegung vorn sehen,
sondern eine genügend gute Widerlegung, die voraussichtlich besonders billig erreicht werden kann. Wird so was gemacht?)
- Hashtabellen: verlustlos
- Nullfenstersucher (Scouting) verlustlos
- Tablebases, sofern sie bereits eine Rolle spiele: verlustlos
- futility pruning: verlustlos(?)
- Nullmove: bei genügender Absicherung wohl auch fast verlustlos

Diese Techniken reichen wohl aber bei weitem nicht, um an Faktor 2 heranzukommen.
Vermutlich bedarf es doch noch diverser spekulativer Cuts. Richtig?

- extendet Frontier nodes: birgt wohl auch gewisse Risiken
- ??? (und hier bin ich dann schon mit meinem Latein am Ende)

Unter welchen Stichworten laufen weitere Cuts, die vermutlich ein Stück weit spekulativ sind?
Gibt es irgendwo eine nette Zusammenstellung?

Benno

By Thomas Plaschke Date 2013-06-17 15:50

Ich bin mir nicht sicher, was mit "verlustlos" gemeint ist. Anhand der Auflistung vermute ich mal: Modifikationen des Suchverfahrens, die keinen Informationsverlust beinhalten und zwingend, aber schneller mit weniger Knoten zum gleichen Ergebnis kommen, wie eine MiniMax-Suche (mit genügend Zeit). So verstanden würde ich von den als verlustlos gelisteten Verfahren futility pruning und Nullmove als spekulativ und nicht sicher betrachten. Hashtabellen (wie sie in veröffentlichten Schachprogrammmen eingesetzt werden) sind sehr sicher, aber eben auch nicht 100%.

Ein etwas anderer Aspekt: Im "Großen Computerschach-Buch" (von 1985) wurde bei der Erklärung des "Demoschach"-Programms generell vor selektiven Vertiefungen gewarnt. Sie könnten dazu führen, dass sich die Suche "totsucht". Wesentlich mehr als HV, Schlag- und Schachzüge hatte das "Demoschach"-Programm auch nicht vertieft, wenn ich mich recht erinnere (- Seine Killerzugheuristik berücksichtigte aber bereits mehrere Killerzüge.).
Die Stärke der heutigen Programme scheint mir eher daher zu kommen, dass sie gut spekulieren und so "wissen", welche Züge nicht vertieft werden müssen. Da bleibt mehr Zeit für nützliche Dinge.
- Und außerdem sind sie vergleichsweise rasend schnell!!!

Ein auffälliger Aspekt der Untersuchung von Michael Scheidl ist, dass - anders, als der Alpha-Beta-Algorithmus erwarten ließe - die Zahl der Knoten vom geraden zum ungeraden Halbzug viel niedriger liegen, als man nach der reinen Lehre erwarten könnte: Der Alpha-Beta-Cut wirkt ja nur auf die Zahl der zu untersuchenden gegnerischen Züge. Die eigenen Züge müssen ja stets alle untersucht werden.

Viele Grüße
Th. Plaschke

By Benno Hartwig Date 2013-06-17 18:50 Edited 2013-06-17 18:52

[quote="Thomas Plaschke"]Modifikationen des Suchverfahrens, die keinen Informationsverlust beinhalten und zwingend, aber schneller mit weniger Knoten zum gleichen Ergebnis kommen, wie eine MiniMax-Suche (mit genügend Zeit).

Ja, so meinte ich es.

Zitat:

So verstanden würde ich von den als verlustlos gelisteten Verfahren futility pruning und Nullmove als spekulativ und nicht sicher betrachten.

Anfangs war Nullmove sicher spekulativ, aber dann baute man Überprüfungen ein. Bleibt das Resultat immer noch ein Stück weit spekulativ? Mag sein, dass du Recht hast.
Auch dachte ich, 'Futility prunig' hätte keinen Informationsverlust, der würde erst durch 'Deep futility pruning'. Irre ich da?

Zitat:

Hashtabellen (wie sie in veröffentlichten Schachprogrammmen eingesetzt werden) sind sehr sicher, aber eben auch nicht 100%.

Wusste ich auch nicht.

Kannst du kurz skizieren, wodurch hier Informationsverluste bzw. ein spekulatives Moment hereinkommen?

Zitat:

Die Stärke der heutigen Programme scheint mir eher daher zu kommen, dass sie gut spekulieren und so "wissen", welche Züge nicht vertieft werden müssen. Da bleibt mehr Zeit für nützliche Dinge.

Das sind dann doch begründet-spekulative Cuts, richtig? Weißt du, welche Art zusätzliche Cuts da ggf. hinzukommen?

Code:

- Und außerdem sind sie vergleichsweise rasend schnell!!!

Im 'Großen Computerschach Buch" (Data Becker) hast du dann ja auch sicher das Programm im interpretierten BASIC gesehen, richtig? Matt in 2 brauchte da dann schon!!

Zitat:

Bei idealer Zugsortierung wirken die Cuts von alpha-beta durchaus auf allen Tiefen (bis auf die allererste natürlich), nur eben unterschiedlich stark. Ebenen mit vielen und Ebenen mit weniger vielen Cuts. Und ich denke, in dem Maße, wie die Zugsortierung dann doch nicht ideal ist, 'Fehler' macht, vermengt sich das noch mehr.

Benno

By Thomas Plaschke Date 2013-06-17 21:12

So viele Fragen. Meine Antworten gebe ich als interessierter Laie, der sich seit Jahrzehnten mit seinen (Schach-)Computer-Neigungen herumschlägt.

--> Das war eine "Ich-bin-kein-Fachmann-Warnung"!

Zum Nullmove: Ist m.E. nach wie vor spekulativ. Natürlich ein geniales Konzept, im Suchbaum einfach mal die Schachregeln zu ignorieren (Zugrechtswechsel). Aber die Gegenmaßnahmen gegen das Nullmove-Problem "Zugzwang" beschränken sich darauf, den Nullmove unter bestimmten Bedingungen nicht anzuwenden. Ob die jeweilige Stellung eine "Nullmove-besser-nicht-nutzen-Stellung" ist, wird aber wohl von keinem Programm sicher erkannt. Daher: spekulativ, weil Fehlgriffe möglich.

Futility pruning: Gehört zu den Verfahren, die mittels Abschätzung "wenig versprechende" Varianten ausblenden. Die Ausgangsfrage (sinngemäß) "Welche cuts sind verlustlos/sicher?" würde ich provokativ so beantworten: Alle forward pruning-Methoden sind nicht sicher. Grund: Sie rechnen eben nicht, sondern beschneiden den Spielbaum (darauf kommt es an) aufgrund von Abschätzungen.

Hashtabellen: Hashkollisionen. Seltener als Supernovae, aber prinzipiell nicht vermeidbar. Anzunehmen, dass keine Hashkollision eintreten wird, ist Spekulation.

Was gibt es für spekulative Cuts, um ungünstige Varianten gar nicht erst zu vertiefen: Keine Ahnung. Einleuchten würden mir Remis-Regeln (das wäre nicht mal spekulativ) oder Material-Abschätzung (nach 4 Halbzügen Dame und Turm im Nachteil, da könnte man auf die vertiefte Suche im 6 Halbzug vielleicht verzichten wollen).

Demoschach: Erinnerungen. Ich hatte das Programm für den Atari ST nach GFA-BASIC übertragen und den Zuggenerator in Assembler umgeschrieben. Das ganze dann kompiliert. Wie hoch die Knotenleistung des Programms war, weiß ich nicht mehr. Ach ja, damals war's ...

Zu Alpha-Beta: Meine geschilderte Erwartung bezieht sich darauf, dass der Anziehende (der auf Halbzugebene 1) alle seine Züge durchrechnen muss - nach dem Motto "Versäume nie ein Schachgebot - es könnte Matt sein!". Auch auf allen weiteren Ebenen, in denen er am Zug ist (3, 5, 7 etc. also allen ungeraden), muss er alle(!) seine Züge berücksichtigen. Tut er das nicht, beschneidet er den Spielbaum spekulativ (s.o. Motto: "Ich mache keine schlechten Züge!") Von seinem Gegner braucht er im Spielbaum (auf der geraden Baumebene) im Idealfall nur einen einzigen Zug - nämlich den, der alle eigenen Züge der darunter liegenden ungeraden Baumebene widerlegt. Wenn ich also auf der ungeraden Ebene alle Züge untersuchen muss, auf der geraden dagegen deutlich weniger müsste sich das in der Rechenzeit pro Suchebene ablesen lassen. Das ist ja auch gerade der Nutzen des Alpha-Beta-Algorithmus.
Geistesblitz: Es wäre wie beschrieben, würden nicht alle Programme, die wir beobachten iterativ vertiefen. Wir sehen ja gar nicht die Zeit pro Halbzug-Ebene, sondern die (undifferenzierte) Gesamtsumme des Zeitverbrauchs jeweilige Suchtiefe.

Sorry für meinen Irrtum. Also wieder auf Anfang: Die Zeit, die ein Programm in einer bestimmten Halbzugebene verbringt, wird weder angezeigt noch dürfte sie zu ermitteln sein.

Viele Grüße
Th. Plaschke

P.S.: Wie spekulativ heute geschnitten wird, kann man an folgender Stellung sehen,
die gerade in einem anderen Thread in diesem Forum gezeigt wird:

(Shinkman, 1908, Matt in 8)

Der Meister der Spekulation schafft es in Sekundenschnelle:

Engine:

Stockfish 3 JA 64bit SSE4.2:
  9/21  00:01    13.064.435  7.823.014  +M8  1.b8S+ Txb8 2.axb8S+ Kd6 3.c8S+ Ke6 4.d8S+ Lxd8 5.exd8S+ Kf6 6.g8S+ Dxg8 7.hxg8S+ Txg8 8.fxg8S+

Aber manchmal ist der konservative Ansatz erfolgreicher (wobei ich die selektive Spitze bemerkenswert finde):

Engine:

Colossus 2008b:
  6/37  00:00       211.001  2.577.607  +M8  1.b8S+ Txb8 2.axb8S+ Kd6 3.c8S+ Ke6 4.d8S+ Lxd8 5.exd8S+ Kf6 6.g8S+ Dxg8 7.fxg8S+ Txg8 8.hxg8S+

Übrigens tut sich manche Engine sehr schwer mit diesem Problem ... (und vielleicht nicht nur wegen der Unterverwandlung)

By Werner Mueller Date 2013-06-18 07:39

[quote="Thomas Plaschke"]...
Zum Nullmove: Ist m.E. nach wie vor spekulativ. Natürlich ein geniales Konzept, im Suchbaum einfach mal die Schachregeln zu ignorieren (Zugrechtswechsel). Aber die Gegenmaßnahmen gegen das Nullmove-Problem "Zugzwang" beschränken sich darauf, den Nullmove unter bestimmten Bedingungen nicht anzuwenden. Ob die jeweilige Stellung eine "Nullmove-besser-nicht-nutzen-Stellung" ist, wird aber wohl von keinem Programm sicher erkannt. Daher: spekulativ, weil Fehlgriffe möglich.
...
[/quote]Unter den von mir verwendeten aktuellen Engines (Houdini, Stockfish, Fritz, Rybka) leistet sich nach wie vor (Kommodo 5.1 kann es auch nicht) nur Houdini den Luxus, ein #6 nicht zu 'übersehen' (btw: seit der allerersten Version).

Quelle und Beschreibung der simplen Lösung:
http://forum.computerschach.de/cgi-bin/mwf/topic_show.pl?pid=29393

By Roland Riener Date 2013-06-18 11:22

Hi,

Neben Houdini 3 schaffen es auch Strelka 5.5 und Critter 1.6a, alle in etwa 25 Sekunden auf meiner moderaten Hardware.

Grüße
Roland

By Ingo Bauer Date 2013-06-18 13:57

[quote="Roland Riener"]
Hi,

Neben Houdini 3 schaffen es auch Strelka 5.5 und Critter 1.6a, alle in etwa 25 Sekunden auf meiner moderaten Hardware.

Grüße
Roland
[/quote]

Ups

Ingo

By Benno Hartwig Date 2013-06-21 20:38 Edited 2013-06-21 20:43

Zitat:

Zum Nullmove: Ist m.E. nach wie vor spekulativ.

Du wirst wohl Recht habe. Allerdings ist nach meinem Eindruck die Fehlerwahrscheinlichkeit hier ausgesprochen klein geworden. Aber prinzipiell spekulativ.

Zitat:

Futility pruning: ... sondern beschneiden den Spielbaum (darauf kommt es an) aufgrund von Abschätzungen.

Wirklich auch beim einfachen Futility Pruning, wo (wie ich es verstand) nur auf der letzten Schicht der Vollsuche geschnitten wird? Ich glaubte, hier wird das geschnitten, was sicher(?) in der Ruhesuche eh zum Schnitt führen würde. Aber vielleicht verstand ich es auch falsch.

Zitat:

Hashtabellen: Hashkollisionen. Seltener als Supernovae, aber prinzipiell nicht vermeidbar.

Und warum soll das zu einer Spekulation führen? Das wird doch erkannt und behandelt, als gebe es einfach keinen Hashtreffer. Dann wird eben nicht geschnitten und stattdessen gerechnet. Oder übersehe ich da was? Hin und wieder einfach mit einem echt falschen Wert zu rechnen, würde die Ergebnisqualität wohl doch zu heftig torpedieren, denke ich.

Zitat:

Nein. so läuft das nicht.
Es wird auf jeder Ebene geschnitten, nur eben unterschiedlich viel.

Idealisiertes Beispiel mit Suchtiefe 5, ideale Zugsortierung, immer 3 Züge zur Auswahl:

Code:

Suchbaum                                                     Züge   Cuts
123 1 1  123 123  1 1 1  1 1 1  123 123 123  123 123 123       35    16 von 51
1___2_3  1   1    1_2_3  1_2_3  1   1   1    1   1   1         17    16 von 21
1________2___3    1      1      1___2___3    1___2___3         11     4 von 15
1_________________2______3      1            1                  5     4 von 9
1_______________________________2____________3                  3     0 von 3

In solchen idealisierten Szenarien wechseln sich also Stufen mit vielen und wenigen Cuts ab.
In dem Maße aber, wie der erste Widerlegunsversuch in einer widerlegbaren Stellung scheitert, wird sich dies vermutlich etwas auflockern.

Benno

By Stefan Pohl Date 2013-06-16 15:42

[quote="Kurt Utzinger"]
Hallo Michael
Ist dieser B.F. von irgendwelcher Relevanz?
Mfg
Kurt
[/quote]

Auf jeden Fall! Ich bin der Ansicht, daß die Faustregel gilt, daß je niedriger der BF ist, desto mehr profitiert eine Engine von mehr Bedenkzeit bzw. schnellerer Hardware weil je größer der BF ist, desto eher frißt sich die Engine bei langen Bedenkzeiten oder schneller Hardware im Suchbaum fest.
Ich warte schon mit Spannung auf die Ergebnisse von Andreas Strangmüller, diese sollten m.E. ergeben, daß Stockfish mehr zulegt (mit mehr Zeit) als Komodo und dieser wiederum etwas mehr als Houdini...Schaun mer mal. Aber es wäre zumindest logisch.

Stefan

By Christian Schmidt Date 2013-06-16 16:16

Ich komme zur gegenteiligen Schlussfolgerung. Wie wichtig ist es, ob eine Engine bis Zug 30 oder 31 rechnet, wenn dieser Weg eh wahrscheinlich nicht zustande kommt? Umgekehrt "übersieht" eine Engine bei einem höheren BF tendenziell weniger.

By Stefan Pohl Date 2013-06-17 02:29

[quote="Christian Schmidt"]
Ich komme zur gegenteiligen Schlussfolgerung. Wie wichtig ist es, ob eine Engine bis Zug 30 oder 31 rechnet, wenn dieser Weg eh wahrscheinlich nicht zustande kommt? Umgekehrt "übersieht" eine Engine bei einem höheren BF tendenziell weniger.
[/quote]

Das klingt zwar naheliegend, ist aber definitiv falsch, denn dann müßte - konsequent zuende gedacht - ein Programm, das gar nichts spekulativ abschneidet und nur das Alpha-Beta Pruning nutzt, allen modernen Engines überlegen sein, denn das übersieht nie etwas innerhalb des Suchhorizonts und rechnet keine tiefen Varianten durch, die eh nie zustandekommen. Das ist aber definitiv nicht der Fall, sondern wir beobachten im Gegenteil, daß ältere Engines höhere BFs haben (z.B. ProDeo) und geringere Suchtiefen erreichen als moderne Engines (auf identischer, moderner Hardware). Und Houdini, Stockfish und Co rauchen ProDeo und andere Steinzeitengines in der Pfeife...

Stefan

By Michael Scheidl Date 2013-06-17 04:55

Ich lese immer von sog. "Reductions". Ich verstehe davon eher nichts, aber wahrscheinlich ist das mitentscheidend dafür daß so geringe B.F. funktionieren und insgesamt (viel) stärker sind als große B.F. Wenn ich richtig verstehe, spricht man von Pruning wenn Züge bzw. Äste vollständig ignoriert , also weggeschnitten werden, während Reductions darüber entscheiden ob bestimmte - vorerst - unwichtig scheinende Äste nur weniger tief durchforstet werden.

http://chessprogramming.wikispaces.com/Reductions

(Das häufig zu sehende Kürzel LMR steht für late move reductions.)

Ich weiß nicht wie groß die Suchtiefenunterschiede dabei sind, es leuchtet aber ein daß bei einer typischen, recht tiefen Suche auch eine etwas kürzere z.B. "plötzlich" den Sinn eines Opfers erfassen kann, das bisher wegen augescheinlicher Sinnlosigkeit nur reduziert durchsucht wurde. Somit ist dieses, anderes als bei Pruning, nicht gänzlich übersehen worden sondern nur später treffender bewertet worden.

Soweit meine Interpretation dieser Techniken ohne Programmierkünste zu beherrschen, aber ich habe das Gefühl, das "grobe Bild" sozusagen zeichnet sich ab...

By Frank Brenner Date 2013-06-16 16:44

Die Schlussfolgerung ist leider falsch.

Viel wichtiger ist die Qualität des Suchbaums, d.h. wieviel übersehen wird. Dies in Zahlen auszurücken oder in Prozent ist nicht so einfach möglich.

Letzlich zählt nur eins: Die Spielstärke in Abhängigkeit von der Bedenkzeit. Um diese funktion zu bestimmen, hilft der BF nicht.

Eine Engine mit sehr kleinem BF und guter platzierung bei kleinen Bedenkzeiten könnte aber ein guter Kandidat sein für eine Engine die unter Fernschachbedingungen besser ist. Aber hier helfen halt nur tausende Von Partien mit sehr langer Bedenkzeit.

Es gibt jedenfalls noch keine verkürzten tests um den Spielstärkenverlauf zuverlässig für längeree Bedenkzeiten zu prognostizieren.

By Stefan Pohl Date 2013-06-17 02:22

[quote="Frank Brenner"]

Es gibt jedenfalls noch keine verkürzten tests um den Spielstärkenverlauf zuverlässig für längeree Bedenkzeiten zu prognostizieren.
[/quote]

Das wird sich ja bald ändern, dank des aufwendigen Testvorhabens von Andreas Strangmüller, welches exzellente Testbedingungen mit hoher Partienzahl und 3 Bedenkzeitstufen hat. Dann werden wir ja sehen, ob meine Prognose stimmt oder nicht.

Stefan

By Michael Scheidl Date 2013-06-17 05:25 Edited 2013-06-17 05:28

Wenn wir von der Spielstärke insgesamt reden, ist ja zudem neben der Suche und ihrer Qualität die Stellungbewertung und deren Qualität der zweite bestimmende Faktor. Ich wüßte nicht wie man das zu gewichten hätte. Jedenfalls kann man annehmen, daß all diese hunderttausenden ultrakurzen Partien welche Entwickler offenbar durchführen, mindestens sosehr dem Feintuning der Bewertung dienen wie dem Austesten von Änderungen der Suche.

Als Critter 1.6a bei nTCEC Saison 1 - Bedenkzeit 150m+60s(!) - überraschend früh aussschied, meinten einige Kibitze im Chat sinngemäß, so unerwartet sei das nicht denn Critter sei nicht gut auf langer Bedenkzeit. Damals habe ich mich gewundert, aber wenn wir nun die Branchingfaktoren vergleichen, wird es plausibel.

Also z.B. für eine Distanz von Tiefe X zu X+10:

Stockfish 3: 1,59^10 = 103

Critter 1.6a: 2,05^10 = 1.311

D.h. um zehn Plies tiefer zu kommen, braucht Critter im Schnitt ~13 Mal so lange wie Stockfish?! Kann das überhaupt stimmen? Hoffentlich habe ich mich nicht fundamental geirrt...

Für sich genommen ist das natürlich nicht alleine entscheidend, sind doch dieselben Rechentiefen verschiedener Engines aus diversen Gründen (Bewertung, Pruning, Reductions, MP-Code, was sich - meistens - unterscheiden wird) nie gleich viel wert.

By Stefan Pohl Date 2013-06-17 05:58

[quote="Michael Scheidl"]
Wenn wir von der Spielstärke insgesamt reden, ist ja zudem neben der Suche und ihrer Qualität die Stellungbewertung und deren Qualität der zweite bestimmende Faktor. Ich wüßte nicht wie man das zu gewichten hätte. Jedenfalls kann man annehmen, daß all diese hunderttausenden ultrakurzen Partien welche Entwickler offenbar durchführen, mindestens sosehr dem Feintuning der Bewertung dienen wie dem Austesten von Änderungen der Suche.

Als Critter 1.6a bei nTCEC Saison 1 - Bedenkzeit 150m+60s(!) - überraschend früh aussschied, meinten einige Kibitze im Chat sinngemäß, so unerwartet sei das nicht denn Critter sei nicht gut auf langer Bedenkzeit. Damals habe ich mich gewundert, aber wenn wir nun die Branchingfaktoren vergleichen, wird es plausibel.

Also z.B. für eine Distanz von Tiefe X zu X+10:

Stockfish 3: 1,59^10 = 103

Critter 1.6a: 2,05^10 = 1.311

D.h. um zehn Plies tiefer zu kommen, braucht Critter im Schnitt ~13 Mal so lange wie Stockfish?! Kann das überhaupt stimmen? Hoffentlich habe ich mich nicht fundamental geirrt...
[/quote]

Im Prinzip stimmt die Rechnung, sie setzt allerdings voraus, daß der BF für alle 10 zusätzliche Iterationen auch gleich bleibt. Ob das so ist, ist eine andere Frage...Es wäre durchaus vorstellbar, eine Engine so zu programmieren, daß der BF in kleineren Rechentiefen größer ist und in höheren Rechentiefen geringer wird, um taktische Löcher im Kurzzug-Bereich nicht zuzulassen, während man in höheren Rechentiefensphären ruhig etwas spekulativer suchen könnte.

Stefan