#1 20.05.2005 12:20:13

Chris
ExtremeMember
Ort: Erlangen, Bay
Registriert: 24.01.2005
Beiträge: 694
Web-Seite

Einheiten-KI im Strategiespiel

Ich mache jetzt einfach mal einen KI Thread auf in dem das ganze is dem Nebel-des-Krieges-Thread weiterdiskutiert werden kann.

Es geht um den Geschützturm, der folgende Probleme hat:

1. Woher weiß er ob jemand in seiner Reichweite ist?
2. Was macht er wenn etwas (feindliches) in seiner Reichweite ist?
3. Was macht er wenn mehrere (feinliche) Objekte in seiner Reichweite sind?

mfg Chris


Nimm meinen Rat an - ich brauch ihn sowieso nicht

Offline

 

#2 20.05.2005 12:30:18

@uzingLG
Member
Registriert: 01.05.2005
Beiträge: 94

Re: Einheiten-KI im Strategiespiel

1. Das findet er mit einer Funktion heraus, die den Abstand zwischen ihm und den feindlichen Einheiten misst.

2. Er nimmt den Gegner unter Feuer.

3. Er bittet die übergeordnete KI um ein Ziel (könnten ja auch andere Türme schon auf eines feuern -> alle auf einen oder er feuert auf das stärkste, das nicht unter Beschuss steht, ...). Eine einfache KI könnte auch einen Zufallsgenerator das Ziel wählen lassen.

Offline

 

#3 20.05.2005 12:37:09

Chris
ExtremeMember
Ort: Erlangen, Bay
Registriert: 24.01.2005
Beiträge: 694
Web-Seite

Re: Einheiten-KI im Strategiespiel

1. Ich wollte die Objektgrenze pro spieler so auf 400 setzen. SpielerZahl 8. Anzahl der Tests: (8*400)^2 = 10240000

2. Ok, das sehe ich ein.

3. Und darum geht es mir. Welche Strategie angreifende Einheiten unter beschuss zu nehmen ist die effinzienteste?

mfg Chris


Nimm meinen Rat an - ich brauch ihn sowieso nicht

Offline

 

#4 20.05.2005 12:47:36

@uzingLG
Member
Registriert: 01.05.2005
Beiträge: 94

Re: Einheiten-KI im Strategiespiel

1. Du musst dafür die Karte in Sektoren aufteilen. Ein Turm prüft dann nur seinen Sektor und die 8 Nachbarn davon (oder auch die Nachbarn der Nachbarn, wenn die Sektoren zu klein sind). Der Sektor, in dem sich eine Einheit aufhält, wird nur ermittelt, wenn sie gerade entsteht oder sich bewegt.
[EDIT]ARGH! Mann, bin ich blöd! Das mit den Sektoren ist schon sinnvoll, aber man kann auch die Ziele nur dann überprüfen, wenn der Turm gerade entsteht (oder das Ziel) oder sich das Ziel bewegt (oder die eigene Einheit, es werden wohl kaum ausschließlich Türme sein).

2. Fein.

3. Also ich würde alle auf den stärksten Gegner feuern lassen, und dann auf den nächsten, usw... bis keiner mehr da ist (oder kein Turm mehr da ist).

Offline

 

#5 20.05.2005 13:10:37

Coolcat
ProGuru
Ort: Aachen, NRW
Registriert: 24.01.2005
Beiträge: 2780
Web-Seite

Re: Einheiten-KI im Strategiespiel

zu 3. Es sollten aber nicht mehr als z.B. 5 Einheiten auf eine einzige feindliche Einheit feuern. Die Einheit ist dann so schnell zerstört, dass weitere Einheiten sich lieber ein neues Ziel suchen sollten.


My software never has bugs. It just develops random features.

Offline

 

#6 20.05.2005 13:16:17

@uzingLG
Member
Registriert: 01.05.2005
Beiträge: 94

Re: Einheiten-KI im Strategiespiel

