Вероятности при последовательном отсечении шансов

Всё что связано с программированием на Lua
Diatlo
c7i.team
Сообщения: 249
Зарегистрирован: Пт ноя 06, 2009 6:04 am

Вероятности при последовательном отсечении шансов

Сообщение Diatlo » Пт ноя 28, 2014 12:31 pm

В нашем коде можно встретить следующие конструкции, последовательные проверки на 25% (или любой другой) шанс выпадения.
Разработчик видимо предполагал, что все варианты равновероятные.
Но для неподготовленного человека тут скрыт подвох, каждый следующий шаг в лесенке elseif
уменьшает шанс выпадения за счет выбивания большого количества шансов на первых шагах.
Визуально - это как пирамида - чем выше от земли тем меньше шанс.
Посмотрим на примере:

Код: Выделить всё

if     math.random(1, 100) > 75 then -- 25% от 100% = 25% шанс от исходных 100%
    ...
elseif math.random(1, 100) > 75 then -- 25% от 75/100  = 18,75% шанс от исходных 100%
    ...
elseif math.random(1, 100) > 75 then -- 25% от 75/100 * 75/100 = 14,0625% шанс от исходных 100%
    ...
elseif math.random(1, 100) > 75 then -- 25% от 75/100 * 75/100 * 75/100 = 10,546875% шанс от исходных 100%
    ...
else                         -- остаток 75% от 75/100 * 75/100 * 75/100 = 31,640625% шанс от исходных 100%
    ...
end


фактически, этот код можно улучшить так, обратившись 1 раз за получением случайного
числа (и округляя дробные вероятности до целого):

Код: Выделить всё

local rnd = math.random(1, 100)
if     rnd > 75 then -- 25% от 100% = 25% шанс от исходных 100%
    ...
elseif rnd > 56 then -- 25% от 75/100  = 18,75% шанс от исходных 100%
    ...
elseif rnd > 42 then -- 25% от 75/100 * 75/100 = 14,0625% шанс от исходных 100%
    ...
elseif rnd > 32 then -- 25% от 75/100 * 75/100 * 75/100 = 10,546875% шанс от исходных 100%
    ...
else         -- остаток 75% от 75/100 * 75/100 * 75/100 = 31,640625% шанс от исходных 100%
    ...
end


или даже так, если нужно получить однотипное значение:

Код: Выделить всё

local rnd_table = {1, 2, 3, 4, 5}
local value = rnd_table[math.random(1, 5)]
...


Если же нужно выполнить разные последовательности кода в каждом блоке - вот тут не хватает оператора swith,
которые разработчики Lua отказываются сделать. :)

Хотя можно выкрутиться и так:

Код: Выделить всё

local rnd_table = {
[1] = function () {...},
[2] = function () {...},
[3] = function () {...},
[4] = function () {...},
[5] = function () {...} }

rnd_table[math.random(1, 5)] () -- получаем функцию из таблицы и выполняем

Если разработчик не подозревает о такой лесенке шансов и ставит последним условием 1%, то можете представить,
какой шанс того, что этот 1% от (x/100 )^n шагов может выпасть. =)

Vant
c7i.team
Сообщения: 179
Зарегистрирован: Вс дек 05, 2010 4:22 am

Re: Вероятности при последовательном отсечении шансов

Сообщение Vant » Пн дек 01, 2014 6:12 pm

Код: Выделить всё

-- -------------------------------------------------------------
-- Неравные шансы
-- -------------------------------------------------------------

rnd = {}

