Dokładnie symulujesz wiele rzutów kostką bez pętli?

OK, więc jeśli twoja gra rzuca dużą ilością kości, możesz po prostu zadzwonić do generatora liczb losowych w pętli. Ale dla każdego rzutu kostką wystarczająco często otrzymasz krzywą dystrybucji / histogram. Więc moje pytanie: czy istnieje miła prosta kalkulacja, którą mogę uruchomić, która da mi liczbę pasującą do tej dystrybucji?

Np. 2D6 - wynik -% prawdopodobieństwa

2 - 2,77%

3 - 5,55%

4 - 8,33%

5 - 11,11%

6 - 13,88%

7 - 16,66%

8 - 13,88%

9 - 11,11%

10 - 8,33%

11 - 5,55%

12 - 2,77%

Znając powyższe, możesz rzucić pojedynczym d100 i wypracować dokładną wartość 2D6. Ale kiedy zaczniemy od 10D6, 50D6, 100D6, 1000D6, może to zaoszczędzić dużo czasu przetwarzania. Więc musi być tutorial / metoda / algorytm, który może to zrobić szybko? Prawdopodobnie przydaje się na giełdach, w kasynach, grach strategicznych, fortecach krasnoludów itp. Co by było, gdybyś mógł zasymulować wyniki pełnej bitwy strategicznej, która wymagałaby wielu godzin gry, z kilkoma wezwaniami do tej funkcji i podstawowymi matematykami?

Jak wspomniałem w moim komentarzu powyżej, zalecamy profilowanie tego przed nadmierną komplikacją kodu. forKości sumujące z szybką pętlą są dużo łatwiejsze do zrozumienia i modyfikacji niż skomplikowane formuły matematyczne i tworzenie / wyszukiwanie tabel. Zawsze profiluj najpierw, aby upewnić się, że rozwiązujesz ważne problemy. ;)

To powiedziawszy, istnieją dwa główne sposoby próbkowania wyrafinowanych rozkładów prawdopodobieństwa za jednym zamachem:

1. Skumulowane rozkłady prawdopodobieństwa

Jest ładna sztuczka do próbkowania z ciągłych rozkładów prawdopodobieństwa przy użyciu tylko jednego jednolitego losowego wejścia . Ma to związek z rozkładem skumulowanym , funkcją, która odpowiada „Jakie jest prawdopodobieństwo, że wartość nie będzie większa niż x?”

Ta funkcja nie zmniejsza się, począwszy od 0 i rośnie do 1 w swojej domenie. Przykład sumy dwóch sześciościennych kości pokazano poniżej:

Jeśli twoja funkcja rozkładu skumulowanego ma wygodną do obliczenia odwrotność (lub możesz ją aproksymować za pomocą funkcji cząstkowych, takich jak krzywe Béziera), możesz użyć tego do próbkowania z oryginalnej funkcji prawdopodobieństwa.

Funkcja odwrotna obsługuje rozdzielanie domeny od 0 do 1 na przedziały odwzorowane na każdym wyjściu pierwotnego losowego procesu, przy czym obszar zlewni każdego odpowiada jego pierwotnemu prawdopodobieństwu. (Jest to nieskończenie prawdziwe w przypadku ciągłych rozkładów. W przypadku dyskretnych rozkładów, takich jak rzuty kostkami, musimy zastosować ostrożne zaokrąglanie)

Oto przykład użycia tego do emulacji 2d6:

int SimRoll2d6()
{
    // Get a random input in the half-open interval [0, 1).
    float t = Random.Range(0f, 1f);
    float v;

    // Piecewise inverse calculated by hand. ;)
    if(t <= 0.5f)
    {
         v = (1f + sqrt(1f + 288f * t)) * 0.5f;
    }
    else
    {
         v = (25f - sqrt(289f - 288f * t)) * 0.5f;
    }

    return floor(v + 1);
}

Porównaj to z:

int NaiveRollNd6(int n)
{
    int sum = 0;
    for(int i = 0; i < n; i++)
       sum += Random.Range(1, 7); // I'm used to Range never returning its max
    return sum;
}

Widzisz, co mam na myśli różnicę w przejrzystości kodu i elastyczności? Naiwny sposób może być naiwny z jego pętlami, ale jest krótki i prosty, natychmiast oczywisty o tym, co robi, i łatwo skalować do różnych rozmiarów i liczb kości. Wprowadzanie zmian w kumulatywnym kodzie dystrybucji wymaga trochę nietrywialnej matematyki i łatwo byłoby go złamać i spowodować nieoczekiwane wyniki bez oczywistych błędów. (Mam nadzieję, że nie zrobiłem powyżej)

Tak więc, zanim usuniesz wyraźną pętlę, upewnij się absolutnie, że naprawdę jest to problem wydajnościowy wart tego rodzaju poświęcenia.

2. Metoda aliasowa

