[Mithrandir]

Moin,
ich hab vor eingier Zeit damit begonnen ein kleines Schachspiel zu programmieren, welches noch mitten in der Entwicklung ist, nun hab ihc mir auch überlegt das ich eine KI dazu entwickeln will, sehr warscheinlich basiert diese auf demMinimax-Algorithmus.
Nun wollte ich fragen ob mir hier jemand/mehrere sagen könnten wie ein möglichst günstiger Anfang aussieht, da dieser Anfang bzw. diese Anfänge gespeichert werden sollen und zufällig eienr ausgewählt wird, erst dann beginnt die Rechnerei.
Zum anderen wie ich die Spielfiguren bewerten muss, d.h. welche Figur eher sterben darf. So wie ich das sehe ist die Hirachie:
König -> Dame -> Turm -> läufer -> Springer ( -> Bauer ).

Somit wird eine Zugmöglichkeit bei der der "feindliche" Spieler Schachmatt gesetzt werden kann am höchsten bewertet,
dann würde die Zugmöglichkeit kommen in der man feinlichen König "nur" Schach setzt,
bzw. man sich selber aus dem Schach holt,

und als nächsthöchsten der Zug mit dme man die feindliche Dame schlägt , danach wiederum der Zug mit dem man die eigene Rettet (oder andersrum?!)
und so weiter.....

zumindest denk ich mir das so irgendwie aber es gibt hier doch sicher Leute die mehr Ahnung haben .. ich will hier ja niemanden danach fragen das er mir eine KI schreibt ich bräuchte lediglich etwas Hilfe mit der Bewertung der Spielzüge...


MFG Mithrandir

[Chris]

Die meisten Schachprogramme eröffnen mit Standarderöffnungen die sich als Allrounder entpuppt haben, genauso sieht es mit den Antworten aus. Eine Analyse des Erfolges bzw. der schwächen des Spielers gegen den man spielt ist wohl für den beginn erstmal das einfachste und zugleich wichtigste was man optimieren kann.
Erst wenn sich die Eröffnung voll entwickelt hat und keine passende Antwort aus einem Standardreportuar finden lässt setzt ja die eigentliche KI ein.

Ich würde eher sagen das der Läufer hinter dem Springer stehen sollte. Aber man sollte die Figuren eher nach ihrer Kampfkraft werten anstatt darüber nachzudenken wie schwer ein Verlust ein, der König ist danach keine wirklich wichtige Figur. Auch ist eine blose Reihenfolge nicht sinnvoll, die Dame ist somit die wichtigste Figur überhaupt, beide Türme zu verlieren aber insgesamt problematischer (was aber wohl auch von der Fähigkeit des Spielers abhängt).
Die Wertigkeit hängt definitiv von der Positionierung und den Zugmöglichkeiten ab, einen Algorithmus zu schreiben der das bewerten kann ist wohl auch recht wichtig.

Man muss auch gut Schach spielen können um sich überhaupt Gedanken über die Wichtigkeit von solchen Dingen zu machen, kann man das nicht sollte man es auch lieber sein lassen. Ich kenne keine einzige Eröffnung und das ist wohl auch der Grund warum ich nicht allzu gut bin.

[ojas]

Nun wollte ich fragen ob mir hier jemand/mehrere sagen könnten wie ein möglichst günstiger Anfang aussieht, da dieser Anfang bzw. diese Anfänge gespeichert werden sollen und zufällig eienr ausgewählt wird, erst dann beginnt die Rechnerei.

Das Problem ist, das du auch am Anfang nicht weißt, wie der Gegner zieht. Eine Eröffnungsbibliothek besteht deshalb aus einer Menge von Schachstellungen, in der pro Schachstellung zu den jeweils besten paar Halbzügen(*) der Erwartungswert gespeichert ist.

Den Erwartungswert kannst du natürlich nicht mit theoretischen Mitteln berechnen, sondern musst ihn durch Analyse gespielter Partien approximieren. Zur Analyse verwendest du ebenfalls den Minimax-Algorithmus, allerdings fließen nicht alle möglichen Züge in deine Berechnung mit ein, sondern nur die, zu denen du in deiner Partiensammlung eine ausreichende Datenbasis hast.

Eine recht bekannte Partiensammlung ist enormous.pgn, nomalerweise unter ftp://ftp.cis.uab.edu/pub/hyatt zu finden (momentan offline). Um darin rumzustöbern kannst du die Datei z.B. in Scid importieren. Scid sagt dir dann z.B. wie oft in einer Stellung was gespielt wurde und was der Erwartungswert für die daraus resultierende Stellung ist. Falls du die Datei nicht findest, wende dich an mich. Ich habe hier noch eine Kopie (ca 1GB) und ca 3GB Partien aus anderen freien Quellen.

