Como crio uma coleção ponderada e depois escolho um elemento aleatório?

34

Eu tenho uma caixa de itens que eu quero preencher com um item aleatório. Mas quero que cada item tenha uma chance diferente de ser escolhido. Por exemplo:

  • 5% de chance de 10 pontos de ouro
  • 20% de chance de espada
  • 45% de chance de escudo
  • 20% de chance de armadura
  • 10% de chance de poção

Como posso fazer para selecionar exatamente um dos itens acima, onde essas porcentagens são as respectivas chances de obter o saque?

Evorlor
fonte
1
Para sua informação, em teoria, o tempo O (1) por amostra é possível para qualquer distribuição finita, mesmo uma distribuição cujas entradas mudam dinamicamente. Consulte, por exemplo, cstheory.stackexchange.com/questions/37648/… .
Neal Young

Respostas:

37

A solução de probabilidades codificadas por software

A solução de probabilidade codificada tem a desvantagem de que você precisa definir as probabilidades no seu código. Você não pode determiná-los em tempo de execução. Também é difícil de manter.

Aqui está uma versão dinâmica do mesmo algoritmo.

  1. Crie uma matriz de pares de itens reais e o peso de cada item
  2. Quando você adiciona um item, o peso do item precisa ser seu próprio peso mais a soma dos pesos de todos os itens que já estão na matriz. Portanto, você deve acompanhar a soma separadamente. Especialmente porque você precisará dele para o próximo passo.
  3. Para recuperar um objeto, gere um número aleatório entre 0 e a soma dos pesos de todos os itens
  4. itere a matriz do início ao fim até encontrar uma entrada com um peso maior ou igual ao número aleatório

Aqui está uma implementação de amostra em Java na forma de uma classe de modelo que você pode instanciar para qualquer objeto que seu jogo use. Você pode adicionar objetos ao método .addEntry(object, relativeWeight)e escolher uma das entradas adicionadas anteriormente com.get()

import java.util.ArrayList;
import java.util.List;
import java.util.Random;

public class WeightedRandomBag<T extends Object> {

    private class Entry {
        double accumulatedWeight;
        T object;
    }

    private List<Entry> entries = new ArrayList<>();
    private double accumulatedWeight;
    private Random rand = new Random();

    public void addEntry(T object, double weight) {
        accumulatedWeight += weight;
        Entry e = new Entry();
        e.object = object;
        e.accumulatedWeight = accumulatedWeight;
        entries.add(e);
    }

    public T getRandom() {
        double r = rand.nextDouble() * accumulatedWeight;

        for (Entry entry: entries) {
            if (entry.accumulatedWeight >= r) {
                return entry.object;
            }
        }
        return null; //should only happen when there are no entries
    }
}

Uso:

WeightedRandomBag<String> itemDrops = new WeightedRandomBag<>();

// Setup - a real game would read this information from a configuration file or database
itemDrops.addEntry("10 Gold",  5.0);
itemDrops.addEntry("Sword",   20.0);
itemDrops.addEntry("Shield",  45.0);
itemDrops.addEntry("Armor",   20.0);
itemDrops.addEntry("Potion",  10.0);

// drawing random entries from it
for (int i = 0; i < 20; i++) {
    System.out.println(itemDrops.getRandom());
}

Aqui está a mesma classe implementada em C # para o seu projeto Unity, XNA ou MonoGame:

using System;
using System.Collections.Generic;

class WeightedRandomBag<T>  {

    private struct Entry {
        public double accumulatedWeight;
        public T item;
    }

    private List<Entry> entries = new List<Entry>();
    private double accumulatedWeight;
    private Random rand = new Random();

    public void AddEntry(T item, double weight) {
        accumulatedWeight += weight;
        entries.Add(new Entry { item = item, accumulatedWeight = accumulatedWeight });
    }

    public T GetRandom() {
        double r = rand.NextDouble() * accumulatedWeight;

        foreach (Entry entry in entries) {
            if (entry.accumulatedWeight >= r) {
                return entry.item;
            }
        }
        return default(T); //should only happen when there are no entries
    }
}

E aqui está um em JavaScript :

