Strategie-Spiel KI-Theorie

Druckbare Version

16.06.2005, 14:11
MagicMagor

Strategie-Spiel KI-Theorie

Hoi,

ich bastele momentan an einem kleinem Strategiespiel im MakerXP (bzw. mit Ruby *g*). Nur ist die Sache, daß ich keine wirkliche Motivation zum Coden habe, wenn die Planung in einer kritischen Stelle eine Lücke hat. Hier ist das die KI.

Ich habe zwar einige Ideen und Ansätze, aber diese sind ein wenig unbefriedigend und unvollständig. Und ein Strategiespiel ohne vernünftige KI ist irgendwie, sinnlos.
Und da hoffe ich hier auf eure Hilfe, daß ihr mir helft meine bestehenden Ideen zu erweitern oder völlig neue Ansätze zu liefern.

Mal eine Kurzbeschreibung des Spieles:
Die Spieler bauen auf einer 2D-Karte eine mittelalterliche Kolonie, dabei belegt jedes Gebäude exakt 1 Feld. Es gibt diverse Wirtschaftskreisläufe, wie vom Weizen zur Nahrung. Jedes Gebäude kostet pro Runde Nahrung und Geld. Produzierte Waren werden im Heimatland verkauft oder mit anderen Spielern bzw. den Ureinwohnern gehandelt.
Mittels Geld und Waffen können Soldaten ausgehoben werden, diese werden in Armeen organisiert. Diese Armeen können über die Karte gezogen werden.
Ziel des Spiels ist es, wie in Colonization, unabhängig zu werden. Dafür muss eine wirtschaftliche Unabhängigkeit gegeben sein, und ein Unabhängigkeitskrieg muss gewonnen werden.
Soviel mal zum groben Spielablauf.

Mein bisheriger Ansatz für KI-Spieler:
Die Runde eines KI-Spielers ist in mehrere Phasen unterteilt. Zu Beginn kommt die Planungsphase.
Bestehnde Ziele werden in ihrer Wichtigkeit ein wenig aufgewertet, danach erfolgt das Setzen neuer Ziele. Die Wirtschafstkraft eines Spielers mißt die KI im Output an Rohstoffen/Produkten pro Runde, sowie der Blianz. Unterschiedliche Rohstoffe sind unterschiedlich gewichtet. Es ergibt sich am Ende eine Zahl, die für die Wirtschafstkraft des Spielers steht. Militärische Stärke ergibt sich aus der Anzahl an Soldaten, wobei bereits in Armeen organisierte Soldaten ein wenig mehr wert sind als die in keiner Armee.
Wirtschaftlich gesehen versucht die KI ihre Bedürfnisse zu decken, sprich kein Rohstoff sollte negatives Wachstum haben, Grundbedürfnisse (Nahrung, Holz) sowie Geld sollten einen Überschuss produzieren.
Militärisch vergleicht die KI ihre Stärke mit ihrem Heimatland, sowie den anderen Spielern. Sobald sie gegenüber einem davon zu stark ins Hintertreffen gerät, wird die Produktion von Soldaten als Ziel gesetzt.

Nach dieser Planungsphase habe ich dann eine Liste aller "Aufgaben" bzw. Ziele die die KI erfolgt, jeweils mit einer Priorität versehen. Von den verfügbaren Resourcen werden prozentual soviele wie die Priorität angibt, den Aufgaben zugeteilt.

Theoretisch habe ich damit einen Aufbau der KI-Kolonie gewährleistet. Was mich noch ziemlich wurmt ist, ich habe keine Ahnung nach welchen Kriterien die KI Armeen bildet und wo sie diese plazieren soll.. Oder wie tief ich beim Stellen der Subziele ins Detail gehen soll.

Im Grunde möchte ich Zufall, sowie Cheaten der KI vermeiden. Letzteres würde ich aber zur Not akzeptieren.

Kommentare und Anregungen sind willkommen. Ist der Ansatz ok, übersehe ich was oder mache ich mir mit meinen Sorgen nur das Leben unnötig schwer?
16.06.2005, 14:33
dadie

Mmm. KI ich mag KI´s das thema kann ich recht gut ^^

Also wie du es machst ist es vom Prinzip richtig.

jedoch noch zu Undynamisch.

Also zu anfang cheackt die KI "Was habe ich"
Dann Prüfft die KI "Was werde ich woll brauchen"
Dann fängt die KI an zu suchen "Wo Finde ich das"
Hierüfr schickt die 1 bis 2 Einheiten los

Gleichzeitig schick die KI Einheiten los um zu klähren :

"Wo ist der feind" und "Wie siht er aus"

Der Gegner Lokalisiert nun den Feind während er gleichzeitig seine Wirtschaft aufbaut soweit bis er das erreicht hat was er brauch.

Sobald er den Feind gefunden hat Speichert er seine Position und evtl. wie viele Felder der Feind (von dem was die KI siht) belegt und wieviele Angreiffer darin sind.

Nun errechnett die KI je nach Schwierichkeits stuffe wieviel einheiten er brauch für einen Schnellen , langsamm , hoffnunglosen Sieg.

Naja und dann baut der gegner eine Varteidung auf um evtl. einen Angriff abzuwehren hierbei prüfft er über ein Kolisions Script wo der gegner herr kommen kann uns sichert das ab ^^

Vom Prinzip würde ich sagen so funtz ne Stratigi KI (ne Ganz billige)
16.06.2005, 15:22
Manuel
Äh... wenn ich's richtig verstanden habe, suchst du nach sowas wie einen KI-Ansatz, damit der Computergegner die Soldaten sinngemäß auf die Karte verteilt und dementsprechend richtig nach Priorität handelt, oder?

