Du bist nicht angemeldet.

Werbeanzeige

Reth

Frischling

  • »Reth« ist der Autor dieses Themas
  • Private Nachricht senden

1

01.03.2013, 18:18

Welchen KI-Ansatz wählen?

Hallo zusammen,

da ich seit Ewigkeiten an einem Spiel bastle möchte ich auch dessen Computergegner verbessern.

Das Spiel ist wie Siedler von Catan aufgebaut, wobei man Versorgungstürme auf die Ecken aneinanderliegender 6-Ecke stellen kann (keine Wege dazwischen).
Pro Zeitintervall bekommt jeder Spieler für jeden Turm einen Rohstoff aus einem der angrenzenden 6-Ecke. Das geschieht automatisch.

Als Aktionen gibt es derzeit nur angreifen oder Turm bauen. Ein Turm wird nach einem Angriff beschädigt und kann nur noch weniger zuverlässig Rohstoffe beschaffen, nach 2 Angriffen ist er zerstört. Die Aktionen kosten unterschiedliche Ressourcen.

Der Computer sucht sich derzeit immer den Turm des Spielers aus, der die Ressourcen beschafft, von denen der Spieler am wenigsten hat. Bei Gleichstand wird einfach eine davon gewählt.

Später sollen noch folgende Aktionen hinzukommen:
  • Turm reparieren
  • Turm schützen (zeitlich begrenzt bzw. nach einem Angriff wieder weg)
  • Turm ausbauen (sammelt doppelt Ressourcen und hält mehr Angriffe aus)
  • Landschaft verfluchen (von dieser können dann keine Ressourcen mehr geholt werden)
  • Landschaft wieder herstellen
  • ... fällt mir gerad nicht mehr ein
Meine Frage ist nun: Welcher (KI-)Ansatz wäre denn hier der Geeignetste? Dachte daran, Punkte für Aktion zu verteilen und den Computer dann die Aktion ausführen zu lassen, welche am höchsten bewertet wurde. Allerdings weiss ich nicht, wie ich die Punkte in Abhängigkeit von der Spielsituation vergeben soll (ein und dieselbe Aktion kann in unterschiedlichen Spielsituationen unterschiedlich gut sein)!?
Oder wäre hier ein Spielbaum geeigneter (also Minmax oder Alpha/Beta)? Allerdings hab ich keine Ahnung, wie ich den hier entwickeln soll?
Habt ihr ein paar gute Vorschläge?
Danke schon mal!
Ciao

2

01.03.2013, 19:18

Alpha/Beta wäre zumindest ein Ansatz, den man hier verfolgen könnte. Dein anderer Ansatz, einfach die beste Möglichkeit auswählen, ist, wenn ich dich richtig verstanden habe, ja nur ein Teil des Alpha/Beta Algorithmus.

Zitat

Allerdings hab ich keine Ahnung, wie ich den hier entwickeln soll?
Spontan hätte ich eine Idee, die funktionieren könnte, bevor ich jetzt aber sinnlos los sprudele, frag ich mal besser, woran es denn hapert.

Schorsch

Supermoderator

Beiträge: 5 206

Wohnort: Wickede

Beruf: Student

  • Private Nachricht senden

3

01.03.2013, 19:44

Ein klassischer Minmax würde hier nicht funktionieren. Der Spielablauf ist ja nicht vorhersagbar, sondern wird vom Zufall beeinflusst.
Ich würde hier auch einen anderen Weg gehen. Die Idee mit den Bewertungen ist gar nicht so schlecht. Das schwierige ist hier sinnvolle Bewertungsfunktionen zu finden. Da könntest du mit Wahrscheinlichkeiten arbeiten. Wie wahrscheinlich ist es, dass bestimmte Zahlen fallen oder nicht fallen. Da kommt es natürlich ein wenig auf dein Zufallssystem an. Bei Siedler von Catan sind es 2 Würfel mit denen bestimmt wird. So ist zum Beispiel eine 8 wahrscheinlicher als eine 2, da es mehrere Möglichkeiten gibt diese Zahl zu werfen. Der Rest ist logisches Denken und ausprobieren. Mal dir das Spiel mal auf und spiel es gegen dich selbst oder einen Freund. Versuch dabei mal selbst bestimmte Strategien bis zum Ende durchzuspielen. Zum Beispiel möglichst viele Türme bauen. Dabei lernt man selbst einiges über das eigene Spiel und sieht was wirklich wichtig für den Sieg ist. Wenn du deine Bewertungsfunktion hast, musst du ja nur noch alle Züge bewerten und den besten auswählen. Das schöne daran ist, dass man die Bewertungsfunktion normal recht flexibel ändern kann. Aber wie gesagt, spiel es vielleicht erst mal analog um selbst zu sehen was sinnvoll ist.

