minimax-algorithmus (inspired by 4gewinnt)

[theWEBster]

hallo alle zusammen,
hab mich gestern nacht von 1.00 - 3.00 mal durch den "4gewinnt"-thread gearbeitet und ich war begeistert!!!

daher erst mal ein dickes kompliment an die meute die mitgemacht hat. wie man sich denken kann, bin ich jetzt natürlich auch heiss gelaufen mal ne kleine ki zu erstellen. allerdings hab ich ein kleines problem:
der thread liest sich hoch interessant, allerdings hab ich ab den seiten 18-20 (oder so) ein wenig den durchblick verloren und mich nur noch gefragt wo die burschen von seite 1 bis zum ende des threads ihr wissen herbekommen haben. smalltalk über z.b. den minimax-algorithmus, gehören normalerweise ja nicht zum all-tag

naja, lange rede kurzer sinn:
hab mir schon einiges zum minimax durchgelesen, das waren allerdings meistens folien die irgendein prof während einer vorlesung an die wand schmeisst. soll heissen, ne menge doller bilder und kurzer extrem gebündelter infos mit denen ich leider nicht klar komme.

hat irgendwer aus dem 4gewinnt-thread, da draussen ein paar gute links oder buchtips? würd mich freuen.
ach ja, ist das richtig das der alpha-beta algo. eine weiterentwicklung des minimax ist? wenn ja, sollte ich mir den lieber angucken?
habt ihr da vielleicht auch ein paar infos (links usw)?

jaja, websta quaselt wieder wie ein doofer.
also: schluss mit diesem text.

man, war das ne nacht, bin völlig im 4gewinnt-fieber, kann daher aber leider auch nur noch bis 4 zählen, help i need minimax

ach eins noch:
einen wettbewerb in der art von 4gewinnt, würd ich auch gern mal mit machen! ist echt ne klasse sache!!!

ach ja, schade das zum schluss des 4g-wettbewerbs nicht mehr so ausführlich auf die lösungsansätze der einzelnen teilnehmer eingegangen wurde, hätte mich interessiert.

jetzt aber schluss.
ciao & danke schon mal für die hilfe

websta

[emax]

hi webster,

ich guck mal ob ich die links die mir geholfen haben noch finde
und poste die dann hier heute abend.

minimax ist die langsamste stellungssuche. es gibt
noch 2 oder 3 andere methoden die um einiges schneller sind,
wie z.b. negamax, aber auch entsprechend verwirrender. eben
wie alles was rekursiv arbeitet.
der alpha-beta cutoff ist nur ein enhancement für alle diese
algorythmen, das eine suche stark verkürzt.

vorab ein paar flashforum links zu diesem thema
rekursive Programmierung//erste Übungen
Array Prototype min / max Werte finden

[theWEBster]

hi emax,
wenn du die links noch posten könntest, wäre das echt ne sehr schöne sache

die anderen beiden links kannte ich bereits, trotzdem danke.


auf bald
keep flashin'
websta

[emax]

mist, hab seit einigen wochen ein neues system und habe
damals vergessen meine bookmarks zu sichern

aber als gute google stichwörter haben sich "connect4" und
"velena" erwiesen.

velena ist eine perfekt spielende 4gewinnt KI von der man viel
lernen kann.
eine ausführliche doku zu velena ist auch veröffentlicht. dort
werden die heuristiken sehr gut erklärt.
"A Knowledge-Based Approach of Connect-Four (M.Sc. Thesis)"
nennt sich die ofiziell.

gute beschreibungen speziell über minimax und alphabeta gibbet
bei google ohne ende ..sogar in deutsch.

hoffe dir wenigstens ein bißchen weitergeholfen zu haben und
bin schon gespannt wie sich deine KI gegen unsere schlägt

[Janoscharlipp]

ich hab mal das pdf gesucht, das hinter meiner KI steht. Es ist auch eine Unterrichtsvorlage, allerdings sehr ausführlich.
Das pdf erklärt das alpha-beta-mini-max Verfahren.

spieltheorie.pdf (ca. 1,4mb)

ich hoffe es hilft

Gruß

Janosch

[theWEBster]

so,
da bin ich wieder, war ein wenig im stress und konnte daher die letzten tage nicht reinschauen.

@emax: schade das du die links über board geworfen hast, trotzdem danke für hilfe! hab mal ein wenig gegoogelt, auch einiges gefunden, allerdings nix wo ich sofort durchgeblickt hab , waren auch alles englische texte, da fällt es mir erfahrungsgemäss immer entwas schwerer mich in ein neues thema einzuarbeiten.

