RISK Computer KI

Übersicht

Sonstiges

Smalltalk

	Trust Betreff: RISK Computer KI	So, Jan 13, 2013 4:38 Antworten mit Zitat
Hallo, ihr kennt doch sicher alle das Brettspiel "Risiko" und die äquivalenten PC-adaptionen davon. Mich würde es interessieren, wie man da ran gehen müsste, um eine halbwegs fordernde und intelligent reagierende KI zu entwerfen, die zudem unabhängig von der Map ist. Gäbe es nur eine Map, könnte man die KI auf bestimmte Felder prüfen lassen und dementsprechend reagieren lassen usw. . Aber gehen wir mal davon aus, dass es verschiedene, absolut unterschiedliche Maps gibt. Wie könnte man so eine KI am besten angehen? Jedes Feld durchgehen und überprüfen, ob es keines ist, welches sich im eigenen oder im Besitz des eigenen Teams befindet, daraufhin überprüfen wieviele feindliche Einheiten sich darauf befinden um die Bedrohung abzuschätzen? Nach welchen Kriterien sollte die KI entscheiden, in welche Richtung sie sich wie ausbreiten soll usw. Welche Felder sie nun als nächstes ausbaut, um sich zu verteidigen oder auch auf einen Angriff vorzubereiten usw. . Wie sollte sie reagieren, wenn ein Teammitglied in Schwierigkeiten ist und vor allem, wie erkennt sie das und woher weiss sie, welcher der Gegner dem Teammitglied so schwer zusetz? Ich würde mich auf Vorschläge, Tipps und Diskussionen über Pro und Kontra verschiedener Möglichkeiten freuen. G, Trust
Es gibt 10 Gruppen von Menschen: diejenigen, die das Binärsystem verstehen, und die anderen.

Trust

Betreff: RISK Computer KI

So, Jan 13, 2013 4:38
Antworten mit Zitat

Hallo,

ihr kennt doch sicher alle das Brettspiel "Risiko" und die äquivalenten PC-adaptionen davon.
Mich würde es interessieren, wie man da ran gehen müsste, um eine halbwegs fordernde und intelligent reagierende KI zu entwerfen, die zudem unabhängig von der Map ist.
Gäbe es nur eine Map, könnte man die KI auf bestimmte Felder prüfen lassen und dementsprechend reagieren lassen usw. .
Aber gehen wir mal davon aus, dass es verschiedene, absolut unterschiedliche Maps gibt.

Wie könnte man so eine KI am besten angehen?

Jedes Feld durchgehen und überprüfen, ob es keines ist, welches sich im eigenen oder im Besitz des eigenen Teams befindet, daraufhin überprüfen wieviele feindliche Einheiten sich darauf befinden um die Bedrohung abzuschätzen?
Nach welchen Kriterien sollte die KI entscheiden, in welche Richtung sie sich wie ausbreiten soll usw.
Welche Felder sie nun als nächstes ausbaut, um sich zu verteidigen oder auch auf einen Angriff vorzubereiten usw. .
Wie sollte sie reagieren, wenn ein Teammitglied in Schwierigkeiten ist und vor allem, wie erkennt sie das und woher weiss sie, welcher der Gegner dem Teammitglied so schwer zusetz?

Ich würde mich auf Vorschläge, Tipps und Diskussionen über Pro und Kontra verschiedener Möglichkeiten freuen.

G,
Trust

Es gibt 10 Gruppen von Menschen: diejenigen, die das Binärsystem verstehen, und die anderen.

	Tritium	So, Jan 13, 2013 12:36 Antworten mit Zitat