Bei der Platzierungsphase von Soldaten hätte ich Vorschläge anzubieten:
(Ich muss gleich vorneweg sagen: Ich hab' Colonization nie gespielt, es kann sein, dass ich eine völlig falsche Vorstellung von deinem Spiel habe^^)
- Die höchste Priorität der Gegner sollte IMO sein: Wenn der Spieler seine Gebäude angreift, sollte der Gegner alle seine Streitkräfte, die sich gerade in der Nähe des Gebäudes aufhalten, zum Gebäude marschieren und alle Streitkräfte des Spielers ausschalten. Dabei könnte man ein wenig an der Priorität der Gebäude rumfummeln, sprich: Je wichtiger das Gebäude, desto wichtiger die Priorität, es zu beschützen (also z. B. auch weiter entfernte Einheiten zum Gebäude schicken, nicht nur Einheiten, die neben dem Gebäude stehen^^).
- Es könnte IMHO eine Art Mindestanzahl der Soldaten mitten in der Basis herrschen, die die Basis im Kampffall verteidigen. Diese Soldaten sollten um die Basis herum marschieren und patrollieren*. Dabei sollten sie natürlich auch angreifen, wenn Gegner gesichtet werden^^. Dabei könnte man auch Prioritäten festlegen, am einfachsten wäre es, jedes Haupthaus/Ressourcenlager gilt (für die KI) als Basis und muss verteidigt werden. Natürlich nur ein Beispiel^^...
- Kommt es zum Kampf mit dem Spieler, würde ich der KI wahrscheinlich folgendes vorschlagen: Erstmal soll geprüft werden, ob eine Mindestanzahl anderer Kampfeinheiten um diese Einheit herum steht. Falls ja, könnte man taktische Finesse nutzen: Nahkampf- oder besonders starke Einheiten vorne platzieren, Fernkampf- und schwache Einheiten dahinter.
  Natürlich kann man es sich auch einfach machen und nur den Befehl zum Angreifen geben ohne taktisches Vorgehen, wenn ein Gegner innerhalb eines bestimmten Radius gesichtet wird^^. Zumindest ein wenig taktisch ohne viel Herumprogrammieren wäre IMO, dass ein Soldat bei Feindsicht die Einheit angreift, die sie auch am meisten verletzen kann. Wenn jetzt z. B. ein Bogenschütze die Wahl zwischen einem schlecht gepanzerten Soldaten und eines Panzers hat, sollte der Bogenschütze dementsprechend nicht den Panzer attackieren^^. Wie gesagt, wenn er die Wahl hat^^. Dabei könnte man auch eine Regel aufstellen: Ist eine besonders teure Einheit alleine im Kampf gegen eine unschaffbare Übermacht, sollte sie sich zur Flucht in die eigene Basis entscheiden. Einheiten, die sich nicht verteidigen können (z. B. Ressourcenarbeiter) sollten nach Feindbeschuss sofort fliehen.
- Sollte es in deinem Spiel auch die Möglichkeit zur Expansion (also zur Suche anderer Rohstoffe) geben, würde ich auch dort Prioritäten setzen für die Soldaten. Dabei könnte z. B. folgende Regel gelten: Je mehr Rohstoffe es in einer Basis gibt, desto mehr Soldaten sollten in ihr patrollieren*.
- Eine Cheat-Methode wäre, per Skript eine besonders taktische Stelle auf der Map verteidigen zu lassen, z. B. eine Brücke, die den einzigen Zugang zu besonders wertvollen Rohstoffen oder den Zugang zur gegnerischen Basis gewähren.
So, ich hoffe, ich konnte helfen. Wie gesagt, es kann auch sein, dass ich gerade völligen Nonsens geschrieben habe und dir das überhaupt nicht weiterhilft, was ich nicht hoffe^^...

*Falsch geschrieben, ich weiß^^...
16.06.2005, 15:28
DFYX

Mein Konzept zur "lernenden" KI kennst du ja ungefähr. Das ganze basiert darauf, dass z.B. in Warcraft häufig Replays von Gegnern studiert werden, um sie besser einschätzen zu können. Allerdings schreib ichs jetzt noch mal gesammelt auf.

Eine KI kann theoretisch "lernen", indem sie Aktionen protokolliert und auswertet. Jede Handlung sowohl des Spielers als auch der KI wird in zusammenhängende Blöcke gruppiert und in einer Datei abgespeichert, wo sie wieder abgerufen werden kann.

So ein Block besteht aus 4 Abschnitten:
1. Ausgangssituation
2. Aktionen
3. Endsituation
4. Auswertung

Die Blöcke sehen folgendermaßen aus:

1. Ausgangssituation
Hier wird festgehalten, wie das Spielfeld zu Beginn aussieht. Etwa wie ein Savegame, nur nicht so präzise. Also so Sachen wie Anzahl der Einheiten von einem bestimmten Typ, Anzahl der Ressourcen, Anzahl der Gebäude und das für alle beteiligten Spieler. Natürlich werden nur Infos festgehalten, die für den Block wirklich relevant sind. Wenn ein Block nur Aktionen gegen einen bestimmten Spieler enthält, ist es meistens Unsinn, Infos über die restlichen Spieler zu speichern. Oder etwa, wenn nur Truppenbewegungen im Aktionsteil stehen. Dann fällt natürlich fast alles weg, was die (eigene) Wirtschaft angeht.

2. Aktionen
Ähnlich wie in einem Replay werden alle Aktionen der beteiligten Spieler aufgezeichnet. Allerdings auch hier wieder nur grob. Also nicht "Bewege Einheit X zu Punkt (122|61)", sondern "Bewege Truppenverband aus n Einheiten vom Typ x zur gegnerischen Basis" und auch nicht "Baue Gebäude A an Punkt (22|421)", sondern "Baue Gebäude A in der Hauptbasis" Da muss man sich überlegen, wie detailiert man das macht, also ob man festhält, über welche Flanke angegriffen wird und so weiter. Ich würde solche Sachen optional machen. Wenn nichts angegeben wird, wird eben ein Standardwert (z.B. Frontalangriff) angenommen.

3. Endsituation
Wie die Ausgangssituation, nur werden nur Sachen gespeichert, die sich verändert haben.

4. Auswertung
Wohl der Teil, der am kniffligsten werden könnte, weil er sehr Stark vom Spiel abhängt. Es werden die Differenzen zwischen Ausgangs- und Endsituation berechnet und daraus ein Gesamtwert ermittelt, wie effektiv die Aktion war. Da ist sicher einiges an Balancing nötig.

Das ist mal die grobe Arbeitsweise bei der Speicherung. Während dem Spiel gleicht die KI dann die aktuelle Situation mit den Ausgangssituationen der gespeicherten Blöcke ab. Dabei ist es egal, ob sie die Rolle mit einem anderen Spieler getauscht hat. So kann sie auch das Verhalten von menschlichen Spielern kopieren. Aus Übereinstimmung und Effektivität wird schließlich ermittelt, welcher Block gewählt wird. Dabei werden noch andere Faktoren berücksichtigt. Etwa der Mut des KI Spielers, auch mal eine nicht ganz so erfolgversprechende Variante zu probieren, die Vorliebe für einen bestimmten Einheitentyp oder auch die Anzahl der bisherigen Versuche, um die Sache abwechslungsreich zu machen.

Diese Art von KI verlangt natürlich auch vom Spieler, seine Taktik immer wieder zu verfeinern. So Standardtaktiken wie ein Rush am Anfang werden damit unterbunden, weil sich die KI irgendwann drauf einstellt. Bei richtiger Auswertung bleibt die KI auch immer auf etwa dem gleichen Level wie der Spieler. Schwierigkeitsgrade wären also nicht mehr nötig. Wenn man noch was einbaut, dass die KI die Aktonen selbstständig variiert, hat man schon fast das Verhalten eines menschlichen Trainingspartners.
16.06.2005, 16:42
Jesus_666

Übrigens kann man sich die KI-Arbeit viel leichter machen, wenn man wie bei FreeCiv einfach die KI-Spieler voll auf Expansion gehen läßt. Für menschliche Spieler ist so ein Stil nicht sehr gut zu spielen, aber er ist so effektiv, daß man bei FreeCiv faktisch nicht gewinnen kann, wenn man nicht ebenfalls voll auf Expansion geht (die FreeCiv-Doku geht sogar davon aus, daß man erst mit zwölf oder mehr Städten überhaupt was anderes tun sollte als Siedler bauen).

Allerdings hat das den Nachteil, daß der Spieler dazu gezwungen wird, das Spiel auf eine einzige Art zu spielen (= die gesamten Ressourcen darin zu investieren, so schnell wie möglich zu expandieren und nacheinander alle Computergegner auszuschalten, ohne das Wachstum zu unterbrechen).
Ich finde das fast genauso schlecht wie das Kaschieren einer nicht sehr schlauen KI durch massives Cheaten (wie in MoO2).

Für dich dürfte DFYXs Ansatz wohl sehr gut geeignet sein; AFAIK arbeiten Strategiespiele häufig so. Abhängig davon, wie groß die untersuchten Blöcke sind könnte der Computergegner sogar innerhalb eines Spiels lernen.

Man könnte auch versuchen, einen (pseudo)genetischen Algorithmus zu verwenden, der an einer gegebenen Taktik zufällige Änderungen vornimmt, bevor er sie einsetzt. Wenn die neue Taktik erfolgreich zu sein scheint wird sie im nächsten Durchlauf verarbeitet, ansonsten wird beim nächsten mal die Ursprungstaktik genommen. Das könnte interessante Ergebnisse bringen; man müßte allerdings eine hohe Mutationsrate verwenden, weil die KI sich sonst nicht schnell genug ändert. Außerdem könnte es zu SEHR exzentrischem Verhalten der KI führen.
16.06.2005, 17:07
DFYX

Zitat:

Zitat von Jesus_666

Für dich dürfte DFYXs Ansatz wohl sehr gut geeignet sein; AFAIK arbeiten Strategiespiele häufig so.

Nicht ganz. Die ersten beiden Schritte sind zwar ähnlich, aber ich kenn kein Spiel, bei dem die Ergebnisse ausgewertet werden. Meistens isses halt so, dass der Entwickler/Modder für jede Situation was passendes vorgeben muss (Siehe WC3 oder AOE2/SWGB)

Zitat:

Abhängig davon, wie groß die untersuchten Blöcke sind könnte der Computergegner sogar innerhalb eines Spiels lernen.

So wars gedacht. Die Blocklänge sollte nicht durch eine gewisse Zeit definiert sein, sondern durch Sinnabschnitte. Also etwa ein Angriff (egal ob eigener oder gegnerischer) oder so was in der Größenordnung. Für den Aufbau einer Armee und die Wirtschaft sind die Blöcke mehr oder weniger undefiniert lang. Sie sind beim Ablauf so lange gültig, bis ein anderer Block besser zur aktuellen Situation passt.

Zitat:

Man könnte auch versuchen, einen (pseudo)genetischen Algorithmus zu verwenden, der an einer gegebenen Taktik zufällige Änderungen vornimmt, bevor er sie einsetzt. Wenn die neue Taktik erfolgreich zu sein scheint wird sie im nächsten Durchlauf verarbeitet, ansonsten wird beim nächsten mal die Ursprungstaktik genommen. Das könnte interessante Ergebnisse bringen; man müßte allerdings eine hohe Mutationsrate verwenden, weil die KI sich sonst nicht schnell genug ändert. Außerdem könnte es zu SEHR exzentrischem Verhalten der KI führen.

Genau das wollte ich in meinem letzten Satz andeuten. Wäre auch interessant zu sehen, was passiert, wenn man mehrere KIs bei x-facher Geschwindigkeit ein paar Stunden lang aufeinander los lässt. Innerhalb von einigen Tagen hätte man wahrscheinlich entweder eine Mega-KI, die auf alles den passenden Konter kennt oder eine KI, die den größten Mist versucht.
16.06.2005, 19:48
Jesus_666

Oder eine KI, die sich super damit auskennt, bestimmtes Verhalten zu kontern, gegen eine andere Strategie aber völlig hillos ist, weil die sich im Sandkasten nie entwickelt hat.
Auf jeden Fall wär's interessant.
16.06.2005, 19:59
Dingsi

Wenn wir dann mit onsetsu, PortaMaker/Yao, Yinc + Yinc.OS, DSAster, mqs und Jeez' IRC-Klienten und DFYX' Kartenspielchen fertig sind können wir ja gemeinsam eine KI proggen. Irgendwann. Später. Viel später.

Ich hab noch mqs und mein XUL/Linux vergessen.

Und MM's People.
17.06.2005, 04:46
Ineluki

die schwierigkeit wird wahrscheinlich darin liegen, die zu speichernden daten zu abstrahieren, bzw zu filtern, was wichtig war, oder was nicht ...

Es ist gar nicht so einfach zu sagen, was an einer situation wichtig ist ...
z.B. haengt das gewinnen einer schlacht ja auch von Taktik und Gelaende (Reiter im Gebirge ?) ab. Wenn die KI dann nur speichert "17 Berserkertotemspriester Stufe 3 gegen 5 berittene Paladine Stufe 5" kann es durchaus sein, dass sie falsche Schluesse zieht.

Andererseits werden bei zu vielen gespeicherten Informationen die Situationen fuer die KI unvergleichbar.

Vielleicht sollte man das ganze auf rein mathematisch abstraktes Modell stellen.
Man ueberzieht die Map bzw das Kampfgebiet mit einem Raster. Jedes Objekt auf der Map hat zwei Prioritaetenparameter, naemlich in Angriff und im Wert (Wert des Behaltens bei eigenen Objekten, Wert des Vernichtens bei fremden Objekten). Nun werden fuer jedes Rasterquadrat die eigenen und fremden Angriffs-Prioritaeten aufsummiert. Fuenf Soldaten mit Angriffsprioritaet 1 in einem Rasterbereich sind dann effektiv mehr, als ein gegnerischer Ritter mit Angriffsprioritaet 4.

Die KI bewertet nun jedes Feld an hand dieser Summenwerte. Zudem werden um jedes Feld die Prioritaeten der umliegenden Felder ebenfalls beruecksichtigt, nur geht ihre Prioritaet dann gewichtet mit dem Abstand ein. Die Rasterkarte mit den Summen der Wertprioritaeten wird als naechstes als Wichtungsfaktor verrechnet. So erhaellt man praktisch eine grobe gemittelte militaerische Potentialflaeche (militaerische relevanz Dichte).

Nun werden gemaess dieser Flaeche die eigenen Einheiten so verschoben, dass versucht wird, dass das militaerische Potential (eigenes - fremdes) positiv an Punkten hoher Wertprioritaet liegt. Mit anderen Worten, man bildet fuer jede (bewegliche) Einheit einen Potentialgradienten (Kraft) und verschiebt sie (entsprechend der Regeln) entlag des selben.

[Einschub]
Ums in einem anderen physikalischeren Bild zu formulieren:
Wir haben einen Raum mit inhomogener Ladungsverteilung, die einer Dichtefunktion p(r) genuegen soll. Wir zerlegen den Raum in (in)finitesimale Raumabschnitte dV und bilden das Integral von p(r) ueber dV. Anschliessend betrachten wir den Wert des Integrals ueber dV als Ladung mit Massepunkt im Zentrum von dV und bestimmen anhand des Coulombgesetzes die Kraefte zwischen diesen Massepunkten. Entlang dieser Kraefte verschieben wir unsere imaginaeren Massepunkte, indem wir p(r) entsprechend modifizieren.
[/Einschub]

Mit dieser Methode sollte unsere KI eigentlich alles machen, was wir von ihr erwarten. Schwaechere Einheiten fliehen vor einer Uebermacht, wenn sie ein lohnenderes Ziel haben, staerkere Einheiten kommen den schwaecheren zu Hilfe (und auch umgekehrt). Eigene Gebaeude werden wehement verteidigt, gegnerische Gebaeude werden angegriffen, und weit entfernte Truppen werden nicht entschliessen, ploetzlich umzukehren, wenn ein eigenes Gebaeude angegriffen wird, aber genuegend eigene Truppen in der Naehe sind. Auch koennen strategisch wichtige Punkte auf der Karte markiert werden, indem ihnen keine militaerische prioritaet gegeben wird, dafuer aber wichtigkeit. Wenn sich in ihrer Naehe gegnerische Einheiten sind, werden die eigenen einheiten versuchen den punkt anzugreifen (weil die staerke der gegnerischen truppen dort staerker gewichtet wird) und sie werden versuchen den Punkt entsprechend auch verteidigen, bzw versuchen, wenn keine Feinde in sicht sind, um den Punkt herum auszuschwaermen.

Das mag vielleicht etwas starr erscheinen, allerdings ist auch hier die KI lernfaehig. Z.B. kann sie an Hand von Kampfesverlaeufen die militaerische Staerke oder die Wichtigkeit neu bewerten, was langfristig einem Lerneffekt gleichkommt, da sie ihre eigenen Einheiten besser auf ihre Faehigkeiten einschaetzen kann.

Eventuell kann sie auch an Hand der Geschwindigkeit und/oder Lebensenergie einer Einheit ihren Entfernungseinfluss bei der Summation von linear abnehmend auf logarithmisch oder quadratisch abnehmend veraendern, was einer dynamischen Anpassung der Situation gleich kommt.

Nun stellt sich natuerlich noch die Frage, warum man ein Raster braucht ...
Es stimmt zwar, dass man kein Raster braeuchte, wenn man die Potentialsummation auf jede Wechselwirkung aller militaerisch relevanten Dinge untereinander anwendet, aber das koennte durchaus in zu viel rechenaufwand bei sehr vielen einheiten fuehren. Das Raster dient dazu, lokale gruppen zu erzeugen, die gemeinsam berechnet werden. Eventuell ist es aber auch besser, nicht rasterorientiert zu arbeiten und dafuer miliaerische gruppen zu bilden, die dann gemeinsam berechnet werden und zusammen losziehen ...

Wieder andere werden jetzt natuerlich sagen, ich sei von meiner Molekueldynamiksimmulation zu geschaedigt, weil das ist genau das selbe, was auch meine Simmulation macht, und damit haben sie recht ...
17.06.2005, 08:58
Feenstaub

@DFYX:
Hervorragender Ansatz! Gefällt mir. Allerdings machst du an genau der wichtigen Stelle leider keine konkreten Angaben. Die ersten drei Schritte (Ausgangssituation speichern, Aktionen aufzeichnen, Endsituation festhalten) sind in jedem Spiel unterschiedlich und müssen individuell gelöst werden. Aber grade deine angesprochene Auswertung ist es doch, bei der es meistens hapert. Die Bewertung einer bestimmten Situation auf einer Skala. Und dann kommt noch der enorme Speicherplatz hinzu, der dafür benötigt wird... wann beginnt eine Ausgangssituation, wann endet sie, und aufgrund der ständig sich verändernden Bedingungen würde sich die Situationsdatenbank in nullkommanix zu einem riesigen Ballon aufblähen.

Zitat:

Zitat von Jesus_666

Für dich dürfte DFYXs Ansatz wohl sehr gut geeignet sein; AFAIK arbeiten Strategiespiele häufig so.

Das halte ich definitiv für falsch. Würde es irgendein Spiel geben, dass eine lernfähige KI besitzt... was glaubst du wohl, wie viele Leute das spielen würden... Tag und Nacht. Es wäre ein Traum! Man müsste sich immer wieder neue Taktiken einfallen lassen, da der Gegner über kurz oder lang neue Gegenmassnahmen erfindet. Man müsste raffinierte Fallen legen, geschickte Manöver durchführen und stetig mit neuen Ideen aufwarten. Und irgendwann könnte man dem Computer nicht mehr das Wasser reichen. Denn dessen Speichervermögen und Analysemöglichkeiten sind (im Vergleich zu der unsrigen genutzten(!) Hirnmasse) unendlich.

@MagicMagor:

Ich empfehle dir die Bücher "Game Programming Gems". Hier findet man sehr gute Artikel über KI-Implementierung. Zum Beispiel eine leicht verständliche Abhandlung über neuronale Netze, falls du wirklich mit einer lernfähigen Intelligenz arbeiten willst.

Ansonsten würde ich an deiner Stelle erstmal mit einfachen Statemachines anfangen, die dann später langsam wachsen und gedeihen... nicht unbedingt lernfähig, aber doch mächtig genug, um auf verschiedene Situationen unterschiedlich zu reagieren. Ausserdem sind Statemachines pflegeleicht und schnell anzupassen.

Küsschen,
Feenstaub.

[EDIT]
@Ineluki:
Ich habe deinen Post dreimal durchgelesen... aber ich habe (fast) nichts davon verstanden. ^^ Entweder du warst ein wenig besoffen beim Schreiben oder ich sollte mir lieber einen anderes Hobby suchen. Hoffentlich ersteres. :P
[EDIT]
17.06.2005, 11:42
DFYX

@Ineluki:

Deine Idee hat einen Haken. Sie geht davon aus, dass eine Einheit "stark" oder "schwach" ist und dass das von Anfang an so definiert ist. Mein Ansatz geht davon aus, dass die KI selber ausprobiert, wer gegen wen stark ist. Ich gehe davon aus, dass eine Armee nicht einfach nur aus vielen superstarken Einheiten bestehen muss, sondern ausgewogen sein sollte. Das ganze ist durch das Schere-Stein-Papier Prinzip geregelt, das schon lange in Strategiespielen angewendet wird. Beispiel Age of Empires 2: Bogenschützen sind gut gegen Pikeniere, Pikeniere sind gut gegen Reiter, Reiter sind gut gegen Bogenschützen. Das ganze wird dann mit mehr Einheitentypen noch komplexer. Gut, bei so einem System könnte die KI evtl. die Faktoren verwenden, die da zur Schadensberechnung auch benutzt werden, um für jede angreifende Armee eine passende Abwehr zusammenzustellen. Jetzt stell dir aber mal Warcraft 3 vor. Da definieren sich diese Wechselwirkungen nicht nur durch die Schadensberechnung, sondern auch durch Fähigkeiten. Selbst menschliche Spieler müssen lange experimentieren, um herauszufinden, welchen Einheitentyp man womit kontern sollte. Mein Ansatz sollte eben dieses menschliche Verhalten imitieren, da ich denke, dass das für den Spieler am angenehmsten ist. Der Computer wird selten eine Antwort auf eine wirklich neue Taktik kennen, aber auch verhindern, dass man ihn einfach immer wieder auf die gleiche Weise niedermetzelt.

@Feenstaub:

Ja, du hast recht, mein Text ist an einigen Stellen etwas unpräzise. Das hat unterschiedliche Gründe. Erst mal der wichtigste: als ich das geschrieben hab, stand ich etwas unter Zeitdruck, deshalb hab ich mich kurz gefasst. Mir war erst mal wichtig, euch die grobe Idee zu vermitteln. Ich hab hier IRC Logs rumfahren, wo ich sicher ne Stunde drüber erzählt hab und auch konkrete Beispiele genannt hab. Allerdings hängen solche Sachen natürlich auch immer vom Spiel ab. Von einer universell einsetzbaren Super-KI ist mein Ansatz weit entfernt. Man müsste einfach durch Ausprobieren entscheiden, welche Faktoren wie gewichtet werden. Auch die Definition, wann ein Block anfängt und wann er aufhört muss erst durch experimentieren wirklich herausgefunden werden. Ich habe nie selbst eine KI für Strategiespiele geschrieben, nur für einfache Shooter. Ich habe einfach nur überlegt, wie ein menschlicher Spieler vorgeht und wie man das auf Computer übertragen kann.
17.06.2005, 13:31
Jesus_666

Zitat:

Zitat von DFYX

Deine Idee hat einen Haken. Sie geht davon aus, dass eine Einheit "stark" oder "schwach" ist und dass das von Anfang an so definiert ist.

Muß nicht. Es ist problemlos möglich, daß am Anfang alle Einheiten gleich gewichtet werden und die KI durch Ausprobieren auf die relativen Stärken kommt, beispielsweise durch das wiederholte Abfahren von KI-gegen-KI-Spielen. Ob diese Daten genutzt werden könnte vom Schwierigkeitsgrad abhängen - oder man gibt dem Spiel eine Möglichkeit, vorgegebene KI-Kenntnisstände zu laden - dann lädt man bei Spielbeginn einfach den Stand, der einem am besten gefällt.
Eine völlig untrainierte KI ins Rennen zu schicken halte ich für eine schlechte Idee, weil erfahrenere Spieler sich so automatisch langweilen und aufhören, bevor die KI genug Erfahrung gesammelt hat, um angemessen reagieren zu können.

@Feenstaub: Auch eine automatische Schwierigkeitsgradanpassung funktioniert in groben Zügen nach dem Prinzip - und die gibt es.
17.06.2005, 17:38
Ineluki

@Feenstaub .. ich war zu dem Zeitpunkt, wo ich das geschrieben habe, keinesfalls besoffen.

Wie ich im einleitenden Teil bereits sagte, ist diese Herangehensweise sehr Mathematisch. Man betrachtet in gewisser Weise die militaerische Verteilung als (bei 2D) 4N-Dimensionale Hyperflaeche, wobei N die Anzahl an beteiligten Objekten ist. Diese 4N koordinaten sind Militaerische Prioritaet, Wichtigkeit und die beiden Koordinaten von jedem betroffenen Objekt. Dadurch erhaellt man (im einfachsten fall) eine 2N Dimensionale Hyperflaeche als Funktion von 2N unabhaengigen variablen (Position) und 2N konstanten (militaerische Prioritaet, Wichtigkeit). Andersbetrachtet ist dies ein Potentialfeld. Mit hilfe der Differentialrechnung ueberfuehren wir dieses in ein Gradientenfeld und wenden die Gradienten auf die Positionierung der N Einheiten an, indem wir sie entlang der Gradienten verschieben.

Das ist die selbe Startegie, die z.B. zur Geometrieoptimierung von Molekuelen angewendet wird, und kommt folglich aus der Mathematik bzw der Physik, ist aber genau so gut auf die Loesung unseres KI Problems anzuwenden. Dadurch, dass sie so mathematisch ist, ist sie natuerlich etwas kompliziert zu verstehen ... aber ihre eigentliche Implementierung ist gar nicht so kompliziert ...
17.06.2005, 18:11
Jesus_666

Es läßt sich ganz einfach erklären:
Die Karte ist unterteilt in x*y Felder. Jedes dieser Felder hat einen Wichtigkeitswert.

Code:

00 00 00 00 00 00 10 30 10 00 00 20 40 20 00 00 10 20 10 00 00 00 00 00 00

Jetzt nehmen wir die militärische Stärke der Feindeinheiten und addieren sie zu jedem Feld. In diesem Beispiel hat der Feind eine Einheit der Stärke 40 im Feld (1,1) (unten links ist (0,0)).

Code:

00 00 00 00 00 00 10 30 10 00 00 20 40 20 00 00 50 20 10 00 00 00 00 00 00

Danach ziehen wir die eigene militärische Stärke von jedem Feld ab. Das gibt die Gesamtsituation wieder. In diesem Fall haben wir eine Einheit der Stärke 60 in der Mitte der Karte.

Code:

00 00 00 00 00 00 10 30 10 00 00 20 -20 20 00 00 50 20 10 00 00 00 00 00 00

Die KI versucht nun, durch Einheitenverschiebungen nach Möglichkeit auf der ganzen Karte den Wert 0 zu erreichen oder geringfügig zu unterbieten. So ist sichergestellt, daß in unwichtigen Gegenden keine unnötigen Einheiten stehen und daß feindliche Einheiten angegriffen werden.
In diesem Beispiel wird der Spieler also die Einheit aus der Mitte der Karte nach (1,1) verschieben.

Durch Manipulation der einzelnen Werte läßt sich das Verhalten des KI-Spielers beeinflussen. Beispielsweise könnte man den Spieler friedfertiger machen, indem man bei der Verrechnung den Wert aller Feindeinheiten halbiert; die strategische Kompetenz läßt sich dadurch einstellen, daß die Wichtigkeitswerten herunter- oder heraufgerechnet werden (oder daß man sie um einen Zufallswert verändert) und über die Gewichtung der eigenen Einheiten kann man bestimme, wie militaristisch die KI arbeitet.
17.06.2005, 20:17
Ineluki

Nun ja .. dein Beispiel ist fast richtig, bis auf, dass die Wichtigkeitskarte mMn werte von 0 bis 2 enthalten sollte, welche dann mit der militaerkarte (elementweise) multipliziert werden ... und das ganze etwas trivialisiert wird ;)

