4 Gewinnt KI - MinMax-Algorithmus

[Accelerator]

Hallo zusammen.
Ich bin neu hier, und habe mich gemäß der hier herrschenden Konventionen in einem anderen Thread bereits vorgestellt.
Ich habe mir schon seit einer Weile Gedanken darüber gemacht, ob ich mich in diesem Forum anmelden soll, und habe mich primär aufgrund einer aktuellen Problematik endgültig dazu entschieden.

Es geht um folgendes: Ich sollte ein auf der Konsole basierendes 4-Gewinnt programmieren - die meisten Funktionen stellten hierbei kein großes Problem dar.
Allerdings habe ich gewisse Schwierigkeiten beim programmieren der KI - sie ist mir zu schwach. Auf der Suche nach einer geeigneten Formel bin ich auf den MinMax-Algorithmus gestoßen, und bin davon ziemlich begeistert, wenngleich er mir doch sehr komplex erscheint.
Ich habe das gesamte Internet nach Code-Beispielen abgesucht, welche (aus meiner Sicht) verständlich kommentiert sind - Fehlanzeige. Ich weiß schlichtweg nicht, wo ich mit dem implementieren anfangen sollte ...
Meine Frage ist nun:
Gibt es hier Leute, die sich mit diesem Algorithmus auskennen, und auch schon mit dessen Hilfe eine AI für ein Strategie-Spiel programmiert haben?
Wenn ja: Kann mir das jemand verständlich erklären? Mir vielleicht einige Code-Beispiele zeigen, und diese möglichst akribisch beschreiben? Ich wäre hierfür sehr dankbar. Melden könnt ihr euch auch gerne über die PN-Funktion.

Accelerator

 

[~ihja]

Hallo!

Wie der Zufall es will, habe ich ihn gestern noch (erfolgreich) implementiert, also als Aufgabe. Weiß natürlich nicht in wie fern ich jetzt meine Unterlagen hier veröffentlichen darf, aber habe zumindest folgendes Dokument gefunden: http://www.igpm.rwth-aachen.de/Download/ws0102/mapra/ma6.pdf.

Im Grunde genommen geht es darum, dass du irgend eine Art von Bewertungsfunktion hast. Dann simulierst du rekursiv (Tiefensuche) Züge, wobei du jeweils die maximale Bewertung nimmst falls du am Zug bist und die minimale, wenn der Gegner dran ist, da er natürlich den aus seiner Sicht am besten Zug macht. Das Problem dabei ist natürlich, dass die Alternativen exponentiell wachsen. Meine Implementierung, die noch zwei primitive Optimierungen nutzt, schafft es in 2 Sekunden 6 Züge zu simulieren und ist damit schon sehr stark.

Das war jetzt zwar keine "akribische" Beschreibung, aber die wirst du hier wohl auch kaum bekommen. Such vielleicht noch mal genau bei Google, lies das pdf und stell vielleicht etwas konkretere Verständnis fragen.

Schönen Tag dir noch und Gruß!

 

[Accelerator]

Hallo!

Dann simulierst du rekursiv (Tiefensuche) Züge, wobei du jeweils die maximale Bewertung nimmst falls du am Zug bist und die minimale, wenn der Gegner dran ist, da er natürlich den aus seiner Sicht am besten Zug macht.

Rekursiv? Damit ist gemeint, dass er zuerst bei den untersten "Wurzeln" des Baumes anfangen soll, oder?

Such vielleicht noch mal genau bei Google, lies das pdf und stell vielleicht etwas konkretere Verständnis fragen.

Stimmt schon - ich hätte präziser fragen sollen. Also: Ich habe mir das von dir verlinkte PDF-Dokument mal durchgelesen, und kann mir zumindest schon in etwa vorstellen, wie ich das bewerkstelligen könnte. Nun drängt sich mir aber die Frage auf nach welchen Kriterien ich eine für die AI positive Stellung berechnen sollte. Gibt es hierfür irgendeine Formel? Oder muss man da auch etwa nach Intuition vorgehen?

Accelerator

 

[GrafZahl]

Rekursiv? Damit ist gemeint, dass er zuerst bei den untersten "Wurzeln" des Baumes anfangen soll, oder?

Um Rekursion zu verstehen muss man zunächst Rekursion verstehen ...

eine rekursive funktion ist eine funktion die sich selbst wieder aufruft ... wenn auch mit anderen parametern ...

das paradebeispiel für rekursion ist die berechnung der fakultäts-funktion x! ...

f(x) := x*f(x-1)

5! = 5 * 4 * 3 * 2 * 1

Nun drängt sich mir aber die Frage auf nach welchen Kriterien ich eine für die AI positive Stellung berechnen sollte. Gibt es hierfür irgendeine Formel? Oder muss man da auch etwa nach Intuition vorgehen?

relativ einfach bei vier gewinnt ... bewerte die anzahl der möglichkeiten die ein spielzug dem jeweiligen spieler bringt 4 in eine reihe zu bringen ...

sagen wir mal du hast ein leeres feld ... ganz links machst du nun deinen zug ... durch diesen zug hast du nun 3 möglichkeiten eine 4er reihe zu bilden ... nach oben ... nach oben rechts ... und nach rechts ...

diese metrik würde diesen zug mit 3 bewerten ... wirfst du den stein dagegen in die mitte, lautet das ergebnis 5 ... nach links ... nach links oben ... nach oben ... nach rechts oben ... und nach rechts ...

da 5>3 ist es gemäß dieser metrik sinnvoller den stein am anfang in die mitte zu werfen ... was ja auch den allgemeinen erfahrungen in diesem spiel entspricht ...

betrachtet man die folgezüge, wird klar, dass man die zugfolge wählen sollte bei der diese metrik für die eigene seite maximal werden kann, und gleichzeitig die gleiche metrik für den gegner minimal wird ...


vier gewinnt ist in dieser hinsicht erledigt ... es gibt genug beweisbare algorithmen die ein perfektes spiel liefern ...

 

[Accelerator]

Um Rekursion zu verstehen muss man zunächst Rekursion verstehen ...

eine rekursive funktion ist eine funktion die sich selbst wieder aufruft ... wenn auch mit anderen parametern ...

das paradebeispiel für rekursion ist die berechnung der fakultäts-funktion x! ...

f(x) := x*f(x-1)

5! = 5 * 4 * 3 * 2 * 1

Danke für deine Ausführungen, GrafZahl.
Ich habe mich nun noch etwas über dir verschiedenen Arten der Rekursion informiert, und denke, dass eine Kaskadenförmige Rekursion hierfür wohl am besten geeignet wäre. Ich versuche das heute mal Zuhause zu implementieren, sollte ich Probleme haben, melde ich mich nochmal.

Accelerator