edit: Ich sehe grad dort steht jeder Spieler bekommt für jeden Turm auf einem Feld einen Rohstoff und das passiert automatisch. Das heißt es hat nichts mit Zufall zutun sondern ist vorhersehbar? Dann würde ein Minmax theoretisch vermutlich doch funktionieren. Das Problem mit der Bewertung würde dann natürlich bleiben.
„Es ist doch so. Zwei und zwei macht irgendwas, und vier und vier macht irgendwas. Leider nicht dasselbe, dann wär's leicht.
Das ist aber auch schon höhere Mathematik.“

Reth

Frischling

  • »Reth« ist der Autor dieses Themas
  • Private Nachricht senden

4

01.03.2013, 22:18

Hallo nochmals,

und danke für eure Antworten.

Eine grundsätzliche Info noch. Das Spiel soll in Echtzeit ablaufen, d.h., die Computerzüge dürfen zeitlich nicht ins Gewicht fallen (hab keine Multithreading/Multiprozessing).

@Schorsch:
Naja vorhersagbar insofern, als das der Computer für jeden Turm alle betroffenen Landschaften betrachtet und für den Spieler die Ressource auswählt, von der dieser am wenigsten Anteile hat. Bei Gleichstand wird zufällig entschieden. Vorhersagbar ist das Spiel dennoch nicht, da ja der menschliche Spieler und seine Aktionen nicht vorhersagbar sind. Die Rohstoffnahme kann man also vorhersagen (der Computer trickst hier und weiss, wie viele Rohstoffe der Spieler immer hat, denn theoretisch könnte der Mensch ja auch mitzählen). Hab das Spiel vor langer Zeit schon mal gegen meine 0815-KI gespielt, weiss aber keine Resultate mehr.

@Rexona for men:
Also bei Spielbaum (Minimax o. ä.) wüsste ich nicht, wie ich die Züge bewerten sollte.
Also 1. Zug Computer, aktuell 3 Möglichkeiten (vorausgesetzt, die Rohstoffe sind ausreichend):
  • Angreifen
  • Turm bauen
  • Nix tun (Rohstoffe sparen)
So nun macht der Mensch einen Zug, dann muss ich wieder die 3 Möglichkeiten durchgehen. Aber diesmal ist die Voraussetzung anders. Evtl. hat der Mensch nun mehr Türme, oder hat einen der Computertürme angegriffen. Dies müsste ja irgendwie in die Bewertung einfließen. Wenn man den Baum nicht vollständig bildet, dann muss man ja die Knoten irgendwie bewerten - aber wie soll ich den Knoten Werte zuordnen, wenn ich nicht weiss, wie der Teilbaum endet?. Keine Ahnung, wie ich das am besten anstellen soll! Dabei ist es eigentlich egal, ob 3, 4,5 oder mehr Aktionen zur Auswahl stehen. Mein Problem ist das Bewerten der Möglichkeiten. Wie gesagt, noch keine Idee, wie das am besten laufen sollte!
Hoffe, das hilft euch erst einmal, ansonsten kann ich gern noch Infos beibringen.
Ciao

5

02.03.2013, 00:44

Hm, also erstmal bin ich von einem Rundenspiel ausgegangen, in einem RTS sehe ich erstmal das Problem für einen Min/Max Baum, dass ein anderer Spieler eine Aktion ausführt, während die KI rechnet.

Zitat

Vorhersagbar ist das Spiel dennoch nicht, da ja der menschliche Spieler und seine Aktionen nicht vorhersagbar sind.
Das wiederum ist nicht schlimm, denn Schachcomputer stehen ja vor dem selben Problem und verwenden häufig(immer?) auch einen Alpha/Beta Algorithmus. Eine andere KI wäre ja auch nicht vorhersagbar, damit muss dein Algorithmus halt umgehen können.

Zitat

Also bei Spielbaum (Minimax o. ä.) wüsste ich nicht, wie ich die Züge bewerten sollte.
Also 1. Zug Computer, aktuell 3 Möglichkeiten (vorausgesetzt, die Rohstoffe sind ausreichend):
  • Angreifen
  • Turm bauen
  • Nix tun (Rohstoffe sparen)