Metoda rozkładu skumulowanego działa dobrze, gdy można wyrazić odwrotność funkcji rozkładu skumulowanego jako proste wyrażenie matematyczne, ale nie zawsze jest to łatwe lub nawet możliwe. Niezawodną alternatywą dla dystrybucji dyskretnych jest metoda zwana metodą aliasową .

Umożliwia to próbkowanie z dowolnego dowolnego dyskretnego rozkładu prawdopodobieństwa przy użyciu tylko dwóch niezależnych, równomiernie rozmieszczonych losowych danych wejściowych.

Działa, biorąc rozkład taki jak ten poniżej po lewej stronie (nie martw się, że obszary / wagi nie sumują się do 1, dla metody Alias ​​dbamy o względną wagę) i przekształcając ją w tabelę taką jak ta na prawo gdzie:

• Dla każdego wyniku jest jedna kolumna.
• Każda kolumna jest podzielona na co najwyżej dwie części, każda związana z jednym z oryginalnych wyników.
• Względna powierzchnia / waga każdego wyniku zostaje zachowana.

(Schemat na podstawie zdjęć z tego doskonałego artykułu na temat metod próbkowania )

W kodzie reprezentujemy to za pomocą dwóch tabel (lub tabeli obiektów o dwóch właściwościach) reprezentujących prawdopodobieństwo wyboru alternatywnego wyniku z każdej kolumny oraz tożsamość (lub „alias”) tego alternatywnego wyniku. Następnie możemy próbkować z dystrybucji w następujący sposób:

int SampleFromTables(float[] probabiltyTable, int[] aliasTable)
{
    int column = Random.Range(0, probabilityTable.Length);
    float p = Random.Range(0f, 1f);
    if(p < probabilityTable[column])
    {
        return column;
    }
    else
    {
        return aliasTable[column];
    }
}

Wymaga to trochę konfiguracji:

1. Oblicz względne prawdopodobieństwa każdego możliwego wyniku (więc jeśli rzucasz 1000d6, musimy obliczyć liczbę sposobów uzyskania każdej sumy od 1000 do 6000)

2. Zbuduj parę tabel z wpisem dla każdego wyniku. Pełna metoda wykracza poza zakres tej odpowiedzi, więc bardzo polecam odnieść się do tego wyjaśnienia algorytmu metody Alias .

3. Przechowuj te tabele i odsyłaj do nich za każdym razem, gdy potrzebujesz nowego losowego rzutu kostką z tej dystrybucji.

Jest to kompromis czasoprzestrzenny . Etap wstępnego obliczenia jest dość wyczerpujący i musimy odłożyć pamięć proporcjonalną do liczby wyników, jakie mamy (chociaż nawet dla 1000d6 mówimy jednocyfrowe kilobajty, więc nie ma co przespać snu), ale w zamian za nasze próbkowanie jest stałym czasem, bez względu na to, jak skomplikowana może być nasza dystrybucja.

Mam nadzieję, że jedna z tych metod może się przydać (lub że przekonałem cię, że prostota metody naiwnej jest warta czasu, jaki zajmuje zapętlenie);)

Odpowiedź jest niestety taka, że ​​ta metoda nie spowodowałaby wzrostu wydajności.

Uważam, że może istnieć pewne nieporozumienie w kwestii sposobu generowania liczby losowej. Weź przykład poniżej [Java]:

Random r = new Random();
int n = 20;
int min = 1; //arbitrary
int max = 6; //arbitrary
for(int i = 0; i < n; i++){
    int randomNumber = (r.nextInt(max - min + 1) + min)); //silly maths
    System.out.println("Here's a random number: " + randomNumber);
}

Ten kod zapętla się 20 razy, drukując losowe liczby od 1 do 6 (włącznie). Kiedy mówimy o wydajności tego kodu, trochę czasu zajmuje stworzenie obiektu Random (co obejmuje utworzenie tablicy pseudolosowych liczb całkowitych na podstawie wewnętrznego zegara komputera w momencie jego tworzenia), a następnie 20 stałych czasów wyszukiwania przy każdym wywołaniu nextInt (). Ponieważ każda „rolka” jest operacją o stałym czasie, to sprawia, że ​​walcowanie jest bardzo tanie pod względem czasu. Zauważ też, że zakres od min. Do maks. Nie ma znaczenia (innymi słowy, komputer równie dobrze rzuca k6, jak i k100). Mówiąc o złożoności czasowej, wydajność rozwiązania to po prostu O (n), gdzie n jest liczbą kości.

Alternatywnie, możemy przybliżać dowolną liczbę rzutów d6 za pomocą pojedynczego rzutu d100 (lub d10000 w tym przypadku). Korzystając z tej metody, musimy najpierw obliczyć s [liczbę twarzy do kości] * n [liczba kości] procenty przed rzuceniem (technicznie jest to * n - n + 1 procentów i powinniśmy być w stanie z grubsza podzielić na pół, ponieważ jest symetryczny; zwróć uwagę, że w twoim przykładzie symulowania rzutu 2k6 obliczono 11 procent, a 6 było unikatowych). Po rzutowaniu możemy użyć wyszukiwania binarnego, aby dowiedzieć się, w jakim zakresie mieści się nasz rzut. Pod względem złożoności czasowej to rozwiązanie daje rozwiązanie O (s * n), gdzie s oznacza liczbę boków, a n liczbę kości. Jak widzimy, jest to wolniejsze niż rozwiązanie O (n) zaproponowane w poprzednim akapicie.