Deine Schach-Engine sollte nicht von einer Eröffnungsbibliothek abhängig sein. Es sollte eine Komponente sein, die du später hinzufügen kannst, genau so wie eine Endspieldatenbank.

Zum anderen wie ich die Spielfiguren bewerten muss, d.h. welche Figur eher sterben darf. So wie ich das sehe ist die Hirachie:
König -> Dame -> Turm -> läufer -> Springer ( -> Bauer ).

Die Figuren werden in Bauerneinheiten bewertet. Der König steht außen vor, da das Spiel vorbei ist wenn er geschlagen wird. Um Sonderfälle in deinem Quelltext zu verhindern kannst du ihm einen hinreichend hohen Wert geben, z.B. 360 Bauern. Dann folgt

• Dame: 9 Bauern
• Turm: 5 Bauern
• Läufer: 3 Bauern
• Springer: 3 Bauern
• Bauer: 1 Bauer

Diese Wertigkeit ist recht allgemein akzpetiert, trotzdem solltest du eine Möglichkeit schaffen, diese Werte per Konfigurationseinstellungen zu ändern.

Du berechnest für beide Seiten wieviel Material sie haben und subtrahierst die Ergebnisse um das Materialverhältnis zu bekomen. Zu diesem Materialverhältnis addierst du nun positionelle Elemente. Positonelle Elemente sind z.B.

• Der gegnerische König ist schachmatt.
• Der gegnerische König steht im Schach.
• Wie gut ist der eigene König gegen Angriffe gesichert (Stichwort Königssicherheit, Rochade)
• Wieviele Felder können die einzelen Figuren betreten, z.B.
  
  • Türme gehören auf offene Linien
  • Läufer gehören auf offene Diagonalen
  • Springer am Rande bringen Kummer und Schande
• Weit vorgerückte Bauern sind gefährlich, insbesondere wenn sie nicht von gegnerischen Bauern aufgehalten werden können (im letzterene Fall heißen sie dann "Freibauern").
• Doppelbauern behindern sich gegenseitig und der eine kann den anderen nicht mehr decken
• Es ist schlecht, viele Bauerninseln zu haben. Am besten man hat nur zwei, eine auf dem Damenflügel, eine auf dem Königsflügel.
• Wer hat mehr Bewegungsfreiheit für seine Figuren(°)?

Die Werte für solche Elemente musst du experimentell bestimmen und natürlich auch genauer herausfinden, was solche schwammigen Aussagen wie Bewegungsfreiheit, vorgerückte Bauern und Königssicherheit wirklich bedeuten.

Als Anhaltspunkt für die Bewertungh kannst du heranziehen, daß bei zwei mittelmäßigen Vereinsspielern (Bezirksklasse oder höher, ca. 1550 DWZ(^)) gleicher Spielstärke ein Nachteil von 3 Bauerneinheiten nur noch in Außnahmefällen aufgeholt werden kann. Unter Topspielern sind schon viel kleinere Vorteile spielentscheidend.

bräuchte lediglich etwas Hilfe mit der Bewertung der Spielzüge...

Spielzüge werden in Schachprogrammen nicht im eigentlilchen Sinne bewertet. Der Wert eines Halbzuges ergibt sich aus dem Wert der Stellung, die durch den Halbzug entsteht.

Aufgrund der Größe des Spiels kann der Minimax-Algorithmus allerdings nicht bis zur Entscheidung der Partie suchen. Deshalb muss der Suchalgorithmus irgendwann abgebrochen werden und die aufgrund der Zugfolge entstandende Stellung muss alleine anhand des verbliebenen Materials und der Verteilung der Figuren auf dem Brett bewertet werden. Dieser Wert ist dann der Wert des letzten Halbzuges, der zu der Position geführt hat. Von dieser Position geht man einen Halbzug zurück, berechnet die Stellungen der anderen möglichen Halbzüge und deren Wert. Je nach dem ob man selbst oder der Gegner am Zug ist nimmt man dann den Halbzug der zu der Stellung mit dem kleinsten oder größten Wert führt und ordnet ihn der Stellung zu für den die Halbzüge berechnet wurden. So rechnet man zurück bis man zur aktuellen Stellung gelangt ist.

Fußnoten

(*) Halbzug: Ein Zug im Schach ist, wenn Weiß eine Figur von einem Feld auf ein anderes bewegt und anschließend Schwarz eine Figur von einem Feld auf ein anderes bewegt. Wenn lediglich eine Partei eine Figur von einem Feld auf ein anderes bewegt, dann nennt man daß einen Halbzug.