Nicht überall! Z. B. wenn Infanteristen gegen einen Superpanzer kämpfen... man muss auch auf die Stärke achten.

Offline

 

#7 20.05.2005 14:04:36

Chris
ExtremeMember
Ort: Erlangen, Bay
Registriert: 24.01.2005
Beiträge: 694
Web-Seite

Re: Einheiten-KI im Strategiespiel

D.h.
Ich schieße immer auf die stärkste Einheit, bis die platt ist, oder schieß ich auf alle kleinen Einheiten.

beides hat in meiner Vorstellung Vor- und Nachteile.

mfg Chris

edit:

kann man (realistisch gesehen) eine KI programmieren, die lernt?
also die sich anschaut wie der Mensch spielt das ganze interpretiert (agressiv - passiv Strategie etc...) und berwertet?


Nimm meinen Rat an - ich brauch ihn sowieso nicht

Offline

 

#8 20.05.2005 14:07:54

Coolcat
ProGuru
Ort: Aachen, NRW
Registriert: 24.01.2005
Beiträge: 2780
Web-Seite

Re: Einheiten-KI im Strategiespiel

Zufall oder der Spieler kann es einstellen....


My software never has bugs. It just develops random features.

Offline

 

#9 20.05.2005 14:12:18

@uzingLG
Member
Registriert: 01.05.2005
Beiträge: 94

Re: Einheiten-KI im Strategiespiel

Also, ich würde auch die Distanz und Reichweite des Gegners berücksichtigen.

Offline

 

#10 20.05.2005 14:19:33

Chris
ExtremeMember
Ort: Erlangen, Bay
Registriert: 24.01.2005
Beiträge: 694
Web-Seite

Re: Einheiten-KI im Strategiespiel

kann man (realistisch gesehen) eine KI programmieren, die lernt?
also die sich anschaut wie der Mensch spielt das ganze interpretiert (agressiv - passiv Strategie etc...) und berwertet?
Und dann auf individuelle Situationen anpasst?


Nimm meinen Rat an - ich brauch ihn sowieso nicht

Offline

 

#11 20.05.2005 14:39:01

artzuk
GodlikeMember
Ort: Leipzig
Registriert: 24.01.2005
Beiträge: 1164

Re: Einheiten-KI im Strategiespiel

@Chris: Man kann solch eine KI programmieren - ist aber äußerst schwer. Ich glaube es gibt sogar schon Spiele (mir fällt blos grad keins ein), die das teilweise machen - könnte aber auch nur so von denen gesagt sein und im Endeffekt lernen die gar nicht.
Jedenfalls kann man die KI in paar Punkten an den Spieler anpassen ... ganz einfaches Beispiel: Wenn der Spieler gerne mit Fliegern angreift, dann schön Flugabwehr bauen.

Wenn ich mein Strategiespiel machen sollte, dann mache ich eine halb dumme KI. Türme schießen einfach auf die nächst beste Einheit, vorausgesetzt diese ist nicht getarnt. Ich möchte den Spieler so richtig ins schwitzen kommen lassen, weil er sehr viel selber unternehmen muss.
Einfacher für mich, schwerer für den Spieler, cooler fürs Spielprinzig big_smile


Mein kleiner .NET Blog: http://artzuk-interactive.de/

Offline

 

#12 20.05.2005 14:42:38

Chris
ExtremeMember
Ort: Erlangen, Bay
Registriert: 24.01.2005
Beiträge: 694
Web-Seite

Re: Einheiten-KI im Strategiespiel

klingt lustig, aber ich rede z.T. auch von der GegnerKI, also der Spieler der vom Computer kontrolliert wird, einheiten baut, angreift etc... das ist noch ein großer Stein in meinem Schotterweg zu Strategiespiel.

mfg Chris


Nimm meinen Rat an - ich brauch ihn sowieso nicht

Offline

 

#13 20.05.2005 15:10:27

DerPeer
GodlikeMember
Ort: Berlin
Registriert: 04.02.2005
Beiträge: 1291

