Reine BruteForce Engine

By Peter Martan Date 2024-10-06 12:34 Edited 2024-10-06 12:37 Upvotes 2

Frank Meißen schrieb:

Hallo zusammen,
Genauso gut wäre natürlich eine Option in einer der verbreiteten engines, von ProDeo bis Stockfisch.

Den Parallelthread wirst du ja wahrscheinlich kennen:

https://talkchess.com/viewtopic.php?p=968184#p968184

Reines brute force wird man bei aktuelleren Engines (die ich kenne) nicht mehr leicht finden, du könntest dir mal die Option "full depth threads" von ShashChess auf Code- Ebene anschauen, ob es dem nahe kommt, was du suchst. Und dasselbe gibt's auch noch ohne NNUE bei Alexander vom selben Autor.

By Frank Meißen Date 2024-10-06 14:01

Hallo Peter,
besten Dank für die Antwort.
Ja, den Parallethread kenne ich, habe aber mit den Postings keine Lösung für mich erkennen können.
LG
Frank

By Max Siegfried Date 2024-10-06 13:25

Frank Meißen schrieb:

Hallo zusammen,
gibt es eine Engine, die strikt BruteForce rechnet, also kein alpha/beta, keine Selektivität etc?
Genauso gut wäre natürlich eine Option in einer der verbreiteten engines, von ProDeo bis Stockfisch.

Ich habe leider nichts gefunden, möchte aber einige Dinge ausprobieren.

LG
Frank

Deep Blue
https://www.arte.tv/de/videos/101841-001-A/rematch-1-6/

By Lars B. Date 2024-10-06 13:39 Upvotes 3

Hallo Frank,

erstmal: alpha/beta ist auch brute force.

Minimax (aus Schach am PC) ist ein reines Brute-Force-Programm, meine ich mich zu entsinnen.

Ansonsten kannst Du mit nur geringen Programmierkenntnissen eines der zahlreichen im Quellcode verfügbaren Programme nehmen und jegliche Selektivität auskommentieren.

<ironie> Oder, ganz dolle modern, Du läßt ChatGPT das für Dich erledigen </ironie>

Grüße
Lars

By Frank Meißen Date 2024-10-06 13:59 Upvotes 1

Hallo Lars,
besten Dank für die Antwort!
Ich wollte halt etwas "stabiles" als uci oder winboard engine

Mal sehen ob ich das mit ChatGPT (wobei ich mit Claude.ai meist bessere Ergebnisse erziele) klappt.

LG
Frank

By Rainer Neuhäusler Date 2024-10-07 21:30

Lars B. schrieb:

erstmal: alpha/beta ist auch brute force.

Nö, Alpha-Beta ist eine Selektionsverfahren, das Suchbaum/Varianten/Knoten stark und effizient reduziert, ohne die überflüssigen und sinnlosen Züge bewerten zu müssen. Brute Force bewertet alle legalen Züge und selektiert den Spielzug ausschließlich nach dem Minimax-Prinzip.
Historisch gesehen verschoben sich die Programme von Shannon-A immer mehr in Richtung Shannon-B. A/B-Engines bewerten alle legalen Züge nur in flacher Suchtiefe, das ist in Bruchteilen von Sekunden erledigt, und dann wird's bereits selektiv.

Lars B. schrieb:

Minimax (aus Schach am PC) ist ein reines Brute-Force-Programm, meine ich mich zu entsinnen.

Wenn du unter reinem Brute-Force Shannon-A verstehts, dann nein, wenn du Alpha-Beta implizierst, dann ja.

Lars B. schrieb:

Ansonsten kannst Du mit nur geringen Programmierkenntnissen eines der zahlreichen im Quellcode verfügbaren Programme nehmen und jegliche Selektivität auskommentieren.

Das geht bei MiniMax recht gut, da bei dem Basic-Programm der Alpha-Beta-Algo in Form einer "Function" gut als separater Programmteil zu handeln ist.

