Как создать «приятно» случайное, а не псевдослучайное?

26

Я делаю игру, в которой последовательно представлены различные виды головоломок. Я выбираю каждую головоломку с псевдослучайным числом. Для каждой головоломки есть несколько вариантов. Я выбираю вариант с другим псевдослучайным числом. И так далее.

Дело в том, что, хотя это приводит к почти случайной случайности, это не то, чего действительно хочет игрок. Игрок, как правило, хочет, чтобы то, что он воспринимает, был идентифицирован как случайный, но только если он не склонен повторять головоломки. Так что не совсем случайно. Просто непредсказуемо.

Думая об этом, я могу представить себе хакерские способы сделать это. Например, временно исключая самые последние N вариантов из набора возможностей при выборе нового варианта. Или присваивая каждому варианту равную вероятность, уменьшая вероятность выбора до нуля при выборе, а затем медленно увеличивая все вероятности с каждым выбором.

Я предполагаю, что есть установленный способ сделать это, но я просто не знаю терминологию, поэтому я не могу ее найти. Кто-нибудь знает? Или кто-нибудь решил это приятным способом?

Хилтон Кэмпбелл
источник
4
В книге «Мудрость программирования игр AI 2» есть глава, посвященная отфильтрованной случайности, которая, насколько я помню, в значительной степени является именно тем, что вы ищете. У меня его сейчас нет, поэтому я не могу дать вам полный ответ.
Антон
Чтобы попытаться уточнить: когда вы говорите «не повторять головоломки», вы имеете в виду, что вы просто не хотите, чтобы две головоломки одного типа рядом друг с другом? Другими словами, если вы только что выбрали судоку, не предлагайте другую загадку судоку, но если это была судоку №19, тогда можно предложить Picross # 19 далее (другими словами, номер варианта не имеет значения) ?
Стивен Стадницкий,
2
Очень связанный вопрос: stackoverflow.com/questions/910215/…
Крис Бурт-Браун
1
Хорошо, моя копия AI Game Programming Wisdom 2 только что прибыла. Я прочитал главу о фильтрованной случайности и проверил исходный код. Это, наверное, лучший подход. Это позволяет мне просто использовать случайные числа, но затем фильтровать числа, чтобы не возникало неожиданных паттернов. Это кажется более пуленепробиваемым, чем случайная сумка.
Хилтон Кэмпбелл
1
Еще одно обновление ... для моего конкретного приложения, отфильтрованная случайность не совсем это сделала. Я действительно хочу, чтобы игрок проиграл все типы и подтипы, прежде чем повторить, поэтому я пошел с сумкой в ​​случайном порядке.
Хилтон Кэмпбелл

Ответы:

25

Если у вас есть конечное число головоломок, вы можете:

  • Составьте список головоломок, все они или некоторые случайно выбранные;
  • Перемешать этот список (см., Например, Knuth Shuffle );
  • Пусть ваш игрок играет через этот список;
  • Когда список пуст, начните с нового.

РЕДАКТИРОВАТЬ

Я не знал этого, но просмотр SE заставил меня осознать, что это на самом деле известно как «случайная сумка». Еще немного информации здесь , здесь или там .

РЕДАКТИРОВАТЬ 2

Классический Кнут Шаффл идет следующим образом:

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]

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

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]
Лоран Кувиду
источник
1
Это может сработать, но вы должны быть немного осторожнее, если вы будете переставлять после каждого прохождения, чтобы не начинать с того же предмета, на котором вы закончили.
Стивен Стадницкий,
@ Действительно Стивен. Этот элемент может быть исключен из нового списка. На самом деле, это может быть идея создать список только из нескольких случайных элементов и создать следующий список только с оставшимися элементами. Поэтому, если у вас есть 100 предметов, создайте, например, перетасованный список из 10. Когда закончите с этим списком, постройте следующий из 10 предметов из 90, которые не были выбраны ранее.
Лоран Кувиду
+1. Добавлена ​​поддержка этой техники, которая была «более веселой»: так тетрис, например, производит «случайные» кусочки. Набор из одного фрагмента перетасовывается и перебирается, что позволяет избежать длинных последовательностей дубликатов, которые неизбежно приведет к истинной случайности.
KutuluMike
1
@ Хилтон: Мне не нравится такой подход «пока цикл не дает мне то, что я хочу», но вряд ли это вызовет какие-либо проблемы. Но, тем не менее, я всегда чувствую, что это вызов случайных бесконечных циклов или падений производительности, которые ужасно отлаживаются. Исключение последнего элемента из предыдущего списка из нового позволяет вам перетасовать только один раз для того же результата.
Лоран Кувиду
1
Вы правы, и у меня были такие же оговорки. Вместо того, чтобы исключить предыдущий последний элемент, у меня теперь он просто перетасовывается один раз, а затем, если предыдущий последний элемент теперь является первым, я случайным образом меняю его на другой элемент.
Хилтон Кэмпбелл
2

Вариант подхода Лоранку: для каждого типа головоломки сохраняйте массив (перемешанных) номеров головоломки; затем каждый раз, когда вы нажимаете на головоломку этого типа, убирайте следующий номер из списка. например, допустим, у вас есть головоломки Sudoku, Picross и Kenken, каждая из которых содержит головоломки 1..6. Вы создали бы три перемешанных массива чисел 1..6, по одному для каждого типа головоломки:

  • Судоку: [5, 6, 1, 3, 4, 2]
  • Picross: [6, 2, 4, 1, 3, 5]
  • КенКен: [3, 2, 5, 6, 4, 1]

Теперь вы бы перемешали типы головоломок, как предлагает Лоранку; допустим, это подходит [Picross, Sudoku, Kenken]. Затем каждый раз, когда вы нажимаете на головоломку определенного типа, используйте следующий номер в «списке случайных чисел»; В целом, ваша презентация головоломки будет [Судоку № 5, Picross № 6, Кенкен № 3, Судоку № 6, Picross № 2, Кенкен № 2, ...]

Если вы не хотите держать головоломки в одном и том же общем порядке каждый раз в цикле, то я думаю, что ваш вариант «выбрать случайным образом, игнорируя последние несколько выборов» является лучшим. Есть способы сделать это немного более эффективным; например, предположим, что у вас есть 20 вещей, и вы хотите игнорировать последние 5 выбранных. Затем вместо случайного выбора числа 1..20 и «перемотки» до тех пор, пока вы не получите одно из последних 5, вместо этого просто выберите число 1..15 и пройдитесь по множеству шагов ваших типов головоломки, просто пропустив любой тип головоломки, который выбранный (вы можете сделать это легко, сохранив битовый массив, содержащий последние 5 выбранных головоломок).

Стивен Стадницки
источник