Hi, ich kenne Risiko zwar, hab aber das genaue Regelwerk nicht im Kopf. Trotzdem ist das hier vielleicht schonmal ein Ansatz: Du könntest Deiner KI mehrere Charakterzüge verleihen, die jeweils in z.B. drei Abstufungen (gering, normal, stark) existieren: Expansionswillen, Hilfsbereitschaft/Egoismus, Taktische Intelligenz (=Fähigkeit, Situationen auf ihren Erfolg hin richtig einzuschätzen), ... Damit hättest Du schonmal eine gewisse Kategorisierung, mit der Du gezielter programmieren kannst. Desweiteren wäre es eine Möglichkeit, die KI in Schritten denken zu lassen (auch wenn das vielleicht trivial klingt ): 1) Bin ich akut in Gefahr (-> taktische Intelligenz)? 2) Sind meine Verbündeten in Gefahr (-> taktische Intelligenz)? 3) Wäre es für mich schlimm, wenn diese Verbündeten schwächer würden (-> taktische Intelligenz)? 4) Gibt es Felder, die ich ohne große Mühe erobern kann (-> taktische Intelligenz)? 5) Gibt es Felder, die ich erobern könnte, um daraus einen großen taktischen Vorteil zu erhalten (-> taktische Intelligenz)? 6) ... Diese Fragen würden also alle mit der taktischen Intelligenz eingeschätzt und müssten früher oder später auf einen vergleichbaren Zahlenwert runtergebrochen werden. Je höher dabei die taktische Intelligenz, desto "richtiger" wird die Situation eingeschätzt. Im nächsten Schritt werden die soeben ermittelten Werte dann mit den restlichen Charakterzügen gewichtet (z.B. "Mein Verbündeter ist in Gefahr? Wen interessiert's?" -> Egoist). Daraus ließe sich dann ablesen, was am schwersten wiegt, woraufhin die KI dann entsprechend handelt. Dabei lässt sich natürlich überall ein Hauch von Zufall einbauen, um das Verhalten nicht vorhersehbar zu machen. Was den Angriff Verbündeter angeht: Ist es nicht immer bekannt, wer von wem angegriffen wird? Im Programm könnte man das bspw. über die EventQueue (BlitzMax) lösen, also dass einfach jeder Spieler über den aktuellen Zug (Wer greift wen an) informiert wird. Die Karte sollte vor Spielbeginn von der KI analysiert werden, sodass sie im Spiel auf fertige Werte zurückgreifen kann. Hier wären vielleicht Wegfindungs-/Suchalgorithmen hilfreich. Mit diesen könnte man z.B. ermitteln, an wie viele Felder ein Feld grenzt. Wichtig könnte auch sein, ob ein Feld genau an zwei Felder grenzt, die aber jeweils nicht aneinander grenzen: Das wäre sowas wie eine "Brücke", also eine taktisch wichtige Position. Das alles beantwortet wahrscheinlich noch keine Deiner Fragen so richtig, aber vielleicht sind ja ein paar Denkansätze dabei

Tritium

So, Jan 13, 2013 12:36
Antworten mit Zitat

Hi, ich kenne Risiko zwar, hab aber das genaue Regelwerk nicht im Kopf. Trotzdem ist das hier vielleicht schonmal ein Ansatz:

Du könntest Deiner KI mehrere Charakterzüge verleihen, die jeweils in z.B. drei Abstufungen (gering, normal, stark) existieren: Expansionswillen, Hilfsbereitschaft/Egoismus, Taktische Intelligenz (=Fähigkeit, Situationen auf ihren Erfolg hin richtig einzuschätzen), ...

Damit hättest Du schonmal eine gewisse Kategorisierung, mit der Du gezielter programmieren kannst. Desweiteren wäre es eine Möglichkeit, die KI in Schritten denken zu lassen (auch wenn das vielleicht trivial klingt Wink

):

1) Bin ich akut in Gefahr (-> taktische Intelligenz)?
2) Sind meine Verbündeten in Gefahr (-> taktische Intelligenz)?
3) Wäre es für mich schlimm, wenn diese Verbündeten schwächer würden (-> taktische Intelligenz)?
4) Gibt es Felder, die ich ohne große Mühe erobern kann (-> taktische Intelligenz)?
5) Gibt es Felder, die ich erobern könnte, um daraus einen großen taktischen Vorteil zu erhalten (-> taktische Intelligenz)?
6) ...

Diese Fragen würden also alle mit der taktischen Intelligenz eingeschätzt und müssten früher oder später auf einen vergleichbaren Zahlenwert runtergebrochen werden. Je höher dabei die taktische Intelligenz, desto "richtiger" wird die Situation eingeschätzt.
Im nächsten Schritt werden die soeben ermittelten Werte dann mit den restlichen Charakterzügen gewichtet (z.B. "Mein Verbündeter ist in Gefahr? Wen interessiert's?" -> Egoist). Daraus ließe sich dann ablesen, was am schwersten wiegt, woraufhin die KI dann entsprechend handelt.

