Zitat von
alzaimar:
Minimax ist nichts anderes als eine rekursive Suche nach dem besten Zug. Der Suchbaum wächst exponentiell mit jedem Halbzug, was natürlich etwas blöd ist. Hier greift dann noch das sog. 'Alpha-Beta-Pruning' (sollte im Wiki zu finden sein). Das schnippelt (engl: to prune: Baum beschneiden) nun den Suchbaum so, das anstatt der x^n Knoten (x=Mögliche Züge, n=Suchtiefe) nur noch log (x^n) übrig bleiben. Also kann man wesentlich tiefer blicken.
Die Minimax/Alpha-Beta-Strategie arbeitet besser, wenn die zu analysierenden Züge so sortiert werden, das vermutliche 'Killerzüge' zuerst ausgeführt werden. Denn dann ist die Wahrscheinlichkeit größer, die restlichen Züge nicht mehr auswerten zu müssen, da diese nie besser werden können. Sie zu implementieren, ist eine Sache von ca. 5 Zeilen, wenn man schon die rekursive Suche hat.
Um eine rekursive Suchstrategie zu implementieren, benötigst Du dann noch eine Stellungsfunktion. Dazu kann man z.B. die Anzahl der offenen 2er,3er oder sonstwelche Muster nehmen, und diese Anzahlen mit Konstanten multiplizieren, um so zu einer Zahl zu kommen, die umso höher ist, je besser die Stellung aus Sicht des Computers ist: Eine Stellung, in der der Mensch gut dasteht, ist hingegen <0.
F(Stellung) = C1*Anzahl(2er) + C2*Anzahl(3er) + C3*Anzahl(4er mit einem offenen Ende)....
Diese Konstanten zu finden ist das eigentlich Schwierige: Vielleicht ist die Multiplikation hier auch blöd, denn wer 2 offene 3er hat, ist nicht etwa doppelt so gut, sondern hat schlicht und ergreifend *gewonnen*.
Um den besten Zug zu finden, muss ich den nehmen,
der meine Stellung maximiert. (Suchtiefe = 0)
Oder den, auf den Du die schlechteste Antwort hast. (Suchtiefe = 1)
Oder den, auf den dein bester Zug mich wieder am Besten dastehen lässt. (Suchtiefe = 2)
....
Nur so, als Denkanstoß: Die Konstanten, mit denen Du deine Stellungseigenschaften multiplizierst, können als 'Genome' angesehen werden. Du kannst nun zwei Programmversionen gegeneinander spielen lassen, wobei eine Version eben zufällig andere Konstanten verwendet (Mutation). Der Gewinner überlebt ('Survival of the fittest') ist dann sozusagen der Vatta (oda die Mutta) für weitere Generationen, die eine andere Konstante verändern. So verbessert sich dein Programm.
Ja, ja, die 'Nullsummenspiele mit vollständiger Information', die sind schon was :mrgreen:
[edit] Alpha-Beta-Strategie wieder aus dem Hirnbackup gezogen[/edit]
Der begriff der "Minimax"-Therorie ist mir neu, ich werde mich bei
nächster Gelegenheit in dieses Thema mal einlesen...
Ich glaube aber das Prinzip das du vorgeschlagen hast, ist das gleiche
an dem ich zur Zeit arbeite und das ich mit "Strategie" beschrieben
habe. Und zwar habe ich vor dass der Computer die "möglichen Züge"
speichert (anstatt sie auszuführen) und anschliessend die, deren
*gedachte* 5er-linie sich überschneidet mit einem höhren faktor
zu bewerten. Schon jetzt werden die Züge die weiter Innen liegen mit
einem Faktor aufgewertet (dadurch erreiche ich dass sich der Computer immer auf das Zentrum konzentriert da es hier mehr Möglichkeiten zu "Zwickmühlen" gibt -> die Linien überschneiden sich schon fast zwangsläufig). Diese zwei faktoren bestimmen dann welche
wertigkeit ein zug hat, der beste zug wird ausgeführt.
Dabei werden die Züge die zu einem offenen 3er oder einem offenen 4er oder gar zu einem 5er (direkter Gewinn) führen natürlich höher bewertet. Also im Prinzip das gleiche was du vorschlägst - oder?