# KI in rundenbasiertem Strategiespiel



## Evolver (15. Dez 2009)

Ich schreibe eine Art rundenbasiertes "Risiko"-Spiel im Weltraum. Die Regeln sind zunächst noch sehr einfach:
- Jede Partei besitzt zu Beginn genau ein System und es gibt weitere neutrale Systeme.
- In jedem System, das einer Partei gehört, wird pro Runde ein Schiff produziert.
- Schiffe können zu anderen Systemen geschickt werden und benötigen eine von der Entfernung abhängigie Zeit an Runden, diese zu erreichen.
- Um neutrale Systeme zu erobern, reicht es bereits ein einzelnes Schiff zu schicken.
- Erreichen Schiffe unterschiedlicher Parteien gleichzeitig ein System, kämpfen sie gegeneinander und wer am Ende Schiffe übrig behält, ist neuer Besitzer des Systems. Gleiches gilt auch, wenn eine Partei Schiffe zum System einer anderen Partei schickt.
- Eine Partei gilt als vernichtet, sobals sie keine Schiffe und keine Systeme mehr besitzt.


Jetzt stellt sich mir die Frage, wie ich die KI aufbauen könnte, also wie sie handeln soll. Es gibt hier totz der wenigen Regeln viele mögliche Strategien. So ist es z.B. sicher wichtig, schnell viele neutrale Systeme einzunehmen, um an mehr Schiffe zu gelangen. Andereseits kann eine anfänglich starke Verteilung der Flotte auch riskant sind, wenn der Gegner eine System in der Nähe besitzt. Dann ist die Frage zu klären, ob sich der Computer nahe Systeme greifen soll, oder auch weiter weg einen "Außenposten" errichtet. Diese Überlegungen müssen natürlich immer Abhängig von der Lage der eigenen Systeme und der Systeme der Gegner gemacht werden ... usw.

Ich freue mich auf eure Ideen.


----------



## objcler (15. Dez 2009)

Es gibt nicht DIE KI. Eine KI hat immer Attribute. Du hast ja schon erkannt, dass es verschiedene Strategien gibt. Eine Strategie ist wieder nur eine Ansammlung von Eigenschaften und entsprechenden Werten. Ich denke der erste Schritt den du machen solltest ist das Spiel (es gibt ja viele fertige Implementationen davon) ausreichend lange selbst zu spielen. Notiere dir dabei genau, welche Klassen von Strategien es gibt und wie du diese beschreiben würdest.

Wichtig ist auch, dass du am Ende nicht EINE "KI"-Klasse hat, die alles macht. Splitte das Ganze auf in "KI", "Strategie". Du implementierst dann eine allgemeine KI, der du eine Strategie zuweist. Das vereinfacht das Ganze dramatisch.

Später kannst du dann einen "Detector" einbauen, der sich den aktuellen Spielstand anschaut und entscheidet, welche verfügbare Strategie jetzt wohl am besten wäre.

Deine KI wird dann mit jeder zusätzlich implementierten Strategie besser, da sie mehr Auswahl hat.

Das sind nur ein paar Tipps von einem, der schon 2-3 KIs implementiert hat.


----------



## SlaterB (15. Dez 2009)

> Deine KI wird dann mit jeder zusätzlich implementierten Strategie besser, da sie mehr Auswahl hat.

das passiert aber auch nicht automatisch sondern erfordert Arbeit, dass es so passt,
sich eine Strategie auszusuchen und zu verfolgen reicht teilweise eh nicht, selbst wenn man es jede Runde neu macht,

das 'Imperium' kann verschiedene Grenzen haben, in die eine muss man sich noch weiter ausweiten, 
in zwei anderen warten unterschiedlich starke Gegner, die zum einen Angriff, zum anderen Verteidigung erfordern,
sowas kann man unendlich komplex bauen und kaum allgemein besprechen, außer in Dimension eines 500 Seiten-Buches
(Tipps allerdings von einem, der sowas noch nicht implementiert hat  )


----------



## Evolver (15. Dez 2009)

Ist schon klar, dass es jetzt nicht nur eine mögliche Umsetzung für die KI gibt. Aber ich sage der einfachheit halber trotzdem weiter "die KI". 

Also soweit ist es klar, die KI muss je nach Lage unterschiedliche Strategien verfolgen können. Sie muss anderes reagieren, wenn 3 benachbarte Systeme vom Gegner besetzt sind, als wenn es nur eines ist oder der Gegner weit entfernt ist.



objcler hat gesagt.:


> Ich denke der erste Schritt den du machen solltest ist das Spiel (es gibt ja viele fertige Implementationen davon) ausreichend lange selbst zu spielen. Notiere dir dabei genau, welche Klassen von Strategien es gibt und wie du diese beschreiben würdest.


