Suche Bewertungsfunktion und generell Infos für/über Schach-Engines

Hallo.

Also das ist hier vielleicht eine sehr ungewöhnliche Frage, aber ich suche im Moment nach möglichst vielen Infos über Schachprogramme bzw. Schach-Engines.

Ich will selber kein Schachprogramm programmieren (dafür gibts ja dann doch hinreichend APIs), jedenfalls ist das nicht mein Hauptziel, auch wenn ich es vielleicht im privaten Rahmen zur Erfahrungssammlung mal versuchen werde. Ich brauche das in einem anderen Zusammenhang, bzw. ich denke, dass mir da Infos über sowas recht gut tun würden.

Jedenfalls... Das liebliche Wikipedia spuckt ja einiges aus, und auch Google spuckt sehr viel aus (leider - wie bei Google üblich - auch sehr viel Schwachsinn). Was man aus Wikipedia und Konsorten so lesen kann, sind Algorithmen wie der AlphaBeta-Algorithmus, die man Anwenden kann, wenn man eine Bewertungsfunktion für Spielpositionen hat.

Aber genau hier hören auch die lesbaren Informationen auf, die ich gefunden habe. Sicher ist ein Zuggenerator und der Alpha-Beta-Algorithmus nicht unbeträchtlich zeitraubend zu implementieren, aber mich würde mal eine einfache Bewertungsfunktion, die von irgendeinem Schachprogramm (das garnicht mal so gut sein muss) verwendet wird, interessieren. Genaugenommen interessiert mich eine positioneller Bewertungsalgorithmus. Materielle Bewertung - wie sie in Wikipedia steht - scheint ja nicht allzu schwer zu sein. Aber wie man eine positionelle Bewertung implementiert, kann ich mir einfach nicht so richtig vorstellen.

Das würde mich interessieren. Da gibts doch sicher auch "freie" bzw. "offene" Bewertungsalgorithmen, die dann auch irgendwo dokumentiert sind.

Wäre klasse, wenn jemand was wüsste.

Hmm... Ich habe mich zwar noch nie mit diesem Thema auseinandergesetzt, aber in Anbetracht der Tatsache, dass es beim Schach eine endliche Menge von Zuständen gibt (wobei ein Zustand in diesem Fall eine der möglichen Positionen aller Spielfiguren ist), würde ich daraus einen Automaten oder Baum generieren. In beiden Fällen wären die während des Spiels notwendigen Operationen recht billig. Versuch aber nicht, so etwas von Hand zu machen, es gibt alleine für die möglichen Verteilungen der Figuren ohne Berücksichtigung der rausgeflogenen Prod(i=64...48) i Möglichkeiten :)
Whatever, wenn du dir einen Algo überlegt hast, der so einen Automaten oder Baum generiert, kannst du das Ergebnis speichern und zukünftig verwenden.
Der Spiel-Algo könnte dann "einfach" entscheiden, welche Sequenz von Folgezuständen am sinnvollsten erscheint, indem von der aktuellen Position alle möglichen Sequenzen untersucht werden. Dabei können solche Sequenzen ausgeschlossen werden, die im Zustand "verloren" oder "Remis" enden würden (bspw. mittels Tiefensuche). Die verbleibenden Sequenzen (die demzufolge im Zustand "gewonnen" enden) können dann nach noch zu bestimmenden Kriterien bewertet werden (bspw. Anzahl der noch nötigen Schritte, Weg mit geringsten eigenen Verlusten, etc.). Der Weg mit der höchsten Bewertung wird dann gegangen.

Diese Bewertungen können übrigens schon während der Generierung berechnet und, im Fall eines Baums, bspw. als Gewichtung integriert werden.

Das ist jetzt natürlich noch nichts, was du direkt umsetzen kannst, aber vielleicht ein kleiner Denkansatz...

Einen Automaten oder Baum... Du meinst wohl einen Spielbaum... Soweit ich weiß, hat man sowas bereits für Mühle generiert, und bei Dame ist bereits irgendein Superrechner dabei, einen zu erstellen. Beim Schach halte ich die Erstellung eines kompletten Spielbaums für Zukunftsmusik.
Wenn ich einen kompletten Spielbaum generieren würde, könnte ich mir auch die Bewertungsprozedur sparen. Denn entweder ich kann Remis erzwingen, oder den Gewinn, oder ich verliere Garantiert - je nach dem, wie beschaffen Schach ist (das ist eben soweit ich weiß noch unbekannt, man vermutet aber, schach geht remis/patt).