So nun macht der Mensch einen Zug, dann muss ich wieder die 3 Möglichkeiten durchgehen. Aber diesmal ist die Voraussetzung anders. Evtl. hat der Mensch nun mehr Türme, oder hat einen der Computertürme angegriffen. Dies müsste ja irgendwie in die Bewertung einfließen. Wenn man den Baum nicht vollständig bildet, dann muss man ja die Knoten irgendwie bewerten - aber wie soll ich den Knoten Werte zuordnen, wenn ich nicht weiss, wie der Teilbaum endet?. Keine Ahnung, wie ich das am besten anstellen soll! Dabei ist es eigentlich egal, ob 3, 4,5 oder mehr Aktionen zur Auswahl stehen. Mein Problem ist das Bewerten der Möglichkeiten. Wie gesagt, noch keine Idee, wie das am besten laufen sollte!

Ich hoffe, ich verstehe dein Problem richtig.

Du musst natürlich alle möglichen Reaktionen des Gegners in Betracht ziehen. Jeder Knoten stellt eine mögliche Stellung nach einem bestimmten Zug dar, beginnend bei der Ausgangsstellung. Wenn du jetzt rekursiv so einen Baum aufbaust, bekommst du alle möglichen Stellungen für eine bestimmte Anzahl von Zügen, z.B. sechs Zügen (drei von dir und drei vom Gegner) was bei drei Zugmöglichkeiten 729 Blätter (nur diese müssen bewertet werden) bedeutet (Wurzel nicht in die Tiefe eingerechnet). Jetzt musst du nur noch die beste Endstellung finden und du weißt, wie du ziehen musst. Dabei hilft dir natürlich der Alpha/Beta Algorithmus.
Eine Bewertungsfunktion hast du ja bereits, die musst du nur noch auf die Stellungen anwenden. Wie Schorsch schon sagte, für eine optimale Bewertungsfunktion wirst du dein Spiel viel spielen müssen.

Interessant wird die Sache jetzt dadurch, dass das Spiel in Echtzeit laufen soll. Ich würde versuchen, die ganze Zeit über einen Baum zu behalten und entweder dann zu ziehen, wenn der Baum eine bestimme Tiefe erreicht hat oder wenn es einen sehr starken Zug gibt (dies würde bedeuten, dass du nicht nur die Blätter, sondern auch alle anderen Knoten bewerten musst, eventuell reicht hier aber auch eine Grobe Bewertung aus). Macht der Gegner einen Zug, so bedeutet dies, das einer deiner Knoten auf der 2. Ebene (0 ist die Wurzel) deine neue Wurzel wird. Dann beginnst du hier von neuem.

Wegen der Zeit musst du mit der maximalen Tiefe, der Einschätzung, was ein sehr guter Zug ist und möglichen Optimierungen des Alpha/Beta Algorithmus herumspielen müssen. Die Spielgeschwindigkeit eines Menschen zusammen mit einer passablen Stärke sollte aber machbar sein.

Schorsch

Supermoderator

Beiträge: 5 206

Wohnort: Wickede

Beruf: Student

  • Private Nachricht senden

6

02.03.2013, 11:56

