MiniMax Algorithmus

[Peter_Mueller]

Hallo,

kennt jemand den einfachen Minimax ( also nicht die ganzen Optimierungen wie alpha beta pruning etc. ).

Ich verzweifel gerade an der Implementierung.

Was ich z.b. gar nicht versteh. Sagen wir man setzt die maximale Tiefe auf 2. Man blickt also nur 2 Züge in die Zukunft. Sagen wir der Computer ist nun dran und sucht nun seinen besten Zug. Danach kommt der Player und sagen wir der würde jetzt gewinnen. Aus Sicht des Computers wäre der gewinner Zug des Players der schlechteste Zug, aber genau diesen sollte der Computer aber wählen, stattdessen würde er aber die Spalte nehmen die für ihn das optimum bringt. z.B. weil er dann 3 gleiche Steine neben einander hätte. Stattdessen verliert er aber da der Player dann gewinnt. Hab ich jetzt nen Denkfehler oder hat der Minimax einen Fehler.

..................Max..............-8
.............Min.......-10................. -8
..........Max...-10........-5.........-8........-7

seht ihr , -10 bedeutet der Player gewinnt und wie ihr seht wählt der computer die falsche spalte....

[dfsfdsfsdfdfs]

du rechnest dir bis zur gewünschten Tiefe die Spielzüge durch.
Die unterste Ebene des Baums, die Blätter, werden dann bewertet. Behaupten wir mal, so eine Bewertung wäre einfach möglich.

Ab dann arbeitest du dich nun von unten nach oben - in jedem Schritt nach oben wählst du den besten Spielzug für den Spieler, der gerade dran ist.
Was für den einen Spieler gut ist, ist für den anderen schlecht. Falls bereits errechenbar ist, dass der Gegner in einem Teilbaum gewinnt, so ist das natürlich für uns ein extrem schlechter Zug den wir natürlich keinesfalls nehmen, stattdessen nehmen wir einen Spielzug, der uns in einen Teilbaum führt, wo der Gegner (selbst mit dem bestmöglichen Spielzug!) nicht gewinnen kann (zumindest nicht im berechneten Zeithorizont).

Programmier es einfach mal für Tic Tac Toe runter, du wirst sehen, das ist in der Basisvariante recht einfach. Und du wirst sehen dass Tic Tac Toe ein ziemlich fades Spiel ist, da eine bestimmte Reihenfolge der Züge immer dazu führt, dass man nicht verlieren kann.