Das möchte ich eigentlich vermeiden. Ich fände es besser, erstmal eine einfach KI zu implementieren und diese dann nach und nach vielleicht zu verbessern. [Und genau für diese einfach KI suche ich hier grundlegende Strategien.


----------



## Marco13 (15. Dez 2009)

Du willst ein Programm schreiben, das etwas besser macht, als du, weißt aber selbst nicht, wie du es machen würdest - Hui  Ich denke, ein paar Grundideen zu entwickeln wird wohl nötig sein. Aber wenn es eine Triviale KI sein soll: 
- Es gibt N Systeme
- Es gibt K<N Spieler
- Besetze am Anfang N/K Systeme
- Baue Raumschiffe wie blöd
- Wenn man X Raumschiffe hat, greife den nächstgelegenen Gegner an.

Interessant wird es, wenn du dann mal N verschiedene KIs über Nacht in N*(N-1)/2 Partien gegeneinander spielen läßt, und nachsiehst, wer am nächsten morgen noch lebt


----------



## Evolver (15. Dez 2009)

Marco13 hat gesagt.:


> Du willst ein Programm schreiben, das etwas besser macht, als du, weißt aber selbst nicht, wie du es machen würdest - Hui


LOL ... Du triffst den Nagel auf den Kopf. Ich habe halt mehr Interesse am Entwickeln als am Spielen. Vielleicht sollte ich es wie "Robocode" machen. Anstatt den Fokus auf die Entwicklung des Spiels zu legen, passe ich nur ein paar Schnittstellen an und tue ich so, als gänge es bei dem Programm um die Herausforderung, eine gute KI zu schaffen. Dann stelle ich es ins Netz. Danach brauche ich nur noch zu warten, bis es von ein paar Informatikstudenten entdeckt wird, die das als Herausforderung sehen. :lol:


----------



## Empire Phoenix (16. Dez 2009)

Ei interessatner ansatz bei wenigen regeln wäre auch ein neuronales netz and das interface zu packen. Dann muss nur die "belohnung"/"bestrafung" richtig eingestellt werden und gucken  was passiert. (Es ist aber nicht so einfach wie es jetzt klingt, hat aber den vorteill das die Ki zum teil sich selber neue Strategien beibringen kann))


----------



## Evolver (16. Dez 2009)

Künstliche neuronale Netze fand ich schon immer sehr interessant. Ich bin ihnen im Studium begegnet und habe mich auch privat kurz damit beschäftigt. Die theorie war mir dann zwar recht gut klar, ich muss aber gestehen, dass ich nie richtig verstanden habe, wie ich das in der Praxis für ein konkretes Problem umsetzen könnte.


----------



## ThreadPool (16. Dez 2009)

Empire Phoenix hat gesagt.:


> Ei interessatner ansatz bei wenigen regeln wäre auch ein neuronales netz and das interface zu packen. Dann muss nur die "belohnung"/"bestrafung" richtig eingestellt werden und gucken  was passiert. (Es ist aber nicht so einfach wie es jetzt klingt, hat aber den vorteill das die Ki zum teil sich selber neue Strategien beibringen kann))



Naja, ohne die Mathematik hinter KNNs zu kennen wird man nicht erfassen welche "Leistungsfähigkeit" sie überhaupt haben, ob das genug ist und vorallem WIE man ein derartiges Netz aufbaut. Zudem sind KNNs nur eine Möglichkeit "Verhalten" zu simulieren. Es gibt noch dutzende andere und je nach Anwendung kann man eine besser verwenden oder die andere oder eine Kombination mehrerer. Und damit überhaupt was brauchbares rauskommt, gilt hier das selbe wie für KNNs man muss es verstanden haben, was da passiert. 

Die Artikel zu "echten" Games auf Game AI for Developers&mdash; AiGameDev.com finde ich immer recht spannend, so bekommt man ungefähr eine Idee welche Techniken wo verwendet werden. Die Übersicht über die Themen der Game AI Conference 2009 findest du z.B. hier GameDev.net -- Paris Game AI Conference

KI ist ein unglaublich großes Thema welches auch sehr viel Wissen in vielen Bereichen erfordert du wirst also sehr lange damit beschäftigt sein.


----------



## spyboot (18. Dez 2009)

Eine KI kann alle Möglichkeiten der naächsten Runden durchgehen oder Rechnerisch vorgehen:
Also als Beispiel denken wir uns einfach mal 3 Planeten die unterschiedliche Mengen von Raumschiffen zur Verfügung haben:
2 davon sind menschlich einer hat eine KI.
Jetzt sucht sich die KI sein Opfer aus:
Entfernung*Stärke 
Jetzt kann er seine Truppen zum Schwächsten fliegen lassen was bedeuten würde dass er sich gegen die verbliebenen Starken Planeten evtl. Verteidigen müsste. Dass heißt seine zurückbleibenden Truppen sollten mindestens 40% (mann kann auch andere Zahlen nehmen und die zb. von der Spieleranzahl abhängig machen) aller auf dem Spielfeld feindlicher Truppen betragen. Wenn er dann aber zu schwach wäre um den Zielplaneten anzugreifen lässt er es lieber (Mann berücksichtige auch dass Wachstum des Zielplaneten in der Zeit des Fluges). dass ist eine art Punktesystem und lässt sich eig. auf fast jede Aufgabe anwenden.
Mann könnte auf diese weise auch bestimmen was er Überhaupt tun soll (Rohstoffe sammeln, Bauen, Angreifen usw.).

Alternativ kann er auch alle Spielzugmöglichkeiten der nächsten Runden durchgehen und sich den besten aussuchen.


----------



## Marco13 (18. Dez 2009)

Wenn's in die Details gehen soll, hier noch eine Buchempfehlung: Artificial Intelligence: A Modern Approach


----------

