Schachprogrammierung - Wie funktioniert MinMax Prinzip
-
Hallo,
ich will versuchen in BASIC (nicht in C++) ein Schachprogramm zu schreiben.
Nur ein minimales versteht sich. Ich habe lange an einer Möglichkeit geforscht. Unter anderem durch meinen GSG-Alogrithmus. (General Strategic Game Algorithm)
Ich werde ihn auch irgendwann implementieren. Allerdings wollte ich ein Schachprogramm kreieren, welches auch gegen einen Hobby Spieler eine Chance hat.
Darum wollte ich gerne die Minimax-Suche implementieren. Das Prinzip mit Minimal und Maximal hab ich verstanden, allerdings nicht, wie sich das aufs Schachfeld auswirkt. Könnte mir das jemand erklären?
MfG,
Christoph
-
Christoph-C++ schrieb:
Unter anderem durch meinen GSG-Alogrithmus. (General Strategic Game Algorithm)
Jedes Spielfeld mit Zusatzinformationen versehen wie Wert/AngriffserfolgsWkeit/VErfolgsWkeit/Truppentransportrichtung und durchs Netz iterieren?
Christoph-C++ schrieb:
Das Prinzip mit Minimal und Maximal hab ich verstanden, allerdings nicht, wie sich das aufs Schachfeld auswirkt.
Gar nicht.
-
Korrekt.
Grundidee lautet:
F1 + F2 + Fi + Fs = Wf
Wobei F1 das Feld bei einem 1-dimensionalen System ist und F2 das Zielfeld
Bei 2D Ansichten wäre das dann die Summe von E1 = 5+1 = 6
Fi Wert der Figur
und Fs ob Möglichkeit des Schlagens besteht.Was macht der Minimax Algorithmus dann im Spiel selber, also wie funktioniert er bei der Bewertung?
-
Vielleicht sollten wir mal ein einfacheres Spiel spielen.
Wir haben einen Stapel mit 6 Streichholzern.
Jeder nimmt abwchslend vom Stapel 1,2 oder 3 Streichhölzer.
Der, der das letzte Hölzchen nimmt, hat verloren.Du fängst an.
Du hast die Möglichkeiten
C:6 -> V:5
C:6 -> V:4
C:6 -> V:3
Und davon wird maximiert. Maximieren kannst Du noch nicht, weil Du keine Werte hast.Aus V:3 habe ich die Möglichkeiten
V:3 -> C:2
V:3 -> C:1(-100)
V:3 -> C:0(+100)
Und davon wird minimiert. Schlechter als -100 geht nicht, also V:3(-100)Aus V:4 habe ich die Möglichkeiten
V:4 -> C:3
V:4 -> C:2
V:4 -> C:1(-100)
Und davon wird minimiert. Schlechter als -100 geht nicht, also V:4(-100)Aus V:5 habe ich die Möglichkeiten
V:5 -> C:4
V:5 -> C:3
V:5 -> C:2
Und davon wird minimiert. Tja, noch nicht genug Daten.Mal C:4 ausrechnen.
Aus C:4 hast Du die Möglichkeiten
C:4 -> V:3(-100)//oben schon rausgefunden
C:4 -> V:2
C:4 -> V:1(+100)
Und davon wird maximiert. Besser als +100 geht nicht, also C:4(+100)Aus C:3 hast Du die Möglichkeiten
C:3 -> V:2
C:3 -> V:1(+100)
C:3 -> V:0(-100)
Und davon wird maximiert. Besser als +100 geht nicht, also C:3(+100)Aus C:2 hast Du die Möglichkeiten
C:2 -> V:1(+100)
C:2 -> V:0(-100)
Und davon wird maximiert. Besser als +100 geht nicht, also C:2(+100)Das trage ich oben bei V:5 mal ein:
Aus V:5 habe ich die Möglichkeiten
V:5 -> C:4(+100)
V:5 -> C:3(+100)
V:5 -> C:2(+100)
Und davon wird minimiert. V:5(+100)Uih, hab langsam Angst. Das trage ich mal ganz oben bei C:6 ein.
Du hast die Möglichkeiten
C:6 -> V:5(+100)
C:6 -> V:4
C:6 -> V:3
Und davon wird maximiert. Besser als 100 geht nicht, also C:6(+100).Du gewinnst also.
Beim Schach leichte änderungen. Ich habe den Baum oft beschneiden können mit dem Argument "besser/schlechter als ... geht es nicht".
Das ist nicht nötig, kannst auch den ganzen Baum ausrechnen.
Ich musste immer runterrechnen bis zum Matt. Kannste beim Schach nicht, da rechnest Du nur ne bestimmte teife weit runter und dann, bewertest Du die Stellung über den Daumen gepeilt. Zum Beispiel durch schlichtes Zählen des Materiels.
Bauer=1, Läufer=3, Springer=3, Turm=4, Dame=9 ist üblich.
König=100!Wo ich schrieb "V:5" wäre beim Schach statt der Ziffer eine ganze Stellung aus 64 Feldern und bis zu 32 Spielsteichen gemeint.
-
Der Baum rechnet bei deinem kleinen Spiel also immer bis zum Sieg runter?
Und da das im Schach zu viele mögliche Variablen sind, rechnet man da nur bis zu einer gewissen Tiefe.
Ergibt Sinn.