Re: Einheiten-KI im Strategiespiel

Zitat:


aber ich rede z.T. auch von der GegnerKI

Man kann versuchen, sowas lernbar zu gestalten, wird aber sehr aufwändig und frustrierend. Für solche Lernaufgaben muß man sehr viele Parameter einstellen, und dieses Einstellen kann länger dauern als die KI konventionell auszuprogrammieren.

Herkömmliche Verfahren brauchen auch sehr lange für soetwas. Die probieren sozusagen alles aus, und am Ende eines jeden Spiels muß man bewerten, wie gut das jetzt war. Dieses Alles-Ausprobieren kann SEHR viel sein.

Wenn Du eine KI willst, die während EINES Spiels sich anpaßt, dann halte ich das für ausgeschlossen, es sei denn, Du findest eine toughe Heuristik dafür.

Offline

 

#14 20.05.2005 15:14:58

DerPeer
GodlikeMember
Ort: Berlin
Registriert: 04.02.2005
Beiträge: 1291

Re: Einheiten-KI im Strategiespiel

Zitat:


Woher weiß er ob jemand in seiner Reichweite ist?

Achja, diese Idee mit den Einheiten, die sich in ein Array eintragen, das so groß wie der ganze Plan ist, war doch gut. Wieso nicht daran festhalten?

Außerdem: 10.000.000 Überprüfungen muß man ja nicht in jedem Frame machen. Wenn mein Panzer eine Sekunde braucht, um zu erkennen, daß was in seiner Reichweite ist, dann ist das okay. Bei 50 FPS macht das 200.000 Abstandsabfragen pro Frame (maximal). Bei der Hälfte der Einheiten sind das nur noch 50.000. Wenn man dann nach den quadrierten Abständen fragt, geht´s noch schneller. 50.000 ist akzeptabel.

Offline

 

#15 20.05.2005 15:31:51

artzuk
GodlikeMember
Ort: Leipzig
Registriert: 24.01.2005
Beiträge: 1164

Re: Einheiten-KI im Strategiespiel

Man kann aber die KI sozusagen lernen lassen, welche Waffenarten bevorzugt genommen werden und dagegen halten. Das kann man schon KI nennen, die lernt  :p


Mein kleiner .NET Blog: http://artzuk-interactive.de/

Offline

 

#16 20.05.2005 16:36:26

Lotipats
UltraMember
Registriert: 17.05.2005
Beiträge: 395

Re: Einheiten-KI im Strategiespiel

Ich weis nicht genau, wie bei dir die KI lernen soll, ob sie z.B. die Richtung, aus der sie angreift, wo der Spieler bevorzugt siedelt, welche Einheiten er bevorzugt nimmt, wie lange er warten sollte bis zum Angriff, einen Angriff erst abwarten und dann selber angreifen, ... oder was auch immer lernen soll.

Es gibt verschiedene Methoden, wie ein Computer sein Wissen vermehren kann. Aber mir faellt da nur ein Neuronales Netz ein. Grob gesagt, ist es ein (sehr) kleines und (sehr) vereinfachtes Abbild eines Gehirns, z.B. vom Menschen.

Es genau zu erklaeren, waere jetzt zu viel und ich weis auch nicht, ob jemand das moechte. Bei Interesse Nachfragen, ich denke aber, dass das lieber in einem neuen Thema gemacht wird.

Irgendwer hat mir gesagt, dass in UT 2003 (und 2004) ein Neuronales Netz in der "Kampagne" vorkommt. Dort lernt der Computer, wie der Spieler angreift und wo er verwundbar ist, ...
So dass er es immer schwerer in der Kampagne hat. Das Finale ist dann die Krönung des ganzen. Wenn jedoch jemand anderes das spielt, ist es fuer den einfach, da das Netz nicht schnell genug "umlernen" kann und falsch an die Sache heran geht.

Sonst ist mir nichts bekannt, wo das in Spielen vorkommt, sonst wird es fuer Sprach und Bilderkennung genutzt.

