Лекция 12::Задача 1

Руска рулетка

В Монте Карло интегрирането, руската рулетка е една относително сложна (за разбиране) техника, която се обяснява най-добре чрез пример.

Представете си, че сте ръководител на китайския национален отбор по информатика - това са ~2000 китайчета, които се борят за правото си да бъдат пратени на международната олимпиада (за момент игнорирайте нереализма на ситуацията - все пак, само 2000 китайчета!). Както и да е, след множество вътрешни контролни, всеки ученик има рейтинг, който отразява неговите умения и е реално число между 0 и 1 (0 = много слаб състезател; 1 = един от най-добрите състезатели).
За нещастие, обаче, при преразпределението на бюджета, вашите финанси са значително поорязани и затова се налага да разпуснете част от децата. Един по-практичен метод би бил да ги сортирате по рейтинг и да оставите само тези с най-голям рейтинг. Но сортирането не винаги е възможно (а в Монте Карло интегрирането - никога). Затова ще приложим друга схема. Ако даден ученик има рейтинг x (x e [0..1]), то, с вероятност 1-x ще пратим ученика вкъщи (еквивалентно: с вероятност x той ще остане). Така, добрите ученици почти сигурно ще останат, докато слабите, в голямата си част, ще бъдат разпуснати.

Окей, сега си представете, че сме имали 50 китайчета с рейтинг 0.2. Математическото очакване е, че след "чистката" ще останат само 10 от тях. Въпросът, който ни задават, е

"Ако бяхте пратили 50-те китайчета, колко медала щяха да завоюват от международната олимпиада?".

Ние пращаме само 10, но зад всяко от изпратените стоят още 4 другарчета, които "не са имали късмета". Нека тези 10 завоюват Y медала. Бихме очаквали 50-те да завоюват 5 пъти повече медали. Иначе казано: Y * (1/x), където x е 0.2.

Макар и не толкова интуитивно, същата идея може да се приложи и върху цялата група от 2000 китайчета първоначално. Нека ни бяха питали: "Тези 2000 колко медала щяха да вземат, ако ги бяхме пратили всичките" (не се безпокойте, медали има достатъчно). За произволно китайче с рейтинг x, оцеляло от чистката, може да приемем, че е представител на групата от около 1/х китайчета с подобен на него рейтинг, като останалите от групата са разпуснати. Затова, неговия принос от олимпиадата умножаваме с 1/x, за да отчетем предполагаемия принос от цялата група. Иначе казано, ако номерираме всички оцелели от чистката китайчета с числата от 1 до N, Xi показва рейтинга на i-тото китайче, и Yi показва броя завоювани медали от него (0 или 1), то очаквания брой медали от 2000-те китайчета е SUM{i = 1..N}(Yi / Xi)

Как се прилага руската рулетка в контекста на алгоритъма Path tracing? Тук, вместо китайчета, имаме пътища (още недостроени), а техния рейтинг е изразен от pathMultiplier. По-точно, rating = pathMultiplier.intensity(). При rating >= 1, прилагаме си досегашния алгоритъм без модификации. Ако rating < 1, то с вероятност (1 - rating) "убиваме" текущия път (руска рулетка). Под "убийство" разбираме следното - прекратавяме строежа на пътя и връщаме черно. Ако пътят оцелее от руската рулетка, то по-нататъшния принос от този път (т.е. това, което pathtrace() връща чрез return) трябва да умножим с 1 / rating.

Добавете един bool с име roulette към GlobalSettings. Ако е включен, прилагайте техниката на руската рулетка в pathtrace(). При включена рулетка, алгоритъма трябва да работи много по-бързо (двойно или тройно), но да връща по-шумен резултат при същия брой пътища на пиксел (с отчетливо напръскани "горещи пиксели", идващи от силно безперспективни пътища, които руската рулетка все пак е избрала да продължи). При правилна реализация, резултатната картинка при включена/изключена рулетка не трябва да е осезаемо по-ярка или по-тъмна.

Comments

Не мога да разбера какво

Не мога да разбера какво означава да направим нещо с вероятност едикаква си. Дали някой ще може да разясни.

Здравей! Да направим нещо с

Здравей!

Да направим нещо с дадена вероятност означава да изберем това нещо произволно, само че вероятността да приема определени стойности да е по-голяма от тази да приема други.

Например когато генерираш случайни цели числа (с rand() в C++, с Random класа в Java и C#) в интервала [0, n), генерираш тези числа с вероятност 1/n, тъй като вероятността да се падне кое да е от числата 0, 1, 2, ..., n-1 е една и съща. Ако обаче искаш да генерираш пак случайно число в интервала [0, n), но с вероятност правопропорционална на големината на числото, то трябва така да генерираш числата, че вероятността да се падне n-1 да бъде по-голяма от вероятността да се падне n-2, която пък да е по-голяма от вероятността да се падне n-3 и т.н.

В контекста на руската

В контекста на руската рулетка, нека имаме някакъв път, на който pathMultiplier.intensity() e 0.4. Т.е. rating = 0.4.

Сега, ние искаме, с вероятност (1 - rating), да убием пътя (еквивалентно на, с вероятност rating, да го оставим да продължи). Да го убием с вероятност (1 - 0.4) = 0.6 значи, че ако сме пуснали 100 пътя с рейтинг 0.4, то се очаква около 60 от тях да бъдат убити, 40 да оцелеят. Иначе казано, трябва ти една булева функция should_I_kill_this_path(), която връща случайно True/False, но в 60% от случаите връща True.

Разбира се, трябва да параметризираш въпросната случайна булева функция, така че да работи за произволен рейтинг от [0..1], не само за 0.4 :)