Dabei lässt sich natürlich überall ein Hauch von Zufall einbauen, um das Verhalten nicht vorhersehbar zu machen.

Was den Angriff Verbündeter angeht: Ist es nicht immer bekannt, wer von wem angegriffen wird? Im Programm könnte man das bspw. über die EventQueue (BlitzMax) lösen, also dass einfach jeder Spieler über den aktuellen Zug (Wer greift wen an) informiert wird.

Die Karte sollte vor Spielbeginn von der KI analysiert werden, sodass sie im Spiel auf fertige Werte zurückgreifen kann. Hier wären vielleicht Wegfindungs-/Suchalgorithmen hilfreich. Mit diesen könnte man z.B. ermitteln, an wie viele Felder ein Feld grenzt. Wichtig könnte auch sein, ob ein Feld genau an zwei Felder grenzt, die aber jeweils nicht aneinander grenzen: Das wäre sowas wie eine "Brücke", also eine taktisch wichtige Position.

Das alles beantwortet wahrscheinlich noch keine Deiner Fragen so richtig, aber vielleicht sind ja ein paar Denkansätze dabei Wink

	BladeRunner Moderator	So, Jan 13, 2013 12:56 Antworten mit Zitat
Eine Strategie für Risiko sollte nicht so schwer sein. - Jedes Land hat immer fixe Nachbarn. Auch bei frei generierten Maps ist diese Infoschon zu Spielbeginn verfügbar. - Länder die an wenig andere Länder Grenzen sind wertvoll, denn sie stellen gut zu verteidigende Schlüsselpositionen dar. - Länder sind zu Kontinenten zusammengefasst, ebenfalls eine leicht numerisch erfassbare Größe. Der Kontinent den ich in der aktuellen Situation am ehesten komplettieren könnte ist deutlich wertvoller, da er mir Boni einbringt. -grundsätzliche Abwägung: Wenn ich angreife und gewinne, habe ich danach genug Armeen um die neuen Nachbarfelder abwehren zu können? (zB gleiche Anzahl Truppen wie im stärksten Gegnerland) - Ich kriege nur eine Armeenkarte wenn ich eine Schlacht gewonnen habe, wenn also die "lohnenden Ziele" alle zu sehr verteidigt sind sollte alternativ ein ungünstiges aber schwaches Ziel angegriffen werden. -Die Entscheidung Attacke oder nicht kann nun mittels der Wertigkeit des Ziellandes (Position+Kontinent+evtl. Teil des Auftrages) und einer KI-abhängigen Risikofreude (aka MinimalPunktezahl) getroffen werden.
Zu Diensten, Bürger. Intel T2300, 2.5GB DDR 533, Mobility Radeon X1600 Win XP Home SP3 Intel T8400, 4GB DDR3, Nvidia GF9700M GTS Win 7/64 B3D BMax MaxGUI Stolzer Gewinner des BAC#48, #52 & #92

BladeRunner

Moderator

So, Jan 13, 2013 12:56
Antworten mit Zitat

Eine Strategie für Risiko sollte nicht so schwer sein.
- Jedes Land hat immer fixe Nachbarn. Auch bei frei generierten Maps ist diese Infoschon zu Spielbeginn verfügbar.
- Länder die an wenig andere Länder Grenzen sind wertvoll, denn sie stellen gut zu verteidigende Schlüsselpositionen dar.
- Länder sind zu Kontinenten zusammengefasst, ebenfalls eine leicht numerisch erfassbare Größe. Der Kontinent den ich in der aktuellen Situation am ehesten komplettieren könnte ist deutlich wertvoller, da er mir Boni einbringt.

-grundsätzliche Abwägung: Wenn ich angreife und gewinne, habe ich danach genug Armeen um die neuen Nachbarfelder abwehren zu können? (zB gleiche Anzahl Truppen wie im stärksten Gegnerland)

- Ich kriege nur eine Armeenkarte wenn ich eine Schlacht gewonnen habe, wenn also die "lohnenden Ziele" alle zu sehr verteidigt sind sollte alternativ ein ungünstiges aber schwaches Ziel angegriffen werden.