Ekstrapolując stamtąd, powiedzmy, że stworzyłeś oba te programy, aby zasymulować rzut 1000d20. Pierwszy rzuciłby 1000 razy. Drugi program musiałby najpierw ustalić 19 001 procentów (dla potencjalnego zakresu od 1 000 do 20 000), zanim zrobiłby cokolwiek innego. Więc jeśli nie masz dziwnego systemu, w którym wyszukiwanie pamięci jest znacznie droższe niż operacje zmiennoprzecinkowe, użycie wywołania nextInt () dla każdego rzutu wydaje się być dobrym rozwiązaniem.

Jeśli chcesz przechowywać kombinacje kości, dobrą wiadomością jest to, że istnieje rozwiązanie, złe jest to, że nasze komputery są w jakiś sposób ograniczone w odniesieniu do tego rodzaju problemów.

Dobre wieści:

Istnieje deterministyczne podejście do tego problemu:

1 / Oblicz wszystkie kombinacje swojej grupy kości

2 / Określ prawdopodobieństwo dla każdej kombinacji

3 / Wyszukaj na tej liście wynik zamiast rzucania kostką

Złe wiadomości:

Liczba kombinacji z powtórzeniami jest podana za pomocą następujących wzorów

$\Gamma_n^k={n+k-1 \choose k}=\frac{(n+k-1)!}{k!~(n-1)!}$

( z francuskiej wikipedii ):

Oznacza to, że na przykład przy 150 kostkach masz 698'526'906 kombinacji. Załóżmy, że przechowujesz prawdopodobieństwo jako zmiennoprzecinkowe 32-bitowe, potrzebujesz 2,6 GB pamięci i nadal musisz dodać wymagania dotyczące pamięci dla indeksów ...

W kategoriach obliczeniowych liczbę kombinacji można obliczyć za pomocą zwojów, co jest przydatne, ale nie rozwiązuje ograniczeń pamięci.

Podsumowując, w przypadku dużej liczby kości radziłbym rzucić kostką i obserwować wynik, zamiast wstępnie obliczać prawdopodobieństwa związane z każdą kombinacją.

Edytować

Ponieważ jednak interesuje Cię tylko suma kości, możesz przechowywać prawdopodobieństwa przy znacznie mniejszych zasobach.

Możesz obliczyć dokładne prawdopodobieństwa dla każdej sumy kości za pomocą splotu.

$F_i(m) = \sum_n F_1(n) F_{i-1}(m - n)$

Następnie, zaczynając od 1/6 z każdego wyniku z 1 kostką, możesz skonstruować wszystkie prawidłowe prawdopodobieństwa dla dowolnej liczby kości.

Oto ogólny kod Java, który napisałem dla ilustracji (niezupełnie zoptymalizowany):

public class DiceProba {

private float[][] probas;
private int currentCalc;

public int getCurrentCalc() {
    return currentCalc;
}

public float[][] getProbas() {
    return probas;
}

public void calcProb(int faces, int diceNr) {

    if (diceNr < 0) {
        currentCalc = 0;
        return;
    }

    // Initialize
    float baseProba = 1.0f / ((float) faces);
    probas = new float[diceNr][];
    probas[0] = new float[faces + 1];
    probas[0][0] = 0.0f;
    for (int i = 1; i <= faces; ++i)
        probas[0][i] = baseProba;

    for (int i = 1; i < diceNr; ++i) {

        int maxValue = (i + 1) * faces + 1;
        probas[i] = new float[maxValue];

        for (int j = 0; j < maxValue; ++j) {

            probas[i][j] = 0;
            for (int k = 0; k <= j; ++k) {
                probas[i][j] += probability(faces, k, 0) * probability(faces, j - k, i - 1);
            }

        }

    }

    currentCalc = diceNr;

}

private float probability(int faces, int number, int diceNr) {

    if (number < 0 || number > ((diceNr + 1) * faces))
        return 0.0f;

    return probas[diceNr][number];

}

}

Wywołaj calcProb () z żądanymi parametrami, a następnie przejdź do tabeli proba, aby uzyskać wyniki (pierwszy indeks: 0 dla 1 kości, 1 dla dwóch kości ...).

Sprawdziłem to z 1'000D6 na moim laptopie, zajęło 10 sekund, aby obliczyć wszystkie prawdopodobieństwa od 1 do 1 000 kości i wszystkich możliwych sum kości.

Dzięki przetwarzaniu wstępnemu i wydajnemu przechowywaniu możesz uzyskać szybkie odpowiedzi na dużą liczbę kości.

Mam nadzieję, że to pomoże.