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:
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)
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 .
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);)