Lars B. schrieb:

<ironie> Oder, ganz dolle modern, Du läßt ChatGPT das für Dich erledigen </ironie>

Wenn du einen Experten zu Hand hast, der die Fehler ausmerzt. Das gleiche bei den fachlichen Recherchen. Mit der Überprüfung des Wahrheitsgehaltes geht mehr Zeit drauf, als wenn du die notwendigen Infos lieber gleich zusammengoogelst. Schreiben kann er am besten, geschäftlich, privat und auch literarisch.
.

By Lars B. Date 2024-10-09 08:51 Upvotes 6

Hallo Rainer,

Rainer Neuhäusler schrieb:

Also, mir scheint, Dein Verständnis von Baumsuchverfahren ist deutlich zu abstrakt. Eventuell hülfe es, wenn Du Dir mal ganz konkret anschaust, wie Alphabeta funktioniert; es gibt zahlreiche sehr gute und bebilderte Erklärungen, auch im Archiv dieses Magazins.

Natürlich kann jeder Begriffe wie "Brute Force" und "Selektionsverfahren" definieren, wie er möchte, aber will man verstanden werden, ist es oft schlau, sich zu informieren, ob und wie ein Begriff bereits definiert ist oder in welchem Sinne er von praktisch allen verwendet wird. Und das ist bei Minimax/Alphabeta/Bruteforce/Selektivität ziemlich eindeutig.

Da Minimax und Alpha/Beta exakt zum selben Ergebnis gelangen, also genau denselben Zug mit identischer Bewertung ermitteln, und darüber hinaus beide bis zu einer festen, vorher definierten Tiefe suchen, sehe ich ehrlich gesagt nur wenig Grund, von der allgemein anerkannten Verwendung des Begriffs Bruteforce abzuweichen.

Sieh es mal so: Minimax bezeichnet zwar ein Suchverfahren, der Name stammt aber daher, daß in der Suche auf jeder Tiefe entweder die eigene Bewertung maximiert oder die des Gegners minimiert wird. Darum heißt das Minimax. Alpha/Beta macht haargenau dasselbe, es läßt aber die Knoten weg, die zum Zeitpunkt, in der die Suche den Knoten erreicht, nachweislich keinen Einfluß auf die Bewertung haben können.

Das ist keine Selektivität in dem Sinne, der diesem Begriff von Schachprogrammierern gegeben wird. Guck, wenn die Suche an einen potentiell entbehrlichen Knoten kommt, muß sie eine Entscheidung treffen. Es gibt zwei Sorten von solchen Knoten: Die einen, die können weg, ohne daß es das Ergebnis der Suche beeinflußt. Das sind die, die Alphabeta wegschneidet. Und dann gibt es die, bei denen es /wahrscheinlich/ keinen Unterschied macht, das sind die, die selektive Verfahren verkürzt untersuchen. Selektive Verfahren können falsch liegen, wenn sie einen Knoten nicht bis zur nominellen Suchtiefe untersuchen, Alphabeta nicht, das liegt immer richtig.

Rainer Neuhäusler schrieb:

A/B-Engines bewerten alle legalen Züge nur in flacher Suchtiefe, das ist in Bruchteilen von Sekunden erledigt, und dann wird's bereits selektiv.

Das ist leider im weiten Spektrum richtig/falsch eher auf der falschen Seite angesiedelt.

LG
Lars

By Rainer Neuhäusler Date 2024-10-09 13:22 Edited 2024-10-09 13:24

Hallo Lars,

also das Abstraktionsniveau hast du mit deinem 'umfangreichen Beitrag': "alpha/beta ist auch brute force" vorgegeben. Da erschien mir wenigstens eine kleine Differenzierung vonnöten, eine Abhandlung zum Baumsuchverfahren aber dann doch zu ausführlich und für einen alten Computerschachhasen zu belehrend