Bei einem RTS verfolg man oft einen bestimmten Ansatz, bei welchem die Aufgaben auf verschiedene Manager verteilt werden. Das wäre bei deinem Spiel vielleicht auch nicht schlecht. Du hast eine Klasse welche über allem steht. Sie koordiniert das ganze und stellt das Gehirn deiner KI da. Sie hält alles zusammen und kümmert sich um High Level Befehle. Darunter sind verschiedene mittelgroße Manager, welche große Hauptaufgaben erledigen. Ein so ein Manager wäre ein Ressourcen-Manager. Dieser würde sich normal um die Ressourcen Beschaffung kümmern und um deren Verwaltung. Hier wird also geguckt, wie viel haben wir in den Kassen, ist dies ausreichen und müssen vielleicht neue beschaffen werden. Möglicherweise zum Beispiel durch den Bau eines Turms. Dann gäbe es noch den Bau-Manager. Das wäre der Manager, welcher die Gebäude verwaltet. Sollen zum Beispiel noch Gebäude gebaut werden? Wenn ja, gibt es eine Anfrage an den Ressourcen-Manager. Nach dem Motto, ich möchte ein Kriegsgebäude bauen. Haben wir hier für Geld? Wenn ja gehts los. Und so weiter. Dann gäbe es normal noch einen Kriegsmanager, welcher sich um die Kämpfe kümmert und so weiter. Ein Ressourcen-Manager könnte einen Manager für die Einheiten unter sich haben, welche Ressourcen abbauen. In deinem Spiel wäre das jetzt nicht der Fall, aber in vielen anderen RTS Spielen. Und jeder verarbeitet seine Befehle und delegiert die Aufgaben passend weiter nach unten. Dabei kann man mit den anderen Managern auf seiner Ebene kommunizieren, oder mit den einem selbst untergeordneten, oder dem einem selbst übergeordneten.
Jetzt sagt das Gehirn, wir möchten angreifen. Dafür wird der Befehl an den Kriegsmanager weitergereicht. Dieser sagt, wir benötigen Krieger und gibt diesen Befehl an den Einheitenmanager. Dieser guckt ob genug zur Verfügung stehen (in deinem Fall Türme). Wenn nicht sagt er dem Baumanager, dass welche gebaut werden müssen. Dafür fragt der beim Rohstoffmanager um Ressourcen. Hat dieser zu wenig, besorgt er erst die passenden und gibt dann passend Rückmeldung. Sind endlich genug Türme da werden diese dem Einheitenmanager gegeben. Dieser kann sie nun an den Kriegsmanager reichen. Hier muss nun die Logik für den Kampf bestimmt werden. Das wird dann im Prinzip weiter runter bis zu den Türmen selbst gereicht, bis diese ihre eigentlichen Kriegsaktionen ausführen können. So ein Grundsystem stellt natürlich oft nur einen Teil der KI dar. Im Prinzip ist das ein Zielgetriebenes System. Damit lassen sich normal recht gut Zeile definieren, welche immer weiter verallgemeinert werden können, bis man auf unterster Ebene wirklich simple Zugfolgen hat. Sicherlich findest du da bei Google noch einige gute Ansätze zu. Ansonsten würde ich dir ein Buch in die Richtung empfehlen.
„Es ist doch so. Zwei und zwei macht irgendwas, und vier und vier macht irgendwas. Leider nicht dasselbe, dann wär's leicht.
Das ist aber auch schon höhere Mathematik.“

ProAmateur

Alter Hase

Beiträge: 435

Wohnort: Bei Simmern, Koblenz

Beruf: Schüler

  • Private Nachricht senden

7

02.03.2013, 19:28

Welches zum Beispiel? ;)
"Die Neugier steht immer an erster Stelle eines Problems, das gelöst werden will."
Galileo Galilei
________________________________________________________________________

"Dumme Fragen gibt es nicht, dumm ist nur, wer nicht fragt.“

Reth

Frischling

  • »Reth« ist der Autor dieses Themas
  • Private Nachricht senden

8

02.03.2013, 20:43

Nochmals Dank euch!

@Rexona for men:
Hm, also erstmal bin ich von einem Rundenspiel ausgegangen, in einem RTS sehe ich erstmal das Problem für einen Min/Max Baum, dass ein anderer Spieler eine Aktion ausführt, während die KI rechnet.
Das stört aber nicht, da so lange der Computer am Zug ist, der Mensch eh nix machen kann (wie schon geschrieben, daher muss es schnell gehen).
Eine Bewertungsfunktion hast du ja bereits, die musst du nur noch auf die Stellungen anwenden. Wie Schorsch schon sagte, für eine optimale Bewertungsfunktion wirst du dein Spiel viel spielen müssen.
Welche meinst Du? Die ist ja gerade mein Problem: Wie ordne ich den Knoten im Baum diskrete Werte zu, wenn ich den Baum nicht voll erstelle? Könnte höchstens in "Siegpunkten" rechnen, jeder ganze Turm zählt 2, jeder angeschlagene 1. Nun wird jeder Knoten damit bewertet, wie viele Siegpunkte beide Spieler haben und dann der gewählt, der dem Computer den möglichst besten Vorteil beschafft. Oder was wäre hier angebracht?
Interessant wird die Sache jetzt dadurch, dass das Spiel in Echtzeit laufen soll. Ich würde versuchen, die ganze Zeit über einen Baum zu behalten und entweder dann zu ziehen, wenn der Baum eine bestimme Tiefe erreicht hat oder wenn es einen sehr starken Zug gibt (dies würde bedeuten, dass du nicht nur die Blätter, sondern auch alle anderen Knoten bewerten musst, eventuell reicht hier aber auch eine Grobe Bewertung aus). Macht der Gegner einen Zug, so bedeutet dies, das einer deiner Knoten auf der 2. Ebene (0 ist die Wurzel) deine neue Wurzel wird. Dann beginnst du hier von neuem.