-Die Entscheidung Attacke oder nicht kann nun mittels der Wertigkeit des Ziellandes (Position+Kontinent+evtl. Teil des Auftrages) und einer KI-abhängigen Risikofreude (aka MinimalPunktezahl) getroffen werden.

Zu Diensten, Bürger.
Intel T2300, 2.5GB DDR 533, Mobility Radeon X1600 Win XP Home SP3
Intel T8400, 4GB DDR3, Nvidia GF9700M GTS Win 7/64
B3D BMax MaxGUI
Stolzer Gewinner des BAC#48, #52 & #92

	Trust	So, Jan 13, 2013 16:10 Antworten mit Zitat
Zitat: Was den Angriff Verbündeter angeht: Ist es nicht immer bekannt, wer von wem angegriffen wird? Ja es ist schon bekannt, nur was ich eher meinte, ist nicht, welcher Gegner in diesem Augenblick das Teammitglied angreift, sondern herrauszufinden, welcher Gegner taktisch dem Teammitglied am meisten überlegen ist und für jenes, die derzeit größte Bedrohung darstellt. Daraufhin sollte dann, die für dieses Teammitglied taktisch beste Situation angestrebt werden, wie zB. bestimmte Schlüsselpositionen einzunehmen um es dem Gegner schwerer zu machen, dieses Teammitglied weiterhin so einzuengen usw. . Zitat: Du könntest Deiner KI mehrere Charakterzüge verleihen, die jeweils in z.B. drei Abstufungen (gering, normal, stark) existieren ... ...Desweiteren wäre es eine Möglichkeit, die KI in Schritten denken zu lassen ... Das klingt sehr gut, demnach wird einem stark ausgeprägten Charakterzug mehr nachgegangen als einem schwächer ausgeprägten. Zitat: - Länder die an wenig andere Länder Grenzen sind wertvoll, denn sie stellen gut zu verteidigende Schlüsselpositionen dar Daran hatte ich auch schon gedacht. Allerdings kann ein Land am Rand auch nur wenige Verbindungen zu anderen Ländern haben. Aber dieses ist verglichen mit einem Land, welches mitten in der Map liegt und ebenso wenige Verbindungen hat und zusätzlich eine Art Flaschenhals bzw. Brücke vom eigenen zum gegnerischen Gebiet darstellt, weitaus uninteressanter. Wie soll da am besten unterschieden werden? G, Trust
Es gibt 10 Gruppen von Menschen: diejenigen, die das Binärsystem verstehen, und die anderen.

Trust

So, Jan 13, 2013 16:10
Antworten mit Zitat

Zitat:

Was den Angriff Verbündeter angeht: Ist es nicht immer bekannt, wer von wem angegriffen wird?

Ja es ist schon bekannt, nur was ich eher meinte, ist nicht, welcher Gegner in diesem Augenblick das Teammitglied angreift, sondern herrauszufinden, welcher Gegner taktisch dem Teammitglied am meisten überlegen ist und für jenes, die derzeit größte Bedrohung darstellt. Daraufhin sollte dann, die für dieses Teammitglied taktisch beste Situation angestrebt werden, wie zB. bestimmte Schlüsselpositionen einzunehmen um es dem Gegner schwerer zu machen, dieses Teammitglied weiterhin so einzuengen usw. .

Zitat:

Du könntest Deiner KI mehrere Charakterzüge verleihen, die jeweils in z.B. drei Abstufungen (gering, normal, stark) existieren ...
...Desweiteren wäre es eine Möglichkeit, die KI in Schritten denken zu lassen ...

Das klingt sehr gut, demnach wird einem stark ausgeprägten Charakterzug mehr nachgegangen als einem schwächer ausgeprägten.

Zitat:

- Länder die an wenig andere Länder Grenzen sind wertvoll, denn sie stellen gut zu verteidigende Schlüsselpositionen dar

Daran hatte ich auch schon gedacht.
Allerdings kann ein Land am Rand auch nur wenige Verbindungen zu anderen Ländern haben.
Aber dieses ist verglichen mit einem Land, welches mitten in der Map liegt und ebenso wenige Verbindungen hat und zusätzlich eine Art Flaschenhals bzw. Brücke vom eigenen zum gegnerischen Gebiet darstellt,
weitaus uninteressanter.

