Vier Gewinnt und die KI ?
-
Hallo, ich habe das Spiel Vier Gewinnt für zwei Spieler entwickelt, nun würde ich gerne dies erweitern mit einem Computer Gegner. Wie geht man hier vor, wenn nun einen Zug mache muss die KI immer alle Möglichkeiten berechnen oder?
-
Ja, das ist eine Möglichkeit. Theoretisch kann man damit eine perfekte KI bauen. Praktisch leider nicht, da der Rechenaufwand zu groß ist. Um das zu umgehen macht man normalerweise eine Suche bis zu einer bestimten Suchtiefe. Außerdem überlegt man sich eine Funktion, die in irgendeiner Weise eine gegebene Stellung bewertet. Dadurch kann man die gefundenen Stellungen bewerten, ohne das Spiel bis zum Ende rechnen zu müssen. Hier noch ein passender Link: http://de.wikipedia.org/wiki/Minimax-Algorithmus
Außerdem kann man sie benutzen um die Suche zu steuern, so dass interessante Spielvarianten viel tiefer durchsucht werden als andere: http://de.wikipedia.org/wiki/Alpha-Beta-Suche
-
und vergiss nicht, eine gute KI reagiert menschlich, d.h. sie darf gar nicht perfekt sein, sondern MUSS auch Fehler machen.
-
Negamax und dazu cachen von zuegen, damit bekommt man ein perfektes spiel hin. also zumindestens bei 4 gewinnt.
es muss kein perfektes caching sein, aber
-viele zuege fuehren zu der selben stellung
-viele spiele sind weit vor ausschoepfung der vollen spieltiefe fertigtheoretisch muss man auch nicht alle zuege testen, es gibt nur 42felder die im endstation den wert 0 oder 1 haben. davon wiederrum gibt es 21:21 (du musst also 21 gesetzte bits haben, siehe dazu http://msdn.microsoft.com/en-us/library/bb531475.aspx ), dazu gibt es spiegelungen und man kann weitere ausschlussklauseln machen beim generieren der felder...
mein negamax spielt recht gut schon mit 6zuegen im voraus (ca 100ms rechenzeit pro zug), ist aber eine sehr generische implementierung auf einer seite *hehe*.