Minimax am Beispiel von TicTacToe

darktrym

Fahnenträger
Hallo,
da hier Programmierthemen so viel Zuspruch bekommen, mal was neues wo ich gerade Verständnisschwierigkeiten habe.
Ich setzte mal voraus jeder kennt den Minimax-Algorithmus, gibt dazu genug YT-Videos und das Spielprinzip von TicTacToe(TTT).
Nun findet die Bewertung des Spielbrettes im Blatt des Baumes statt und die Ergebnisse werden zurückpropagiert(nach oben).
Im Falle von TTT gibt es drei Endergebnisse: S(1), N(-1), U(0).
Da in der Vielzahl der Erklärungen nicht auf die Bewertungsfunktion eingegangen wird, frage ich mich wie da sinnvolles rauskommen soll, wenn nur abwechselnd minimiert und maximiert wird?
Ich würde meinen man müsste bei den Knoten noch die Ergebnisse darunter addieren um wirklich den besten Pfad zu wählen. Andernfalls wandern nur diese 3 Zahlen(1, -1, 0) nach oben und jegliche Information welche Abbiegung am vielversprechendsten ist geht verloren. Ich sehe meinen Denkfehler nicht, kann das jemand mir erklären?
 
Ich weiß nicht, ob ich deine Frage verstanden habe: Tic Tac Toe ist ein sehr einfaches Beispiel, fast schon zu einfach. Bei vollkommener Kenntnis aller Züge, die für einen Computer leicht zu berechnen sind, geht das Spiel immer unentschieden aus. Erinnere dich An Wargames[1]. Der WOPR spielte gegen sich selbst Tic Tac Toe. Weil er alle Züge kannte, konnte er immer perfekt ziehen. Es gewann niemand. Alle Züge lassen sich immer klar mit "Durch diese Zug gewinne ich das Spiel", "Durch diesen Zug erreiche ich ein Unentschieden" und "Durch diesen Zug verliere ich das Spiel" bewerten. Alle Nodes haben also entweder 1, 0 und -1 zugeordnet. Wenn jeder Spieler auf Sieg spielt, wirst du aus deiner Sicht immer 1 wählen und der Gegner -1. Das hebt sich auf, folglich ist der Gesamtscore 0. Unentschieden.

Um Minimax wirklich zu verstehen (und auch, wieso man heute abgeleitet Algorithmen verwendet), musst du ein komplexeres Spiel nehmen. Dort hat der Computer nur eine beschränkte Sicht, die Bewertungen sind zudem nicht zwingend 1, 0 oder -1. Das führt zu krummen Werten, die sich nicht mehr aufheben. Ein gutes Beispiel ist Dame, zumindest solange man ignoriert, dass es vor einigen Jahren gelöst wurde.

1: http://de.wikipedia.org/wiki/WarGames_–_Kriegsspiele
 
Das ist mir schon klar, in meinen Überlegungen war die Denke, dass das auch wertmäßig Ausdruck gewinnt. In TTT vielleicht nicht aber in anderen Spielen hat der Führende einen Vorteil den er mit optimalen Spiel nicht wieder hergibt, Beispiel 4gewinnt.
 
Back
Top