Also bei Interesse fragen, sonst ist auch gut.

LOTIPATS

Offline

 

#17 20.05.2005 16:48:17

artzuk
GodlikeMember
Ort: Leipzig
Registriert: 24.01.2005
Beiträge: 1164

Re: Einheiten-KI im Strategiespiel

So detailliert wäre echt der Hammer.
Aber kleine Features könntest du schon beibringen. Zum Beispiel könnte er auch lernen, nach welcher Zeit der Spieler so Panzer baut und könnte demzufolge entweder Mittel ergreifen, um das zu verhindern, oder schon Verteidungsmaßnahmen ergreifen.


Mein kleiner .NET Blog: http://artzuk-interactive.de/

Offline

 

#18 20.05.2005 17:21:34

Chris
ExtremeMember
Ort: Erlangen, Bay
Registriert: 24.01.2005
Beiträge: 694
Web-Seite

Re: Einheiten-KI im Strategiespiel

Zitat:

Aber mir faellt da nur ein Neuronales Netz ein.

also irgendwann will ich mein Spiel auch fertigbekommen...

das problem ist einfach nur, dass man bei einem neuen Spiel eben keine Taktiken kennt. also muss der Computer entweder welche erfinden oder aus vorgegebenen Teilen zusammenbasteln und bewerten.

mfg Chris


Nimm meinen Rat an - ich brauch ihn sowieso nicht

Offline

 

#19 20.05.2005 19:01:32

Coolcat
ProGuru
Ort: Aachen, NRW
Registriert: 24.01.2005
Beiträge: 2780
Web-Seite

Re: Einheiten-KI im Strategiespiel

dein Computergegner sollte einfach aus verschiedenen kategorien zufällig auswählen. Dadurch bekommst du viele unterschiedliche Taktiken. Bei bedarf kann man die Taktik auch ab und zu zufällig ändern. (sollte dann nur in einer kategorie sein)

Bereich 1:
· setzt auf Technologie und Forschung
· setzt auf Masse

Bereich 2:
· dezentrale Basis / Ressourcen. Er expandiert zu beginn extrem schnell um soviel Ressourcen wie möglich zu sichern. Das geht natürlich am Anfang auf Kosten der Basissicherheit. Dadurch das aber alle Gebäude mehrfach existieren ist er später fast unbesiegbar.
· Defensiv. Die Basis wird von anfang an voll ausgebaut und zur Festung.

Bereich 3:
· Frontalangriff-Taktik
· Angriff aus dem Hinterhalt
· kommt immer von mehrern Seiten gleichzeitig

Bereich 4:
· spezialisiert auf Luft / Bomber
· spezialisiert auf schwere Panzer
· spezialisiert auf leichte Panzer (beweglicher)
· setzt hauptsächlich die Superwaffen ein (Atomrakten, Hochenergieplasma, Ionenstrahlsatelit,...)

An dieser Liste muss man sicher noch ein wenig feilen, aber so in der Art könnte ne gute KI draus werden.

Coolcat


My software never has bugs. It just develops random features.

Offline

 

#20 20.05.2005 20:25:15

artzuk
GodlikeMember
Ort: Leipzig
Registriert: 24.01.2005
Beiträge: 1164

Re: Einheiten-KI im Strategiespiel

Ich würde aber den Gegner nicht auf einen Einheitentyp spezialisieren, weil sich der Spieler darauf einstellen könnte.


Mein kleiner .NET Blog: http://artzuk-interactive.de/

Offline

 

#21 20.05.2005 22:31:36

DerPeer
GodlikeMember
Ort: Berlin
Registriert: 04.02.2005
Beiträge: 1291

Re: Einheiten-KI im Strategiespiel

Jo, sowas geht natürlich. Auf diese Art kann man einen Berg von kleinen Regeln zusammentragen, die dann sicher ganz gut funktionieren.

Von wo greift der Feind am meisten an? -> Dort am meisten Verteidigung.