@janosch: danke danke, der link ist echt sehr hilfreich! konnte heute nicht pennen und hab von 5.00 - 7.00 (!!!) die unterlagen mal durchgearbeitet.
immerhin verstehe ich jetzt bei den schlagwörtern minimax, suchtiefe, alpha beta algorithmus und co nicht nur bahnhof, sondern ich könnte sie sogar erklären denke ich

wenn ich das richtig verstanden habe, muß ich jetzt den alpha-beta-algo programmieren und bei der feldbewertung muss ich bestimmte heuristiken ausarbeiten. also, z.b. suche nach 3er-reihen, 4-er-reihen und zwickmühlen. korrekt?

ihr habt ja eine zeit lang gebraucht bis ihr eure ki's fertig hattet, da kommt wohl noch einiges an arbeit auf mich zu naja, so lange es spass macht

so, das war es dann erst mal wieder. wer noch tips, links und ähnliches für mich hat: immer her damit.

bis denne dann
keep flashin
websta

[Janoscharlipp]

richtig erfasst.
Mein Hauptproblem war es, eine schnelle und vorallem gute Stellungsbewertung zu bauen; es ist mir leider nie gelungen; aber du solltest dir mal die von Gnut ansehen, die ist wahnsinnig schnell, und "nebenbei" auch noch sehr gut.

[Gnut]

wer ist bereit für die zweite runde? *hehe*
ich denke es gibt noch mehr techniken dazu, habe aber leider nie richtig lust noch eins alleine zu basteln... es sei denn wir machen noch nen wettbewerb, von mir aus auch ohne gewinnpreis


Gruß,

Gnut

[Janoscharlipp]

hmm, bei mir stehen erstmal ziemlich viele Arbeiten an, aber bald sind Ferien, und dann bin ich für ne 2. Runde bereit
Muss wegen mir auch nicht so offiziell sein, die Engine von Bokel war ja nahezu perfekt.

[Gnut]

Ja, von mir aus koennen wir die auch gern weiter benutzen.

[Gnut]

Geschrieben von Janoscharlipp
Mein Hauptproblem war es, eine schnelle und vorallem gute Stellungsbewertung zu bauen; es ist mir leider nie gelungen; aber du solltest dir mal die von Gnut ansehen, die ist wahnsinnig schnell, und "nebenbei" auch noch sehr gut.

Ich würde Neueinsteiger empfehlen mit Minimax und AB auseinanderzusetzen, denn wie ich gemerkt habe ist mein Code wirklich schwer für einen anderen zu erlernen, das ist eher ein persönlicher Programmierstil. Ich werde deswegen AB und MM in der nächsten KI verwenden.

[theWEBster]

hello again,
neuer wettbewerb. ja, ich will ja sowieso ne ki basteln, von daher hab ich da bestimmt nix gegen

hmm, bei mir stehen erstmal ziemlich viele Arbeiten an, aber bald sind Ferien, und dann bin ich für ne 2. Runde bereit
Muss wegen mir auch nicht so offiziell sein, die Engine von Bokel war ja nahezu perfekt.

konnt man sich den final source-code von bokel (oder jemand anderem) irgendwo saugen?
es hieß ja zu beginn des letzten kontests, das es so etwas wie ne nachbesprechung geben soll, wo die einzelnen techniken mal näher verglichen werden sollten. das fand aber nie so richtig statt, oder?

auf in den kampf
websta

[Janoscharlipp]

naja, ich glaube, nachdem das Tunier vorbei war hatte keiner mehr so Lust sich weiter damit zu beschäftigen.

Bokel hat doch garkeine KI geschrieben??? Oder meinst du die Organisations-Engine (oder wie auch immer)?

die Fla meiner KI müsste irgendwo in dem riesen Thread noch als Anhang rumfliegen, wenn nicht kann ich sie nochmal raussuchen.

[Gnut]

@Janosch: Ich würde gern ein 2.es Tunier machen, damit wir mit den allg. Techniken soweit durch sind und irgendwann mit Schach in Flash anfangen können
Sollte ich eine Schach-Engine in Flash machen, würde ich schon mal den Namen "Chash" (aus Chess und Flash) vorbestellen.

[emax]

@websta

ich kann dir meine ki gerne mailen. ich möchte sie nur nicht ins
forum stellen weil sie nicht sehr ästhetisch ist.