Frage zu Minimax Algorithmus in TicTacToe
-
Hallo
Ich programmiere momentan als Schularbeit ein TicTacToe. Nach einer ersten Version, welche mit Gittern arbeitet, wage ich mich nun an eine Version mit Minimax. Mir ist grundsätzlich klar, wie der Minimax Algorithmus funktioniert, nur ist mir folgendes unklar.
min = Mensch
max = CPUmax (CPU) versucht ja, seinen max-Wert auf 1 zu maximieren und das von min (Player) auf 0 zu minimieren. Würde aber eine Minimierung auf 0 nicht bedeuten, dass die CPU den Spieler für "dumm" hält, da sie von weniger schädlichen Zügen für sich ausgeht ?
Muss das Programm (respektive die CPU) dem Minimum vom min folgen, welches 0 ist oder jenes, welches -1 ist, sofern am Leaf Ende ein Endwert von 0 (Unentschieden, Expert vs Expert) oder 1 (Amateur vs Expert) herrscht ? Ein min(-1) und max(1) würde ja bedeuten, dass das Spiel recht heftig läuft, sprich sich Expert vs. Expert gegenüberstehen und es ist ja nicht im Sinne der CPU, solche gefährliche Möglichkeiten zu generieren. Ich habe hier eine super Erklärung gefunden, welche viele Fragen, aber nicht die hier beantwortet:
http://forum.codecall.net/topic/37522-need-help-with-simple-c-tictactoe-game-with-ai/
Gruss Humbus
-
Ich hab mir den Link nicht angesehen, aber aus deinem Post denke ich, dass du den MinMax Algorithmus noch nicht ganz verstanden hast. Bei den Spielen, die du damit lösen kannst, musst du immer davon ausgehen, dass der Gewinn des einen auch gleichzeitig ein Verlust des anderen ist, d.h. wenn Spieler A einen Gewinn von n Einheiten macht, mach Spieler B einen Verlust von n Einheiten (sog. Nullsummenspiele). Der Spieler, der am Zug ist, ist max, weil er seinen Gewinn ja maximieren möchte und wenn er möglichst viel für sich selbst rausholt, dann nimmt er dem anderen damit auch möglichst viel weg. Der Gegenspieler min versucht das zu verhindern, denn wenn er den Gewinn des anderen minimiert, minimiert er damit auch seinen Verlust. Das hat nichts damit zu tun, ob der eine den anderen für dumm hält oder nicht.
Der minmax Algorithmus ist dann eigentlich nur noch eine Tiefensuche auf dem Spielbaum. Die Wurzel dieses Baums ist die aktuelle Situation auf dem Spielbrett (oder sonstwo), die Kinder der Wurzel sind die Stellungen auf den Brettern, wenn der aktuelle Spieler einen Zug macht. Deren Kinder wiederum sind die Stellungen, wenn der Gegenspieler einen Antwortzug macht usw. Man sieht, dass dieser Baum riesig wird und das ist auch der Grund, warum man z.B. Schach nicht mit so einem Ansatz berechnen kann. Für TicTacToe reicht es allerdings. Die finalen Züge, also die Blätter des Baums werden Bewertet und zwar abhängig von dem Spieler, der den Baum aufgebaut hat (also z.B. 1 für Gewinn, -1 für Niederlage, 0 für Unentschieden). Der Maximierer möchte jetzt natürlich gewinnen, also versucht er einen Zug zu spielen, der in Richtung eines Blattes geht, das mit 1 bewertet wurde. Um dieses zu finden macht er eine Tiefensuche bis ganz unten. Dann hat in der darüberliegenden Ebene der Minimierer die Auswahl welchen Zug er seinen Gegener denn nun spielen lässt und er wählt hier natürlich den mit dem minimalen Wert (kleinster Verlust für ihn selbst). In der Ebene darüber selektiert wiederum der Maximierer aus den Zügen, die ihm noch übrig sind denjenigen, der ihm den größten Gewinn bringt usw. usf.
Also du implementierst quasi ein Programm, das dir in jedem Zug einen Spielbaum aufbaut, die Blätter bewertet, darauf eine Tiefensuche laufen lässt und dann in jeder geraden Ebene das Maximum aus den gefundenen Knoten nach oben weitergibt und auf jeder ungeraden Ebene das Minimum.
-