(°) Eines der ersten Schachprogramme hatte als einziges Bewertungskriterium die Anzahl der möglichen Züge des Gegners.

(^) DWZ: Deutsche Wertungszahl. Eine Zahl die die Spielstärke eines Spielers im Deutschen Schachverband angibt, ähnlich der auf internationaler Ebene verwendeten Elo-Zahl der FIDE. Ungefähr wie eine Glockenkurve verteilt, der Durchschnitt liegt bei ca 1580, 25% der Spieler liegen über 1850 DWZ, der Weltmeister bei ca. 2800 DWZ. Bei gleicher DWZ ist der Erwartungswert 50%, bei ca. 200 DWZ-Punkten Unterschied ist er 75%, ab ca 700 DWZ-Punkten Unterschied ist er 100%.

[ojas]

Ich würde eher sagen das der Läufer hinter dem Springer stehen sollte.

Normalerweise bewertet man den Läufer etwas besser als den Springer. Der Läufer kann schneller das Brett überqueren. Der Nachteil des Läufers ist, das er nur die hälfte aller Felder besetzen kann. Das wird aber durch die Fähigkeit des Springers nicht ganz kompensiert, zumal gegen Ende der Partie aufgrund der wenigen verbleibenden Figuren ein Springen nicht mehr notwendig ist und die kürzere Reichweite des Springers den Ausschlag gibt.

Es ist aber wirklich so, daß Anfänger Springer schlechter berechnen können, genau so wie Anfänger mit Turmpaar gegen Dame verlieren, weil sie ihre Türme nicht koordinieren können.

[Chris]

Normalerweise bewertet man den Läufer etwas besser als den Springer.

Damit war nicht gemeint das er schlechter ist sondern das er "eher nicht sterben sollte".

[ojas]

Damit war nicht gemeint das er schlechter ist sondern das er "eher nicht sterben sollte".

Ich verstehe den Bezug nicht. Meinst du das der Läufer besser ist als der Springer? Das hat ja auch Mithrandir in seiner Aufstellung so geschrieben.

[Mithrandir]

So, erstmal vielen Dank für die schnellen Antworten, ich werd dann mal schauen wie ich es hinbekomm und ggf. nochmal melden.

MFG Mithrandir

[Chris]

Ich verstehe den Bezug nicht. Meinst du das der Läufer besser ist als der Springer? Das hat ja auch Mithrandir in seiner Aufstellung so geschrieben.

Hab mich verguckt, dachte du meinst es umgekehrt, ist aber auch etwas verwirrend weil man die Logik im Kopf umdrehen muss von "darf eher nicht sterben" zu "ist besser".
Wie auch immer...

[Thoronador]

Somit wird eine Zugmöglichkeit bei der der "feindliche" Spieler Schachmatt gesetzt werden kann am höchsten bewertet,
dann würde die Zugmöglichkeit kommen in der man feinlichen König "nur" Schach setzt,
bzw. man sich selber aus dem Schach holt,[...]

Die Zugmöglichkeit, bei der man sich selbst aus einem Schach rausholt, sollte noch höher bewertet werden als ein Mattsetzen des Gegners, schließlich muss man laut Schachregeln den König immer erst aus einer solchen Situation befreien. Wenn man das also geschickt über passende Bewertungen implementiert, muss man nicht noch extra dafür sorgen, dass die KI sich vorrangig aus so einer Situation befreit. Danach sollte erst das Schachmatt kommen. (Theoretisch wäre es auch denkbar, dass es Stellungen gibt, bei denen man sich aus einem gebotenen Schach befreit und gleichzeitig, im gleichen Halbzug, den Gegner Matt setzt, aber das ist eher unwahrscheinlich.)

Auch würde ich den Zug, der dem Gegner Schach bietet, nicht zwingend als höchsten Zug nach den oben genannten Fällen bewerten, sonst bekommt man möglicherweise Dauerschachsituationen. Evtl. sollte man Züge, mit denen man stattdessen (gefahrlos) gegnerische Figuren schmeißen kann, höher bewerten. Allerdings könnte das dann im Extremfall zu Schlagschach ausarten. (Das ist eine Spielvariante, bei der Schlagzwang herrscht, also immer wenn ein Spieler die Möglichkeit hat, eine Figur zu schlagen, diese geschlagen werden muss.)

und als nächsthöchsten der Zug mit dme man die feindliche Dame schlägt , danach wiederum der Zug mit dem man die eigene Rettet (oder andersrum?!)