Zum Thema Begriffsdefinition, Brute Force, Alpha-Beta-Algorithmus, Minimax habe ich in den folgenden Beiträgen das meine gesagt. Das Ganze hat sich dann ja auch mehr zur Begriffsklärung der Shannon-A-Strategie hin verschoben.

Schau mal wieder vorbei

Rainer

By Olaf Jenkner Date 2024-10-09 14:27 Upvotes 5

Rainer Neuhäusler schrieb:

eine Abhandlung zum Baumsuchverfahren aber dann doch zu ausführlich und für einen alten Computerschachhasen zu belehrend

Es ist traurig, daß die alten Hasen nicht mal die primitivsten Grundlagen des Computerschachs kennen.
Dieser ganze Thread ist ja nur Geschwurbel, das so einfache Dinge wie Brute Force, Minimax und Alpha-Beta
zu einem geisteswissentschaftlichen Brei verrührt und damit ungemein kompliziert erscheinen läßt.
Wenn Lars die Begriffe geduldig und mustergültig erklärt, fühlt sich manch einer "belehrt".
Wer alles besser weiß, möchte nichts mehr lernen.

By Rainer Neuhäusler Date 2024-10-09 15:17

Olaf Jenkner schrieb:

Rainer Neuhäusler schrieb:

eine Abhandlung zum Baumsuchverfahren aber dann doch zu ausführlich und für einen alten Computerschachhasen zu belehrend

Von oben herab mosern kann ein jeder. So hilfst du uns auch nicht weiter. Steig herunter vom hohen Ross, mach dem Geschwurbel ein Ende. Sei kompetent und bemühe dich selbst um einen konstruktiven Beitrag zum Thema.
.

By Olaf Jenkner Date 2024-10-09 15:25 Upvotes 2

Rainer Neuhäusler schrieb:

So hilfst du uns auch nicht weiter.

Braucht ihr wirklich Hilfe?

Bitteschön:

Lest dreimal ganz langsam den Beitrag von Lars und wenn ihr dann noch Fragen habt, schreibt es hier hin.

By Rainer Neuhäusler Date 2024-10-09 16:38 Edited 2024-10-09 16:59

Olaf Jenkner schrieb:

Rainer Neuhäusler schrieb:

So hilfst du uns auch nicht weiter.

Braucht ihr wirklich Hilfe?
Bitteschön:
Lest dreimal ganz langsam den Beitrag von Lars und wenn ihr dann noch Fragen habt, schreibt es hier hin.

Wenn du nicht mehr weißt als das, was da in den wenigen Zeilen über Brute Force, Alpha-Beta, Minimax etc. steht, und was man in zig Artikeln, Büchern, Internetseiten, ausführlicher und genauer nachlesen kann, dann bist du entlassen
.

By Thomas Plaschke Date 2024-10-06 15:06 Upvotes 2

Frank Meißen schrieb:

… kein alpha/beta …

Mit Alfa-Beta-Algorithmus ist's auch noch Brute-Force. Ohne wäre es nur Minimax und überhaupt nicht effizient in Bezug auf Rechentiefe pro Zeit bzw. Knoten. Das Ergebnis mit Alfa-Beta ist identisch, aber schneller da.

VG
Th. Plaschke

By Rainer Neuhäusler Date 2024-10-07 21:45

Frank Meißen schrieb:

Hallo zusammen,
gibt es eine Engine, die strikt BruteForce rechnet, also kein alpha/beta, keine Selektivität etc?
Genauso gut wäre natürlich eine Option in einer der verbreiteten engines, von ProDeo bis Stockfisch.
Ich habe leider nichts gefunden, möchte aber einige Dinge ausprobieren.