var WeightedRandomBag = function() {

    var entries = [];
    var accumulatedWeight = 0.0;

    this.addEntry = function(object, weight) {
        accumulatedWeight += weight;
        entries.push( { object: object, accumulatedWeight: accumulatedWeight });
    }

    this.getRandom = function() {
        var r = Math.random() * accumulatedWeight;
        return entries.find(function(entry) {
            return entry.accumulatedWeight >= r;
        }).object;
    }   
}

Pró:

  • Pode lidar com qualquer proporção de peso. Você pode ter itens com probabilidade astronomicamente pequena no conjunto, se desejar. Os pesos também não precisam somar 100.
  • Você pode ler os itens e pesos em tempo de execução
  • Uso de memória proporcional ao número de itens na matriz

Contra:

  • Requer mais programação para acertar
  • Na pior das hipóteses, pode ser necessário repetir toda a matriz ( O(n)complexidade do tempo de execução). Portanto, quando você tem um conjunto muito grande de itens e desenha com muita frequência, pode ficar lento. Uma otimização simples é colocar os itens mais prováveis ​​primeiro, para que o algoritmo termine mais cedo na maioria dos casos. Uma otimização mais complexa que você pode fazer é explorar o fato de que a matriz é classificada e fazer uma pesquisa de bissecção. Isso leva apenas O(log n)tempo.
  • Você precisa criar a lista na memória antes de poder usá-la (embora você possa adicionar itens facilmente em tempo de execução. A remoção de itens também pode ser adicionada, mas isso exigiria a atualização dos pesos acumulados de todos os itens que vêm após a entrada removida, que novamente tem o O(n)pior tempo de execução)
Philipp
fonte
2
O código C # pode ser gravado usando LINQ: return inputs.FirstOrDefault (e => e.accumulatedWeight> = r). Mais importante, há uma pequena possibilidade de que, devido à perda de precisão do ponto flutuante, esse algoritmo retorne nulo se o valor aleatório ficar apenas um pouquinho maior que o valor acumulado. Como precaução, você pode adicionar um valor pequeno (digamos, 1.0) ao último elemento, mas então você deve declarar explicitamente em seu código que a lista é final.
IMIL
1
Uma pequena variante disso que eu usei pessoalmente, se você quiser que os valores de peso em tempo de execução não sejam alterados para o valor de peso acima de todo o anterior, você pode subtrair o peso de cada entrada passada do seu valor aleatório, parando quando o valor aleatório é menor do que o atual peso itens (ou quando subtraindo o peso faz com que o valor <0)
Lunin
2
@ BlueRaja-DannyPflughoeft otimização prematura ... a pergunta era sobre a seleção de um objeto em uma caixa de pilhagem aberta. Quem abrirá 1000 caixas por segundo?
IMIL
4
@IMil: Não, a questão é geral para a seleção de itens ponderados aleatórios . Para as caixas de loot especificamente, essa resposta provavelmente é boa porque há um pequeno número de itens e as probabilidades não mudam (embora, como essas geralmente sejam feitas em um servidor, 1000 / s não sejam irrealistas para um jogo popular) .
BlueRaja - Danny Pflughoeft
4
@opa então sinalize para fechar como um idiota. É realmente errado votar uma boa resposta apenas porque a pergunta já foi feita antes?
precisa
27

Nota: Criei uma biblioteca C # para esse problema exato

As outras soluções são boas se você tiver apenas um pequeno número de itens e suas probabilidades nunca mudarem. No entanto, com muitos itens ou probabilidades variáveis (por exemplo, removendo itens após selecioná-los) , você desejará algo mais poderoso.

Aqui estão as duas soluções mais comuns (ambas incluídas na biblioteca acima)

Método de Alias ​​de Walker

Uma solução inteligente que é extremamente rápida ( O(1)!) Se suas probabilidades são constantes. Em essência, o algoritmo cria um alvo de dardos 2D ("tabela de alias") a partir de suas probabilidades e lança um dardo nele.

Dartboard

Existem muitos artigos on-line sobre como funciona, se você quiser saber mais.

O único problema é que, se suas probabilidades mudarem, você precisará gerar novamente a tabela de alias, que é lenta. Portanto, se você precisar remover itens após a seleção, essa não é a solução para você.

Solução baseada em árvore

