Ich mache eine KI für mein Dame-Spiel und versuche es so schwer wie möglich zu machen. Hier sind die aktuellen Kriterien für einen Zug auf der schwierigsten Schwierigkeitsstufe:
1: Suchen Sie nach einem Block: In diesem Fall wird ein Teil bedroht und ein anderes Teil kann zum Schutz hineingezogen werden. Hier ist ein Beispiel:
Schwarze Bewegungen
|W| |W| |W| |W| |
| |W| |W| |W| |W|
|W| | | |W| |W| |
| | | |W| | | | |
| | | | |B| | | |
| |B| | | |B| |B|
|B| |B| |B| |B| |
| |B| |B| |B| |B|
Weiße Blöcke
|W| |W| |W| |W| |
| |W| | | |W| |W|
|W| |W| |W| |W| |
| | | |W| | | | |
| | | | |B| | | |
| |B| | | |B| |B|
|B| |B| |B| |B| |
| |B| |B| |B| |B|
2: Teile aus der Gefahrenzone bewegen: Wenn ein Teil bedroht ist und ein Teil nicht für dieses Teil blockieren kann, versucht es, sich aus dem Weg zu räumen. Wenn sich das Teil nicht aus dem Weg räumen kann, ohne immer noch in Gefahr zu sein, ignoriert der Computer das Teil.
3: Wenn der Computerspieler Könige besitzt, versucht er, feindliche Teile auf dem Brett zu "jagen". Wenn keine Bewegungen ausgeführt werden können, die den König oder andere Teile nicht gefährden, ignoriert der Computer diese Regel.
4: Jedes Teil, das dem Computer in Spalte 1 oder 6 gehört, versucht, zur Seite zu gehen. Wenn sich ein Stück in Spalte 0 oder 7 befindet, befindet es sich in einer sehr strategischen Position, da es nicht erfasst werden kann, während es sich in einer dieser Spalten befindet
5: Es wird ein gebildeter zufälliger Zug ausgeführt. Der Zug gefährdet weder das sich bewegende Stück noch ein Stück, das sich auf dem Brett befindet.
6: Wenn keine der oben genannten Möglichkeiten möglich ist, wird ein zufälliger Zug ausgeführt.
Diese Frage ist nicht wirklich spezifisch für eine Sprache, aber wenn alle Beispiele in Java sein könnten, wäre das großartig, wenn man bedenkt, dass diese App in Android geschrieben ist. Hat jemand Raum für Verbesserungen in diesem Algorithmus? Gibt es etwas, das es besser machen würde, Dame zu spielen?
Antworten:
Wenn Sie versuchen, eine gute KI für Ihr Prüferprogramm zu erstellen, sollten Sie zunächst nach der sogenannten Alpha-Beta -Spielbaumsuche suchen. Die kurze Version ist, dass jede KI, die nur statische Merkmale der aktuellen Position berücksichtigt, Probleme bekommen kann, insbesondere im frühen bis mittleren Spiel, weil sie einfach nicht verstehen kann, was aktuell im Spiel passiert und was Die Bedrohungen sind. Stattdessen möchten Sie einen Algorithmus schreiben, der alle möglichen Züge und Antworten nach einer bestimmten Anzahl von Zügen durchsucht (5 bis 10 wären typisch) und die Position am Ende jedes Zweigs dieses Zuges auswertet -Reply Tree (in Bezug auf 'wie viele Teile vor oder hinter bin ich?) und macht dann den Zug, der ihm die beste Chance gibt - mit anderen Worten, den Zug, der maximiertsein möglicher Wert, wobei der mögliche Wert als minimaler möglicher Wert für alle Antworten Ihres Gegners berechnet wird (vorausgesetzt, er wird den für ihn besten Zug ausführen) usw. - aus diesem Grund ist dieser Algorithmus oft als Minimax- Algorithmus bezeichnet.
Sie werden feststellen, dass viele der Elemente, über die Sie sprechen - das Verschieben von Teilen zur Seite, das Verschieben von Teilen aus der Gefahr usw. - zu Elementen der Positionsbewertungsfunktion der Spielbaumsuche werden. Anstatt die einfache Frage zu stellen: "Wie viele Teile liegen auf der einen oder der anderen Seite?", Sagen Sie im Wesentlichen: "Was ist der Wert dieser Position?" und geben Sie dann verschiedenen Merkmalen des Bretts Punktwerte (z. B. ob ein Teil auf der Seite liegt, ob es anfällig ist usw.) in Bezug auf Teilteile - zum Beispiel können Sie entscheiden, dass der Unterschied zwischen einer Kante und einer Mitte besteht Stück ist möglicherweise 0,1 Stück wert. In einer Position, in der Sie ein Mann hinter sich sind, aber ein zusätzliches Randstück haben, beträgt der Gesamtwert für Sie -0,9.
Ein kritischer fortgeschrittener Begriff für die KI der Kontrolleure ist speziell das Konzept der Ruhesuche : Stellen Sie sich vor, Sie gehen sechs Züge in Ihren Baum hinein und am hinteren Ende hat Ihr Gegner gerade eine Erfassung vorgenommen, bei der Ihre (erzwungene) Antwort eine sofortige Wiedererfassung ist. Leider kann die Positionsbewertungsfunktion die Wiedererfassung nicht sehen, sodass die Position als Teil Ihres Gegners bewertet wird, obwohl Sie kurz davor sind, die Parität wiederzugewinnen. Die Ruhesuche ist ein Versuch, dieses Problem zu lösen, indem der Evaluator gezwungen wird, in einen Zweig zu gehen, bis alle möglichen erzwungenen Erfassungen vorgenommen wurden, und erst dann die Position bewertet.
Das mag alles ziemlich kompliziert klingen, aber ich denke, Sie werden feststellen, dass es einfacher ist als es aussieht - sobald Sie Ihre Evaluatorfunktion geschrieben haben, ist die Baumsuche relativ einfach; Es gibt viele intelligente Konzepte (z. B. Transpositionstabellen ), die Sie darauf anwenden können, aber es sollte einfach sein, etwas zum Laufen zu bringen und es dann weiter zu verbessern. Für weitere Details schlage ich vor, nach so ziemlich allen Schlüsselbegriffen zu suchen (Alpha-Beta-Suche, Minimax, Ruhesuche, Spielbaum usw.). Es gibt viele gute Informationen zu all diesen Konzepten im Internet.
quelle