[Spass]
vielleicht koennte man das ganze auch ueber matrizen machen und als bewertungskriterium nehmen wir determinanten http://www.multimediaxis.de/images/s...old/1/ugly.gif
Die ergebnisse waeren unvorhersehbar \o/
[/Spass]
20.06.2005, 09:58
Feenstaub

Zitat:

Zitat von Jesus_666

@Feenstaub: Auch eine automatische Schwierigkeitsgradanpassung funktioniert in groben Zügen nach dem Prinzip - und die gibt es.

A) Bitte benenne mir drei bekannte Spiele, die eine solche dynamische Schwierigkeitsgradanpassung haben. Mir persönlich ist kein kommerziell erfolgreiches Game bekannt, dass so etwas anbietet. Btw, dann könnte man also extra schwachsinnig spielen, um sich Vorteile zu verschaffen???

B) Anpassung des Schwierigkeitsgrades... entweder statisch auswählbar oder aber dynamisch abhängig von der Qualität des Spielers hat imo überhaupt nichts mit einer lernfähigen KI zu tun. Es sind vorgefertigte Skripte, die bei vorbestimmten Ereignissen abgearbeitet werden. Ein Spiel besitzt in meinen Augen dann eine lernfähige KI, wenn es von dem Spieler gekauft und installiert wird... und sich BEIM SPIELEN ein vollkommen neue Art der Ereignisbehandlung realisiert (zB kleine Skripte von der KI "selbständig" entwickelt), wie es diese auf den Rechnern der Entwickler nie gegeben hat.

