Best Practice KI für Mensch ärgere Dich nicht

[hüteüberhüte]

Hi,

wie kann man eine KI schreiben für o.g. Spiel? Im Prinzip muss doch nur gewürfelt und entschieden werden, welche der maximal 4 Figuren gezogen werden soll? Welches ist die optimale Strategie? Bin schon gespannt auf Antworten 😛opcorn:

Grüßle

 

[Gast2]

Für den Anfang:
- Wenn ich ins Haus laufen kann mach ich das.
- Wenn ich jemanden schlagen kann mach ich das.
- Ansonsten: Bewege eine zufällige Figur

 

[The_S]

Für Mensch ärger dich nicht ist die KI ja ziemlich simpel. Ergänzend zu EikeB würde ich anstatt "Bewege eine zufällige Figur" verschiedne Spielertypen festlegen. Einer könnte bspw. schauen, dass alle Figuren ca. gleich weit sind. Ein anderer könnte den Fokus darauf legen erst einmal eine Figur ganz nach vorne zu bringen. Ein dritter zieht wirklich willkürlich mit einer Figur. Ein vierter orientiert sich am Spielverhalten des Gegners. Wenn man ggf. die Reihenfolge von den drei von EikeB vorgeschlagenen Schritten variiert kann man auch ganz gut unterschiedliche Schwierigkeitsgrade und Spielertypen generieren.

 

[szapf]

Hallo,

ist zwar keine Java Frage, aber ich glaube diese KI könnte eine einfache Prioritätentabelle sein.

1) Kann ich mit den Augen eine Figur "nach Hause" bringen.
2) Kann ich mit diesen Augen ein Gegnerische Figur die nahe an ihrem zuhause ist rauskicken?
3) Kann ich mit diesen Augen nahe an Gegnerische Figur kommen um sie im nächsten Zug rauszukicken?
4) Habe ich noch eine Figur nicht auf dem Feld?
5) Wenn nicht 1 - 4 ziehe ich eine meiner Figuren vor. Aber...
5.1) Keine Figur die nach am Heim ist und sich mit diesen Augen vor ein Gegnerische Figur setzt und damit eventl. geschlagen werden könnte.

Das sollte als Basis erstmal reichen.

 

[pL4Gu333]

ergänzend zu EikeB Vorschlag könnte man noch prüfen,

- ob man auf einem "Startfeld" des Gegners steht und da evtl. lieber runterzieht.

- ob Gegner in der Nähe sind, die einen erreichen könnten und man so außerhalb der "normalen" Reichweite kommt. (Normal heißt er würfelt nur einmal 😀)

 

[bone2]

Es gibt die eine beste Strategie für Mensch-äger-dich-nicht, findet man sicher bei google. Kann mich gerade nicht erinnern ob das alle bewegen oder vordersten bewegen war.

edit: pro7 hat dazu einen beitrag gehabt, von den deutschen meistern

 

[Marco13]

Ich hatte das mal ("ohne KI") implementiert. Ich weiß nicht, ob das die offiziellen Regeln sind, aber dort war es so, dass man, wenn man z.B. eine Figur schlagen konnte, aber das NICHT getan hat, wieder zurück ins Haus mußte - und noch ein paar ähnliche Dinge, so dass von einer "Strategie" nicht mehr viel übrig blieb. Das einzige, was mir spontan einfallen würde, wäre, zu versuchen, eine Figur (wenn möglich) so zu bewegen, dass sie aus dem "Schlagbereich" einer gegnerischen Figur raus wäre. Aber vermutlich haben sich da schon mehr Leute mehr Gedanken dazu gemacht.

 

[hüteüberhüte]

ist es sinnvoll, eine gegnerische Figur nicht zu schlagen, wenn eine andere andernfalls mit hoher Wahrscheinlichkeit geschlagen werdende Figur gesichert werden kann im Haus?

 

[The_S]