rnd.tab = function( t )

    return t[ math.random( 1, #t ) ]
end

rnd.create = function( t )

    local res = {}

    for p1, p2 in pairs( t ) do
 
        for k = 1, p2 do
           
            table.insert( res, p1 )
        end
    end

    return res
end

-- -------------------------------------------------------------
-- Генерируем случайный предмет из списка с учетом его редкости
--

p01 = 3009  -- шанс  1 из 20  большой вкусный пирог
p02 = 3011  -- шанс  2 из 20  буханка хлеба
p03 = 3012  -- шанс  2 из 20  рулет с корицей
p04 = 3013  -- шанс  5 из 20  покрытая шоколадной стружкой булочка
p05 = 3014  -- шанс 10 из 20  пирожное с голубикой

local freq_obj = rnd.create({ [p01] = 1, [p02] = 2, [p03] = 2, [p04] = 5, [p05] = 10, })

local vnum = rnd.tab( freq_obj ) 

    obj = create_object( vnum )


-- -------------------------------------------------------------
-- Если идешь охотиться на Годзиллу, то шансы 50:50. Либо он тебя,
-- либо ОНА тебя – зависит от пола Годзиллы.

-- kick - шанс 25%  или 1
-- bash - шанс 75%  или 3

local freq_act = rnd.create({ ["kick"] = 1, ["bash"] = 3 })

local act = rnd.tab( freq_act ) 

    mob.execute( act )


-- -------------------------------------------------------------
-- Такой прием называется векторным вычислением
--

function f_atac( self, ch )
    self.cast( "dispel magic", 110, ch )
end

function f_heal( self, ch )
    self.cast( "heal", 110, self )
end

function f_nope( self, ch )

end

local atacker = rnd.create({ [f_heal] = 1, [f_atac] = 3, [f_nope] = 8 })
local healer  = rnd.create({ [f_heal] = 3, [f_atac] = 1, [f_nope] = 8 })

-- Обработчики события FIGHT:

-- Любим атаковать
function mob_atacker( self, ch )

    rnd.tab( atacker )( self, ch )
end

-- Любим лечиться
function mob_healer( self, ch )

    rnd.tab( healer )( self, ch )
end

-- Все зависит от ситуации
function mob_univer( self, ch )

    if self.hit > self.max_hit/2 then
       rnd.tab( atacker )( self, ch ) -- пока есть здоровье, атакуем
    else
       rnd.tab( healer )( self, ch )  -- здоровья мало - лечимся
    end
end


Upd: Пояснения к коду выше:

Допустим, у нас есть пять предметов и нам нужно, чтобы их выпадение отличалось по частоте.

Назовем предметы p1 p2 p3 p4 p5

Присвоим предмету p1 коэффициент 1. Этот коэффициент означает, что данный предмет имеет самую маленькую вероятность выпадения. Вероятность выпадения остальных предметов будем задавать относительно этого коэффициента.
Если теперь второму предмету присвоить коэффициент 2, то это будет означать, что предмет p2 будет выпадать в 2 раза чаще, чем p1.
Остальным предметам назначим коэффициенты 2, 3, 8. Это означает, что p3 будет выпадать в два, p4 в три и p5 в восемь раз чаще, чем первый предмет.

Как теперь реализовать этот механизм. Как вариант, так:

Код: Выделить всё

t_ver = { p1, p2, p2, p3, p3, p4, p4, p4, p5, p5, p5, p5, p5, p5, p5, p5 }

obj = t_ver[ math.random( 1, #t_ver ) ]


или с учетом функции:

Код: Выделить всё

function rnd_tab(tab)
    return tab[ math.random(1,#tab) ]
end

так:

t_ver = { p1, p2, p2, p3, p3, p4, p4, p4, p5, p5, p5, p5, p5, p5, p5, p5 }

obj = rnd_tab( t_ver )


Здесь таблица t_ver заполняется каждым из нужных нам предметов в количестве, соответствующем его коэффициенту.

Нетрудно заметить, что в нашем случае в половине случаев будет выпадать предмет p5. Определить вероятность выпадения предмета несложно - она равна коэффициенту предмета, деленному на сумму всех коэффициентов.

Подсчитаем:

p1 -- 1 / 16 = 0,0625 ( 6.25 % )
p2 -- 2 / 16 = 0,125 ( 12.50 % )
p3 -- 2 / 16 = 0,125 ( 12.50 % )
p4 -- 3 / 16 = 0,1875 ( 18.75 % )
p5 -- 8 / 16 = 0.5 ( 50.00 % )

В случае, если требуется более тонкая градация вероятностей, начальный коэффициент следует брать большим единицы. Например для шага 0.5 начальный коэффициент будет 2. При этом нужно помнить, что соответственно будет увеличиваться и таблица t_ver.

Пусть теперь разница между предметами составит 1,5 2,5 3,5 4,5 раз. Тогда коэффициенты будут равны:

для p1 -- 2, p2 -- 3, p3 -- 5, p4 -- 7, p5 -- 9

Код: Выделить всё

Код выглядит так:

t_ver = { p1, p1,
          p2, p2, p2,
          p3, p3, p3, p3, p3,
          p4, p4, p4, p4, p4, p4, p4,
          p5, p5, p5, p5, p5, p5, p5, p5, p5 }

obj = rnd_tab( t_ver )


В случае, когда количество предметов (вариантов выбора) большое, имеет смысл поручить построение таблицы t_ver самой программе,
чем и занимается функция rnd.create в первом примере кода.

Следует хорошо понимать, что происходит с вероятностью выпадения одного предмета при увеличении общего количества предметов. Например, при равных вероятностях, но для разного количества предметов:

Код: Выделить всё

 2 - 0,5000
 3 - 0,3333
 4 - 0,2500
 5 - 0,2000
 6 - 0,1666
 7 - 0,1428
 8 - 0,1250
 9 - 0,1111
10 - 0,1000


Вернуться в «Lua»

Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и 1 гость