bash.1 - Sa 29.01.05 14:43
Titel: Min-Max-Algorithmus

---

hallo an alle delphi user,

ich benötige hilfe bei meinem programm welches ich mit hilfe des min-max-algorithmus implemenieren möchte.

und zwar möchte ich das an einem beispiel wie vier gewinnt realisieren. hab schon angefangen und bin auch schon zeimlich weit, jedoch komm ich momentan nciht weiter. also wenn einer lust hat sich mit dem problem auseinanderzusetzen bzw. mir zu helfen, der sol sich doch bitte melden. dauert bestimmt ein bisschen sich da einzuarbeiten. aber es lohnt sich sicherlich auch :D

also besten dank schonma und viele grüße
jan

Gausi - Sa 29.01.05 14:53

---

Hallo und :welcome:

Woran genau hakt es denn? An welcher Stelle kommst du nicht weiter?

Die Wahrscheinlichkeit, dass man dir hilft, steigt, wenn du dein Problem etwas genauer beschreibst.

Und: Was ist der min-max-Algorithmus?

ossix - Sa 29.01.05 15:32

---

unter min-max algorithmus kenne ich nur einen sortier-slgo der durch das zu sortierende array läuft und das jeweils größte und kleinste element rausfischt. danach werden die an den anfang/ende des feldes gepackt und weiter gehts (mit eingeschränktem laufbereich natürlich ;)).

was das mit vier gewinnt zu tun hat weiss ich allerdings auch nicht :roll:

cu
ossix

UGrohne - Sa 29.01.05 15:56

---

Ich glaube, der meint damit den Minimax-Algo. Darüber hab ich am Di unter anderem eine Klausur geschrieben ;-)

Das ist ein Algo, der vor allem im Schach verwendet wird. Dabei werden die einzelnen Stellungen bewertet (hat bestimmt schon mal jmd gesehen, die Zahl von -10 bis +10). Es wird dabei in die Tiefe gerechnet. Da ja immer man selbst und dann der Gegner zieht, gibt es verschiedene Ebenen. Die erste Ebene ist die Maximierungsebene, denn man selbst will ja eine möglichst gute Stellung. Die zweite Ebene ist eine Minimierungsebene, denn der Gegner will ja das andere. So geht das weiter bis zu einer bestimmten Tiefe. In der letzten Ebene wird eine Wertung gegeben und dann hochgerechnet bis zur obersten Ebene, welche Wertung maximal bei diesem Zug in der Tiefe möglich wäre, egal, was der Gegner macht. Der Zug mit der höchsten Wertung kann dann genommen werden.

Weiter geht dann noch der Alpha-Beta-Minimax, der aufgrund der Wertungen auch ganze Teilbäume auslässt, weil diese sowieso uninteressant sind.

Ich versuch mal noch ein Bild eines solchen Baumes hochzuladen, damit man das besser sieht.
Wie man sowas in Delphi realisiert, darüber hab ich mir noch keine Gedanken gemacht, aber mit Prolog isses einfacher ;-)

//EDIT: Hab jetzt mal ein Bild hochgeladen, der Baum ist aber von Alpha-Beta-Minimax (was man an den durchgestrichenen Zweigen sieht: Hier klicken [http://aptus.grohne.de/files/minimax.jpg]

bash.1 - So 30.01.05 15:18

---

jo genau das mein ich so ungefähr, aber der heißt minmax-algorithmus und nich minimax :D aber gut darüber lässt sich streiten.. naja und in delphi realisiert hab sich auch eigentlich..hab dafür verschiedene klassen verwendet, damit ich den algorithmus später auch für andere spiele verwenden kann, soll ja ers der anfang sein ;) also hab alles abstrakt geschrieben, naja und jetzt die klassen zu verknüpfen ist schwieriger als ich dachte, außerdem weiß ich net o ich alles richtig gemacht hab und bis jetzt geht auch nur spieler gegen spieler, (hrhr) ich will ja gegen ne computer spielen, also muss ich meine gameclss auch noch zur anwendung bringe... naja, das is mein problem.. aber schonam danke für eure antworten... ^^

liebe grüße jan

edit: das bild is krass, n bisschen verwirrend für die, die den algo noch nich kennen :D

UGrohne - So 30.01.05 17:58

---

Also wenn Du schon so viel hast, dann veröffentliche doch mal ein bisschen Code (würd mich nämlich auch interessieren *g*) und sag, wo es genau hakt. Dann können wir Dir auch helfen.

Das Bild ist aus einem Foliensatz raus, ich hab nur die letzte Folie genommen, damit man alles auf einmal sieht ;-)

P.S.: Selbst bei Wikipedia steht er unter Minimax drin: http://de.wikipedia.org/wiki/Minimax-Algorithmus

bash.1 - Di 01.02.05 16:21

---

aaaaahhh... habs geschafft. hab den fehler gefunden und nach einer langen nachtschicht und einer komplett neuen unit (sehr umständlich, aber auch sehr übersichtlich :) ) hab ich das programm zum laufen gebracht.
der fehler lag in der anwendung also nich am algorithmus selber...trotzdem vielen dank.

achja mit dem veröffentlichen wird schierig, wenn dann müsste ich dir das ganze programm geben. ma schauen kann mir hier beim forum was hochladen??

UGrohne - Di 01.02.05 16:32

---

bash.1 hat folgendes geschrieben:

achja mit dem veröffentlichen wird schierig, wenn dann müsste ich dir das ganze programm geben. ma schauen kann mir hier beim forum was hochladen??

Ähm, abwarten. Aber wäre sehr nett, wenn Du das veröffentlichen würdest, denn ich glaube, da sind auch einige andere scharf drauf ;-).

Evtl. kann Dein Algorithmus dann ja auch noch verbessert werden ;_)

bash.1 - Di 01.02.05 16:36

---

klar kann ich machen.. steckt auch ne menge arbeit drin und war an manchen stellen nich grad einfach ^^

@verbessern:

der algorithmus ist auch nur für einfach strategiespiele geeignet,so zum einstieg für mich, da ich bald ein schachprogramm realisieren wollte, und es da sicherlich komplizierter wird.


achja gewonnen hab ich auch noch nich gegen den computer :(

UGrohne - Di 01.02.05 16:48

---

bash.1 hat folgendes geschrieben:

achja gewonnen hab ich auch noch nich gegen den computer :(

Lass Dir nen Baum mit mehr Ebenen einfach ausgeben, so als Unterstützung. Dann dürfte das auch leichter fallen *g*.

Delete - Di 01.02.05 17:10

---

Lad den ganzen Krempel doch einfach auf deine Homepage hoch.