Der MiniMax-Algorithmus ist eine künstliche Intelligenz, die in der Simulation von Brettspielen oder ähnlichem sehr viel Verwendung findet. Das Arbeitsprinzip des Algorithmus sieht folgendermaßen aus:
Von einer Ausgangsposition simuliert der Computer abwechselnd eigene und gegnerische Züge (alle, die es gibt) bis zu einer bestimmten Tiefe, bei der er dann die Stellung bewertet. Diese Bewertung sieht so aus, dass eine günstige Stellung für ihn einen positiven (großen) Wert erhält, eine günstige Stellung für den Gegner erhält einen negativen (niedrigen) Wert.
Hierdurch entsteht nun ein Spielbaum. Ganz oben befindet sich die Ausgangsposition. Von dieser zweigen ab alle Stellungen, die der Computer durch einen Zug erreichen kann. Von jenen Stellungen wiederum zweigen jeweils wieder alle Stellungen ab, die durch einen erneuten Zug des Spielers (der Computer simuliert ja diesen gegnerischen Zug) erreicht werden können. Etc. etc. bis irgendwann Schluss ist, und der Baum entweder eine vorgeschriebene Tiefe erreicht hat oder - wie in diesem Beispiel - ein Endzustand (Sieg, Niederlage oder Brett ist voll) erreicht ist.
Nun versucht der Rechner einen Weg zurückzuverfolgen, auf dem er auf eine für ihn möglichst günstige Stellung auf der letzten Eben des Baumes gelangt. Zu diesem Zweck sucht er sich aus allen Stellungswerten, die er durch einen eigenen Zug erreichen kann, das Maximum heraus und gibt dieses weiter an den Elternknoten. Aus allen Stellungswerten, die durch einen simulierten gegnerischen Zug entstanden sind, wählt er denjenigen, der am kleinsten ist. Der Computer geht nämlich davon aus, dass der Spieler den seinerseits besten Zug nimmt und dadurch die schlechteste Stellung für den PC erreicht.
Durch dieses Weitergeben von abwechselnd maximierten und minimierten Knoten erhält der Computer nun für jede ihm zur Verfügung stehende Auswahl einen bestimmten Wert, der ihm angibt, welche der Auswahl er am günstigsten treffen sollte.
Dies hört sich wahrscheinlich alles sehr schwer verständlich an, ist es aber wirklich nicht. Am besten einfach mal in Google "MiniMax" eintippen oder ähnliches. Unter den Suchergebnissen wird man sicher viele lustige Bildchen mit beschriebenen Spielbäumen finden. Visuell dargestellt lässt sich das ganze dann sehr viel einfacher begreifen =)
History
09.07.2003 Hinzugefügt
Autor: Benjamin Schröder <immoertael_auf_gmx.de>