Hat er wenig Flugabwehr -> viele Flugzeuge bauen.

Baut er bevorzugt schwere, langsame Autos -> schnelle, wendige bauen.

Gibt es Zyklen im menschlichen Verhalten? -> Diese Lücken ausnutzen (wie auch immer man das jetzt macht).

Immer dort angreifen, wo die Verteidigung am schwächsten ist.

Einheiten vorher sammeln, niemals einzeln angreifen.

Man kann es sich auch einfach machen, und die KI allwissend proggen, also daß sie alles sieht, wohingegen der Mensch ja seinen Nebel des Krieges hat.

Edit: Ups! Da sind ja inzwischen einige Beiträge dazugekommen.

Offline

 

#22 21.05.2005 07:34:49

Lotipats
UltraMember
Registriert: 17.05.2005
Beiträge: 395

Re: Einheiten-KI im Strategiespiel

Hallo,

@Chris:
Ich glaube es geht vielen so, dass sie ihr Projekt irgendwann zuende bringen wollen. Natürlich ist ein Neuronales Netz langwierig im Wissen sammeln. Aber dafuer ist es relativ flexibel. Aber nur um einen Neuronalen Netz etwas beizubringen, muss du (oder Beta-Tester) nicht sonst wie oft spielen. Es reicht aus, wenn du Anfangswerte bestimmst und Endwerte die rauskommen sollen. Dann schreibst du ein Programm, dass die Werte so oft durchgeht, bis das Netz auf das kommt, was du als Endwerte ausgegeben hast. Du musst also den Computer nur rechnen lassen.
Aber Vorsicht, nicht "überlernen".

Hier sind aber noch andere Varianten, wie der Computer lernen kann. Das Beispiel stimmt wahrscheinlich nicht, ich habe es nur gewählt, weil ich denke, dass man es gut verfolgen kann.

Induktives Lernen basiert auf (vielen) Daten. Hier dienen Beispiele als Grundlage der Entscheidungen, es ist eine Art vorhersagen. Aus den gesammelten Daten werden Gemeinsamkeiten herreusgefiltert. Tritt nun etwas ein, was schon damals vor einer bestimmten Aktion kam, dann schliesst der Computer, dass diese Aktion geschehen wird.
Beispiel:
Soll der Computer eine Diagnose erstellen (meist Expertensysteme, aber egal), so vergleicht er meistens mit den "vorherigen" Patienten.
Hat unser Patient Magenschmerzen, Übelkeit und leidet unter Atemnot, so kann unser Computer eine Zinkvergiftung diagnostizieren, da auch viele andere Patienten, die diese Symptome hatten, zinkvergiftet waren.
Kommt jetzt jedoch noch Durchfall hinzu, so kann es eine andere Vergiftung sein, aber auch nur rein zufällig hervorgerufen sein.
Zum Schluss steht fest, ob die Regel, die der Computer angewand hatte erfolgreich war oder nicht. Das Ergebnis wird abgespeichert und beeinflusst somit das nächste verhalten.
War der Durchfall z.B. zufällig, so wird der Computer nächstes mal mehr die zufällige Variante in betrachtziehen.
Das Lernen ist somit eine Art Suchproblem.

Nun kann man aus diesen Daten Regeln ableiten. Z.B. Wenn Magenschmerzen und Übelkeit und Atemnot und nicht Durchfall, dann Zinkvergiftung.
Um damit Entscheidungen zu fällen brauch man Anfangswert bzw. Grundwissen. Die abzuleitenden Regeln müssen dabei aber möglichst einfach sein, damit der Computer diese finden kann.
Dies nennt sich "lernen mit der Versionenraum-Methode". Aus neuem wissen können neue Regeln erstellt werden, wenn sich eine Regel als nicht erfolgreich erweisst, koennen Regeln verwurfen werden.