A outra solução comum é criar uma matriz em que cada item armazene a soma de sua probabilidade e todos os itens anteriores. Em seguida, basta gerar um número aleatório a partir de [0,1) e fazer uma pesquisa binária para onde esse número está na lista.

Essa solução é muito fácil de codificar / entender, mas a seleção é mais lenta que o método de alias de Walker e a alteração das probabilidades ainda é O(n). Podemos aprimorá-lo transformando o array em uma árvore de pesquisa binária, onde cada nó controla a soma das probabilidades em todos os itens de sua subárvore. Então, quando geramos o número de [0,1), podemos simplesmente descer a árvore para encontrar o item que ela representa.

Isso nos O(log n)permite escolher um item e alterar as probabilidades! Isso torna NextWithRemoval()extremamente rápido!

Os resultados

Aqui estão alguns benchmarks rápidos da biblioteca acima, comparando essas duas abordagens

         Benchmarks do WeightedRandomizer | Árvore Tabela
-------------------------------------------------- ---------------------------------
Adicione () x10000 + NextWithReplacement () x10: | 4 ms | 2 ms
Adicione () x10000 + NextWithReplacement () x10000: | 7 ms | 4 ms
Adicione () x10000 + NextWithReplacement () x100000: | 35 ms | 28 ms
(Add () + NextWithReplacement ()) x10000 (intercalado) | 8 ms | 5403 ms
Adicione () x10000 + NextWithRemoval () x10000: | 10 ms | 5948 ms

Como você pode ver, no caso especial de probabilidades estáticas (sem alterações), o método Alias ​​de Walker é cerca de 50 a 100% mais rápido. Mas nos casos mais dinâmicos, a árvore é várias ordens de magnitude mais rapidamente !

BlueRaja - Danny Pflughoeft
fonte
A solução baseada em árvore também nos fornece um tempo de execução decente ( nlog(n)) ao classificar itens por peso.
Nathan Merrill
2
Sou cético em relação aos seus resultados, mas esta é a resposta correta. Não sei por que essa não é a resposta principal, considerando que essa é realmente a maneira canônica de lidar com esse problema.
whn
Qual arquivo contém a solução baseada em árvore? Segundo, sua tabela de referência: o Alias ​​de Walker é a coluna "tabela"?
Yakk
1
@ Yakk: O código para a solução baseada em árvore está aqui . Ele é construído sobre uma implementação de código aberto de uma árvore AA . E 'sim' para sua segunda pergunta.
BlueRaja - Danny Pflughoeft
1
A parte de Walker é apenas apenas link.
precisa saber é o seguinte
17

A solução Wheel of Fortune

Você pode usar esse método quando as probabilidades no seu pool de itens tiverem um denominador comum bastante grande e você precisar extrair dele com muita frequência.

Crie uma matriz de opções. Mas coloque cada elemento nele várias vezes, com o número de duplicatas de cada elemento proporcional à sua chance de aparecer. Para o exemplo acima, todos os elementos têm probabilidades que são multiplicadores de 5%, então você pode criar uma matriz de 20 elementos como este:

10 gold
sword
sword
sword
sword
shield
shield
shield
shield
shield
shield
shield
armor
armor
armor
armor
potion
potion

Em seguida, basta escolher um elemento aleatório dessa lista, gerando um número inteiro aleatório entre 0 e o comprimento da matriz - 1.

Desvantagens:

  • Você precisa criar a matriz na primeira vez que desejar gerar um item.
  • Quando um de seus elementos deve ter uma probabilidade muito baixa, você acaba com uma matriz muito grande, que pode exigir muita memória.

Vantagens:

  • Quando você já possui a matriz e deseja extraí-la várias vezes, é muito rápido. Apenas um número inteiro aleatório e um acesso à matriz.
Philipp
fonte
3
Como uma solução híbrida para evitar a segunda desvantagem, você pode designar o último slot como "outro" e manipulá-lo por outros meios, como a abordagem de matriz de Philipp. Portanto, você pode preencher esse último espaço com uma matriz que oferece 99,9% de chance de uma poção e apenas 0,1% de chance de uma poção Epic Scepter of the Apocalypse. Essa abordagem em duas camadas aproveita as vantagens de ambas as abordagens.
Cort Ammon - Restabelece Monica
1
Eu uso um pouco uma variação disso no meu próprio projeto. O que faço é calcular cada item e peso, e armazená-los em uma matriz, [('gold', 1),('sword',4),...]somar todos os pesos e, em seguida, rolar um número aleatório de 0 até a soma, iterar a matriz e calcular onde o número aleatório cai (ou seja, a reduce) Funciona bem para matrizes que são atualizadas com freqüência e sem grandes quantidades de memória.
1
@Thebluefish Essa solução é descrita na minha outra resposta "as probabilidades Solução Soft-codificado"
Philipp
7