@Ineluki:

*Nase kraus* Schön, dass du nicht besoffen warst. Muss ich mir also jetzt Sorgen machen? ;) Militaerische Prioritaet? Wichtigkeit und Hyperfläche? Potentialfeld? Gradient? Hm... ich bin natürlich beeindruckt über dein theoretisches Fachwissen... aber ich selber hab' da irgendwie immer Schwierigkeiten, mich entsprechend zu unterhalten. Ich mag es, wenn man die Dinge in einer klaren, einfachen und praktischen Form darlegt, die auch Aussenstehende zumindest einen Hinweis geben, worüber hier gesprochen wird. Aber das kann ja zum Glück jeder für sich entscheiden.

Küsschen,
Feenstaub.
20.06.2005, 12:55
Jesus_666

Zitat:

Zitat von Feenstaub

A) Bitte benenne mir drei bekannte Spiele, die eine solche dynamische Schwierigkeitsgradanpassung haben. Mir persönlich ist kein kommerziell erfolgreiches Game bekannt, dass so etwas anbietet. Btw, dann könnte man also extra schwachsinnig spielen, um sich Vorteile zu verschaffen???

Ich glaube, mich entsinnen zu können, daß Q3A so was hatte, bin mir aber nicht so ganz sicher. Spiele mit moderner KI haben eine gute Chance, mich nich zu interessieren, weil auch der Rest zu modern ist.

