KI für Mühle-Spiel

[Simonek]

Ich habe ein Mühle-2D Spiel in C geschrieben (um mein Wissen zu vertiefen).

Man soll als Spieler gegen den Computer spielen.

Die Felder sind in einem einfachen Array
f[24] abgespeichert, wo Informationen enthalten sind was sich auf den Feldern befindet.

Für die (noch nicht vorhandene) KI habe ich drei Funktionen:
- cpu_setzen: Computer setzt einen Stein auf das Feld (am Anfang)
- cpu_ziehen: Computer macht einen Zug
- take_stein_cpu: Computer nimmt einen Stein vom Spieler bei Mühle

Momentan sieht das noch so aus:
- Alle möglichen Züge werden aufgelistet und die Anzahl wird gespeichert.
- Aus den vorhandenen Zügen wird ein zufälliger Zug ausgewählt und ausgeführt.

Das ist natürlich sehr unbefriedigend und ich möchte eine richtige KI erstellen.
Meine Überledung war bisher:
- Jedem möglichen Zug eine Prirität (z.B. von 1 - 100) zuweisen.
Der Zug mit der höchsten Priorität wird ausgeführt.

Züge, die z.B. eine Mühle bringen bekommen Priotiät 100
Züge, die z.B. eine Mühle des Gegners verhindern bekommen Priorität 90
Züge, die z.B. eine Mühle für den nächsten Zug vorbereiten bekommen Priorität 80
u.s.w.

Bevor ich mich da jetzt jedoch blindlinks reinsteiger möchte ich wissen, ob es einen besseren Ansatz dafür gibt, da mir meiner zu linear und berechenbar erscheint.

Ich möchte vor allem die Stärke des Computers (Rechengeschwindigkeit) ausnutzen, dass er viele folgende Spielzüge berechnet und auch Möglichkeiten des Gegenspielers berücksichtigt.

Das ganze möchte ich in C realisieren wenn das möglich ist.

[das_brot]

Hi,

dein Ansatz mit der Priorisierung ist für ein solches Spiel (laut Wiki ein "Spiel mit perfekter Information" :)) gut geeignet.
Ein Algorithmus, der die Power deiner CPU nutzt und mit der Priorisierung vereinbart, ist der Minimax-Algo -> http://de.wikipedia.org/wiki/Minimax-Algorithmus.
Das einzige, wo du dir etwas zurechtlegen musst (kann man sicher auch vom Netz runterladen aber wo bleibt da der Lerneffekt^^), sind die Kriterien zur "Beurteilung" eines Spielfelds inkl. gesetzter Steine.

Have Fun!

[Simonek]

Kennst Du auch eine Beispielimplementierung für C?
Aus dem Pseudocode auf Widipedia werde ich nicht schlau.

Ich denke ich programmier mir erstmal ein VierGewinnt, da es bei 7 möglichen Spielzügen sicherlich einfacher ist um das Prinzip zu lernen.

[Mecnels]

Mühle ist wesentlich komplexer als 4gewinnt? In beiden Fällen wird ein guter KI immer ein Hauptspeicherfresser sein! (13 Halbzüge Tiefe beim Schach und auch ein 1 GB RAM ist voll mit Hash Tables_zumindest mit dem allmächtigen Fritz!)

Es läuft eigentlich bei dieser Sorte Spiel (Computer und Spieler ziehen abwechselnd, beispielsweise Mühle, Schach oder 4Gewinnt) nach dem Prinzip Versuch&Irrtum, d.h. alle möglichen eigenen Züge in einem Array aus möglichen resultierenden Spielfeldzuständen zu speichern. Anschließend müssen für jeden dieser möglichen Spielfeldzustände ziemlich viele weitere (mögliche! nicht zwingend eintretende!) Spielfeldzustände berechnet werden, indem man alle diese Spielfeldzustände erneut in einem Array speichert. Irgendwann muss man den Schlussstrich setzen und beispielsweise bei einer Zugtiefe 7 Halbzüge das Programm eine 'Bewertung' der Stellung SPEICHERN lassen.
Taktische bzw. strategische Brettspiele gehören zu den schwierigsten Programmieraufgaben IMO! Und falls der Computer gute oder godlike Züge machen soll, sind sie auch immer extrem speicherhungrig! Mehr als Versuch&Irrtum Methode ist nämlich nicht möglich für das Spatzenhirn des Computers!

[Jester]

naja, mit pruning-techniken kann man bestimmte zweige recht schnell abschneiden und so tiefer suchen.

[obbba]

Bei 4 gewinnt hatte ich das so gemacht:

1. Wenn du gewinnst, war der Zug gut.
2. Wenn der Gegner danach einen guten Zug machen kann ist der zug schlecht.
3. Wenn alle Antworten des Gegners schlecht sind, ist der Zug gut.
4. Sonst ist der Zug neutral/egal.

Das ist glaube ich so ähnlich wie der Minimax-Algorithmus.

[Simonek]

Ich denke die mittleren Felder sind generell besser, weil es dort mehr Kombinationsmöglichkeiten gibt.

Wenn das mit Mühe wirklich so schwer ist programmiere ich mir erstmal ein VierGewinnt und übe dort mit der KI.