Wie soll da am besten unterschieden werden?

G,
Trust

Es gibt 10 Gruppen von Menschen: diejenigen, die das Binärsystem verstehen, und die anderen.

	LordCoder	So, Jan 13, 2013 17:19 Antworten mit Zitat
Ich finde dabei auch die Fragen interessant, mit welcher Armee ein Land angegriffen werden soll. Dazu habe ich in Wikipedia folgendes gefunden: http://de.wikipedia.org/wiki/R...Schlachten Man könnte die Risikobereitschaft aufgrund dieser Tabelle gut kalibrieren.
3. Platz BCC #60

LordCoder

So, Jan 13, 2013 17:19
Antworten mit Zitat

Ich finde dabei auch die Fragen interessant, mit welcher Armee ein Land angegriffen werden soll.
Dazu habe ich in Wikipedia folgendes gefunden:
http://de.wikipedia.org/wiki/R...Schlachten

Man könnte die Risikobereitschaft aufgrund dieser Tabelle gut kalibrieren.

3. Platz BCC #60

	PSY	Mo, Jan 14, 2013 0:03 Antworten mit Zitat
Uh, sehr geiles Thema. Risiko hab ich schon immer gern gezockt. Vor allem Risk 2 aufm PC mit Kampagne und Simultanzuegen...supergeil. Hab auch das Risk 2210 A.D. Board Game aus den Staaten. Werd mir die Tage mal Gedanken dazu machen! PSY
PSY LABS Games Coders don't die, they just gosub without return

PSY

Mo, Jan 14, 2013 0:03
Antworten mit Zitat

Uh,

sehr geiles Thema.
Risiko hab ich schon immer gern gezockt. Vor allem Risk 2 aufm PC mit Kampagne und Simultanzuegen...supergeil.
Hab auch das Risk 2210 A.D. Board Game aus den Staaten.

Werd mir die Tage mal Gedanken dazu machen!

PSY

PSY LABS Games
Coders don't die, they just gosub without return

	biggicekey	Mo, Jan 14, 2013 9:34 Antworten mit Zitat
Trust hat Folgendes geschrieben: Allerdings kann ein Land am Rand auch nur wenige Verbindungen zu anderen Ländern haben. Aber dieses ist verglichen mit einem Land, welches mitten in der Map liegt und ebenso wenige Verbindungen hat und zusätzlich eine Art Flaschenhals bzw. Brücke vom eigenen zum gegnerischen Gebiet darstellt, weitaus uninteressanter. Wie soll da am besten unterschieden werden? Da man bei Risiko über die Ränder hinweg auf die andere Seite des Spielfeldes kommt ist es eigentlich nur eine Frage der Darstellung wo die "Mitte" der Map ist. Flaschenhälse zu Kontinenten sind am wertvollsten. Wenn ich die Karte richtig im Kopf habe sind dies auch die einzigen Flaschenhälse auf der Karte. Sowohl am "Rand" (Australien, Nordamerika) Als auch in "der Mitte" (Nordafrika?).
#45 www.icekeyunlimited.de www.starcrusade.de Gewinner BCC#17 !!! mit dotkiller Nothing more to register - you've cleaned us out![/size]

biggicekey

Mo, Jan 14, 2013 9:34
Antworten mit Zitat

Trust hat Folgendes geschrieben:

Allerdings kann ein Land am Rand auch nur wenige Verbindungen zu anderen Ländern haben.
Aber dieses ist verglichen mit einem Land, welches mitten in der Map liegt und ebenso wenige Verbindungen hat und zusätzlich eine Art Flaschenhals bzw. Brücke vom eigenen zum gegnerischen Gebiet darstellt,
weitaus uninteressanter.

Wie soll da am besten unterschieden werden?

Da man bei Risiko über die Ränder hinweg auf die andere Seite des Spielfeldes kommt ist es eigentlich nur eine Frage der Darstellung wo die "Mitte" der Map ist. Flaschenhälse zu Kontinenten sind am wertvollsten. Wenn ich die Karte richtig im Kopf habe sind dies auch die einzigen Flaschenhälse auf der Karte. Sowohl am "Rand" (Australien, Nordamerika) Als auch in "der Mitte" (Nordafrika?).

