Como eu produzo aleatoriamente "divertidamente", em vez de pseudo-aleatório?

26

Estou fazendo um jogo que apresenta vários tipos diferentes de quebra-cabeças em sequência. Eu escolho cada quebra-cabeça com um número pseudo-aleatório. Para cada quebra-cabeça, há várias variações. Eu escolhi a variação com outro número pseudoaleatório. E assim por diante.

A questão é que, embora isso produza aleatoriedade quase verdadeira, não é isso que o jogador realmente deseja. O jogador normalmente quer o que eles percebem ser e se identifica como aleatório, mas apenas se não tender a repetir quebra-cabeças. Então, não é realmente aleatório. Apenas imprevisível.

Pensando bem, posso imaginar maneiras erradas de fazê-lo. Por exemplo, eliminar temporariamente as N opções mais recentes do conjunto de possibilidades ao selecionar uma nova opção. Ou atribuindo a cada escolha uma probabilidade igual, reduzindo a probabilidade de uma opção a zero na seleção e aumentando todas as probabilidades lentamente a cada seleção.

Suponho que exista uma maneira estabelecida de fazer isso, mas simplesmente não conheço a terminologia, portanto não consigo encontrá-la. Ninguem sabe? Ou alguém resolveu isso de uma maneira agradável?

algorithm random Hilton Campbell
fonte
4
O livro "AI Game Programming Wisdom 2" tem um capítulo sobre aleatoriedade filtrada que, pelo que me lembro, é praticamente o que você está procurando. No momento, eu não o tenho, então não posso realmente dar uma resposta completa.
287 Anton
Para tentar esclarecer: quando você diz 'não repetir quebra-cabeças', você quer dizer que não quer dois quebra-cabeças do mesmo tipo um ao lado do outro? Portanto, em outras palavras, se você acabou de escolher um sudoku, não ofereça outro quebra-cabeça de sudoku, mas se for o Sudoku # 19, não há problema em oferecer Picross # 19 a seguir (em outras palavras, o número da variação não importa) ?
Steven Stadnicki
2
Pergunta muito relacionada: stackoverflow.com/questions/910215/…
Chris Burt-Brown
11
OK, minha cópia do AI Game Programming Wisdom 2 acabou de chegar. Eu li o capítulo sobre aleatoriedade filtrada e verifiquei o código fonte. Esta é provavelmente a melhor abordagem. Ele permite que eu use apenas números aleatórios, mas depois filtre os números para que padrões inesperados não ocorram. Parece mais prova de balas do que a sacola aleatória.
Hilton Campbell
11
Mais uma atualização ... para meu aplicativo em particular, a aleatoriedade filtrada não foi suficiente. Eu realmente quero que o jogador jogue com todos os tipos e subtipos antes de repetir, então fui com uma sacola aleatória.
Hilton Campbell

Respostas:

25

Se você tiver um número finito de quebra-cabeças, poderá:

  • Construa uma lista de quebra-cabeças, todos eles ou alguns escolhidos aleatoriamente;
  • Embaralhe esta lista (consulte o Knuth Shuffle, por exemplo);
  • Deixe seu jogador jogar nessa lista;
  • Quando a lista estiver vazia, comece com uma nova.

EDITAR

Eu não sabia disso, mas navegar pelo SE me fez perceber que isso é realmente conhecido como "shuffle bag". Mais algumas informações aqui , aqui ou ali .

EDIT 2

O Knuth Shuffle clássico é assim:

To shuffle an array a of n elements (indices 0..n-1):
    for i from n − 1 down to 1 do
        j ← random integer with 0 ≤ j ≤ i
        exchange a[j] and a[i]

Steven Stadnicki apontou com razão em seu comentário que esse tipo de coisa não impede a repetição de uma remodelação. Uma maneira de levar isso em consideração é adicionar um caso especial para o último item:

