Ich würde euch gerne fragen, wie man so etwas am besten anpackt(Funktionen/Klassen usw.)
Danke im voraus
Einfaches Schachprogramm in Python
Ich will ein Programm schreiben, mit dem man am Ende Schach spielen kann, grafisch(pygame), oder über Textnachrichten ist erstmal egal.
Ich würde euch gerne fragen, wie man so etwas am besten anpackt(Funktionen/Klassen usw.)
Danke im voraus
Ich würde euch gerne fragen, wie man so etwas am besten anpackt(Funktionen/Klassen usw.)
Danke im voraus
Ok, danke, ich schau mir minimax mal an wenn ich Zeit hab(Termindruck 
)
Aufbaugedanke:
-Funktion die alle legalen Züge berechnet, eine bestimmt Anzahl Züge vorraus, und die als Liste zurückgibt
-Funktion, die aus einer Liste mit Zügen, den besten auswählt
)Aufbaugedanke:
-Funktion die alle legalen Züge berechnet, eine bestimmt Anzahl Züge vorraus, und die als Liste zurückgibt
-Funktion, die aus einer Liste mit Zügen, den besten auswählt
Was für eine Strategie du wählst ist eigentlich zweitrangig entscheidend ist die Bewertungsfunktion.
Deshalb sollte man schon gut Schachspielen um gute von schlechten Stellungen zu unterscheiden und richtig zu bewerten.
Deshalb sollte man schon gut Schachspielen um gute von schlechten Stellungen zu unterscheiden und richtig zu bewerten.
Du schreibst das so, als wäre es relativ einfach, einen Schachcomputer zu programmieren. Du brauchst ja überhaupt erstmal eine ausreichende Datengrundlage, damit der Computergegner zu jedem Zeitpunkt halbwegs sinnvolle Züge wählen kann. Ich würde mindestens erwarten, dass er die gängigen Eröffungen drauf hat und auch nicht gleich auf so billige Dinge wie Schäfermatt reinfällt. Auch ein einigermaßen realistisches Finale dürfte eine Mindestanforderung sein. Da bin ich mal sehr gespannt, wie du deine 2 Stichpunkte umsetzen willst. Ich würde ja eher dazu raten, zunächst einmal ein Schachspiel ohne Computergegner (also Mensch gegen Mensch) zum Laufen zu kriegen. An der Computerintelligenz kann man sich IMHO besser ganz zum Schluss versuchen.Tobs hat geschrieben:Aufbaugedanke:
-Funktion die alle legalen Züge berechnet, eine bestimmt Anzahl Züge vorraus, und die als Liste zurückgibt
-Funktion, die aus einer Liste mit Zügen, den besten auswählt
Eigentlich ist es noch schlimmer, weil am Anfang so viele Züge möglich sind, werden Eröffnungsdatenbanken verwendet.
Trotzdem würde ich das nicht als Raketenwissenschaft sehen.
Ich kannte sogar ein Kommilitone der an einfachen Informatikgrundstudiensachen gescheitert ist, aber sein Schach in Visual Basic umgesetzt hatte. Soll wohl nicht die schlechte Implementierung gewesen, seiner Aussage nach.
Trotzdem würde ich das nicht als Raketenwissenschaft sehen.
Ich kannte sogar ein Kommilitone der an einfachen Informatikgrundstudiensachen gescheitert ist, aber sein Schach in Visual Basic umgesetzt hatte. Soll wohl nicht die schlechte Implementierung gewesen, seiner Aussage nach.
Ansonsten wäre es ja, statt der Implementierung einer eigenen KI (vorübergehend) auch überlegenswert, für den Mensch vs. Computer-Modus ein Protokoll zur Einbindung von Schach-Engines wie z.B. UCI zu implementieren, bevor man sich an was eigenem versucht.snafu hat geschrieben: Ich würde ja eher dazu raten, zunächst einmal ein Schachspiel ohne Computergegner (also Mensch gegen Mensch) zum Laufen zu kriegen. An der Computerintelligenz kann man sich IMHO besser ganz zum Schluss versuchen.
Ok, danke erst mal für die ganzen Antworten
Das Schachprogramm, schreibe ich, weil ich seit kurzem in einem Schachverein bin.
Wenn es einigermaßen spielen kann, will ich es mitnehmen, und es dann zum Spaß gegen das Schachprogramm von einem Kumpel(auch in Python) spielen lassen
Aber ich hab Python, erst vor einem Jahr angefangen, deshalb bin ich schon glücklich, wenn das Programm sich beim Spielen an Regeln hält
Das Schachprogramm, schreibe ich, weil ich seit kurzem in einem Schachverein bin.
Wenn es einigermaßen spielen kann, will ich es mitnehmen, und es dann zum Spaß gegen das Schachprogramm von einem Kumpel(auch in Python) spielen lassen
Aber ich hab Python, erst vor einem Jahr angefangen, deshalb bin ich schon glücklich, wenn das Programm sich beim Spielen an Regeln hält
@darktrym:
Damit da in Sachen AI was halbwegs Brauchbares rauskommt, sollte man schon etwas dicker aufgestellt sein in Sachen Suchbäumen und effizienten Algorithmen. Mit einfacher und schnell implementierter Tiefensuche kommt man bei Schach nicht weit (siehe Spielkomplexität).
@Tobs:
Vergiss am besten zunächst die Idee eines Computergegners. Allein die korrekte Implementation aller Schauchregeln wird Dich am Anfang gut beschäftigen. So könntest Du zunächst mit einem Programm anfangen, was die gewünschten Züge der Spieler prüft und erlaubt/verbietet. Ein Spieler kannst Du dann später durch eine AI ersetzen.
Damit da in Sachen AI was halbwegs Brauchbares rauskommt, sollte man schon etwas dicker aufgestellt sein in Sachen Suchbäumen und effizienten Algorithmen. Mit einfacher und schnell implementierter Tiefensuche kommt man bei Schach nicht weit (siehe Spielkomplexität).
@Tobs:
Vergiss am besten zunächst die Idee eines Computergegners. Allein die korrekte Implementation aller Schauchregeln wird Dich am Anfang gut beschäftigen. So könntest Du zunächst mit einem Programm anfangen, was die gewünschten Züge der Spieler prüft und erlaubt/verbietet. Ein Spieler kannst Du dann später durch eine AI ersetzen.
Das ist richtig und steht nicht im Widerspruch zu dem, was ich sagte. Trick ist, den Suchbaum schmal zu halten, was beim Schach äussert schwierig ist (Stichwort - iterative Tiefensuche, wenig aussichtsreiche Zweige werden früh verworfen). Die Bewertung guter oder schlechter Zweig geht im Schach nur mit zusätzlicher "Erfahrung" - gerade im Eröffnungsspiel muss man auf diese zurückgreifen, da spielprinzipbedingt alle Stellungen potenziell in offene Spiele münden, also gar nicht durchrechenbar wären (man begnügt sich mit Scheinlösungen - Spiele wie z.B. Reversi haben immer einen definierten Endzustand und sind daher theoretisch durchrechenbar. Die Güte der Scheinlösungen ist der springende Punkt und entscheidet, ob eine AI als stark oder schwach wahrgenommen wird). Trotzdem können Datenbanken im weiteren Spielverlauf nicht alle Stellungen kennen, da es zu viele gibt. Hier muss man dann mit Tricks wie Partitionierung und verstärkter Tiefensuche ran, um die Güte hochzuhalten. Alles in allem - algorithmisch sehr komplex zu lösen und nicht mal eben in Python oder VisualBasic zusammengehackt.darktrym hat geschrieben:@jerch: Nein, entscheidend ist deine Bewertungsfunktion und deren Gewichtung.
Das ist ja alles klar, aber ich hatte nicht das Gefühl, dass der OP vorhatte, ein Schachprogramm auf den Markt zu bringen, das um die Weltspitze kämpft. Vielmehr ging es ihm - ähnlich wie beim Roboterfußball - darum, seine Strategieüberlegungen, Bewertungsfunktionen, Suchmechanismen etc. mit einem Kollegen zu messen. Und da würde ich mal sagen, dass kann man schon machen. Im Zweifel startet das mit einem Baum über alle möglichen Züge in den nächsten 3 Schritten. Dann noch 100 Punkte für ein Matt des Gegners, 75 Punkte+Wert_von_Spielfigur, wenn eine gegnerische Figur geschlagen wird, 50 Punkte für ein Schach beim Gegner, das alles in negativ, wenn man selbst durch die Züge in diese Situation kommt. Und unter denen wird der beste Anfangszug gewählt, bei Gleichheit macht es ein Zufallsgenerator.
Das Programm wird sicher keine Meisterschaft gewinnen, wenn es steht, dann wird man sicher die Bewertungsfunktion ausbauen sowie den Suchbaum selektiv in die Tiefe richten (verheißungsvolle Züge tiefer ausloten etc.)
Aber wie man das in python umsetzen kann (eine einfache Variante), würde mich schon auch interessieren. Ich würde vielleicht auch eine Bewertungsfunktion beisteuern, wenn es denn soweit ist.
Das Programm wird sicher keine Meisterschaft gewinnen, wenn es steht, dann wird man sicher die Bewertungsfunktion ausbauen sowie den Suchbaum selektiv in die Tiefe richten (verheißungsvolle Züge tiefer ausloten etc.)
Aber wie man das in python umsetzen kann (eine einfache Variante), würde mich schon auch interessieren. Ich würde vielleicht auch eine Bewertungsfunktion beisteuern, wenn es denn soweit ist.
Mit NegaMax* könnte man anfangen und die Züge wichten (Bruteforce). Problem ist hier schon bei einer Iterationstiefe von 1 die Anzahl von möglichen Zügen, welche sich aus beweglichen Figuren und deren erreichbaren Feldern ergibt (sehr breiter Baum). In die Bewertung müssen einige Aspekte einfliessen - Wert der eigenen Figur, Deckung einer eigenen wertvollen Figur, Zugzwang für Gegner (Bedrohung einer nicht gedeckten gegnerischen Figur), Schlagen einer gegnerischen Figur usw. Damit sollte man starten können.NoPy hat geschrieben:Das ist ja alles klar, aber ich hatte nicht das Gefühl, dass der OP vorhatte, ein Schachprogramm auf den Markt zu bringen, das um die Weltspitze kämpft. Vielmehr ging es ihm - ähnlich wie beim Roboterfußball - darum, seine Strategieüberlegungen, Bewertungsfunktionen, Suchmechanismen etc. mit einem Kollegen zu messen. Und da würde ich mal sagen, dass kann man schon machen. Im Zweifel startet das mit einem Baum über alle möglichen Züge in den nächsten 3 Schritten. Dann noch 100 Punkte für ein Matt des Gegners, 75 Punkte+Wert_von_Spielfigur, wenn eine gegnerische Figur geschlagen wird, 50 Punkte für ein Schach beim Gegner, das alles in negativ, wenn man selbst durch die Züge in diese Situation kommt. Und unter denen wird der beste Anfangszug gewählt, bei Gleichheit macht es ein Zufallsgenerator.
Das Programm wird sicher keine Meisterschaft gewinnen, wenn es steht, dann wird man sicher die Bewertungsfunktion ausbauen sowie den Suchbaum selektiv in die Tiefe richten (verheißungsvolle Züge tiefer ausloten etc.)
Aber wie man das in python umsetzen kann (eine einfache Variante), würde mich schon auch interessieren. Ich würde vielleicht auch eine Bewertungsfunktion beisteuern, wenn es denn soweit ist.
Nächster Schritt wäre die Eingrenzung des Suchbaumes, um Strategien über größere Suchtiefen erkennen zu können (multiple Deckungen, Schlagabtausch). Später sollte die Gewichtung auch lokale Minima überwinden können, sonst fällt die AI zuverlässig auf Opferstellungen herein.
Edit: Typos
[*] Was ich vergessen habe - den Suchbaum kann man mit einer alpha-beta Suche deutlich verkleinern (z.B. NegaScout). Wenn man dann noch eine gute Sortierung für die Zugtestung findet, kann man über 90% des Baumes abkürzen.
Halte ich für den Anfang für übertrieben. Es wird schon eine gewisse Mühe machen, eine Situation auf Schach/-Matt und Remis zu testen. Aus dem Test auf Schach kann man sicher ableiten, wie die Bedrohungslage der einzelnen Figuren ist. Aber Deckung wertvoller Figuren, Zugzwang, Schlagabtausch - das ist doch eher Teil 2, oder? Mit Teil 1 könnte man zumindest schon mal spielen, wenn es vermutlich auch keine Hürde darstellt.jerch hat geschrieben:Mit NegaMax* könnte man anfangen und die Züge wichten (Bruteforce). Problem ist hier schon bei einer Iterationstiefe von 1 die Anzahl von möglichen Zügen, welche sich aus beweglichen Figuren und deren erreichbaren Feldern ergibt (sehr breiter Baum). In die Bewertung müssen einige Aspekte einfliessen - Wert der eigenen Figur, Deckung einer eigenen wertvollen Figur, Zugzwang für Gegner (Bedrohung einer nicht gedeckten gegnerischen Figur), Schlagen einer gegnerischen Figur usw. Damit sollte man starten können.NoPy hat geschrieben:Das ist ja alles klar, aber ich hatte nicht das Gefühl, dass der OP vorhatte, ein Schachprogramm auf den Markt zu bringen, das um die Weltspitze kämpft. Vielmehr ging es ihm - ähnlich wie beim Roboterfußball - darum, seine Strategieüberlegungen, Bewertungsfunktionen, Suchmechanismen etc. mit einem Kollegen zu messen. Und da würde ich mal sagen, dass kann man schon machen. Im Zweifel startet das mit einem Baum über alle möglichen Züge in den nächsten 3 Schritten. Dann noch 100 Punkte für ein Matt des Gegners, 75 Punkte+Wert_von_Spielfigur, wenn eine gegnerische Figur geschlagen wird, 50 Punkte für ein Schach beim Gegner, das alles in negativ, wenn man selbst durch die Züge in diese Situation kommt. Und unter denen wird der beste Anfangszug gewählt, bei Gleichheit macht es ein Zufallsgenerator.
Das Programm wird sicher keine Meisterschaft gewinnen, wenn es steht, dann wird man sicher die Bewertungsfunktion ausbauen sowie den Suchbaum selektiv in die Tiefe richten (verheißungsvolle Züge tiefer ausloten etc.)
Aber wie man das in python umsetzen kann (eine einfache Variante), würde mich schon auch interessieren. Ich würde vielleicht auch eine Bewertungsfunktion beisteuern, wenn es denn soweit ist.
Nächster Schritt wäre die Eingrenzung des Suchbaumes, um Strategien über größere Suchtiefen erkennen zu können (multiple Deckungen, Schlagabtausch). Später sollte die Gewichtung auch lokale Minima überwinden können, sonst fällt die AI zuverlässig auf Opferstellungen herein.
Edit: Typos
[*] Was ich vergessen habe - den Suchbaum kann man mit einer alpha-beta Suche deutlich verkleinern (z.B. NegaScout). Wenn man dann noch eine gute Sortierung für die Zugtestung findet, kann man über 90% des Baumes abkürzen.