#45 www.icekeyunlimited.de www.starcrusade.de
Gewinner BCC#17 !!! mit dotkiller
Nothing more to register - you've cleaned us out![/size]

	Trust	Mo, Jan 14, 2013 10:42 Antworten mit Zitat
Zitat: Da man bei Risiko über die Ränder hinweg auf die andere Seite des Spielfeldes kommt.... Wenn ich die Karte richtig im Kopf habe sind dies auch die einzigen Flaschenhälse auf der Karte.... Da hast du natürlich recht, dies trifft jedoch nur auf die originale Risikokarte zu. Davon ausgegangen, dass die Karten zufällig generiert werden und somit alle unterschiedlich sind, kann man die KI-Strategie nicht auf eine Kartensituation hin programmieren.
Es gibt 10 Gruppen von Menschen: diejenigen, die das Binärsystem verstehen, und die anderen.

Trust

Mo, Jan 14, 2013 10:42
Antworten mit Zitat

Zitat:

Da man bei Risiko über die Ränder hinweg auf die andere Seite des Spielfeldes kommt....
Wenn ich die Karte richtig im Kopf habe sind dies auch die einzigen Flaschenhälse auf der Karte....

Da hast du natürlich recht, dies trifft jedoch nur auf die originale Risikokarte zu.

Davon ausgegangen, dass die Karten zufällig generiert werden und somit alle unterschiedlich sind, kann man die KI-Strategie nicht auf eine Kartensituation hin programmieren.

Es gibt 10 Gruppen von Menschen: diejenigen, die das Binärsystem verstehen, und die anderen.

	aMul Sieger des Minimalist Compo 01/13	Mo, Jan 14, 2013 12:24 Antworten mit Zitat
Gegeben dein English ist gut genug ist das hier vielleicht was wert: http://www.unimaas.nl/games/fi...-paper.pdf Allgemein haben sich schon viele zu dem Thema Gedanken gemacht. Die Grund-regeln von Risiko sind im Verhältnis recht einfach, was es ermöglicht eine akzeptable AI in relativ kurzer Zeit zu implementieren, vorrausgesetzt man hat Erfahrung mit Suchalgorithmen und Heuristiken .
Panic Pong - ultimate action mashup of Pong and Breakout <= aktives Spiele-Projekt, Downloads mit vielen bunten Farben! advASCIIdraw - the advanced ASCII art program <= aktives nicht-Spiele-Projekt, must-have für ASCII/roguelike/dungeon-crawler fans! Alter BB-Kram: ThroughTheAsteroidBelt - mit Quelltext! \| RGB-Palette in 32²-Textur / Farbige Beleuchtung mit Dot3 \| Stereoskopie in Blitz3D \| Teleport-Animation Screensaver

aMul

Sieger des Minimalist Compo 01/13

Mo, Jan 14, 2013 12:24
Antworten mit Zitat

Gegeben dein English ist gut genug ist das hier vielleicht was wert:
http://www.unimaas.nl/games/fi...-paper.pdf

Allgemein haben sich schon viele zu dem Thema Gedanken gemacht.
Die Grund-regeln von Risiko sind im Verhältnis recht einfach, was es ermöglicht eine akzeptable AI in relativ kurzer Zeit zu implementieren, vorrausgesetzt man hat Erfahrung mit Suchalgorithmen und Heuristiken .

Panic Pong - ultimate action mashup of Pong and Breakout <= aktives Spiele-Projekt, Downloads mit vielen bunten Farben!
advASCIIdraw - the advanced ASCII art program <= aktives nicht-Spiele-Projekt, must-have für ASCII/roguelike/dungeon-crawler fans!
Alter BB-Kram: ThroughTheAsteroidBelt - mit Quelltext! | RGB-Palette in 32²-Textur / Farbige Beleuchtung mit Dot3 | Stereoskopie in Blitz3D | Teleport-Animation Screensaver

	Trust	Mo, Jan 14, 2013 18:36 Antworten mit Zitat
Danke, das sieht interessant aus. Werde es mir mal näher anschauen.
Es gibt 10 Gruppen von Menschen: diejenigen, die das Binärsystem verstehen, und die anderen.