Zitat:

B) Anpassung des Schwierigkeitsgrades... entweder statisch auswählbar oder aber dynamisch abhängig von der Qualität des Spielers hat imo überhaupt nichts mit einer lernfähigen KI zu tun. Es sind vorgefertigte Skripte, die bei vorbestimmten Ereignissen abgearbeitet werden. Ein Spiel besitzt in meinen Augen dann eine lernfähige KI, wenn es von dem Spieler gekauft und installiert wird... und sich BEIM SPIELEN ein vollkommen neue Art der Ereignisbehandlung realisiert (zB kleine Skripte von der KI "selbständig" entwickelt), wie es diese auf den Rechnern der Entwickler nie gegeben hat.

Ich habe nur angemerkt, daß es in etwa nach dem gleichen Grundschema verläuft (Daten sammeln, mit Sollwerten vergleichen, Arbeitsparameter anpassen)

Zitat:

*Nase kraus* Schön, dass du nicht besoffen warst. Muss ich mir also jetzt Sorgen machen? ;) Militaerische Prioritaet? Wichtigkeit und Hyperfläche? Potentialfeld? Gradient? Hm... ich bin natürlich beeindruckt über dein theoretisches Fachwissen... aber ich selber hab' da irgendwie immer Schwierigkeiten, mich entsprechend zu unterhalten. Ich mag es, wenn man die Dinge in einer klaren, einfachen und praktischen Form darlegt, die auch Aussenstehende zumindest einen Hinweis geben, worüber hier gesprochen wird. Aber das kann ja zum Glück jeder für sich entscheiden.

