Thema: Der Kampf, der mit einem Wurf entschieden ist

[Weltengeist]

Wie kommst du auf 1000 mögliche Zustände? Ich lese ind em von dir verlinkten Post "100 x 100.000 Möglichkeiten". Kann es sein, dass dud ich hier um 4 Nullen vertan hast?

Nein, ich habe mich nur um eine Null vertan - zu seinen Gunsten. Denn da steht 100 und nicht 1000.

Mit den 100 waren (so verstehe ich das jedenfalls) die Zahl der relevanten Spielstände nach der ersten Runde gemeint, also die Anzahl unterschiedlicher Ausgangssituationen, die einen Einfluss auf die zweite Runde haben. Mit den 100.000 sind die Zahl der Handlungsoptionen in der zweiten Runde gemeint (um die ging es hier nicht, die kann man als vereinfachte Arbeitshypothese so stehen lassen).

Nur dass man mit 100 möglichen Spielständen nicht mal abbilden kann, welcher der 12 Teilnehmer überhaupt noch am Leben ist (allein das sind schon 4096 verschiedene Möglichkeiten), geschweige denn, in welcher Verfassung (fit, angeschlagen, dem Tode nah, volle AsP, wenig AsP, ohne AsP,...). Was aber wichtig ist für das Verhalten (bzw. sein Überleben) in der nächsten Runde.

Wenn man es sich wirklich, wirklich einfach macht und für die nächste Runde nur als relevant erachtet, ob eine Figur "viel, wenig oder keine LeP" und "viel, wenig oder keine AsP" hat, dann kommen wir schon auf 3^14 = 4.782.969 mögliche relevante Ausgangssituationen für die nächste Runde. Und mit "DSA1 simulieren" hat das natürlich auch nichts mehr zu tun.

[Taschenschieber]

Welchen Aspekt man jemandem gibt, ist egal.

Das ist der wohl größte Bullshit, den ich in diesem Thread bisher gelesen habe, und das will schon echt was heißen.

Meine Berechnung ignoriert ihr also einfach? Warum denn nur? Etwa, weil sie die ganze Debatte beenden würde, wenn ihr drauf eingeht?

[Eulenspiegel]

Nehmen wir mal an, wir spielen auf einem Quadratgrid (d. h. wir bewegen uns z. B. in DnD). Unser Char hat eine Bewegung von meinetwegen 5 Feldern. Diagonale Bewegung lassen wir mal aus dem Spiel. Wie viele Möglichkeiten für die Bewegung ergibt das? Eine Möglichkeit für "keine Bewegung", vier für "ein Feld Bewegung", acht für "zwei Felder Bewegung", zu viele zu zählen für drei, vier und fünf Felder Bewegung. Sind mehr als 20, jedenfalls. Dazu kommt dann noch der Angriff: Meistens gibt es mehrere Ziele und mehrere Arten, anzugreifen. Das wird ja quasi multipliziert. Dazu kommen noch alternative Aktionen wie Sprinten (was den Bewegungsfoobar noch mal schlimmer macht), Waffen wechseln, Zauber, Aufheben rumliegender Gegenstände, ...

D&D:
Du lässt dabei außer acht, dass vieles davon redundant ist: Ob ich nun stehen bleibe oder erst einen Schritt nach rechts und dann einen nach links gehe oder erst einen nach rechts, dann nach oben, dann nach links und dann nach unten, ist egal.

Wenn wir diagonale Züge zulassen, gibt es für einen Char, der sich n Felder bewegen kann, (n+1)² Möglichkeiten. Bei 5 Feldern wären das also 36 Möglichkeiten. Hinzu kommt noch, dass die exakte Positionierung bei D&D nicht ganz so extrem wichtig ist wie bei Schach.

Fate:
Dazu kann ich wiegesagt nichts sagen.

[evil bibu]

D&D:
Du lässt dabei außer acht, dass vieles davon redundant ist: Ob ich nun stehen bleibe oder erst einen Schritt nach rechts und dann einen nach links gehe oder erst einen nach rechts, dann nach oben, dann nach links und dann nach unten, ist egal.