A solução de probabilidades codificadas

A maneira mais simples de encontrar um item aleatório de uma coleção ponderada é percorrer uma cadeia de instruções if-else, onde cada if-else provavelmente aumenta, pois a anterior não é atingida.

int rand = random(100); //Random number between 1 and 100 (inclusive)
if(rand <= 5) //5% chance
{
    print("You found 10 gold!");
}
else if(rand <= 25) //20% chance
{
    print("You found a sword!");
}
else if(rand <= 70) //45% chance
{
    print("You found a shield!");
}
else if(rand <= 90) //20% chance
{
    print("You found armor!");
}
else //10% chance
{
    print("You found a potion!");
}

A razão pela qual os condicionais são iguais à sua chance, mais todas as chances dos condicionais anteriores, é porque os condicionais anteriores já eliminaram a possibilidade de serem esses itens. Portanto, para o condicional do escudo else if(rand <= 70), 70 é igual à chance de 45% do escudo, mais a chance de 5% do ouro e 20% de chance da espada.

Vantagens:

  • Fácil de programar, porque não requer estruturas de dados.

Desvantagens:

  • Difícil de manter, porque você precisa manter suas taxas de queda no seu código. Você não pode determiná-los em tempo de execução. Portanto, se você quiser algo mais à prova do futuro, verifique as outras respostas.
Evorlor
fonte
3
Isso seria realmente irritante de manter. Por exemplo, se você deseja remover o ouro e fazer a poção, é necessário ajustar as probabilidades de todos os itens entre eles.
Alexander - Restabelece Monica
1
Para evitar o problema mencionado pelo @Alexander, você pode subtrair a taxa atual em cada etapa, em vez de adicioná-la a cada condição.
AlexanderJ93
2

Em C #, você pode usar uma varredura do Linq para executar seu acumulador e comparar com um número aleatório no intervalo de 0 a 100.0f e .First () a obter. Então, como uma linha de código.

Então, algo como:

var item = a.Select(x =>
{
    sum += x.prob;
    if (rand < sum)
        return x.item;
    else
        return null;
 }).FirstOrDefault());

sumé um número inteiro inicializado zero e aé uma lista de estruturas de prob / item / tuplas / instâncias. randé um número aleatório gerado anteriormente no intervalo.

Isso simplesmente acumula a soma na lista de intervalos até exceder o número aleatório selecionado anteriormente e retorna o item ou nulo, onde nulo seria retornado se o intervalo de números aleatórios (por exemplo, 100) for menor que o intervalo de ponderação total por engano , e o número aleatório selecionado está fora da faixa de ponderação total.

No entanto, você notará que os pesos no OP correspondem à distribuição normal (curva de Bell). Penso que, em geral, você não desejará intervalos específicos, tenderá a desejar uma distribuição que diminua em torno de uma curva em sino ou apenas em uma curva exponencial decrescente (por exemplo). Nesse caso, você pode usar apenas uma fórmula matemática para gerar um índice em uma matriz de itens, classificados em ordem de probabilidade preferida. Um bom exemplo é o CDF na distribuição normal

Também um exemplo aqui .

Outro exemplo é que você pode usar um valor aleatório de 90 a 180 graus para obter o quadrante inferior direito de um círculo, usar o componente x usando cos (r) e usá-lo para indexar em uma lista priorizada.

Com diferentes fórmulas, você pode ter uma abordagem geral, onde você apenas insere uma lista priorizada de qualquer tamanho (por exemplo, N) e mapeia o resultado da fórmula (por exemplo: cos (x) é de 0 a 1) por multiplicação (por exemplo: Ncos (x ) = 0 a N) para obter o índice.