Er hat sich so ausgedrückt, wie Fachleute das nun mal tun: Mit dem korrekten Fachjargon. Letzenendes läuft es eben auf das hinaus, was ich gepostet habe... Abgesehen davon, daß die Matrix natürlich problemlos mehrdimensional sein könnte (was dann eine Hyperfläche wäre). Ein Gradient ist an sich nichts anderes als ein Verlauf: Am einen Ende ist viel und am anderen wenig.

Das funktioniert überall: Fast niemand könnte aus dem Stehgreif einen stimmlosen postalveolaren Frikativ vormachen - aber den Sch-Laut kennt (zumindest im deutschsprachigen Raum) jeder. Linguisten bevorzugen trotzdem die erste Form, weil sie präzise ist.
Anderes Beispiel: Für den theoretischen Informatiker dienen Regexps dazu, eine formale Sprache zu beschreiben, die zu einem deterministischen endlichen Automaten äquivalent ist, mit dem man ein Eingabewort überprüfen kann. Für alle anderen ist ein Regexp ein Ding, das Text erkennt.
20.06.2005, 14:25
MagicMagor

Ja da hat sich ja eine schöne Diskussion entwickelt =).

Ich wollte mal melden wie ich mich jetzt, erstmal, entschieden habe.

Ich denke ich werde eine Mischung aus Inelukis Ansatz (mathematische Berechnung der Wichtigkeit von Feldern) und vorgefertigten Skripten nehmen.
Die beiden wichtigsten Dinge, die die KI leisten soll, sind für mich:
- Sinnvolle Aktionen, die auch zusammendhängend einen Sinn ergeben
- Eine gewisse Varianz im Spiel
Das die KI sich dem Spieler anpaßt und "lernt" ist zwar eine nette Sache, wenn sie nebenher anfällt, aber nicht mein primäres Ziel.