Wegen der Zeit musst du mit der maximalen Tiefe, der Einschätzung, was ein sehr guter Zug ist und möglichen Optimierungen des Alpha/Beta Algorithmus herumspielen müssen. Die Spielgeschwindigkeit eines Menschen zusammen mit einer passablen Stärke sollte aber machbar sein.
Wenn z.B. der Computer einen Turm baut, dann der Mensch auch, kann der Computer ermitteln, welche Ressourcen beide verbraucht haben und welche sie gewonnen haben (was geschummelt ist, denn der Mensch könnte nicht ermitteln, welche Ressourcen der Computer bekommen hat). Und dann? Wie wird daraus ein Wert? Hab hier keinen guten Ansatz.


@Schorsch:
Uff, das klingt kompliziert und würde einen kompletten Codeumbau bedeuten! Zudem werden die Entscheidungen im oberen Hirnlevel getroffen, aber auf welcher Grundlage (die restlichen Manager sind dann nur noch die ausführenden Organe - oder ich hab Dich komplett falsch verstanden)? Also wie entscheide ich, ob angegriffen wird, oder aber gerade nix getan werden soll, oder gebaut?

Was wären denn die Stichworte, nach denen ich googlen sollte?

Ciao

9

02.03.2013, 21:45

Zitat

Welche meinst Du? Die ist ja gerade mein Problem: Wie ordne ich den Knoten im Baum diskrete Werte zu, wenn ich den Baum nicht voll erstelle? Könnte höchstens in "Siegpunkten" rechnen, jeder ganze Turm zählt 2, jeder angeschlagene 1. Nun wird jeder Knoten damit bewertet, wie viele Siegpunkte beide Spieler haben und dann der gewählt, der dem Computer den möglichst besten Vorteil beschafft. Oder was wäre hier angebracht?
Ups, mein Fehler, ich hielt deine bisherige Strategie für eine Bewertungsfunktion, was sie aber nicht ist ^^
Aber was du sagst, geht schon in die richtige Richtung. Alles was sich bewerten lässt, sollte natürlich in die Bewertung mit einfließen, z.B. Türme, Rohstoff Einkommen, die Positionierung der Türme usw. Damit kannst du die Stellungen deiner Blatt Knoten berechnen. Die Eltern nehmen dann den Wert eines ihrer Kinder an, je nachdem ob sie Min- oder Maxknoten sind. Und wenn ein Teil des Baumes nicht erstellt wird, dann weil er sowieso keinen Einfluss auf den Ausgang nehmen würde, also brauchst du ihn auch nicht zu berechnen ;)

Hier noch ein Beispiel für eine Bewertung (vielleicht sagt etwas Code ja mehr als 1000 Worte ;) ):

C-/C++-Quelltext

1
2
3
4
int rateSituation(const Situtation& situation){ int rating = 0;
    for(int i = 0; i < towerList.size(); ++i)  { if(towerList[i].belongsTo(player1))  {  rating += 1000;  }  else  {rating -= 1000;  }  }
    rating += player1.woodIncome() * 10;  rating += player1.stoneIncome() * 10; rating -= player2.woodIncome() * 10;  rating -= player2.stoneIncome() * 10;
    }





Hier ist noch ne interessante Seite http://www.fierz.ch/strategy.htm

E: Die Code Formatierung spielt gerade verrückt, hoffe, es ist trotzdem klar.



Reth

Frischling

  • »Reth« ist der Autor dieses Themas
  • Private Nachricht senden

10

02.03.2013, 23:09

Danke!
Und wenn ein Teil des Baumes nicht erstellt wird, dann weil er sowieso keinen Einfluss auf den Ausgang nehmen würde, also brauchst du ihn auch nicht zu berechnen ;)
Aber wie findet man denn diesen heraus, wenn man eh nur eine geringe Tiefe berechnen will?
int rateSituation(const Situtation& situation){ int rating = 0;
for(int i = 0; i < towerList.size(); ++i) { if(towerList.belongsTo(player1)) { rating += 1000; } else {rating -= 1000; } }
rating += player1.woodIncome() * 10; rating += player1.stoneIncome() * 10; rating -= player2.woodIncome() * 10; rating -= player2.stoneIncome() * 10;
}
Und wofür die Gewichtungen (also die Multiplikatoren)? Und würdest Du hier noch ein Zufallselement mit aufnehmen (oder nach der Baumauswertung)?

Werbeanzeige