How do I produce "enjoyably" random, as opposed to pseudo-random?

Question

I'm making a game which presents a number of different kinds of puzzles in sequence. I choose each puzzle with a pseudorandom number. For each puzzle, there are a number of variations. I choose the variation with another pseudorandom number. And so on.

The thing is, while this produces near-true randomness, this isn't what the player really wants. The player typically wants what they perceive to be and identify as random, but only if it doesn't tend to repeat puzzles. So, not really random. Just unpredictable.

Giving it some thought, I can imagine hacky ways of doing it. For example, temporarily eliminating the most recent N choices from the set of possibilities when selecting a new choice. Or assigning every choice an equal probability, reducing a choice's probability to zero on selection, and then increasing all probabilities slowly with each selection.

I assume there's an established way of doing this, but I just don't know the terminology so I can't find it. Anyone know? Or has anyone solved this in a pleasing way?

Answer 1

If you have a finite number of puzzles, you can:

• Build a list of puzzles, either all of them or some randomly picked;
• Shuffle this list (see the Knuth Shuffle for instance);
• Let your player play through this list;
• When the list is empty, start with a new one.

EDIT

I didn't know this, but browsing SE made me realize that this is actually known as a "shuffle bag". Some more infos here, here or there.

EDIT 2

The classic Knuth Shuffle goes this way:

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 rightfully pointed out in his comment that this kind of thing doesn't prevent repetition on a reshuffle. A way to take this into account is to add a special case for the last 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]

Answer 2

A variant on lorancou's approach: for each puzzle type, keep an array of (shuffled) puzzle numbers; then every time you hit a puzzle of that type, get the next number off the list. for instance, let's say you have Sudoku, Picross and Kenken puzzles, each with puzzles #1..6. You'd create three shuffled arrays of the numbers 1..6, one for each puzzle type:

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

Now, you'd shuffle the puzzle types just like lorancu suggests; let's say it comes up [Picross, Sudoku, Kenken]. Then every time you hit a puzzle of a given type, use the next number in its 'shuffle list'; overall your puzzle presentation would be [Sudoku #5, Picross #6, Kenken #3, Sudoku #6, Picross #2, Kenken #2, ...]

If you don't want to keep the puzzles in the same overall order each time through the loop, then I think your 'choose randomly, ignoring the last few picks' option is the best. There are ways you can make this a little bit more efficient, too; for instance, let's say that you have 20 things and you want to ignore the last 5 picked. Then instead of randomly choosing a number 1..20 and 'rerolling' until you get one outside the last 5, instead just choose a number 1..15 and walk through your puzzle types that many steps, just skipping over any puzzle type that's been picked (you can do this easily by keeping a bit array that holds the last 5 picked puzzles).