"Strikt BruteForce rechnen, also kein alpha/beta, keine Selektivität" entspricht genau der Shannon A-Strategie. Alle legalen Züge einer Stellung werden materiell und positionell bewertet und der beste Zug wird dann nach dem Minimax-Prinzip bestimmt. Solche Programme, Rechnerboliden und Schachcomputer gab es. Meines Wissens rechneten die ersten Bell-Versionen nur mit der A-Strategie und auch mein erster Schachcomputer, der Chess Champion MK I. https://www.schachcomputer-online-museum.de/index-1/novag/novag-chess-champion-mk-i-1978/ Er konnte nur Weiß und brachte es mit reinem Shannon A-Brute Force auf 762 Elo.

Die Aussortierung überflüssiger Knoten und Züge durch den Alpha-Beta Algorithmus beschneidet den Varianten-/Zug-/Such-/- Spielbaum bereits sehr stark und effizient. Es wird eine A/B-Engine daraus. Die Missverständnisse entstehen wohl deshalb, weil es es Leute gibt, die Shannon-A mit Brute Force gleichsetzen. Jedoch alle A/B-Engines, wie schon der Name sagt, untersuchen in mehr oder weniger flacher Zugtiefe alle legalen Züge, bis dann der Alpha-Beta Logarithmus und die vielen weiteren Selektionsverfahren greifen.
.

By Thomas Plaschke Date 2024-10-07 22:29 Upvotes 1

>… "Strikt BruteForce rechnen, also kein alpha/beta, keine Selektivität" entspricht genau der Shannon A-Strategie. …

… und ähnliche Zitate. Alpha-Beta ist eine Optimierung des Minimax-Algorithmus. Beide Algorithmen kommen zum gleichen - identischen - Ergebnis. Ich verstehe nicht, warum die "wegoptimierten" Knoten, die offensichtlich keine Relevanz für das Ergebnis haben, für ein "reines" Brute-Force-Programm wichtig sein könnten und aus einem Shannon-A-Programm ein … was auch immer Programm machen soll (selektiv wird es dadurch nicht).

Im Übrigen war Alpha-Beta zum Zeitpunkt als Shannon die Suchstrategien A und B beschrieb noch unbekannt. Unter diesem Aspekt optimiert Alpha-Beta ein Shannon-A-Programm, wenn man sich darauf kapriziert als dessen zwingendes und unverzichtbares Merkmal nicht das Durchlaufen aller Knoten des vollständigen Spielbaums zu fordern, was in den mir zugänglichen Quellen niemand tut.

Viele Grüße
Th.Plaschke

By Rainer Neuhäusler Date 2024-10-08 22:41 Edited 2024-10-08 22:45

Thomas Plaschke schrieb:

… und ähnliche Zitate. Alpha-Beta ist eine Optimierung des Minimax-Algorithmus. Beide Algorithmen kommen zum gleichen - identischen - Ergebnis.

Prima, je weniger Knoten, desto weniger Minimax-Berechnungen. Eine Binsenweisheit. Wer und welche Formulierung hat was dagegen? Welche Programmteile nun primär, sekundär und insgesamt von Alpha-Beta profitieren (Optimierung), bedürfte wohl eines längeren Diskurses.

Thomas Plaschke schrieb:

Ich verstehe nicht, warum die "wegoptimierten" Knoten, die offensichtlich keine Relevanz für das Ergebnis haben, für ein "reines" Brute-Force-Programm wichtig sein könnten und aus einem Shannon-A-Programm ein … was auch immer Programm machen soll (selektiv wird es dadurch nicht).

Da muss eine Missverständnis vorliegen, fasch interpretiert oder nicht eindeutig formuliert. Ein „reines Brute Force Programm“, das ich eindeutigkeitshlaber lieber als Shannon-A Programm bezeichne, hat keinen Alpha-Beta Algorithmus, infolgedessen auch keine wegoptimierten Knoten. Integriert man letzteren in das A-Programm, wird eine A/B-Programm daraus (so heissen die und nicht „was auch immer : -) Das war doch die zentrale Rede meines Beitrages ??? Aber vielleicht reden wir da aneinander vorbei.