Wenn man komplexere Regeln erhalten will, so greift man auf "Induktion von Entscheidungsbäumen" zurück.
Um zu einer Entscheidung zu kommen wird der Baum durchschritten. Dabei werden meist Ja-Nein Fragen (Bedingungen) gestellt, die der Computer dann beantwortet am Ende kommt der Computer zu einem Ergebnis.
An dem Beispiel. Zuerst kommt die Frage "Magenschmerzen" da unser Patient diese hat, folgt er dem "Ja-Ast". "Übelkeit" Ja, "Atemnot" Ja, "Durchfall" Nein. Zum schluss steht die Diagnose "Zinkvergiftung".
Um einen Algorithmus zu bekommen, wie sokche Entscheidungsbäume erstellt werden, einfach mal nach "ID3" suchen, er basiert auf Statistik.

Als letztes möchte ich nur noch die Genetischen Algorithmen erwähnen. Sie werden nicht nur zum lernen, sondern auch für versch. Suchprobleme genutzt.
Sie können auch als Evolutionsalgorithmen bezeichnet werden.

Ich weis nicht, ob du eine dieser Methoden gebrauchen kannst, aber das sind alle, die ich (halbwegs) kenne. Aber bei allen ist eine gewisses Grundwissen erforderlich. Ich denke nicht, das eine echt lernende KI in Strategiespielen benötigt wird. Ich denke einfache von dir aufgestellte Regeln (wie sie z.B. schon einige hier erwähnt haben) reichen aus. Wenn du aber umbedingt eine Art Lerneffekt haben willst, merke dir einfach Dinge, die der Spieler macht/nicht macht.

@DerPeer :
Ein Allwissende KI betrachte ich persönlich als unfair. Dadurch ist eine schwere KI leicht zu erstellen, aber man kann dies auch schnell herreusfinden (z.B. Gegner greift immer richtig an) und das könnte den Spieler verfrusten (meine Meinung!)

LOTIPATS

PS: Es gibt ein Buch "Die Kunst des Krieges", dass laut einer Zeitschrift fuer die KI von Strategiespielen genutzt wird. Es hat ein chinesischer Philosoph und General vor rund 2500 Jahren geschrieben. Sein Name war "Sun-Tzuin".

Offline

 

#23 21.05.2005 09:09:27

Coolcat
ProGuru
Ort: Aachen, NRW
Registriert: 24.01.2005
Beiträge: 2780
Web-Seite

Re: Einheiten-KI im Strategiespiel

Eine allwissende KI ist wirklich unfair....
Aber leider ist das in vielen Spielen so. So erzielen z.B. Schattengeneratoren in vielen Spielen gegen den Computer keine Wirkung. Würde man gegen einen Menschen spielen, würde er nichts merken bis man mitten in seiner Basis steht und anfängt zu feuern. Aber der Computer weiß trotzdem wo man ist und schießt....

Coolcat


My software never has bugs. It just develops random features.

Offline

 

#24 21.05.2005 09:45:43

Coolcat
ProGuru
Ort: Aachen, NRW
Registriert: 24.01.2005
Beiträge: 2780
Web-Seite

Re: Einheiten-KI im Strategiespiel

Also im Offtopic-Forum ist diese Diskussion etwas fehlplaziert. wink
Hab mal einfach nen neues Forum gemacht...

Coolcat


My software never has bugs. It just develops random features.

Offline

 

#25 22.05.2005 16:49:59

Chris
ExtremeMember
Ort: Erlangen, Bay
Registriert: 24.01.2005
Beiträge: 694
Web-Seite

Re: Einheiten-KI im Strategiespiel

Was ist eigentlich wichtiger:

A: Dass die KI auf jedem Möglichen weg versucht zu gewinnen

B: Dass die KI versucht so stark wie der Spieler zu spielen und so das Spiel ausgeglichnener macht.

???

mfg Chris


Nimm meinen Rat an - ich brauch ihn sowieso nicht

Offline

 

Brett Fußzeile

Powered by PunBB
© Copyright 2002–2005 Rickard Andersson