Wenn ich dich richtig verstanden habe, versuchst du mir einen Algo zu geben, um einen möglichst effizienten Baum zu bekommen. Dieses Alphabeta-Teil scheint mir da aber schon recht gut zu sein...

Mich interessiert eigentlich viel mehr - und da hört jedes Tutorial, das ich dazu finde, auf - eine Bewertungsprozedur. Wenn ich z.B. zehn oder zwanzig Ebenen des Spiels berechnet habe, muss ich ja die einzelnen Bretter bewerten. Die meisten solchen Bewertungsfunktionen sind, nehm ich an, geheim, aber da es open-source-schachprogramme gibt, wird es sicher auch einige geben, die es nicht sind. Auch wenn ich grad anfange, irgendwelche Quellcodes durchzuforsten, hoffe ich mal, dass sowas dann auch irgendwo ein wenig dokumentiert ist...

Nach sowas suche ich eigentlich. Algorithmen zur Baumgenerierung gibt es genügend, die sind auch ausreichend dokumentiert, deshalb würde ich es nie wagen, danach zu fragen ;)

Trotzdem danke für die Antwort.

Das ist schon ziemlich heftig was Du da verwirklichen möchtest.

Was auf keinen Fall Schaden kann, dein Anliegen in einem
örtlichen Schachclub vorzutragen. Auch wenn du von Programmierung
keine Ahnung haben, kannst du dich der Philosophie des Schachs
nähern, und mit diesem Wissen bestimmt deine App. später
verbessern.

Gute Schachspieler haben nun einmal eine andere Denke.

