Frage von WillibergiUsermod Junior, 155

Schachprogramm einfach entwickeln?

Moin,

ich bin Lehrer für Oberstufe Informatik und mache mit meinen Schülern gerne kleinere Projekte.

Vor einiger Zeit fragte mich ein Schüler, ob wir nicht als Projekt ein Schachprogramm entwickeln könnten. Ich sagte ihm, dass ich mich einmal darüber informieren müsste.

So, das Problem ist nun folgendes:

Die Schüler können die Grundstrukturen von Java - Klassen, Objekte, GUI, etc.

Ich habe mich im Internet mal über die Algorithmen schlau gemacht und erfahren, dass diese doch scheinbar etwas komplex sind, vor allem für Java-Anfänger.

Meine Frage ist nun: Kennt ihr einfache, nicht zu komplexe Algorithmen, die man gut erklären kann?

Das Schachprogramm muss keinen Weltmeister schlagen können, aber es sollte schon plausible Züge machen können.

Gibt es überhaupt einfache Algorithmen für solche Anwendungen, oder muss ich mir etwas anderes überlegen?

Danke schon mal für eure Antworten.

LG Willibergi

Hilfreichste Antwort - ausgezeichnet vom Fragesteller
von MalNachgedacht, 26

Ob Schach, Dame, Vier gewinnt oder Tic Tac Toe - das Prinzip wie man so etwas normalerweise programmiert ist immer das gleiche

Man braucht eine Datenstruktur / eine Klasse die eine aktuelle Stellung beschreibt - 

desweiteren einen Zuggenerator der für jede beliebige Stellung alle möglichen Züge berechnet - und die daraus resultierenden Stellungen 

und man braucht eine Bewertungsfunktion, die eine beliebige Stellung möglichst gut dahingehend bewertet ob sie eher gut für den einen oder anderen Spieler ist.

Dazu muß dann noch die Alpha-Beta Suche programmiert werden die für jede Stellung mit Hilfe des Zuggeneratos und der Stellungsbewertung den Zug ermittelt der unter Berücksichtigung von einer bestimmten Anzahl von Folgezügen für einen Spieler optimal ist. 

https://de.wikipedia.org/wiki/Alpha-Beta-Suche

Schach ist dabei insofern schwierig weil de Zuggenerator relativ kompliziert ist. Es gibt verschiedene Figuren mit unterschiedlichen Zugmöglichkeiten, Spezialfälle wie Rochade oder Bauernumtausch, En passant-Schlagen, Bauern die beim ersten Zug gleich zwei Felder nach vorne ziehen dürfen....

Das alles zu implementieren ist für Anfänger recht zeitaufwendig.

Die Stellungsbewertung kann für Lehrzwecke relativ einfach ausfallen. Zur Not weißt man jedem Figurentyp einen bestimmten Wert zu (Bauer=1, Dame=8) der ungefähr die Bedeutung wiederspiegelt.
Dann addiert man alle noch vorhandenen eigenen Figurenwerte und subtrahiert die Figurenwerte der gegnerischen Figuren...

Ein gutes Schachprogramm berücksichtigt für die Stellungsbewertung noch einiges mehr - was dann aber auch zusätzlich wieder Zeit kostet die dann fehlt um per Zuggenerator möglichst viele Züge vorauszuberechnen.
Da muiß dann immer ein Kompromiss gefunden werden.

Ein gutes Schachprogramm solle auch nicht exakt x Züge voraus berechnen - da es sonst passieren kann das die eigene Dame einen Bauer schlägt aber der nächste Gegnerzug (wo dessen Bauer dann die Dame schlägt) nicht mehr "gesehen" wird.
Eine Methode das zu vermeiden ist, dass aber einer bestimmten Zugtiefe nur noch Züge berücksichtigt werden die Figuren schlagen - die dann aber bis zum "bitteren Ende" durchgerechnet werden.

Das sprengt aber wohl bei weitem den schulischen Rahmen - und deswegen würde ich eher "Vier Gewinnt" vorschlagen.-

Der Zuggenerator ist bei "Vier gewinnt" extrem simpel - jeder der sieben Schächte der noch nicht voll ist ist ein erlaubter Zug.

Die Stellung ist auch leicht abbildbar. Ein zweidimensionales int Array

0=leer 1=eigener Stein 2=Gegnerischer Stein.

Und die Stellungsbewertung ist auch vergleichsweise einfach-

für jedes der 7 x 6 "Felder" prüft man ob es noch Teil einer eigenen oder gegnerischer "Vierer-Reiher" werden kann und vergibt entsprechend Punkte.

Da es nur maximal 7 mögliche Züge pro Stellung gibt kann man auch ohne großartige Optimierungen leicht 5 Züge oder mehr vorausberechnen - was dann bereits reichen könnte damit der eine oder andere junge Programmierer gegen sein eigenes Programm verliert - was sicherlich ein prägendes Erlebnis sein dürfte....

Das ein komplizierteres Spiel wie Schach letztlich auf die gleiche Weise programmiert wird dürfte den Schülern dann auch klar werden...

Kommentar von MalNachgedacht ,