Ich werde wohl nach Lukis Ansatz jedem Feld eine strategisch/militäriche Bedeutung geben, sowie eine Bedeutung für jede Wirtschaftsgruppe (Baumaterial, Grundmaterial, Luxusgut1 etc..). Anhand dieser Bedeutung und der Entsprechenden Berechnung, wird die KI dann entscheiden wo sie ihre Einheiten stationiert und wo sie Gebäude baut.
Bestimmte Faktoren dieser Berechnung werden durch vorgefertigte Skripte vorgegeben bzw. leicht variiert. Dadurch kann ich der KI eine gewisse Persönlichkeit geben (eher militärisch, eher defensiv, eher wirtschaftlich).
Global, bei der Auswahl was überhaupt gemacht wird, werden die Bedeutungen der einzelnen Bereiche gegeneinander abgewogen. Neben der Persönlichkeit der KI, spielt hier auch die Rundenzahl, sowie der Status der anderen Spieler eine Rolle. (Wenn der Gegner extrem aufrüstet, investier ich auch lieber etwas mehr ins Militär)

Diese ganzen Profiltechnischen Bewertungen werden wohl beim Start des Spiels aus einem bestimmten Bereich zufällig gewürfelt. Das sollte erst einmal für die nötige Varianz von Spiel zu Spiel sorgen.
Das schwierigste ist hier nur das finden der richtigen Formeln, wenn man diese einmal hat, ist die Umsetzung recht simpel.
20.06.2005, 14:31
Jesus_666

Eine Frage: Werden deine KI-Spieler omniszient (= sie wissen immer, welche Einheiten der Spieler wo hat) oder müssen sie ihr Wissen genau wie menschliche Spieler sammeln?
20.06.2005, 14:50
MagicMagor

Die KI-Spieler kennen jederzeit die komplette Karte und den Aufenthaltsort sämtlicher Armeen. Ich glaube ich gehe sogar soweit, daß auch menschliche Spieler dieses Wissen haben.
Damit verliere ich zwar das Spielmoment der Entdeckung (bzw schwäche es extrem ab), aber es spart einerseits Aufwand (gut das wär nich so viel), und der Spieler kann sich mehr auf die strategischen und wirtschaftlichen Aspekte konzentrieren.

Alternativ wäre ein Entdecken möglich, wobei es keinen Fog of War gibt. Also was einmal entdeckt wurde, bleibt für immer voll sichtbar.

Ein bisl Cheaten ist für die KI ja akzeptabel =).
20.06.2005, 16:04
Ineluki

@Feenstaub ....

Wenn du willst, gebe ich dir gerne einen ausfuehrlicheren Bericht ueber das, was ich meine, allerdings stehen die Fachtermini auch in nahezu jedem Buch ueber hoehere Mathematik, nur dann meist wesentlich umfassender ... ^__^

