|
Ideen zur Schach KI
Hallo !
Ich möchte zur Zeit 'ne Schach-KI programmieren. Meine Komponenten sind fast fertig. Ich fang also damit an meinem Gegner beizubringen schach zu denken. Nach welchen Kriterien sollte denn die KI ihre Entscheidungen treffen ? :wiejetzt: meine ersten Ideen: - Figurenvorteil - möglichst große Anzahl an gedeckten Feldern ... Teilt mir bitte eure Ideen mit ! |
Re: Ideen zur Schach KI
Tja, sowas hab ich auch mal vor längerer Zeit probiert, bin aber an der KI gescheitert. :oops:
Also ich bin damals davon ausgegangen, dass man neben dem rein materiellen Vorteil auch die jeweilige Stellung auf dem Schachbrett bewertet. Je nachdem, welcher Zug zu einer besseren Stelung führte (d.h. einen positionellen Vorteil brachte), wurde dieser ausgeführt. MfG Binärbaum |
Re: Ideen zur Schach KI
also, da ich auch mal dieses projekt hatte, habe ich mir genau die selben fragen gestellt.
- Material - Angriffsmöglichkeiten - Königsstellung/sicherheit - Bauernstellung - Zentrum - Entwicklung - Felder unter Kontrolle - Taktische Gesichtspunkte (Löcher, Springer/Läufer, ...) hilft dir vielleicht weiter... |
Re: Ideen zur Schach KI
Zitat:
Welche Stellungen sind denn gut ? |
Re: Ideen zur Schach KI
Zitat:
Also ein Bauer ist zum Beispiel am wertvollsten, wenn er in der 7. (weiß) bzw. 2. Reihe (schwarz) steht, da man diesen beim nächsten Zug verwandeln kann. Für König ist es hingegen sinnvoll, wenn man die Rochade ausführt, da er so besser geschützt ist. Für Springer ist es gut, wenn aich sich im (erweiterten) Zentrum befinden,... ... Die Liste lässt sich jetzt noch ein ganzes Stück fortsetzen. Das eigentliche problem ist, erstmal die Kriterien zu finden, nach denen man entscheidet, ob eine Figur mindestens genau so gut oder besser steht als vorher. Die Umsetzung sollte dann das kleinere Problem sein (zumindest war es bei mir so). MfG Binärbaum |
Re: Ideen zur Schach KI
Zitat:
Zum Beispiel: Taktische Gesichtspunkte: Löcher. Wie findet mein Programm löcher ? Durch neuronale Netze ? Schach kann ich ja mehr oder weniger spielen. Für mein' Prohjekt interessiert mich aber mehr die mathematische Logik dahinter. Und was verstehst du unter Entwicklung ? Möglichst viele Figuren an der Front ? Trotzdem danke. |
Re: Ideen zur Schach KI
Zitat:
Bin zwar, was programmieren angeht ein totaler n00b, aber egal.. Vergessen sollte man nicht, dass ein Schachprogramm besonders am Spielbeginn dem menschl. Spieler unterlegen ist, da dieser oft bestimmte Varianten (Sizilianisch, Französisch, etc. etc.) einstudiert hat, die, langfristig gesehen, den Spielaufbau zu seinen Gunsten entscheiden können, während die nur auf die nächsten Züge bedachte KI erst im Mittel- bzw. Endspiel den Vorteil "mathematischer Logik" einsetzen kann. Ich würde daher empfehlen, dass du deinem Programm eine Reihe von Eröffnungen einprogrammierst, die dem Programm beim Spielbeginn "auf die Sprünge helfen". :coder2: |
Re: Ideen zur Schach KI
OT:
Danke für die Fjorde Slartibart ;) (hoffe das ich den Namen jetzt noch richtig im Kopf habe, 42 :) Zurück zum Thema: Ich weiss zwar nicht wie man ne Schach KI programmiert aber diesen Thread behalt ich mal weiter im Auge, ist ne seeehr interessante Problemstellung! Vielleicht mal n OSS Schachprogramm nach Denkansätzen durchforsten? mfg |
Re: Ideen zur Schach KI
Zitat:
Da musst du einfach abfragen, ob z.B. auf den betreffenden Feldern noch eigene Figuren stehen, die die dahinterliegenden schützen (beim König wichtig), oder ob sie evtl. auch nur einen Läufer blockieren. Mit Entwicklung meint er sicher, dass man mehrere Züge hintereinander auf ein bestimmtes Ziel (z.B. Angriff auf dem Königsflügel) hinarbeitet. Das wird aber schon schwieriger (für die KI). Und zur "mathematischen Logik": Ein ehemaliger Schach-Weltmeister hat mal gesagt (nicht wörtlich, aber vom Inhalt her): "Ein Spiel, indem alles so klar wäre wie 2 mal 2 gleich 4, würde schnell an Reiz verlieren." Soll heißen, dass es nicht so einfach ist, eine gewisse Logik herauszuarbeiten, um das Schachspiel zu beschreiben. Und wie man diese "Logik" dann in dein Programm implementiert, hängt stark davon ab, wie du die gegenwärtige Stellung auf dem Brett darstellst (d.h. Datentypen, ...). MfG Binärbaum |
Re: Ideen zur Schach KI
Zitat:
Das interessante an Schach ist ja gerade, das jeder mögliche Zug der beste sein kann. Es gibt genug Partien die gewonnen wurden, weil der spätere Gewinner 4 Züge vorher seine Dame geopfert hat! Deshalb ist der Ansatz nach generell-günstigen Positionen zu spielen IMHO falsch. Ich bin mit so einer KI zwar auch gescheitert aber mein Ansatz war die Position bewerten zu lassen nach Anzahl der ungedeckten Figuren/Anzahl der gedeckten (Im Optimum 1) sowie Anzahl der ungedeckten Felder/Anzahl der gedeckten (Im Optimum 1) Damit hat man 1) ne Aussage über die eigene Position (Wenn alles gedeckt ist steht man gut ;) ) 2) ne Aussage über die Möglichkeiten des Gegners (Wenn alle Felder gedeckt sind... Wo soll er noch hin) Dieser Ansatz ist schon nicht so schlecht, aber er führt zu 2 Problemen: 1) Wenn ein Bauer durch ne Dame gedeckt ist, so ist er eigentlich nicht gedeckt da niemand die Dame opfert... 2) Im Endspiel läuft man so komplett gegen den Baum! Soweit ich weiß benutzen heutige KI's 3 Engines: die Erste für die Eröffnung (wird in Datenbanken gespeichert) die Zweite für das Spiel (das ist die Richtige KI) die Dritte für das Endspiel (Ab 5 Steinen pro Spieler steht bei Fehlerfreiem Spiel fest wer gewinnt, glaube ich) Falls das Opensource-entwickelt werden soll würde ich mich da übrigens gerne dran beteiligen! nen neuer Versuch kann nicht schaden ;) |
Re: Ideen zur Schach KI
Zitat:
Aber IMHO arbeiten manche Schahprogramme (z.B. GNUchess) nach dem von mir beschriebenen Prinzip/ Ansatz, und fahren damit auch nicht schlecht und es schickt nicht alle Bauern zur Grundlinie, so wie du es behauptest. Sinnvoll sind diese Ansätze mit dem bewerten der Züge ja auch erst dann, wenn man mehrere Züge vorrausberechnet. MfG Binärbaum |
Re: Ideen zur Schach KI
Zitat:
Zitat:
Zitat:
Delphi-Quellcode:
da wir gerade dabei sind, was hältst du davon ?
type
TFigure = record Pos:Tpoint; Info:Integer; end; TFields = array[1..8,1..8] of TFigure; TBoard = class Fields:TFields; parent:TBoard; Children:array of TBoard; //... end; // zur Darstellung TChessBoard = class Image:Timage; Board:TBoard; //... end; |
Re: Ideen zur Schach KI
Spontan fallen mir da noch Figur-Wertigkeit, Schlagrichtung und Sprungrichtung ein.
|
Re: Ideen zur Schach KI
Zitat:
|
Re: Ideen zur Schach KI
Zitat:
Wozu speicherst du in TFigure die Position in pos, wenn diese doch schon aus den Indices von TFields hervorgeht? |
Re: Ideen zur Schach KI
Ganz nebenbei glaub ich bei MiniMax ein gewisses Bepunktungssystem gesehen zu haben. Ich hab' nämlich mal eine Source in die Finger bekommen, die aber nich' kompilierbar ist, da dort Units wie 'Diag*.dcu' nicht vorhanden sind.
Weiß da noch jemand was dazu ('ne komplette Source vielleicht) ? |
Re: Ideen zur Schach KI
Zitat:
Delphi-Quellcode:
hier kannst du die Pos auch ermitteln ohne lange zu suchen.
procedure TBoard.IrgendNeProc(F:TFigure);
begin // ... end; Worauf ich aber meine Frage bezog, war, ob diese Children-Verschachtelung Sinn macht (unter anderem). Ich wollte nämlich noch 'ne Methode einbauen, die die Punkte einer bestimmten Stellung 'misst' und das Parent-Board prüft wie gut der Zug, der zu dieser Stellung geführt hat, war. usw. Gibt es vielleicht noch andere sinnvolle Vorgehensweisen, die dieses 'Vorausdenken' sorgen ? |
Re: Ideen zur Schach KI
bepunktungssystem? die figuren?
Bauer: 1 Läufer: 3 Springer: 3 Turm: 5 Dame: 8 (oder 9 ?) König: ~ (unendlich, ohne könig hat man verloren ;) ) bevor du mit ner ki anfängst, schreib erstmal eine "grafik"-engine, die folgende anforderungen erfüllt: - darstellung der akuellen stellung - entgegennahme von user-inputs (maus, tastatur) - entgegennahme von programm-inputs (functions/ procedures) - einfach ansteuerung (zb. TrackFigure(x1,y1,x2,y2); ) dann erweiterst du diese engine mit einem reinen bewertungssystem, das einfach sagt, wie es seiner meinung nach grade steht. dieses testest du dann ausführlich wenn es gut ist, dann baust du ein das er züge selber ausprobiert. und dann, ist es nur noch ein kleiner schritt bis zur "richtigen" ki |
Re: Ideen zur Schach KI
Zitat:
Solange man die KI bzw. das Zitat:
Das reicht auch erstmal, bis man die KI (nahezu) fertig hat. (Bis zu dem Punkt bin ich leider bis heute nicht gekommen :( ) Erst dann sollte man sich um die Grafik kümmern. MfG Binärbaum |
Re: Ideen zur Schach KI
Zitat:
Minimax liegt ein sog. Spielbaum zu Grunde, der folgendermaßen aufgebaut ist: Wurzel ist das Schachbrett im Ausgangszustand. Davon ab gehen n Unterknoten, in denen jeweils ein möglicher Zug des nächsten Spielers (weiss hier) abgebildet wird. Von dieses aus gehen jeweils Kinder ab die alle Zugmöglichkeiten vom Gegenspieler (schwarz hier) darstellen, usw... Ganz am Ende in den Blättern gibt es dann 3 Möglichkeiten die es zu erkennen gilt: Matt(weiss), Matt(schwarz), Remis. Nun vergibt man an diese Blätter eine Wertung, z.B. 1 für Matt(weiss), 0 für Remis und -1 für Matt(schwarz). Diese Wertung muss nun rekursiv bis in die Wurzel hochgezogen werden, und bildet die Grundlage der KI. Ziel von schwarz ist es ein Matt(weiss) zu erreichen - folglich spielt er immer zum Teilbaum mit der höchsten Bewertung hin, da es dort wahrscheinlicher ist zu gewinnen. Er ist somit hier der Maximierer, und weiss der Minimierer (da er auf -1 = Matt(schwarz) spielt). Möchte man seiner KI jetzt auch noch beibringen möglichst schnell einen Sieg zu verbuchen, so empfiehlt sich eine Portion A*: Man zählt also den Baum hinab in welchem Teilbaum man den kürzesten Weg bis zu einer positiven trivialen Situation hat (Sieg), und entscheidet sich für diesen. (Das wäre aber nur nen Bonbon ;)) Man braucht für obiges System aber alle möglichen Spielstände! Was fällt einem auf? Genau: Das werden allein schon nach nur 2-3 Spielerwechseln irre viele Knoten! Einen kompletten Schachbaum aufzubauen sollte heutzutage nicht in vernünftiger Zeit schaffbar sein. Lösung 1) Teilbäume aus der aktuellen Stellung mit vorgegebener Tiefe berechnen. So wird es imho auch gemacht. Das Problem hierbei: In den Blättern sind eher selten echte Endsituationen zu finden. Also kommt man nun an die Stelle die den ganzen Thread lang schon diskutiert wurde (und nur einen Teilaspekt einer KI darstellt ;)) - man muss ein unfertiges Spiel bewerten und das also Grundlage für eine Zahl von -1 bis 1 hernehmen mit der entschieden wird. (Diese Stelle ist vital für die Intelligenz der KI.) Da kann ich allerdings kein geeignetes Verfahren anbieten, und würde ähnlich vorgehen wie es hier ja schon passiert. (Ideen sammeln + Try&Error) Lösung 2) Das sog. Alpha-Beta-Pruning. Dies ist eine Verbesserung des Minimax-Algos (hinsichtlich der Laufzeit), da man auf Grund günstiger Konstellationen von vorne herein ganze Teilbäume einfach weglassen kann; also erst garnicht aufstellen muss. Das Verfahren ist jedoch nicht ganz so einfach nachvollziehbar (für Details sei auf Onkel Googel / WiKiPedia / etc. verwiesen) und es wäre wohl auch nicht ausreichend um einen kompletten Spielbaum aufzubauen, da es trotzdem noch zu viele Knoten würden. Somit böte sich das also eher an um Lösung 1 zu verschnellern bzw. zu verbessern, da man ggf. tiefere Bäume aufbauen kann als ohne A-B-Pruning. Der goldene Weg wäre also ein partieller Spielbaum mit A-B-Pruning aufgebaut für eine KI die einfach nur gewinnen will, und ohne A-B-Pruning aber mit einer Priese A* für eine KI die schnell gewinnen soll (heisst nach mögl. wenigen Zügen, das Programm ist sicherlich langsamer ;)). Warum nicht A-B-Pruning und A* zusammen? Weil durch das Wegschneiden der Teilbäume ohnehin schon auch schnellere Wege gekillt würden, so dass auch A* nur mittelmäßige Wege finden könnte. A-B-Pruning ist NICHT auf schnellen Sieg ausgelegt, nur auf "überhaupt gewinnen" :). Versteift euch nicht zu sehr auf die reine Bewertungsfunktion unfertiger Bretter. Die ist zwar sehr wichtig, aber auch nur ein Teilaspekt. Und sie muss schließlich zum eigentlichen Wegfindungsalgo passen ;). Schönen Gruß, Fabian :hi: |
Re: Ideen zur Schach KI
Habe zwar nicht alles gelesen, aber ich würde das so ansetzen:
Du setzt jedem Zugtyp eine Priorität, dannach rechnest du für jede Figur im Spiel die Priorität ihrer Züge aus. Als Beispiel: Du hast einen Bauer der wenn er Vorzieht, z.b. folgende Prioritäten erhält: - Feld Rechts wird verdeckt verhindet Angriff auf König(P25) - Feld Links ist ein gegn. Pferd (P4) - Figur kann nicht mehr geschlagen werden(P8) - Figur ist 3 fach gedeckt(3 * P2) - Figur deckt den Bauern danneben nicht mehr Schräg(- P16) Das Rechnest du jetzt für jede Figur aus, wenn man jetzt ein Bischen weiterkommt kommt man schnell auf die Idee, wie man dies für eine Vorrausdenkende KI machen kann. Die Punkteverteilung ist dabei sehr Hilfreich um die verschiedenen Schwierigkeitsgrade zu Realisieren. |
Re: Ideen zur Schach KI
@Speedmaster: So würdest du dich in Spezialfällen verlieren. Das kann so in der Form imho nichts werden, bzw. würde man ewig daran programmieren. Dazu kommt dass der Schwierigkeitsgrad fix wäre. Bei der Baumvariante kann man die KI z.B. nicht GANZ auf Min oder Max spielen lassen, sondern z.B. mit Remis als Ziel. Oder gar gegen sich selbst, so dass man fast gezwungen wird zu gewinnen :mrgreen:. Das wäre dann nur einen Wert ändern.
|
Re: Ideen zur Schach KI
Zitat:
Find ich 8). Ich verfolge diesen Thread mit erstaunen, weil ich das viel zu kompliziert finde. Aber macht mal. Vielleicht fällt mir ja auch noch was dazu ein. :cyclops: MfG freak |
Re: Ideen zur Schach KI
Zitat:
@dizzi: Wozu gibts es die Maximale Zugvorraussicht? :D |
Re: Ideen zur Schach KI
Zitat:
|
Re: Ideen zur Schach KI
Zitat:
Aber if then else kommt in meiner Idee auch fast garnicht vor! |
Re: Ideen zur Schach KI
:roll: Ich denke hier nicht an die normale Verwendung von if..then..else, sondern das war als Synonym gedacht für das gezielte Behandeln einer Großzahl von Einzelfällen der Art:
Delphi-Quellcode:
Auf soetwas in der Art würde dein Vorschlag hinauslaufen, und noch viel verschachtelter ;). (Glaub mir, ich hab schon Leute so TicTacToe programmieren sehen - es war grauenvoll! Und das dann für SCHACH!? *schüttel* :))
if KönigImSchach then
PackNeDaWech else if DameInGefahr then SiehZuDassuDiInSicherheitBekommst else if BauerKannDickenGegnerSchlagen then TuDasVerdammtNochmal else if ... ... ... |
Re: Ideen zur Schach KI
Naja, du hast nicht diesselbe denkweise wie ich, ich redete von Mathematik, und nicht von Dutzenden if..then..else Verzweigungen.
|
Re: Ideen zur Schach KI
Meine Weißheit hierzu:
die besten Schachprogramme sind von Programmieren geschrieben, die kaum oder gar kein schach spielen können. Als ich meine erste Schach KI programmiert habe hab ich auch den Fehler gemacht viel zu viele sonderbewertungen mit hineinzunehmen. Das besondere einer KI ist ja, dass sie umso besser spielt, umso besser sie stellungen berwerten kann. also schnapp man sich binäre bäume und ein relativ simples bewertungssystem: Figur mit wert x schlagen: X Punkte. Wenn man das noch schön auf geschwindigkeit optimiert hat man ein schachprogramm dass (umso besser es optimiert ist) schon recht stark spielt. Regel sollte man ihm beibringen... Wenn du soweit bist kannst du dein berwertungssystem weiter ausbauen wenn du es brauchst, aber das habe ich dann nicht mehr gemacht, da es das ganze extrem kompliziert. also schreib dir ne function der du ne stellung übergiebst un die dir dann nen wert liefert (Z.b <0 positiv für schwarz >0 positiv für weiß) machst nen shönen baum un rechnest mit den stellungen die die besten werte für die KI und die wenigsten schlechten werte für den Spieler besitzen. Fertig. Aus. Läuft. Hat mich igrnedwann mal geschlagen *hehe* jetzt nicht mehr mfg Chris |
Re: Ideen zur Schach KI
Zitat:
Zitat:
|
Re: Ideen zur Schach KI
bei TicTacToe, mühle oder 4 gewinnte kann man sagen "spiel so und so, und due gewinnst oder hälts zumindest unentschieden".
Das geht jedoch bei Schach NICHT. man sollte beide möglichkeiten verknüpfen. also einen Baum, der allerdings sofort abbricht, wenn sich die Stellung deutlich verschlechtert. und ja, die Stellungsbewerterei endet in einem ziemlichen if..then..else..if..then.... aber nur mit baum kommst du nicht weiter. ich werd mich heut abend mal dransetzen und eine stellungsbewertungs-procedure schreiben, und die mal testen... |
Re: Ideen zur Schach KI
Was ich doch grundsätzlich nur aussagen wollte ist, dass einem die Stellungsbewertung alleine nichts bringt. Als erstes sollte man das Drumherum, sprich die Baumlogik usw. fertig haben, und kann dann mehrere Bewertungsfuktionen darin testen. Es macht wenig Sinn mir dieser anzufangen, da sie nicht im Zielumfeld getestet werden kann, und ihre Güte somit kaum bewertbar ist.
Und was TicTacToe usw. angeht: Natürlich kann man eine statische Logik einbauen die mindestens einen Gleichstand hält. Aber das hat nichts mehr mit einer KI zu tun! Eine KI ist ein Algo der aufgrund von Heuristiken dynamisch Situationen bewertet, und auf Grund dieser dann Entscheidungen trifft. Die Besonderheit einer KI liegt ja gerade darin, dass sie auch auf unbekannte/neue Situationen angemessen reagieren kann. Das schafft eine statische Logik nie. Ich persönlich würde mich mit einer solchen nicht zufrieden geben ;). Was Schach bzw. dessen bessere Implementationen angeht: Imho werden dort KI und wissensbasierte Systeme vermischt. So dass bekannte besondere Spielweisen wie z.B. eine spezielle Eröffnung die evtl. erst viel Später einen Vorteil nach sich zöge, und somit bedingt durch die Baumtiefe nicht früh genug erfasst würde, separat erkannt wird, um dann ausserhalb jeder Heuristik eine statische Taktik zur geeigneten Abwehr einzusetzen. Dieses ist aber quasi nur eine Ausnahmebehandlung. Die sonstige Logik ist heuristisch. Was ich extrem spannend fände: Wir definieren hier in der DP im Rahmen eines Projektes eine Kommunikationsschnittstelle, und wer mag baut ein Schachspiel dass diese unterstützt. Mit dem Ziel dass man diese Programme anschließend gegeneinander antreten lassen kann! Das wäre (imho) sauspannend :). |
Re: Ideen zur Schach KI
ich werd vielleicht mal versuchen ein klasse zu schreiben die eben diese eröffnungen generiert.
also das züge aus ner datei ausliest, und dann einen input bekommt (der zug halt) und dann den besten eröffnungszug zurückgibt. müsste eigentlich relativ einfach zu realisieren sein: alles schön übersichtlich in verschiedene tabellen innerhalb einer db tuen temorär alles in eine tabelle schmeissen immer wenn input kommt alle nicht mehr möglichen züge rausschmeissen den zug mit der besten bewertung zurückgeben dann müsste man sich nur die mühe machen und paar eröffnungen mal eingeben... |
Re: Ideen zur Schach KI
Zitat:
Ein neuer Wettbewerb! (Das müsste aber ne Weile gehen...) |
Re: Ideen zur Schach KI
Zitat:
Am besten wäre ein einfacheres. Wenn man eine eigene Schach-KI entwickele, dauert das Jahre (bei mir noch länger). Interessanter wären doch Spiele wie Dame, Mühle oder Mensch ärger dich nicht. Bei letzterem ist der Zufallsfaktor noch mit drin, was das ganze schon ziehmlich interessant machen dürfte. Interessant wären auch Kartenspiele wie Mau-Mau oder gar Skat. Man sollte dafür aber ein eigenes Topic erstellen und hier mal wieder zur eigentlichen Frage zurückkommen. |
Re: Ideen zur Schach KI
Man kann sich doch in Teams organisieren...
Und das am Ende nicht das neue Fritz rauskommt ist doch klar! Aber man könnte mal schauen was die Einzelnen für Ansätze benutzen. |
Re: Ideen zur Schach KI
Warum nicht gleich eine richtige KI( AI?? ), eine künstliche Intelligenz für unser Forum!!
|
Re: Ideen zur Schach KI
<Einschub>
Zitat:
AI = Artificial Intelligence => Ist das selbe ;) </Einschub> |
Re: Ideen zur Schach KI
Zitat:
|
Re: Ideen zur Schach KI
Das Problem bei einer Stellungsbewertung ist doch, dass eine Stellung für die Berechnung *schwäbisch* sauschlecht */schwäbisch* aussehen kann und trotzdem im nächsten Zug einen deutlichen Vorteil arrangiert
air |
| Alle Zeitangaben in WEZ +1. Es ist jetzt 04:44 Uhr. |
Powered by vBulletin® Copyright ©2000 - 2024, Jelsoft Enterprises Ltd.
LinkBacks Enabled by vBSEO © 2011, Crawlability, Inc.
Delphi-PRAXiS (c) 2002 - 2023 by Daniel R. Wolf, 2024 by Thomas Breitkreuz