Wenn wir diagonale Züge zulassen, gibt es für einen Char, der sich n Felder bewegen kann, (n+1)² Möglichkeiten. Bei 5 Feldern wären das also 36 Möglichkeiten. Hinzu kommt noch, dass die exakte Positionierung bei D&D nicht ganz so extrem wichtig ist wie bei Schach.
[...]

Ignorierst du nicht jetzt die Regeln zur AoO? Eigentlich ist es schon relevant wie man sich bei D&D bewegt, oder?

[Taschenschieber]

D&D:
Du lässt dabei außer acht, dass vieles davon redundant ist: Ob ich nun stehen bleibe oder erst einen Schritt nach rechts und dann einen nach links gehe oder erst einen nach rechts, dann nach oben, dann nach links und dann nach unten, ist egal.

Falsch, in jeder Stufe beziehe ich nur die "neuen" Zielfelder ein, die nicht schon in der vorigen Stufe erreicht werden konnten. Darfste gerne nachrechnen.

Wann die exakte Positionierung wichtig ist (mal ist sie's, mal nicht - Stichwort "Sichtlinien"!) kann aber bestenfalls eine (suboptimale) Heuristik erkennen. Die Überlegung hatte ich schon mit einbezogen, aber bin zu dem Schluss gekommen, dass man da nicht drumrum kommt, alle möglichen Bewegungen zu betrachten.

[Weltengeist]

D&D:
Du lässt dabei außer acht, dass vieles davon redundant ist: Ob ich nun stehen bleibe oder erst einen Schritt nach rechts und dann einen nach links gehe oder erst einen nach rechts, dann nach oben, dann nach links und dann nach unten, ist egal.

Wenn wir diagonale Züge zulassen, gibt es für einen Char, der sich n Felder bewegen kann, (n+1)² Möglichkeiten. Bei 5 Feldern wären das also 36 Möglichkeiten. Hinzu kommt noch, dass die exakte Positionierung bei D&D nicht ganz so extrem wichtig ist wie bei Schach.

Nur so als kombinatorischer Besserwiss: Wenn ich mich nicht verrechne, sind es (2n+1)² Möglichkeiten (er kann sich auch nach hinten bewegen, oder)? Bei 5 Schritt Bewegungsweite kann er ein Quadrat der Größe 11x11, also 121 Felder abdecken. Bei diagonaler Bewegung wohlgemerkt. Wenn diagonale Bewegung verboten ist, bleiben immerhin noch 61 Felder übrig (oder verallgemeinert ((2n+1)²+1)/2).

[Eulenspiegel]

Ignorierst du nicht jetzt die Regeln zur AoO? Eigentlich ist es schon relevant wie man sich bei D&D bewegt, oder?

Ich sage nicht, dass es irrelevant ist. Ich sage nur, dass es nicht so relevant wie bei Schach ist.

@ Weltengeist
Stimmt. Ich hatte nur die Länge der Quadrate im Kopf. Aber die Bewegung geht ja in beide Richtungen.

[Taschenschieber]

Ich sage nicht, dass es irrelevant ist. Ich sage nur, dass es nicht so relevant wie bei Schach ist.

Und wie ich bereits sagte, ist völlig irrelevant, wie relevant das ist. Den PC interessiert nur, ob es überhaupt relevant ist, und da lautet die Antwort "ja".

Um es noch einmal klarzustellen: Ich halte meinen Post von Seite 8 für einen ziemlich eindeutigen Hinweis darauf, dass ich Recht habe und unterstelle jedem, der hier noch ernsthaft das Gegenteil behauptet, ohne sämtliche Kernpunkte dieses Beitrags zu widerlegen, völlige Realitätsferne. You can't argue with the math.

[ArneBab]

Nein, ich habe mich nur um eine Null vertan - zu seinen Gunsten. Denn da steht 100 und nicht 1000.

Autsch, jupp, da hast du Recht: Ich hatte noch die Bitmaske im Kopf. Das sind nicht 100 Mögliche Zustände, sondern eine 100 Bit Bitmaske.

Du rechnest allerdings immernoch brute force: Du versuchst, alle möglichen Zustände mit ihrer Zug-Information abzubilden und dann den besten zu wählen - und dadurch lässt du alle Optimierungsmöglichkeiten weg.

Was wir aber brauchen, um ein Optimum zu finden, ist nicht die Liste aller Zustände, sondern aller entscheidungsrelevanten Zustände. Und auch da nicht aller Zustände aller Runden, sondern nur der Zustände, die für die jetzige Runde relevant sind.

Für meine Entscheidung ist es irrelevant, wie es dazu kam, dass jemand verletzt wurde. Dadurch sind die Zustände zeitunabhängig. Und das heißt:

dann kommen wir schon auf 3^14 = 4.782.969 mögliche relevante Ausgangssituationen…

…für beliebige Runden.

Für die vereinfachte Version hast du gerade den gesamten Rechenaufwand gefunden. Dann müssen diese Zustände nur noch in einen Graphen eingebunden werden (welcher kann in welchen übergehen - wird auch ein Weilchen dauern zu berechnen, kann aber durch Kenntnis der Handlungsmöglichkeiten massiv reduziert werden) und dann vom optimalen Endzustand alle Wege durch den Graphen gefunden werden.

Und das ist trotz allem noch Brute Force.

Eine elegantere Methode wäre ein inverses Modell: Es werden Entscheidungszustände der Charaktere definiert, die von einer Funktion genutzt werden, um den aktuellen Zustand zu verändern.

Dann kannst du durch eine Variation der Entscheidungszustände ein optimiertes Ergebnis finden. Da in diesen Kämpfen (wie du mit den 4mio Zuständen gezeigt hast) viel Redundanz ist, dürfte die Anzahl der nötigen Durchläufe für das Auffinden des Optimums deutlich unter denen für eine exakte Rechnung liegen - und deutlich besser sein, als das, was echte Spieler können.

Der Aufwand sind dann N Durchläufe der Entscheidungsfunktion, wobei N festlegt, wie nah wir an das Optimum kommen.

Allerdings ist die Definition der Entscheidungsfunktion und der Entscheidungszustände nicht trivial. Einfach mal kurz programmieren ist also nicht. Da es hier um die Betrachtung der Möglichkeit geht und nicht um die Realisierung, ist mir das aber egal.

Hintergrund:
- Ensemble Kalman Filter: http://en.wikipedia.org/wiki/Ensemble_Kalman_filter
- 4DVar: http://en.wikipedia.org/wiki/Data_assimilation

Da das eben der vom TE genannte Bayessche Ansatz ist, gehe ich davon aus, dass das als ausreichende Bestätigung der These gelten kann.
(ich kenne das, weil ich in meiner Doktorarbeit damit arbeite…)

[Taschenschieber]

Wieso reichen auf einmal die Zustände der jetztigen Runde? Ich muss doch vor dem Kampf den gesamten Kampf durchrechnen können und dabei alle optimalen Pfade (abhängig von den Würfelergebnissen) analysieren, um eine Wahrscheinlichkeit berechnen zu können?

[Eulenspiegel]

Wieso reichen auf einmal die Zustände der jetztigen Runde? Ich muss doch vor dem Kampf den gesamten Kampf durchrechnen können und dabei alle optimalen Pfade (abhängig von den Würfelergebnissen) analysieren, um eine Wahrscheinlichkeit berechnen zu können?

Nein, wenn Aktion 1 beim Gegner 5 Schaden verursacht und Aktion 2 beim gleichen Gegner 8 Schaden verursacht, sich ansonsten aber nichts ändert, ist Aktion 2 besser und man kann Aktion 1 verwerfen.

Ebenso ist es egal, ob du zu Beginn der 2. Runde auf Position x stehst und dort stehen bleibst oder ob du zu Beginn der 2. Runde auf Position y stehst und am Ende der Aktion auf Position x stehst. In beiden Fällen werden die gleichen Werte an die Nachfolge-Runde weitergegeben.

[Crimson King]

Was ist mit Aktionen, die Zustände verursachen, die die Qualität der Folgeaktionen verändern?

[Taschenschieber]

Nein, wenn Aktion 1 beim Gegner 5 Schaden verursacht und Aktion 2 beim gleichen Gegner 8 Schaden verursacht, sich ansonsten aber nichts ändert, ist Aktion 2 besser und man kann Aktion 1 verwerfen.

Aktionen machen aber nicht 8 Schaden, sondern sie machen zum Beispiel mit 40% Wahrscheinlichkeit einen Schaden, der über die natürlichen Zahlen zwischen 3 und 8 laplace-verteilt ist.

[Eulenspiegel]

@ CK
Das ist auch ein Zustand. Aber hier ist es ja egal, weshalb die Qualität der Folgeaktion geändert wurde. Es ist nur wichtig, wie stark die Qualität der Folgeaktion verändert wurde.

@ TS
Unabhängig davon kann man sagen, dass die eine Aktion mehr Schaden macht als die andere. (Die eine macht 1W6 Schaden, die andere macht 1W6+2 Schaden. Die eine macht 1W6 Schaden, die andere macht 1W8 Schaden.)

Klar gibt es auch Fälle, wo man sich beispielsweise überlegen muss, ob 1W6+1 oder 1W8 Schaden jetzt besser ist. Aber das sind Ausnahmen. Und in diesen seltenen Fällen kann man dann beide Aktionsmöglichkeiten weiterberechnen.

[ArneBab]

Wieso reichen auf einmal die Zustände der jetztigen Runde? Ich muss doch vor dem Kampf den gesamten Kampf durchrechnen können und dabei alle optimalen Pfade (abhängig von den Würfelergebnissen) analysieren, um eine Wahrscheinlichkeit berechnen zu können?

Weil die möglichen Entscheidungen nicht abhängig von den Vorentscheidungen sind, sondern nur von dem Ergebnis der Vorentscheidungen.

Und mit den möglichen Entscheidungen kannst du Übergänge zwischen den Zuständen berechnen.

Durch sinnvolle Aufteilung der Zustände in welche, die ineinander übergehen können, und welche, die das nicht können, kannst du die Kosten der Berechnung dieser Übergänge minimieren, so dass du den exponentiellen Teil minimieren kannst (idealerweise so weit, dass er für die Dauer eines Kampfes nicht den Hauptteil der Rechenzeit braucht).

Beispielsweise kann durch einen Nahkampfangriff meist nur ein Charakter Lebenspunkte verlieren. Dadurch können durch Nahkampfangriffe nur Zustände ineinander übergehen, in denen sich höchstens die Lebenspunkte eines Charakters unterscheiden. Und ASP können nur dann verloren werden, wenn ein Magier handelt.

Der letzte Schritt ist dann, die besten Zustände zu analysieren und alle möglichen Pfade zu diesen Zuständen zu finden. Dafür gibt es Algorithmen der Graphentheorie.

Und das ist immernoch brute force: Inverse Modelle reduzieren den Aufwand nochmal deutlich, geben allerdings den Versuch auf, das garantierte Optimum zu berechnen, weil angenommen wird, dass dafür entweder nicht genug Informationen oder nicht genug Rechenzeit zur Verfügung steht.

Ein Optimum wird für die Aufgabe des TE aber auch nicht gebraucht: Das Ergebnis muss nur so gut sein, dass es das Verhalten menschlicher Spieler widerspiegelt.

[Taschenschieber]

@ TS
Unabhängig davon kann man sagen, dass die eine Aktion mehr Schaden macht als die andere. (Die eine macht 1W6 Schaden, die andere macht 1W6+2 Schaden. Die eine macht 1W6 Schaden, die andere macht 1W8 Schaden.)

Abhängig davon, was der W8 ergibt, entwickelt sich der Kampf aber unterschiedlich, z. B. weil bei einer 8 dann doch der Magier heilen sollte, anstatt einen weiteren Feuerball zu werfen. Oder weil eine 8 einen Gegner tötet, eine 1 aber nicht.

[Weltengeist]

Wieso reichen auf einmal die Zustände der jetztigen Runde? Ich muss doch vor dem Kampf den gesamten Kampf durchrechnen können und dabei alle optimalen Pfade (abhängig von den Würfelergebnissen) analysieren, um eine Wahrscheinlichkeit berechnen zu können?

Wenn du dir das Entscheidungsproblem als Baum vorstellst, kannst du natürlich auf jeder Ebene alle gleichwertigen Zustände zusammenfassen. Dann ist es zwar streng genommen kein Baum mehr, aber trotzdem. Wenn du sehr grobe Kategorien bastelst (so wie ich es mit dem "unverletzt, leicht verletzt, tot" gemacht habe, auch wenn ich das für deutlich zu grob für eine sinnvolle Simulation halte), dann fallen auf diese Weise schon ein paar Zustände weg (viele Wege führen zum Ergebnis "Charakter A ist tot, alle anderen unverletzt"), und du kannst dich in der nächsten Runde darauf beschränken, mit den verbleibenden Zuständen weiterzuarbeiten. Und wenn du tatsächlich nur so kriminell wenige Zustände zulässt wie ich das in dem Beispiel getan habe, dann hast du einen Baum, der zwar auf jeder Ebene erstmal heftig wächst, dann aber wieder auf die Zahl der möglichen Zustände schrumpft. Würde wie gesagt funktionieren, wenn es echt nur so wenige Zustände wäre. Wenn es aber (wie ArneBab in seinem ursprünglichen Posting wohl gemeint hat) eine 100-Bit-Maske ist, dann käme der Baum auf eine Breite von bis zu 2^100 - viel zu viel, um jemals praktikabel zu sein.

Nein, wenn Aktion 1 beim Gegner 5 Schaden verursacht und Aktion 2 beim gleichen Gegner 8 Schaden verursacht, sich ansonsten aber nichts ändert, ist Aktion 2 besser und man kann Aktion 1 verwerfen.

@Eulenspiegel: Was du meinst, ist die andere Möglichkeit, den Baum zu reduzieren, nämlich bereits erkennbar unsinnige Zweige so früh wie möglich nicht mehr weiterzuverfolgen. Die würde man natürlich auch anwenden, aber sooo viel würde sie am Anfang nicht bringen, weil bei vielen Zuständen anfangs nicht klar wäre, welcher auf lange Sicht wirklich besser ist.

@ArneBab: Aaah, jetzt kommen wir einander näher. Wenn wir uns jetzt noch darauf einigen, dass für so etwas wie DSA1 schon die Zielfunktion enorm schwierig zu definieren ist, dass wir DSA1 inzwischen fast bis zur Unkenntlichkeit vereinfacht haben und das Ergebnis letztlich nur eine Heuristik ist (von der zumindest ich jetzt so auf Anhieb nicht sagen könnte, wie gut die wirklich wird - findet die auf Dauer globale Optima oder bleibt sie u.U. in lokalen Optima hängen?), dann sind wir plötzlich richtig dicke Kumpels .

[Eulenspiegel]

Richtig: Wir haben dann für eine Aktion 8 weitere Folgezustände. Das ändert aber nichts daran, dass man die andere Aktion verwerfen kann.

Und wie ArneBab schon sagte: Über inverse Berechnung* oder über Punkteanalyse** lässt sich dann berechnen, ob der Magier nun heilen sollte oder lieber einen Feuerball werfen.


*inverse Berechnung bedeutet stark vereinfacht: Der Computer beginnt in der letzten Runde und berechnet dann rückwärts, wie man zu diesem Ergebnis kommt
**Punkteanalyse wäre, dass man jedem Zustand einen Punktewert zuweist. Eine Möglichkeit wäre z.B.:
Summe des durchschnittlichen eigenen Schadensoutput/durchschnittliche LE der Gegner - Summe des durchschnittlichen gegnerischen Schadensoutput/durchschnittliche LE der eigenen SCs
Diese Punktzahl sollte maximiert werden.

[Taschenschieber]

Wir sind also tief im Reich der Abstraktion, der Heuristiken und des Ratens?

Dann können wir doch auch gleich eine gehandwedelte vergleichende Probe nutzen - damit baut uns unser Programm nämlich wahrscheinlich auch ganz ordentlich Fehler ein.

Richtig: Wir haben dann für eine Aktion 8 weitere Folgezustände. Das ändert aber nichts daran, dass man die andere Aktion verwerfen kann.

Das habe ich auch nie behauptet. Trotzdem, es ergeben sich 8 weitere, völlig andere Verlaufsmöglichkeiten für den Kampf.

**Punkteanalyse wäre, dass man jedem Zustand einen Punktewert zuweist. Eine Möglichkeit wäre z.B.:
Summe des durchschnittlichen eigenen Schadensoutput/durchschnittliche LE der Gegner - Summe des durchschnittlichen gegnerischen Schadensoutput/durchschnittliche LE der eigenen SCs
Diese Punktzahl sollte maximiert werden.

Wie aus meinem XXL-Post klar geworden sein sollte, weiß ich das.

[ArneBab]

Was ist mit Aktionen, die Zustände verursachen, die die Qualität der Folgeaktionen verändern?

Sie müssen Teil des Zustandes sein, erhöhen damit also die Kosten deutlich, weil sie sich nicht mit den Ergebnissen von anderen Handlungen zusammenfassen lassen.

Diese Zustände lassen sich nur erreichen, wenn diese spezielle Handlung ausgeführt wird, oder der vorige Zustand auch schon nach dieser Handlung kam (möglicherweise „x Sekunden nach dieser Handlung kam“).

PS: Arg, hier kommen ja die Beiträge schneller als ich einen verfassen kann…

[Eulenspiegel]

@ Taschenschieber
Wir sind tief im Bereich der Abstraktion und teilweise im Bereich der Heuristik. Aber nicht im Bereich des Ratens.

Und nein, eine gehandwedelte Vergleichsprobe kommt wahrscheinlichkeitstechnisch sehr wahrscheinlich zu einer vollkommen falschen Wahrscheinlichkeitsverteilung.

[Blutschrei]

Habe ich das richtig verstanden, dass bei der Punkteanalyse der Programmierer vorher Punkte, sprich Prioritäten für gewisse Handlungen in gewissen Situationen vergeben muss? Das würde voraussetzen, dass der Programmierer die weitestgehend optimalen Vorgehensweisen kennt, und selbst dann, wäre das Resultat nicht akkurat, oder?

[Taschenschieber]

@ Taschenschieber
Wir sind tief im Bereich der Abstraktion und teilweise im Bereich der Heuristik. Aber nicht im Bereich des Ratens.

Hyperbel! Hyperbel!

Wobei, ab wie viel HP Heilen sinnvoll ist, ist ja eigentlich schon geraten, wenn der PC es nicht selbst herausfinden darf.

Und nein, eine gehandwedelte Vergleichsprobe kommt wahrscheinlichkeitstechnisch sehr wahrscheinlich zu einer vollkommen falschen Wahrscheinlichkeitsverteilung.

Wie willst du aus einem einzelnen Wurf viel mehr als "Kampf gewonnen/verloren" lesen? Gerade dann, wenn du genaue Schadenspunkte etc. in der Berechnung sogar noch wegabstrahieren musst, um überhaupt zu irgendeinem Ergebnis zu kommen?

Und wenn es nur zwei mögliche Ergebnisse gibt, halten sich die möglichen Wahrscheinlichkeitsverteilungen arg in Grenzen - das ist einfach ne Erfolgswahrscheinlichkeit p und ne Misserfolgswahrscheinlichkeit 1-p. Ich sage einfach mal, ein so stark wie hier vorgeschlagen approximiertes Verfahren hat da +/-10% Messungenauigkeit und das kriegt ein SL auch hin.

[Weltengeist]

@ Taschenschieber
Wir sind tief im Bereich der Abstraktion und teilweise im Bereich der Heuristik. Aber nicht im Bereich des Ratens.

Ja. Zum Vergleich: Ein Schachcomputer ist auch eine Heuristik. Deshalb kann er auch nicht die optimale Schachstrategie berechnen, sondern nur eine Annäherung. Und genau das war ursprünglich auch meine These: Dass man das optimale Ergebnis (und damit die genauen Erfolgswahrscheinlichkeiten eines Kampfes) nicht berechnen kann. Dass man es sie bei genügend Augenzudrücken annähern kann, steht für mich dagegen außer Frage.

[Taschenschieber]

Ja. Zum Vergleich: Ein Schachcomputer ist auch eine Heuristik. Deshalb kann er auch nicht die optimale Schachstrategie berechnen, sondern nur eine Annäherung. Und genau das war ursprünglich auch meine These: Dass man das optimale Ergebnis (und damit die genauen Erfolgswahrscheinlichkeiten eines Kampfes) nicht berechnen kann. Dass man es sie bei genügend Augenzudrücken annähern kann, steht für mich dagegen außer Frage.

Man kann JEDE Wahrscheinlichkeit mit einer Ungenauigkeit von +/-0,5 annähern. Also ist das eine sehr schwache Aussage

Und wie gesagt, ich weiß, wie ein Schachkomputer funktioniert.