Was das Anpassen von Parametern vs neue Algorithmen angeht, muss ich dir leider widersprechen ... ich halte sehr wohl die Neubewertung von Parametern fuer einen Vorgang der Lernfaehigkeit. Wenn du herausfindest, dass "Dallmayer Prodomo" besser schmeckt als "Jacobs Kroenung" (was ein Lerneffekt ist) hat diese Erkenntnis trotzdem ihren Wert (und Einfluss auf dein Verhalten), auch wenn du nicht den Algorithmus des Kaffeekochens veraenderst. Man wag vielleicht sogar soweit gehen und behaupten, dass das Sammeln von Erfahrungswerten einen wesentlich groesseren Anteil an unserem eigenen Lernen ausmacht, als die Variation von Algorithmen. Ein Bubblesort bleibt z.B. ein Bubblesort, egal in welcher Sprache man ihn schreibt. Das er dann aber auch konkret in der Sprache funktioniert, basiert einzig und allein auf deinem (Parameter)Erfahrungsschatz mit der jeweiligen Sprache. Ein einfacheres Beispiel waere, dass Stahl in der Regel haerter als Glas ist, Gummi jedoch nicht, weshalb man idR mit einem Stahlhammer ein Fenster einschlagen kann, nicht jedoch mit einem Gummihammer. Der Algorithmus ist in beiden Faellen der selbe, das Resultat ist ganz unterschiedlich. Wenn die KI anfangs diesen Unterschied nicht weiss, wird sie beide Varianten ausprobieren, und schliesslich zu dem Ergebnis kommen, es ist effektiver den Stahlhammer zu nehmen, wodurch sie etwas gelernt hat.

Ich denke, dass eine lernfaehige KI nicht unbedingt Algorithmen veraendern muss. Um sie als lernfaehig einzustufen ist das hinreichende Kriterium, dass sie ihre Spielparameter anpassen kann, um danach besser zu spielen.
23.06.2005, 09:40
Feenstaub

Zitat:

Zitat von Ineluki

Ich denke, dass eine lernfaehige KI nicht unbedingt Algorithmen veraendern muss. Um sie als lernfaehig einzustufen ist das hinreichende Kriterium, dass sie ihre Spielparameter anpassen kann, um danach besser zu spielen.

Nein, guter Ineluki, über diese Brücke gehe ich (vorerst) nicht.

Erstmal habe ich nicht gesagt, dass die KI zwangsläufig Algorithmen verändern muss, sondern lediglich ein Beispiel für ein mögliches Kriterium echten Lernens gegeben.

Und eine vorprogrammierte Spielanpassung ist in meinen Augen keine lernfähige KI. Wenn ich das Spiel zB so programmiert habe:

Wenn der Gegner 10 Wachtürme gebaut hat, dann benutze Schwierigkeitsgrad 3.
Bei Schwierigkeitsgrad 3 werden von der KI mehr Züge vorrausberechnet und das Spielverhalten wird aggressiver.
Aggressiveres Spielen heisst, sich mehr auf die Kriegerherstellung konzentrieren.
Mehr auf die Kriegerherstellung konzentrieren heisst: Auf einen Handwerken kommen drei Krieger.

Du siehst, in jedem Satz habe ich eine schwammige Aussage gemacht. Diese muss dann zwangsläufig irgendwo anders im Programmcode/Script definiert sein. Erst wenn eins dieser Sachen wegfällt und beim Spieler am Rechner von der KI irgendwie definiert werden würde... wäre das ein Anfang von wirklicher Intelligenz. Wenn sie das nun noch so definiert, dass es zu einem Ziel führt (unerheblich ob Sieg oder Niederlage), könnte man es als lernfähig einstufen.

Solange die KI in einem Spiel nur so gut ist, wie der Programmierer es zu entwerfen vermochte ... und mom haben wir nichts anderes (vielleicht wird Spore daran was ändern) ... solange ist es für mich keine lernfähige KI.

"Um sie als lernfaehig einzustufen ist das hinreichende Kriterium, dass sie ihre Spielparameter anpassen kann, um danach besser zu spielen."

Bitte definiere "Spielparameter anpassen" und "besser". Meinst du nun statische Variablenanpassung OHNE Lerneffekt (so, wie ich es oben beschrieben habe) oder dynamische Generierung der Variablenanpassung MIT Lerneffekt. Sollte ersteres zutreffen, bitte ich um eine bessere Begründung. Sollte Letzteres zutreffen, dann hast du mir also doch zugestimmt und rechtgegeben. ;)

Küsschen,
Feenstaub.
23.06.2005, 12:24
DFYX

Also mal meine persönliche Definition von "lernender KI":

Eine lernende KI wertet bisherige Erfahrungen/Ereignisse aus. Sollte sie wieder in eine ähnliche Situation kommen, entscheidet sie sich für die Vorgehensweise, die bisher am erfolgversprechendsten war. Im Lauf der Zeit kann sich die KI durch neue Ereignisse auch mehr Vorgehensweisen aneignen.

Dazu reicht eben das Verändern von ein paar Parametern nicht unbedingt. Die sind nur das Ergebnis. Was eine lernende KI ausmacht, ist WIE sie die Parameter verändern muss.

Einen Ansatz zur praktischen Umsetzung hab ich ja schon gepostet. Ich behaupte nicht, dass das der einzig richtige oder auch nur EIN richtiger Ansatz ist. Es ist nur die Methode, wie ICH es probieren würde. Wenn es nicht funktioniert, habe ICH wieder was gelernt und so schließt sich der Kreis.
23.06.2005, 18:21
Ineluki

@Feenstaub

Ich hab nie gesagt, dass es nach dem fall "wenn A, dann B" vorgegeben sein soll ...
Ich habe gemeint, dass er z.B. Truppen gegen den Gegner schickt, und das Ergebnis der Kaempfe auswertet. Verlief der Kampf fuer seine Truppen erfolgreich, erhoeht er den "Wert" der Truppe in Bezug auf die verwendete Truppe des Gegners, im Verlustfall erniedrigt er den "Wert". So wird die KI von alleine lernen, welche Einheiten gegen welche anderen Einheiten besonders stark sind, bzw selche Einheitenkombinationen sinnvoll sind.