To reshuffle an array a of n elements and prevent repetitions (indices 0..n-1):
    return if n <= 2

    // Classic Knuth Shuffle for all items *except* the last one
    for i from n − 2 down to 1 do
        j ← random integer with 0 ≤ j ≤ i
        exchange a[j] and a[i]

    // Special case for the last item
    // Exchange it with an item which is *not* the first one
    r ← random integer with 1 ≤ r ≤ n - 1
    exchange a[r] and a[n - 1]
Laurent Couvidou
fonte
11
Isso pode funcionar, mas você deve ter um pouco de cuidado se reorganizar após cada jogada para não começar com o mesmo item em que terminou.
Steven Stadnicki
@ Steven De fato. Este item pode ser excluído da nova lista. Na verdade, pode ser uma ideia criar apenas uma lista de alguns itens aleatórios e criar a próxima lista apenas com os itens restantes. Portanto, se você tiver 100 itens, construa, por exemplo, uma lista embaralhada de 10. Quando terminar com esta lista, construa o próximo com 10 itens nos 90 que não foram selecionados anteriormente.
Laurent Couvidou
+1. O suporte adicionado a esta técnica é "mais divertido": é assim que o Tetris, por exemplo, produz peças "aleatórias". Um conjunto de cada peça é embaralhado e iterado, o que evita as longas sequências de duplicatas que a verdadeira aleatoriedade produziria inevitavelmente.
KutuluMike #
11
@ Hilton Eu costumo não gostar desse tipo de abordagem "while loop, até que aleatoriamente me dê o que eu quero" ... Não é muito provável que isso cause problemas. Ainda assim, sempre sinto que essa é uma chamada para loops infinitos aleatórios ou quedas de desempenho - que são terríveis para depuração. A exclusão do último item da lista anterior da nova permite que você embaralhe apenas uma vez, para o mesmo resultado.
Laurent Couvidou
11
Você está certo, e eu tinha as mesmas reservas. Em vez de excluir o último item anterior, agora o embaralhe apenas uma vez e, se o último item anterior for o primeiro, troquei-o por algum outro item aleatoriamente.
Hilton Campbell
2

Uma variante da abordagem de lorancou: para cada tipo de quebra-cabeça, mantenha uma variedade de números (embaralhados); toda vez que você acertar um quebra-cabeça desse tipo, tire o próximo número da lista. por exemplo, digamos que você tenha quebra-cabeças de Sudoku, Picross e Kenken, cada um com os quebra-cabeças # 1..6. Você criaria três matrizes embaralhadas dos números 1..6, uma para cada tipo de quebra-cabeça:

  • Sudoku: [5, 6, 1, 3, 4, 2]
  • Picross: [6, 2, 4, 1, 3, 5]
  • KenKen: [3, 2, 5, 6, 4, 1]

Agora, você embaralha os tipos de quebra-cabeça como sugere Lororu; digamos que aparece [Picross, Sudoku, Kenken]. Então, toda vez que você acertar um quebra-cabeça de um determinado tipo, use o próximo número em sua 'lista aleatória'; No geral, sua apresentação de quebra-cabeça seria [Sudoku # 5, Picross # 6, Kenken # 3, Sudoku # 6, Picross # 2, Kenken # 2, ...]

Se você não deseja manter os quebra-cabeças na mesma ordem geral de cada vez no ciclo, acho que sua opção 'escolher aleatoriamente, ignorando as últimas escolhas' é a melhor. Existem maneiras de tornar isso um pouco mais eficiente também; por exemplo, digamos que você tenha 20 itens e queira ignorar os últimos 5 escolhidos. Em vez de escolher aleatoriamente um número 1..20 e 'rolar novamente' até obter um fora dos últimos 5, basta escolher um número 1..15 e percorrer seus tipos de quebra-cabeças por muitas etapas, apenas pulando sobre qualquer tipo de quebra-cabeça que seja foi escolhido (você pode fazer isso facilmente mantendo um conjunto de bits que contém os últimos 5 quebra-cabeças escolhidos).

Steven Stadnicki
fonte