Das kommt drauf an, ob die KI eher offensiv oder defensiv sein soll. Es kann ja durchaus Situationen geben, in denen beides möglich ist, also beide Damen gefährdet sind. Sollte man dann eher die Chance nutzen und die feindliche Dame schlagen, oder sollte man lieber seine eigene in Sicherheit bringen? Wenn man nicht gerade auf Schlagschach steht oder bereit ist, auf seine Dame zu verzichten, sollte man der Rettung der eigenen Dame den Vorzug geben, denn rettet man sie nicht, wird es in der oben genannten Situation höchstwahrscheinlich dazu kommen, dass man zwar die gegnerische Dame schlägt, im nächsten Zug dann aber auch die eigene Dame verliert, denn so eine Möglichkeit lassen sich die wenigsten Spieler entgehen. Damit stünde man unter dem Strich materiell auch nicht besser da als zuvor, da beide Seiten ihre Dame verloren haben.

ich will hier ja niemanden danach fragen das er mir eine KI schreibt ich bräuchte lediglich etwas Hilfe mit der Bewertung der Spielzüge.

Wie schon von meinen Vorrednern angedeutet wurde, sollte man nicht die Züge bewerten, sondern die dadurch erreichten Stellungen. Eine Schachmattstellung ist natürlich das oberste Ziel, also die Stellung mit der höchsten Bewertung.

Bewertungskriterien könnten z.B. sein (Reihenfolge der Nennungen ist nicht nach Wichtigkeit geordnet):

Bei allen Figuren:

• Punktabzug für ungedeckte Figuren (also jene, die vom Gegner geschlagen werden können, ohne dass die schlagende Figur dadurch in eine Situation gerät, bei der sie selbst geschlagen werden kann)

Bei Bauern:

• Punktabzug für blockierte Bauern
• Bonus für Fortschritt hin zur hintersten Linie, da sie dort umgewandelt werden können. Evtl. sollte der in der Mitte etwas größer sein als am Rand des Feldes, da die meisten Figuren in der Mitte besser positioniert sind als am Rand. (Der Bonus eines Bauern auf der siebenten Linie sollte auch in etwa dem Materialwert einer Dame entsprechen, da dort ja die Umwandlung unmittelbar bevorsteht.)
• Eigene Bauern in der unmittelbaren Nähe des eigenen Königs könnten einen Bonus bekommen, da sie diesen quasi gegen Schach(matt) durch Figuren mit langer Reichweite (Dame, Türme, Läufer) decken.

Bei Springern:

• Bonus für Position im Zentrum des Spielfeldes
• Bonus für jede gegnerische Figur, welche maximal zwei Felder vom Springer entfernt ist, diesen aber nicht schlagen kann (Damen lassen sich ggf. gut mit Springern ausschalten)
• Bonus für jeden Springer, der nicht durch Bauern bedroht wird

Bei Läufern:

• Bonus für jedes Feld, dass ein Läufer begehen kann (d.h. lange, freie Diagonalen geben einen Bonus)
• Bonus für jede bedrohte Figur
• Bonus für jedes bedrohte Feld, welches in unmittelbarer Umgebung des feindlichen Königs liegt (wichtig für Matt, um dem König Fluchtmöglichkeiten zu nehmen)

Bei Türmen:

• Im Prinzip erhalten Türme die gleichen Boni wie Läufer, nur eben mit den Geraden anstelle der Diagonalen.

Bei Damen:

• Abzug für Bedrohungen durch feindliche Figuren
• Hier könnte man die Boni für Läufer und Türme anwenden, da Damen sowohl diagonal als auch gerade ziehen können.

Beim König:

• Abzug für Position in der Nähe des Zentrums zu Spielbeginn (anfangs sollte der König gedeckt hinter eigenen Figuren bleiben, im Endspiel, wenn der Gegner keinen nennenswerten Figuren mehr hat, um den König zu bedrohen, kann man das ändern)
• Abzug für Position auf einer (größtenteils?) freien Diagonalen oder Geraden (Läufer, Türme, Damen würden sich sonst freuen)
• Abzug, falls keine Bauern in unmittelbarer Umgebung sind, um vor solchen langen Linienangriffen zu schützen
• Abzug für jeden Zug, den der Gegner hat, um den König Schach zu setzen
• Abzug, falls der König bewegt wurde, ohne zuvor Rochade zu machen
• Bonus für Rochade (egal ob lange oder kurze)

Das wär's so im Wesentlichen erstmal. Natürlich kann man die Kriterien auch entsprechend umdrehen und dann Bonus anstelle eines Abzugs vergeben (und umgekehrt), also statt "Bonus für Rochade" könnte da auch "Abzug für keine Rochade" stehen, das ist letztlich identisch. Daher ist "Punktabzug für ungedeckte Figuren" auch das gleiche wie "Bonus für gedeckte Figuren".

[Mithrandir]

Danke auch für diesen langen, übersichtlichen und nützlichen Beitrag