Sentinela
fonte
3
Você poderia nos dar essa linha de código se for apenas uma linha? Eu não sou tão familiarizado com C #, então não sei o que você quer dizer.
HEGX64
@ HEGX64 adicionado, mas usando o celular e o editor não está funcionando. Você pode editar?
Sentinel
4
Você pode alterar esta resposta para explicar o conceito por trás dela, em vez de uma implementação específica em um idioma específico?
Raimund Krämer
@ RaimundKrämer Erm, pronto?
Sentinel
Voto negativo sem explicação = inútil e anti-social.
WGroleau
1

As probabilidades não precisam ser codificadas. Os itens e os limites podem estar juntos em uma matriz.

for X in itemsrange loop
  If items (X).threshold < random() then
     Announce (items(X).name)
     Exit loop
  End if
End loop

Você ainda precisa acumular os limites, mas pode fazê-lo ao criar um arquivo de parâmetro em vez de codificá-lo.

WGroleau
fonte
3
Você poderia elaborar como calcular o limite correto? Por exemplo, se você tiver três itens com 33% de chance cada, como você criaria esta tabela? Como um novo random () é gerado a cada vez, o primeiro precisará de 0,3333, o segundo precisará de 0,5 e o último precisará de 1,0. Ou eu li o algoritmo errado?
pipe
Você calcula da mesma forma que os outros em suas respostas. Para probabilidades iguais de X itens, o primeiro limiar é 1 / X, o segundo, 2 / X, etc.
WGroleau
Fazer isso por três itens nesse algoritmo faria os limites 1/3, 2/3 e 3/3, mas as probabilidades de resultado 1/3, 4/9 e 2/9 para o primeiro, segundo e terceiro itens. Você realmente quer ter a chamada random()no loop?
pipe
Não, isso é definitivamente um bug. Cada verificação precisa do mesmo número aleatório.
WGroleau
0

Eu fiz esta função: https://github.com/thewheelmaker/GDscript_Weighted_Random Now! no seu caso, você pode usá-lo assim:

on_normal_case([5,20,45,20,10],0)

Ele fornece apenas um número entre 0 e 4, mas você pode colocá-lo na matriz onde obteve os itens.

item_array[on_normal_case([5,20,45,20,10],0)]

Ou em função:

item_function(on_normal_case([5,20,45,20,10],0))

Aqui está o código. Eu fiz isso no GDscript, você pode, mas pode alterar outro idioma, também verificar erros de lógica:

func on_normal_case(arrayy,transformm):
    var random_num=0
    var sum=0
    var summatut=0
    #func sumarrays_inarray(array):
    for i in range(arrayy.size()):
        sum=sum+arrayy[i]
#func no_fixu_random_num(here_range,start_from):
    random_num=randi()%sum+1
#Randomies be pressed down
#first start from zero
    if 0<=random_num and random_num<=arrayy[0]:
        #print(random_num)
        #print(array[0])
        return 0+ transformm
    summatut=summatut+arrayy[0]
    for i in range(arrayy.size()-1):
        #they must pluss together
        #if array[i]<=random_num and random_num<array[i+1]:
        if summatut<random_num and random_num<=summatut+arrayy[i+1]:
            #return i+1+transform
            #print(random_num)
            #print(summatut)
            return i+1+ transformm

        summatut=summatut+arrayy[i+1]
    pass

Funciona assim: on_normal_case ([50,50], 0) Isso fornece 0 ou 1, tem a mesma probabilidade ambos.

on_normal_case ([50,50], 1) Isso fornece 1 ou 2, tem a mesma probabilidade ambos.

on_normal_case ([20,80], 1) Isso fornece 1 ou 2, pois possui maiores alterações para obter dois.

on_normal_case ([20,80,20,20,30], 1) Isso fornece números aleatórios entre 1 e 5 e números maiores são mais prováveis ​​que números menores.

on_normal_case ([20,80,0,0,20,20,30,0,0,0,33], 45) Esse lançamento corta entre os números 45,46,49,50,51,56 que você vê quando há é zero, nunca ocorre.

Portanto, sua função retorna apenas um número aleatório que depende do comprimento dessa matriz e do número de transformadores, e as ints na matriz são pesos de probabilidade que um número pode ocorrer, onde esse número está localizado na matriz, pluss transformm number.

Narutofan
fonte