Hi
Muss ich wirklich einen Binären Suchbaum programmieren, um eine KI zu entwickeln?
a) Kein "binärer" Baum, außer beim betroffenen Spiel hat man nie mehr als zwei Zugmöglichkeiten.
b) Wenn man die Vorgänge vom Algo speichern will, ja, man braucht einen Baum. Wenn man nur daran interessiert ist, welchen Zug man machen will ... rekursive Funktionen mit jeweils lokalen einzelnen Variablen imitieren den "Baum" ganz gut. Kein Grund, die Datenstruktur selber zu programmieren.
Wo finde ich übersichtliche Codebeispiele, wo gezeigt wird, wie ich Minimax und Alphabeta programmieren muss
Sollte "eigentlich" nicht nötig sein, wenn man den Algo und Rekursion versteht. Sonst
(Allerdings hab ich auf die Schnelle keinen übersichtlichen
und fertigen Code gefunden, eben deswegen...).
...
Was jeder "Baum"knoten an Daten braucht:
a) Einen vollen Spielstand (was man da wie abspeichert hängt ganz vom Spiel ab. zB. bei Schach wäre es, welche Figur samt Farbe auf welchem Feld steht, welcher der zwei Spieler noch die Rochade machen darf, und welcher der vorhandenen Bauern zurzeit enpassant-fähig ist)
b) Welcher der zwei Spieler gerade dran ist.
c) Eine Zahl, die den Spielstand bewertet. Wertebereich kann man sich selber aussuchen, unter folgenden Bedingungen: Je höher, desto besser ist der aktuelle Spielstand für den Algo-verwendenen Spieler (KI), und je neidriger desto besser für den Anderen. Beim höchstmöglichen Wert hat die KI gewonnen, beim Niedrigsten eben der Andere. ... Ein mögliches (aber nicht gutes) Beispiel wäre 1 für A gewinnt, -1 für B gewinnt, und 0 für ein unfertiges Spiel und auch für Unentschieden. Der Algo arbeitet aber besser mit breiteren Wertebereichen.
Außerdem braucht man ein paar spezielle Funktionen, die beide vom Spiel abhängen:
a) Eine Funktion, die einen Spielstand von Punkt a darauf hin überprüft, ob jemand gewonnen hat (und auch wer) oder ob das Spiel noch offen ist.
b) Eine Bewertungsfunktion, die aus den Daten von Punkt a die Zahl aus Punkt c berechnet. Natürlich einhalten, dass höhere Werte besser für die KI sind usw.
Falls man nicht nur 1/-1/0 hat ist das oft schwierige Teil am Ganzen. Eine gute Werteermittlung (bessere Spielstände für den Algoverwender also bessere Zahlen) ist aber essentiell für den Erfolg vom Algo.
c) Eine Funktion, die aus einem Spielstand (aus a) und aus der Info wer gerade dran ist (aus b) alle möglichen nächsten Spielstände ermittelt. Also, genau einen Zug später.
...
Dann, die Idee von Minimax (in der einfachsten Form und ohne Heuristiken, und als Baum beschrieben):
Man ist gerade eben mitten im Spiel, udn die KI muss den nächsten Zug berechnen.
a) Dafür zuerst einmal den aktuellen Spielstand als Baumknoten abbilden (aber ohne Bewertungszahl c noch, also nur a und b)
b) Baumaufbau: Alle nächsten Spielstände generieren, von denen rekursiv wieder alle nächsten ... bis zu einer bestimmten (wählbaren) Tiefe. Je tiefer desto besser fürs Ergebnis, aber tiefer dauert auch länger. Ideal wäre natürlich ein kompletter Baum, aber für Spiele wie Schach etc. geht das einfach nicht.
(Falls man auf Spielenden stößt, bei denen natürlich keine weiteren Kindknoten generieren)
c) Für alle Blätter in dem Baum (egal ob Spielende oder einfach wegen der Tiefe dort aufgehört) die C-Zahl mit der Bewertungsfunktion berechnen.
d) Von unten nach oben wie folgt die Bewertung der Nicht-Blätter ermitteln: Wenn man die Bewertung für einen Knoten will, bei dem die KI dran ist, die höchste Bewerung der (direkten) Kindknoten nehmen. Für Knoten, wo der Gegner dran ist, stattdessen die niedrigste Bewertung der (direkten) Kindknoten.
Sinn dahinter: Wenn die KI dran ist, immer den Zug mit dem wahrscheinlich besten Ergebnis nehmen; aber immer auch annehmen dass der Gegner den für sich besten Zug macht (also den für die KI schlechtesten)
Die Schritte b, c und d können codemäßig eben leicht durch eine rekursive Funktion mit Parametern und Returnwert umgesetzt werden.
e) Fertiggerechnet, man ist wieder an der Baumwurzel: Das Kind der Wurzel hernehmen, das die höchste Bewertung hat, und genau diesen Zug machen.
Pseudocode b/c/d:
Code:
solve(spielstand, kiIstDran, wieTief)
{
if(spielIstAus(spielstand) || wieTief < 1) return bewerte(spielstand);
variablen zielwert, aktuellerwert
if(kiIstDran) zielwert = kleinsterBewertungswert //kann mit max nur größer werden
else zielwert = gröterBewertungswert //umgekehrt
für jeden zielspielstand in (berechneAlleZüge(spielstand, kiIstDran))
{
aktuellerwert = solve(zielspielstand, not kiIstDran, wieTief - 1)
if(kiIstDran) zielwert = max(aktuellerwert, zielwert)
else zielwert = min(aktuellerwert, zielwert)
}
return zielwert;
}
Jetzt das für alle gerade jetzt möglichen Züge (bzw. deren Ergebnis-Spielstände) aufrufen, und den Zug mit dem höchsten Returnwert nehmen.
...
Alphabeta (wieder in der einfachsten Form und ohne Heuristiken) sind zwei Verschnellerungen, ohne das Ergebnis zu verschlechtern. Es geht darum, dass man anhand der Bewertungszahlen schon bekannter Knoten verschiedene Kind-Teilbäume einfach nicht berechnen braucht.
Voraussetzung im Code ist, dass man in solve() auch den aktuellen Zielwert des nächsthöheren Knoten bzw. der oberen aufrufenden Funktion hat, auch wenn die mit ihrem eigenen Schleifendurchgang noch nicht fertig ist.
Code:
solve(spielstand, kiIstDran, wieTief, obererZielwert)
{
if(spielIstAus(spielstand) || wieTief < 1) return bewerte(spielstand);
variablen zielwert, aktuellerwert
if(kiIstDran) zielwert = kleinsterBewertungswert //kann mit max nur größer werden
else zielwert = gröterBewertungswert //umgekehrt
für jeden zielspielstand in (berechneAlleZüge(spielstand, kiIstDran))
{
aktuellerwert = solve(zielspielstand, not kiIstDran, wieTief - 1, zielwert)
if(kiIstDran) zielwert = max(aktuellerwert, zielwert)
else zielwert = min(aktuellerwert, zielwert)
}
return zielwert;
}
Idee 1: Im aktuell zu solve-nden Knoten ist die KI dran. In den Unteraufrufen von solve ist klarerweise der Gegner dran. Die KI nimmt den höchsten Wert ihrer Kinder, und die Kindern nehmen den niedrigsten Wert ihrer Kinder. Klar soweit.
Angenommen, der KI-Knoten hat drei Kinder, eins ist schon abgearbeitet, Wert 10. Sollte eins der zwei anderen Kinder höher sein wird natürlich der höhere Wert genommen, sonst bleibts bei 10.
Diese zwei noch zu prüfenden Kinder müssen also mindestens 10 (bzw. 11) erreichen, um überhaupt relevant zu sein.
Wenn eines der Kinder während der eigenen Schleife draufkommt, dass eines der Kindeskinder kleiner als 10 war ...
bei den Kindern ist ja der Gegner dran
=> kleinster Wert ist das Ergebnis
=> Ein Wert kleiner 10 bedeutet, es kann nicht mehr größer als 10 werden
=> Die noch offenen Kindeskinder können weggelassen werden, weil das Kind
selber schon nicht mehr über 10 kommen kann und damit unwichtig ist.
Code:
solve(spielstand, kiIstDran, wieTief, obererZielwert)
{
if(spielIstAus(spielstand) or wieTief < 1) return bewerte(spielstand);
variablen zielwert, aktuellerwert
if(kiIstDran) zielwert = kleinsterBewertungswert //kann mit max nur größer werden
else zielwert = gröterBewertungswert //umgekehrt
für jeden zielspielstand in (berechneAlleZüge(spielstand, kiIstDran))
{
aktuellerwert = solve(zielspielstand, not kiIstDran, wieTief - 1, zielwert)
if(kiIstDran) zielwert = max(aktuellerwert, zielwert)
else zielwert = min(aktuellerwert, zielwert)
if(not kiIstDran and zielwert < obererZielwert) return zielwert;
}
return zielwert;
}
Idee 2, das Umgekehrte dazu
Code:
if(kiIstDran and zielwert > obererZielwert) return zielwert;
(Sinn sollte klar sein).
