Hi @all

Ich muss in der Schule in einen Projekt 4Gewinnt in c++ schreiben (Nur Konsole).
Das Grundgerüst habe ich schon gemacht und einen "dummen" Computergegner habe ich bereits implementiert. (Dumm weil er seine Spielzüge random setzt).
Nun möchte ich einen guten bis sehr guten Computerspieler noch einbauen nur leider habe ich noch keine Ahnung wie ich den realisieren soll.

Im Netz habe ich verschiedene Algorithmen gefunden (MiniMax, NegaMax usw.)
Nur leider sind die verstehe ich nicht wie die funktionieren oder wie ich die fehlerlos in mein eigenes Programm/Spiel einbauen kann.

Zum Spiel selbst: Ich habe das Spielfeld durch ein Zweidimensionales Array realisiert und die Eingabe der gewünschten Position des eigenen Spielsteines habe ich "noch" mit der einfachen Eingabe der Reihe.


Nun kommt ihr ins Spiel
Weiß jemand wo ich noch eine gut Dokumentierte Anleitung für einen solchen Algorithmus finde oder hat vllt jemand schon selber ein 4Gewinnt in c++ geschrieben?


Ich möchte bewusst keine fertige Lösungen von euch da ich es ja selber (^^) machen muss und dabei noch etwas lernen möchte. Über ein paar Tipps und Tricks von euch würde ich mich aber sehr freuen und ihr würdet mir echt helfen.


Hoffe ihr könnt mir helfen

MfG cyrus



(Ich war mal so frei und habe das Programm hochgeladen)

http://phoenixpiraterie.ph.funpic.de/4Gewinnt.zip


Quelltext gibt es nur auf Anfrage


Edit: Die Auswertung des Gewinners programmiere ich zum Schluss ein.
Edit: Zusätzlich habe ich einen kleinen Debug Mode für euch eingebaut, wo man dann genau sehen kann wo welches Element des Array dargestellt wird.

Ich habe zwar noch kein 4 Gewinnt gecoded, aber ein TicTacToe in Lua..

Es war ohne KI sondern für 2 Spieler, aber ich habe das mit nem Freund sehr lange gezockt und taktiken entwickelt..

die musst du bei 4 Gewinnt auch finden, und natürlich jedesmal prüfen ob der gegenspieler beim nächsten Zug gewinnen könnte..

[21:36:11] Paul (xecon) : du würdest dein leben für evo geben oder? :D

Ein TicTacToe haben ich in C++ bereits auch gecodet.
Da war es ja auch noch kein großes Problem da es nur 9 Felder gibt.
Und eine Siegstrategie für einen Computergegner war da noch "fast" problemlos einzucoden. (Auch in der Schule und die SiegTechnik "manuell (also ohne Schleifen)" einprogrammiert)

Aber bei 4 Gewinnt ist das Spielfeld nicht 3x3 sondern 6x7 und währe exponentiell schwerer. Außerdem habe ich die Auflage bekommen es mit Schleifen zu lösen und dass der Computer mit einer minimalen Suchtiefe von 2 Zügen suchen soll was man mit dem Algorithem die ich im ersten Post "angeblich" problemlos realisieren kann.
Nur leider finde ich keine gute Anleitung (mit Code Beispielen) wie diese Algorithem funktionieren.

Wie bereits im ersten Post erwähnt möchte ich keine fertige Lösungen

Du musst ja nicht alle Felder prüfen, sondern nur die bei denen jeweils die oberste und unterste Kugel von dir und deinem Gegner ist. Das wäre: (2 (4)) + (2 (4)) = 16
Kann sein das es nicht stimmt, aber hab jetzt im Kopf gedacht, aber irgendwie so sollte es sein.

Mein erster Ansatz wäre, zu schauen bei welchem Feld am Ende die meisten Steine in einer Reihe sind.
Das ganze Feld analysieren musst du ja sowieso. Und dann implementierst du den Algorithmus ungefähr so, wie den für die Gewinnüberprüfung. Dort musst du ja auch jedes mal prüfen, wie viele Steine jeweils hintereinander in welcher Reihe, Spalte und den beiden Diagonalen liegen.

Sobald der Bot dran ist, führst du diese Überprüfung einfach vor dem Zug durch und schaust bei welchem "Loch" am Ende die meisten Steine in einer "Folge" liegen. Dazu solltest du ein verschachteltes Array nehmen (denke ich, bin kein C++ Kenner) und für jede mögliche Stelle (als einen Wert in diesem Array) speichern, wie viele Steine hintereinander liegen würden, wenn dort ein Stein gesetzt würde.
Dieser sollte allerdings nochmal in einem Array stehen, da ja jede frei Stelle ("jedes Loch") in mehreren "Folgen" liegen kann.

Dann musst du halt nur ermitteln, welcher Stein in den meisten Folgen liegt bzw. wie viele Steine dann letztendlich in diesen Folgen liegen.

Du kannst das ganze nur in Schleifen realisieren. Im Prinzip musst du wie gesagt nochmal einen ziemlich ähnlichen Algorithmus schreiben, wie den bei der Gewinnüberprüfung. Nur musst du JEDE Folge von Steinen (des Bots) suchen und das ganze dann Auswerten, so das du die Stelle mit dem größten Nutzen herausfindest.

So ähnlich habe ich auch schon überlegt...

Muss ich mal gucken ob ich das gebacken bekomme. Zum Glück habe ich über 2 Monate damit zeit und nicht wie andere die in der letztes Woche erst anzufangen zu programmieren.

Wenn ich wieder Hilfe benötige meld ich mich wieder.

Ihr könnt trotzdem noch Problemlösungen Posten ^^