Thomas Plaschke schrieb:

Im Übrigen war Alpha-Beta zum Zeitpunkt als Shannon die Suchstrategien A und B beschrieb noch unbekannt. Unter diesem Aspekt optimiert Alpha-Beta ein Shannon-A-Programm, wenn man sich darauf kapriziert als dessen zwingendes und unverzichtbares Merkmal nicht das Durchlaufen aller Knoten des vollständigen Spielbaums zu fordern, was in den mir zugänglichen Quellen niemand tut.

Aha... Ein komplexes Elaborat mit vielen Bezugspunkten. Wiedervorlage für Momente kognitiver Höchstform

Fazit: Ich höre entferntes Gebell, erkenne aber keinen Grund

Als passionierter Forumsstöberer weiß ich, dass Alpha/Beta seit jeher ein diskussonsförderndes Thema ist. Für Interessierte hier eine Diskussion, auch mit Beteiligung von Plaschke, Neuhäusler:
https://forum.computerschach.de/cgi-bin/mwf/topic_show.pl?pid=163322#pid163322
.

By Jörg Oster Date 2024-10-08 23:02 Upvotes 3

Das sehe ich etwas anders.
Reine Alpha-Beta-Suche ist immer noch Typ Shannon-A.

By Rainer Neuhäusler Date 2024-10-08 23:34

Jörg Oster schrieb:

Das sehe ich etwas anders.
Reine Alpha-Beta-Suche ist immer noch Typ Shannon-A.

Das wäre mir neu, ist aber wenigstens auf den Punkt gebracht. Das schreit nach Recherche..
.

By Thomas Plaschke Date 2024-10-09 00:26 Upvotes 1

Rainer Neuhäusler schrieb:

...
Das wäre mir neu, ist aber wenigstens auf den Punkt gebracht. Das schreit nach Recherche..
.

Es geht auch leiser. Bspw. findet man bspw. in der CPW:

The Type A Strategy was coined in 1949 by Claude Shannon in his groundbreaking publication "Programming a Computer for Playing Chess" as a brute-force strategy, ...

("Die Strategie vom Typ A wurde 1949 von Claude Shannon in seiner bahnbrechenden Veröffentlichung "Programming a Computer for Playing Chess" als Brute-Force-Strategie bezeichnet, ...")
und

However, with the advent of alpha-beta and all its enhancement, brute-force got very successful from the 70s until present, since the task of classifying and excluding "not plausible" moves, turned out to be quite difficult and error-prone.

("Mit dem Aufkommen von Alpha-Beta und all seinen Verbesserungen wurde Brute-Force jedoch von den 70er Jahren bis heute sehr erfolgreich, da sich die Aufgabe, „nicht plausible“ Züge zu klassifizieren und auszuschließen, als ziemlich schwierig und fehleranfällig erwies.")

Außerdem wird Shannon dort so zitiert: Eine Strategie dieser Art, bei der alle Varianten bis zu einer bestimmten Anzahl von Zügen berücksichtigt werden ... ("Eine Strategie dieser Art, bei der alle Varianten bis zu einer bestimmten Anzahl von Zügen berücksichtigt werden ..."). Daraus Shannon zu unterstellen, dass er zu Programmen des A-Typs nur solche zählt, die ausschließlich den "reinen", unveränderten und vor allem nicht optimierten Minimax-Algorithmus verwenden, weil nur der alle Zweige des Suchbaums durchläuft, geht mE zu weit. Mir fällt kein Grund ein, warum Shannon eine, das Suchergebnis nicht verändernde Optimierung des Algorithmus hätte ablehnen sollen. Er hätte genug Gelegenheit gehabt, dagegen Einwände vorzubringen oder seine Skepsis zu äußern.

Viele Grüße
Th. Plaschke

By Rainer Neuhäusler Date 2024-10-09 02:10 Edited 2024-10-09 02:14

