spieleprogrammierer.de - Forum und Wiki zur Spieleprogrammierung und Spieleentwicklung

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.

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.

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.

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.

Welches zum Beispiel?

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 ):






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.