Baum ist im Fall von Schach nicht zu empfehlen (auch schon beim wesentlich einfacheren Reversi/Othello nicht - füllt da schon mehr HD's als in deinen PC reinpassen ;) bei einem 8x8-Feld etwas um die 64! - selbst wenn du nur schon alle möglichen Feldbelegungen (rot, schwarz, leer) finden willst - gibt das 3^64 Möglichkeiten mit sagen wir 32 Bit pro Feld (int) füllt dies etwa 1EE20 handelsübliche Festplatten - wenn ich mich gerade nicht verrechnet habe... Bei einem Volumen von 1dm^3 pro Festplatte füllt deine Sammlung einen Kubus von 460 Kilometern Seitenlänge...)

Das schwierige ist meist, die Bewertungsfunktion zu proggen. Ein Beispiel: Ein Springer am Rand sollte weniger Punkte geben, als ein Springer in der mitte (da er weniger Möglichkeiten hat). Auch könntest du wohl noch überprüfen, wie gut eine Figur von anderen (billigeren) Figuren gedeckt ist...

Dann hört aber mein Schachwissen auf (ich hab mal für Reversi so ein Ding geproggt - schon das war extrem schwierig und Zeitaufwendig (du hast das Gefühl, du hättest die neue Idee, lässt deinen neu geproggten Spieler gegen den Zufallsspieler (einfach ein random auf die leeren Felder) antreten und er verliert 9 von 10 Partien :D )

MfG Bischi

Danke für die vielen Antworten.

Zitat:

---

Zitat von bischi

Baum ist im Fall von Schach nicht zu empfehlen

---

Sag ich ja. Wobei soweit ich weiß auf zehn Ebenen oder so wird vorausberechnet, auch von gängigen Schachprogrammen. Dabei werden aber nicht alle Felder gespeichert, sondern die werden soweit ich weiß berechnet, bewertet, und sofort wieder verworfen - man hat also maximal 10 schachbretter (bei einer entsprechenden rekursionstiefe) im Speicher. Das Problem dürfte wohl weniger der Speicher sein - wenn man den baum wie eben gesagt garnicht erst speichert - als die Berechnungszeit. Wenn schon moderne Supercomputer das nicht hinbekommen...

Zitat:

---

Zitat von bischi

Das schwierige ist meist, die Bewertungsfunktion zu proggen. Ein Beispiel: Ein Springer am Rand sollte weniger Punkte geben, als ein Springer in der mitte (da er weniger Möglichkeiten hat).

---

Ja. Genau danach frage ich. Wie ich gesagt habe, interessieren mich irgendwelche wenigstens nicht ganz schlechten Bewertungsprozeduren. Natürlich wird man da nichts Weltklassiges einfach so frei finden, aber da gibt es doch bestimmt offene Algorithmen zur Bewertung. Nachdem es ja auch offene Schachprogramme gibt - ich glaub kaum, dass jemand, der was open source anbietet, versucht, seine Algorithmen geheim zu halten.

Ich muss ganz ehrlich sagen, ich hab überhaupt keine Ahnung, wie man sowas realisieren sollte. Also, klar, wenn ich irgendwie so einzelne Sachen lese, dann leuchten mir die schon ein, aber so insgesamt...

Also dass z.B. ein Bauer weniger wert ist, als ein Springer leuchtet mir ja z.B. ein. Und dass ein Springer, der in der Ecke steht, und nur auf zwei Felder ziehen kann, weniger wert ist, als einer, der mitten im Feld ist, und total manövrierfähig ist, ist auch einleuchtend (bzw. ok - am rand kann natürlich auch vorteile haben).

Nur, wie man sowas in der Gesamtheit macht, das würde mich mal interessieren. Natürlich erwarte ich da jetzt nicht irgendwie, dass jemand das herausposaunt, aber ich hoffe halt, dass ggf. irgendwer mich wo hin verweisen kann, wo man über sowas lesen kann... ansonsten muss ich nämlich liebliches source-durchforsten betreiben, und versuchen, da was rauszufinden - was sicher nicht allzu leicht ist.

Aber trotzdem danke für alle bisherigen Antworten.

Wenn du tatsächlich eher an einer theoretischen Betrachtung interessiert bist (ohne das ganze also in absehbarer Zeit zu implementieren), dann ist vielleicht der von Romanday vorgeschlagenen Weg der sinnvollste. Das vorrangige Problem scheint für dich ja zu sein, woran du eine gute respektive schlechte Situation erkennst, und da sind eingefleischte Schachspieler mit Sicherheit die richtigen Ansprechpartner.

Zitat:

---

Zitat von bischi

Baum ist im Fall von Schach nicht zu empfehlen (auch schon beim wesentlich einfacheren Reversi/Othello nicht - füllt da schon mehr HD's als in deinen PC reinpassen bei einem 8x8-Feld etwas um die 64! - selbst wenn du nur schon alle möglichen Feldbelegungen (rot, schwarz, leer) finden willst - gibt das 3^64 Möglichkeiten mit sagen wir 32 Bit pro Feld (int) füllt dies etwa 1EE20 handelsübliche Festplatten - wenn ich mich gerade nicht verrechnet habe... Bei einem Volumen von 1dm^3 pro Festplatte füllt deine Sammlung einen Kubus von 460 Kilometern Seitenlänge...)

---

Das ist zumindest schon mal nicht weit weg von der Wahrheit :) Aber hey, bei der Größenordnung gibt es, bis heute verfügbare Rechner die Berechnung abgeschlossen hätten, mit Sicherheit auch schon Platten mit einer entsprechenden Kapazität für die Hosentasche :D Und bis dahin machen wir halt einfach aus der Pfalz oder so ein riesen Plattenlager...

Ein guter Einstieg in die Problematik sollten die von Robert Hyatt angegebenen Technical Papers zu seinem Programm "crafty" sein.
Darüber kannst du hoffentlich Refernezen zu weiterer Literatur finden.

Wie wärs wenn du deinen Bayes-Spamfilter missbrauchst bzw. umbaust? *ggg*

MfG Peschmä

Ist das dieses Teil, das irgendwie mit neuronalen Netzen arbeitet oder so, und damit Spam filtert?

Also ich hab mal von nem Spamfilter gehört, dem man sowas beibringen kann. Hat mich damals nicht weiter interessiert, jedenfalls nicht tiefer, find ich aber sehr interessant, dass man Programmen sowas beibringen kann.

Generell find ich so "lernendes" Zeugs interessant.

Naja. Aber für mein konkretes Problem bin ich hier wohl wirklich falsch - scheint mir mehr mit Schach als mit Programmierung zu tun zu haben. Aber war ja mal den Versuch wert.

Also das mit neuronalen Netzen wäre mir neu. Bisher hiess das einfach Statistik ;)

MfG Peschmä