Thomas Plaschke schrieb:

Rainer Neuhäusler schrieb:

...
Das wäre mir neu, ist aber wenigstens auf den Punkt gebracht. Das schreit nach Recherche..

Es geht auch leiser. Bspw. findet man bspw. in der [url]CPW[/url]:
<code>The Type A Strategy was coined in 1949 by Claude Shannon in his groundbreaking publication "Programming a Computer for Playing Chess" as a brute-force strategy, ...</code> ("Die Strategie vom Typ A wurde 1949 von Claude Shannon in seiner bahnbrechenden Veröffentlichung "Programming a Computer for Playing Chess" als Brute-Force-Strategie bezeichnet, ...")
und
<code>However, with the advent of alpha-beta and all its enhancement, brute-force got very successful from the 70s until present, since the task of classifying and excluding "not plausible" moves, turned out to be quite difficult and error-prone.</code> ("Mit dem Aufkommen von Alpha-Beta und all seinen Verbesserungen wurde Brute-Force jedoch von den 70er Jahren bis heute sehr erfolgreich, da sich die Aufgabe, „nicht plausible“ Züge zu klassifizieren und auszuschließen, als ziemlich schwierig und fehleranfällig erwies.")
Außerdem wird Shannon dort so zitiert: <code>Eine Strategie dieser Art, bei der alle Varianten bis zu einer bestimmten Anzahl von Zügen berücksichtigt werden ...</code> ("Eine Strategie dieser Art, bei der alle Varianten bis zu einer bestimmten Anzahl von Zügen berücksichtigt werden ..."). Daraus Shannon zu unterstellen, dass er zu Programmen des A-Typs nur solche zählt, die ausschließlich den "reinen", unveränderten und vor allem nicht optimierten Minimax-Algorithmus verwenden, weil nur der alle Zweige des Suchbaums durchläuft, geht mE zu weit. Mir fällt kein Grund ein, warum Shannon eine, das Suchergebnis nicht verändernde Optimierung des Algorithmus hätte ablehnen sollen. Er hätte genug Gelegenheit gehabt, dagegen Einwände vorzubringen oder seine Skepsis zu äußern.

Die Diskussion erfordert eindeutige und klare Definitionen und keine Relativierungen, sonst geht es immer wieder von vorne los.

Die Behauptung, dass die Shannon-A-Strategie (reines Brute Force, wie es viele nennen) bereits den Alpha-Beta-Algorithmus enthält, ist falsch. Claude Shannon entwickelte seine A-Strategie 1949, während der Alpha-Beta-Algorithmus erst in den 1950er Jahren entdeckt wurde. Daher konnte Shannon den Alpha-Beta-Algorithmus in seine ursprüngliche A und B-Strategie gar nicht einbeziehen.
"Er hätte bestimmt nichts dagegen gehabt", finde ich lieb

Natürlich wäre er begeistert gewesen, aber was nu..? Hätte er den Algorithmus der A- oder der B-Strategie zugeordnet ? Immerhin ist es die B-Strategie, die darauf abzielt, die Anzahl der zu bewertenden Positionen zu minimieren, indem unnötige Berechnungen vermieden werden.
Dem Programmierer ist das relativ egal, der schreibt über seine Subprogramme, Funktionen und Schleifen kaum Shannon A oder B. Aber für die Wissenschaft und auch für jedermann, der darüber diskutiert, ist die Eindeutigkeit der Begriffe die Voraussetzung dafür , dass man über die gleichen Dinge redet. In Abänderung eines bekannten Sprichwortes:

Wer A sagt, der soll auch wissen, was mit B gemeint ist. In diesem Sinne, meine Herren, eine geruhsame Nacht

Rainer Neuhäusler
.

Warum A sagen, wenn es B ist ? Dem Programmierer ist es sowieso völlig egal, der wird kaum Shannon A und Shannon B über die Subs schreiben. Aber