Ich entwickle ein Weltraumkampfspiel in Java als Teil einer fortlaufenden Anstrengung, die Sprache zu lernen. In einer Schlacht habe ich k Schiffe, die ihre Waffen auf eine Flotte von n ihrer ruchlosen Feinde abfeuern. Abhängig davon, wie viele ihrer Gegner von wie vielen Schüssen getroffen werden (jedes Schiff feuert einen Schuss, der einen Feind trifft), werden einige beschädigt und einige zerstört. Ich möchte herausfinden, wie viele Gegner einmal getroffen wurden, wie viele zweimal getroffen wurden und so weiter, so dass ich am Ende einen Tisch habe, der ungefähr so aussieht, für 100 abgegebene Schüsse:
%Vor%Natürlich kann ich das für eine kleine Anzahl von Schüssen und Feinden brutal erzwingen, indem ich jeden Schuss zufällig auf einen Gegner lege und dann zähle, wie oft jeder am Ende getroffen wurde. Diese Methode wird jedoch sehr unpraktisch sein, wenn ich drei Millionen unerschrockene Helden habe, die auf einen Schwarm von zehn Millionen Feinden schießen.
Im Idealfall möchte ich eine Verteilung erzeugen, die angibt, wie viele Gegner wahrscheinlich von genau einer bestimmten Anzahl von Schüssen getroffen werden. Ich könnte dann einen Zufallszahlengenerator verwenden, um einen Punkt auf dieser Verteilung auszuwählen, und dann diesen Vorgang wiederholen, wobei die Anzahl der Treffer jedes Mal erhöht wird, bis ungefähr alle Schüsse berücksichtigt sind. Gibt es eine allgemeine statistische Verteilung / Schätzungsweise, wie viele Gegner von wie vielen Schüssen getroffen werden?
Ich habe versucht, etwas aus dem Geburtstagsproblem herauszuarbeiten, um herauszufinden, wie viele Geburtstage genau von einer bestimmten Anzahl von Menschen geteilt werden, aber ich habe keinen nennenswerten Fortschritt gemacht.
Ich werde dies in Java implementieren.
BEARBEITEN: Ich habe eine Vereinfachung gefunden, die leichter zu lösen ist: Wie verteilt sich die Wahrscheinlichkeit, dass n Feinde überhaupt nicht getroffen werden? I.e. was ist die Wahrscheinlichkeit, dass Null nicht getroffen wird, man nicht getroffen wird, zwei nicht getroffen werden usw.
Es ist ein ähnliches Problem, (ok, das gleiche Problem, aber mit einer Vereinfachung), aber es scheint, als wäre es einfacher zu lösen, und würde ich die vollständige Verteilung in ein paar Iterationen generieren lassen.
Habe einen Weg gefunden, das zu lösen, und habe es schließlich geschafft, es in Java zu schreiben. Dies ergibt eine genaue Lösung für die Berechnung der Wahrscheinlichkeit, dass m Schiffe nicht getroffen werden, wenn k ships und n shots angegeben sind. Es ist jedoch ziemlich rechenintensiv. Zuerst eine Zusammenfassung dessen, was ich getan habe:
Die Wahrscheinlichkeit ist gleich der Gesamtzahl der Möglichkeiten, die Schiffe mit genau m nicht getroffen zu schießen, dividiert durch die Gesamtzahl der Arten, Schiffe zu schießen.
Gesamt ist k^n , da jeder Schuss einen von k Schiffen treffen kann.
Um den Zähler zu erhalten, beginnen Sie mit nCr(k,m) . Dies ist die Anzahl der Möglichkeiten, m Schiffe so zu wählen, dass sie nicht getroffen werden. Dies multipliziert mit der Anzahl der Möglichkeiten, k-m Schiffe zu treffen, ohne die Anzahl zu verpassen, ist die Gesamtwahrscheinlichkeit.
Nun um den zweiten Term im Zähler zu berechnen. Dies ist die Summe über alle Verteilungen von Aufnahmen, wie viele Möglichkeiten es gibt, dass eine bestimmte Schussverteilung stattfindet. Wenn zum Beispiel 2 Schiffe von 3 Kugeln getroffen werden und jedes Schiff mindestens einmal getroffen wird, können sie auf folgende Arten getroffen werden:
%Vor%Die Schussverteilungen sind gleich der Länge k-m Kompositionen von k. In diesem Fall hätten wir [2,1] und [1,2], die Länge 2 Zusammensetzungen von 3.
Für die erste Komposition, [2,1], können wir die Anzahl der Möglichkeiten berechnen, indem wir 2 der 3 Schüsse wählen, um das erste Schiff zu treffen, und dann 1 der verbleibenden 1 Schüsse, um das zu treffen Zweitens, dh nCr(3,2) * nCr(1,1) . Beachten Sie, dass wir dies in 3!/(2!*1!) vereinfachen können. Dieses Muster gilt für alle Shot-Muster, also kann die Anzahl der Möglichkeiten, dass ein bestimmtes Muster, p , auftreten kann, als n!/prodSum(j=1,k-m,p_j!) geschrieben werden, wobei die Notation die Produktsumme von 1 bis% angibt. Co_de%, k-m ist ein Index und j steht für p_j t in j .
Wenn wir p als Menge aller P Kompositionen von k-m definieren, ist die Wahrscheinlichkeit, dass n Schiffe nicht getroffen werden, dann:
Die Notation ist ein bisschen schlampig, da es keine Möglichkeit gibt, Gleichungen von mathematischen Symbolen in SO zu schreiben, aber das ist der Kern davon.
Allerdings ist diese Methode furchtbar ineffizient, aber ich finde keine bessere. Wenn jemand das vereinfachen kann, poste deine Methode auf jeden Fall! Ich bin gespannt, wie es geht.
Und der Java-Code dafür:
%Vor% Sie sollten sich die multinomiale Verteilung ansehen und sie auf den Fall beschränken, in dem p ist i sind gleich 1 / k (achten Sie darauf, dass der Wikipedia-Artikel die Bedeutung von k und n
Vielleicht wird ein Ansatz wie der folgende fruchtbar sein:
Wenn Sie S Schiffe haben und Schüsse auf sie abfeuern, folgt die Trefferzahl jedes einzelnen Schiffs einer Binominalverteilung mit p = 1 / S und n = A:
Sie können diese Verteilung abfragen und fragen:
und multipliziere diese mit der Anzahl der Schiffe, S, um die Anzahl der Schiffe zu erhalten, von denen du erwartest, dass sie 0, 1, 2, 3 usw. erreicht haben. Da dies jedoch eine Erwartung und kein zufällig gewürfeltes Ergebnis ist, werden Kämpfe jedes Mal genau gleich verlaufen.
Wenn Sie eine geringe Anzahl an Schiffen, aber eine hohe Anzahl an Schüssen haben, können Sie die Binominalverteilung einmal pro Schiff rollen. ODER wenn Sie eine geringe Anzahl von Schüssen haben, aber eine hohe Anzahl von Schiffen, können Sie jeden Schuss zufällig platzieren. Ich habe noch nicht an einen coolen Weg gedacht, um die zufällige Verteilung (oder eine zufällige Annäherung davon) von hoher Anzahl von Schüssen UND hoher Anzahl von Schüssen zu erhalten, aber es wäre toll, einen zu finden:)
Ich gehe davon aus, dass jeder Schuss Wahrscheinlichkeit h hat, jedes schlechte Schiff zu treffen. Wenn h = 0 ist, werden alle Schüsse fehlen. Wenn h = 1, treffen alle Schüsse etwas .
Nehmen wir an, Sie schießen b Kugeln. Der erwartete Wert von getroffenen Schiffen ist einfach Hs = h * b, aber diese sind nicht eindeutige Schiffe, die getroffen werden.
Also haben wir eine Liste von Schiffen, die Hs lang ist. Die Chance, dass ein bestimmtes feindliches Schiff bei N gegnerischen Schiffen getroffen wird, ist 1 / N. Daher ist die Wahrscheinlichkeit, in den ersten k Slots, aber nicht in den anderen Slots zu sein,
%Vor%Beachten Sie, dass dies die Antwort von Marko Topolnik ist. Das Problem besteht darin, dass es sich um ein bestimmtes Schiff handelt, das sich in den FIRST k-Slots befindet, im Gegensatz zu einer Kombination von k Slots. Wir müssen dies ändern, indem wir die Anzahl der Kombinationen von k Slots in Hs gesamten Slots in das Konto aufnehmen:
%Vor%Jetzt haben wir die Chance, dass ein bestimmtes Schiff in k Slots ist. Nun, jetzt müssen wir die gesamte Flotte von N Schiffen betrachten:
%Vor%Dieser Ausdruck repräsentiert die erwartete Anzahl von Schiffen, die innerhalb einer N-großen Flotte, die mit Hs-Schüssen in einer gleichmäßigen Verteilung getroffen wurde, k-mal getroffen werden.
Numerische Gesundheitsprüfung:
Nehmen wir an, zwei Kugeln treffen (Hs = 2) und wir haben zwei feindliche Schiffe (N = 2). Weisen Sie jedem Schiff eine binäre ID zu, und lasst uns die möglichen Trefferlisten aufzählen.
%Vor%Die Anzahl der einmal getroffenen Schiffe ist:
%Vor%Die Anzahl der doppelt getroffenen Schiffe ist:
%Vor%Um die Plausibilitätsprüfung abzuschließen, müssen wir sicherstellen, dass unsere Gesamtzahl der Treffer gleich Hs ist. Jedes zweimal getroffene Schiff benötigt 2 Kugeln und jedes getroffene Schiff benötigt eine Kugel:
%Vor%Noch ein kurzes Beispiel mit Hs = 3 und N = 2:
%Vor%