Hängt von der Spielsituation ab. Wenn der Gegner nur noch eine Figur auf dem Feld hat und diese im nächsten Zug das Ziel erreichen kann, dann würde ich die gegnerische Figur schlagen. Ist man dagegen selbst kurz vorm Sieg und hat bspw. nur noch die beiden Figuren auf dem Feld wohingegen der beste Gegner noch viele Figuren hat, würde ich erst einmal meine eine Figur ins Ziel bringen.

 

[Bleiglanz]

hm
maximal 4 steine
würfelwurf hat 6 möglichkeiten
also ca. 24 möglichkeiten pro Zug(wenn weniger als 4 Steine dann ist ja reinsetzen auch eine Option)

da 24 x 24 x 24 x 24 nicht sooo riesig ist, kannst du 2 volle Züge vorausrechnen (das reicht beim Mensch ärgere dich 🙂

und als Endbewertung einer Stellung nimmst du einfach die "im Moment nötige Augenzahl um alle meine heimzufahren" für dich und für den Gegner

 

[Landei]

Eine mögliche Strategie (wenn Einziehen und Schlagen nicht möglich ist) ist so zu ziehen, dass man möglichst "hinter" den anderen Gegnern steht. Als Maß könnte man z.B. (Wahrscheinlichkeit, beim nächsten mal schlagen zu können)/(Wahrscheinlichkeit, beim nächsten mal geschlagen zu werden) verwenden.

Eventuell ist es auch sinnvoll, das Spiel wie Schach in "Phasen" einzuteilen, und eine "Eröffnungsstrategie", eine normale Strategie und eine "Schlusssprint"-Strategie anzuwenden. Das würde schon recht "intelligent" wirken...

 

[chef2]

Wenn man das alles beachtet kann das ja ziemlich unübersichtlich werden.
Deshalb würde ich für Jede Figur Punkte vergeben:

50 wenn sie ins Haus kommt
20 wenn sie Schlagen kan
-10 wenn sie geschlagen werden kann
...

Und die Figur mit den Meisten Punkten würde ich ziehen lassen.

 

[mrbela]

-10 wenn sie geschlagen werden kann

Das geht ja nicht.. Entweder wurde sie dann von dem Gegner schon geschlagen oder dieser muss nochmals würfeln und dann ist nicht klar, ob diesre nochmals die nötige Zahl zum Schlagen würfelt..

Oder Du meinst, dass wenn die Figur im Range [1-6] zu einer gegnerischen steht, dann sollte sie mit -10 bewertet werden...

Weiß aber nicht, ob die Zahlen ausreichen.

Man muss bpsw. auch bedenken, dass Figuren, die schon im Haus sind, aber dennoch noch innerhalb des Hauses "ans Ende des Haus" vorrücken könnten, dies uach tun müssen, um so anderen Platz zu machen. Es ist also nicht damit getan, dem Computer zu sagen: Bring die Figuren ins Haus, danach musst dud dich um diese nicht mehr kümmern.

 

[hüteüberhüte]

Seht ihr, es ist also doch komplex.

1 bis 6 Felder vor (nach) einer gegnerischen Figur ist es auch nicht immer "gleich gefährlich", denn die Wahrscheinlichkeit, geschlagen zu werden, ist 6 Felder vor einer Figur viel höher als z.B. 1 Feld vor einer Figur.

Ich würde das mit nem Backtracking Algo machen, dann bleibt nur die Frage offen, wie eine Spielsituation zu bewerten ist. Wahrscheinlich Figuren im Spiel und schon zurückgelegte Schritte, oder?

Hat einer mal ein UI dafür gebastelt?

 

[deetee]

Man könnte noch beachten, dass die KI priorisiert gegen menschliche Gegener spielt, d.h. wenn zwei Figuren geschlagen werden können, sollte die des menschlichen Gegners dran glauben. Gehört dann wohl zum Thema Schwierigkeitsgrade.

Das Prinzip "Goal seeking" wird für den ein oder anderen Fall auch nützlich sein.

 

[bone2]

1 bis 6 Felder vor (nach) einer gegnerischen Figur ist es auch nicht immer "gleich gefährlich", denn die Wahrscheinlichkeit, geschlagen zu werden, ist 6 Felder vor einer Figur viel höher als z.B. 1 Feld vor einer Figur.

Warum? Würfel sollten random sein.
as einzige was vlt zutrifft ist, dass, je nach regeln, nur 1-5 gefährlich sind, solange der spieler noch figuren im startbereich hat und diese bei einer 6 rausrutschen muss.

Generell musst du dich erstmal auf einen regelsatz einigen den du verwenden willst, bevor du dich an die ki machst. Muss man schlagen und einsetzen?

 

[szapf]

Der Regelsatz ist natürlich das allerwichtigste. Vielleicht sollte man den mal Posten, dann kann man sich über den Rest Gedanken machen. Hat der TE da eine Vorgabe?

 

[hüteüberhüte]

Warum? Würfel sollten random sein.

Na, der Würfel ist rnd. Aber wenn ich beim ersten mal keine 6 würfle, stehe ich immer noch vor der Figur und habe einen zweites mal die Möglichkeit, wegzunehmen. 😉

Regeln muss ich mal schauen.

 

[t4ce]

Hi, AI Experte hier

TLDR; Monte Carlo Tree Search und Binary Decision Cutoff

Zuerst etwas vereinfacht, mit nur einem Würfel und ohne Pasch. Darauf aufbauend dann die vollständige Vorgehensweise.

Wir bedenken 1–4 Spieler (Ja, auch der Single Player Fall kann, gespielt / bedacht werden, auch wenn in der Praxis eher langweilig) oder man generalisiert zu X Spielern und findet eine Regel, das Spielbrett für X Spieler zu generieren.

Aber gehen wir einfach mal vom Standard Mensch ärgere dich nicht aus, mit 1 - 4 Spielern.

Ziel:
Wenn ein Spieler S an der Reihe ist, muss der beste Zug ermittelt werden. Wobei natürlich bekannt ist, was der Würfel W grade anzeigt. (S → 1 bis 4, W → 1 bis 6) Ebenfalls sind Spielfiguren Positionen entscheidend.

Wenn S dran ist, kann von der Wurzel aus ein Suchbaum erzeugt werden.
Sobald das Spiel beginnt und der erste Spieler gewürfelt hat, gilt folgendes Szenario:

Die Wurzel des Baumes B hat 4 direkte Kindknoten. Jedes Kind ist genau eine der möglichen Konfigurationen, die dadurch entstehen, dass der Spieler die Wahl hat, welche seiner Figuren er zieht.

Die Kindknoten sind also diejenigen Spielbrett-Konfigurationen, welche sich ergeben, sobald ein Spieler gewürfelt hat und eine Figur gezogen wurde.

Da wir alle 4 Knoten auf diese Weise darstellen können, kommt nun die Simulation.

Rein konzeptionell wollen wir für jeden Knoten eine Anzahl Simulationen bis zum Spielende durchführen, um statistisch zu bestimmen, wie gut der Zug war / wie oft die Konfiguration im Mittel gewinnt.

Angenommen nach dem ersten Zug führen wir für jeden der 4 Kind-Knoten 1000 Simulationen durch.
Gemerkt wird sich, wie oft der Spieler S (Spieler, der am Zug ist) in jeder der 4 Konstellationen die gemachten Simulationen gewonnen hat.

Zum Beispiel könnte das Resultat sein, dass der Spieler mit der ersten Spielfigur ein Resultat von 200 gewonnenen Simulationen hat und das Resultat der zweiten bis vierten Spielfigur unter 150 lag. Das wäre dann auch schon der gewünschte, beste Zug.

Hier noch Gedanken, die unerlässlich sind:
Bei der Simulation muss das Schlagen programmiert werden
Muss auf 2 Würfel und Pasch angepasst werden
Da die einzelnen Figuren gleichwertig sind, können viele Kindknoten, die zu gleichen Konfigurationen führen, zusammengefasst werden und der Suchbaum wird dramatisch kleiner, aber bleibt optimal


Da kann man jetzt fast eine Bachelorarbeit in Informatik draus machen.

 

[DasFrageezeichen]

Hallo AI Experte,

ich denke auch, mit reiner Wahrscheinlichkeitsrechnung kommt man hier nicht weit.