Entwickler-Ecke
Algorithmen, Optimierung und Assembler - 4 Gewinnt KI?
jackie05 - Di 02.02.10 23:53
Titel: 4 Gewinnt KI?
Hallo,
ich habe ein 4 Gerwinnt Spiel geschrieben, leider finde ich es nicht so gut ohne einen richtigen Gegner zu spielen.
Wie kann ich ohne grosse aufwand einen richtigen Gegner Programmieren?
1. Prüfe ob Computer gewinnen kann.
2. Prüfe ob Spieler gewinnen kann, wenn ja, dann dementsprechend blockieren.
3. Wenn keins von beiden zutrifft, dann den Stein für den Computer an einer gewissen stelle plazieren und die beste möglichkeit für den Computer finden um zu gewinnen.
Wie ich den Spieler blockieren kann, ist nicht so schwer.
Mir geht es nur dadrum um die Steine der Computer richtig zu plazieren und die beste möglichkeit zu finden, damit der Computer gewinnen kann.
Gibt es vielleicht schon fertige units oder kann mir jemand einen beispiel Posten?
Ich bedanke mich schonmal für die Hilfe.
MfG
jackie05 - Mi 03.02.10 00:06
Ich danke Dir.
Da war ich schon bereits, leider verstehe ich das nicht so gut, also wie ich MinMax in Delphi verwenden kann und bei 4 Gewinnt diese Felder zu prüfen.
Kann mir Vielleicht jemand erklären wie ich das ambesten mit MinMax in Delphi hinbekomme?
MfG
Jann1k - Mi 03.02.10 12:11
Eine KI für Vier gewinnt ist eigentlich relativ einfach, du hast ja nur 7 Zugmöglichkeiten, da kannst du deine KI ja jeden Zug "in Gedanken" ausprobieren lassen und dann jeweils überprüfen was passiert. Auf die einzelnen Spalten kannst du dann Prioritäten aufsummieren, in dem du überprüfst was jeweils passiert. Kleines Beispiel:
Wirfst du einen Stein in Spalte ein entsteht ein "Dreier" für die KI das gibt dann zB +5 Prioritätspunkte für die Spalte. Wirfst du den Stein in Spalte 2, verhinderst du einen "Vierer" vom Gegner (zB +20 Punkte) und es entstehen zwei Zweier für die KI (zB + 2*2 Punkte), wirfst du in Spalte drei entsteht ein Vierer für die KI (zB +1000 Punkte) usw. SPalte drei hat höchste Priorität, also wird da ein Stein reingeworfen.
Die einzelnen Punktwerte für die Situtationen musst du dir aber zurechtbasteln, weiß da nicht was optimal wäre. Und natürlich musst du auch checken, was passiert wenn der Gegner einen Stein auf deinen setzt.
danielf - Mi 03.02.10 12:24
Generell gibt es für KI verschiedene Ansätze:
BackTracking mit MinMax) wie Jann1k und Dude556 es beschrieben hat. D.h. man versucht jede Möglichkeit aus und bewertet danach die neue Spielsituation und macht dann den Zug der unter Berücksichtigung dass der Gegner auch den besten Zug mach (min für dich) für dich in x Schritten am besten ist. Wobei x bis zum Ende bzw. bis zu einer Suchtiefe (Schwierigkeitsgrad geht).
Backtracking ist ein generischer Ansatz und kann für alle Spiele angewendet werden.
Dagegen wäre ein Logik) Du definierst eine Logik nach der deine KI Fährt (speziell für 4 Gewinnt). Sprich du sagst wenn er bei 1 rein wirft, werfe ich bei 2 rein. oder so etwas. Je nachdem wie intelligent die Logik ist, ist es dann schwieriger sie zu Knacken. Im Schach wäre das dann das Implementieren von "Weisheiten/Sprichwörtern" wie "Pferd am Rand ist eine Schand" ....
Das einfachste ist wohl Backtracking mit MinMax: Dafür musst du eine Situationsbewertung implementieren, wie es Janni1k erklärt hat. Und dann ein Algorithmus der einmal das Max und beim nächsten mal (gegnerischer Zug) das Min nimmt.
Gruß Daniel
Entwickler-Ecke.de based on phpBB
Copyright 2002 - 2011 by Tino Teuber, Copyright 2011 - 2025 by Christian Stelzmann Alle Rechte vorbehalten.
Alle Beiträge stammen von dritten Personen und dürfen geltendes Recht nicht verletzen.
Entwickler-Ecke und die zugehörigen Webseiten distanzieren sich ausdrücklich von Fremdinhalten jeglicher Art!