Auch wenn die Alpha-Beta-Suche deutlich effizienter ist reicht es für die Schule sicherlich auch, die gleich gute aber langsamere Mini-Max-Methode zu verwenden:

https://de.wikipedia.org/wiki/Minimax-Algorithmus


Alpha-Beta wäre dann noch eine nette Erweiterung für die schnellen Überflieger....

Antwort
von Schachpapa, 42

Mensch ärgere dich nicht

überschaubares GUI, einfache Regeln.

Ausbaubar:
Hot Seat (Spieler wechseln sich am Rechner ab)
vs Netzkommunikation

Computer als Supervisor (der die Einhaltung der Regeln überwacht) oder als Spieler mit "künstlicher Intelligenz".

Ist aber kein Projekt für zwei Wochen, wenn etwas dabei herauskommen soll.

Antwort
von amdphenomiix6, 84

Ich tendiere zu Nein. Wie Sie bereits gesagt haben, sind diese Algorithmen in der Tat sehr komplex. Ich weiß nicht, wie viele Wochenstunden Sie haben, aber die Zeit wird wahrscheinlich nicht ausreichen. 

Selbst eine einfache Alpha-Beta-Suche mit binärem Suchbaum dauert einfach zu lange, vernünftig zu implementieren, da es eben sehr viele Entscheidungskriterien zu beachten gilt. Auch hat Java bei großen Datenmengen unschöne Randerscheinungen.

Stattdessen schlage ich Ihnen z.B. Vier-Gewinnt als Projekt vor.

Kommentar von Willibergi ,

Stattdessen schlage ich Ihnen z.B. Vier-Gewinnt als Projekt vor.

Keine schlechte Idee!
Werde ich mir mal überlegen. ;)

LG Willibergi

Kommentar von rmnstr ,

Auch hat Java bei großen Datenmengen unschöne Randerscheinungen.

Bitte, was?

Antwort
von herakles3000, 47

Schach hat zuviele regeln  und auch sonder zug möglichkeiten deswegen ist es zu komplex aber Stadt Schach könnte Dame Eine Gute Alternative sein

zb Den Algorytmus für das Schaltjahr zum berechnen ist noch sehr einfach .

Antwort
von triopasi, 64

Denke Schach ist zu komplex. Wie wäre es mit einer KI für TicTacToe, oder ist das zu langweilig? Da kann man denk ich innerhalb einiger Stunden was recht ordentliches zaubern, wogegen man nurnoch schwer oder garnicht gewinnen kann.

Kommentar von Willibergi ,

Nein, zu langweilig keinesfalls!

Aber das ist auch eine gute Idee!

LG Willibergi

Kommentar von triopasi ,

Kommt halt immer drauf an, was deine Schüler können. 4 Gewinnt ist von Prinzip der KI ja auch recht ähnlich. Ne andere Idee wäre Schiffe versenken (wobei das schon vom Spiel her wieder realativ komplex wird).

Kommentar von hibas123 ,

Also ich weiß aus erfahrung das Tic Tac Toe eine sehr schöne möglichkeit ist sich mit Algorithmen zu beschäftigen, vor allem wenn man noch etwas begrenzte java kenntnisse besitzt. Außerdem kann man recht gut die Vorteile von Objektorientierter programmierung zeigen. Vor allem macht es den meißten viel spass den Algorithmus auf die Probe zu stellen. Also ich persöhnlich kann es nur empfehlen

Antwort
von wolfgang1956, 25

Ein Schachprogramm dürfte zu komplex werden. Alleine eine brauchbare Bewertungsfunktion einer beliebigen Schachstellung, die sich aus den Zügen zwischen SchülerInnen und Computer entwickelt, dürfte locker einige Schuljahre brauchen.

Interessanter wäre ein Turnierprogramm, dass Paarungen für Einzel- und Mannschaftskämpfe ermittelt und auswertet wäre da interessant.

Eingabe der Spielernamen, -vereine, Ergebnisse, Turnierkopfdaten (Ort, Datum, Zeit …), Auswertung der Ergebnisse, Auslosung neuer Runden bei Turnieren nach Schweizer System, wo nicht jeder gegen jeden spielt … dürfte reichlich Arbeit bedeuten …

Antwort
von slutangel22, 73

Check mal http://www.tckerrigan.com/Chess/TSCP/; das ist das kleinste Schachprogramm, das ich kenne. 2500+ Lines of code, also immer noch ganz schön vertrackt. Für Schüler würde ich sagen: Definitiv zu hart.

Kommentar von Willibergi ,

Jaja, das ist, wenn überhaupt, vielleicht was für mehrere Jahre.

Trotzdem danke!

LG Willibergi

Antwort
von Morge4now, 32

Schach ist deutlich zu komplex. Allein weil vom Computer logische Spielzüge durchgeführt werden sollten.

Ich kann durchaus Minesweeper, Vier Gewinnt oder Schiffe versenken empfehlen. Nicht stupide. Nicht zu schwer nicht zu einfach.

Keine passende Antwort gefunden?

Fragen Sie die Community

Weitere Fragen mit Antworten