Born-to-Frag - Mi 24.05.06 19:54
Titel: Vier gewinnt KI

---

Hallo!

Ich wollte mich mal an der Erstellung einer KI für mein Vier gewinnt versuchen, weiß aber nicht richtig wo ich anfangen soll :?!?:

Ich hab mal ein Beispiel für TicTacToe gesehn, war schon ziemlich kompliziert :(
Ich weiß auch nicht genau wie ich anfangen soll.

Hab mir überlegt z.B. erst 'offene' 3er Steine vom Gegner zu suchen, dann 2er Reihen die auf 2 Gegenüberliegenden Seiten offen sind und sonst eine Reihe von sich selbst weiter auszubauen.
Ist die Überlegung gut oder geht es anders besser?


greetz

Arno Nym - Mi 24.05.06 23:48

---

Hi,
ich würde wie folgt vorgehen:
Grundidee ist das jeder möglicher Zug mit Punkten bewertet wird.
Du gehst deine 7 (oder weniger) Reihen durch in die der Stein fallen kann.
ergibt sich daraus z.B. Zweier, merkst du dir 2 punkte oder so, bei x-Zweiern x mal 2 Punkte.
ergibt sich ein oder mehrere Dreier dann vergibtst du vielleicht x mal 5 Punkte oder so. Die Gewichtung ist dann noch zu erproben. Sollte sich ein Vierer ergeben wird abgebrochen (oder geb dann einfach 1000 Punkte und nehm das als Abbruchbedingung).
Da dein Spielfeld ja sicher als array[0..6,0..6] oder so gespeichert wird, kannst du dir die jeweils neue Spielposition in einem temporären Array merken.
Das heißt für die max.7 möglichen Positionen ergeben sich 7 neue Spielsituationen, also Spielfelder.
Nun gibst du diese neuen Spielfelder in die gleiche Bewertungsroutine ein. Und da der Gegner, also nicht die KI jetzt dran wäre, ziehst du von den gemerkten Punkten für die 7 situationen nun die Punkte ab (kriegt der Gegner nen Vierer musst du z.b. -1000 Punkte setzten). Das ganze läuft dann, am besten reukursiv weiter, bis alle Möglichkeiten durchgerechnet sind. Bei so kleinen Spielfeldern, ist das kein Problem. Wenn die KI perfekt sein soll, nimmst du am ende den Zug von den 7 der die meisten Punkte bringt.
Sollte der Mensch den gleichen idealen Algorithmus anwenden, ist dieses Verfahren optimal.
Hoffe es war einigermaßen verständlich.
MFG Arno Nym

alzaimar - Do 25.05.06 09:10

---

Damit so ein Programm richtig gut spielt, muss man die Strategie von Arno aber noch mit dem Minimax-Algorithmus verknüpfen.
Dabei wird dann nicht der Zug bwertet, sondern am Ende des Suchbaumes die Stellung. Auf diese Weise wird vom Algorithmus genau der Zug ausgewählt, der nach einber bestimmten Zugtiefe zur insgesamt beste Stellung führt ('Vorausberechnen').