Go Down

Topic: Foolproofing a randomizer (Read 3326 times) previous topic - next topic

PSneep

Hiya! First post after lurking around for a while, here goes!

I'm building a somewhat simple, random 'Hotkey Presser' by using a Teensy (which mimics a USB keyboard) and the Arduino programming environment. Basically, I'm imitating this guy: http://blog.makezine.com/archive/2011/04/the-awesome-button.html, but I've replaced his words by letters and numbers and added some more input buttons. Here's the code:

Code: [Select]
// Defining first category of random keys (letters)
const byte randomLetters = 20;
char* letters[randomLetters] = {
  "a", "b", "c", "d", "e", "f", "g", "h", "i",
  "j", "k", "l", "m", "n", "o", "p", "q", "r",
  "s", "t" };
 
// Defining second category of random keys (numbers)
  const byte randomNumbers = 10;
char* numbers[randomNumbers] = {
  "1", "2", "3", "4", "5", "6", "7", "8", "9", "0"};
 
// Hello buttons, we will use you. Ha!
int button1 = 0;
int button2 = 1;
int button3 = 2;


void setup(){
  Serial.begin(9600);
  randomSeed(analogRead(0));
  pinMode(button1,INPUT_PULLUP);
  pinMode(button2,INPUT_PULLUP);
  pinMode(button3,INPUT_PULLUP);
  delay(500);
}


void loop (){
  if(digitalRead(button1) == LOW)  //read buttonpress on button1

  {
   //generate a random letter, print it to the Mac:
    Keyboard.print(letters[random(0,randomLetters)]);
    Keyboard.print("");
   
    delay(300); //little delay so we only get 1 letter at a time
  }
 

if(digitalRead(button2) == LOW) //read buttonpress on button2

  {
    //generate a random letter, print it to the Mac
    Keyboard.print(letters[random(0,randomLetters)]);
    Keyboard.print("");
    delay(300);
  }
 

if(digitalRead(button3) == LOW) //read buttonpress on button3
  {
   //generate a random number, print it to the Mac
    Keyboard.print(numbers[random(0,randomNumbers)]);
    Keyboard.print("");
    delay(300);
  } 
}


That works fine and all, but I need a little more functionality. For example, it should not be possible for two exactly the same letters to show up right after another (aa, bb, etc.). So I think this is what it needs to do:

1 - After randomizing, check if the current 'random result' matches the previous random result.
2 - If so, randomize and check again.
3 - If not, print the result, but remember it so we can compare the next result with it.

I was thinking of making oldResult and currentResult variables and somehow fill them with whatever the randomfunction gave and gives, but I miss the code knowhow to actually do this without getting quite a lot of errors. So could anybody help me out a little? : 0

Thanks in advance!

johnwasser

Code: [Select]
char oldResult = 0;

void loop ()
    {
    char currentResult;

    if(digitalRead(button1) == LOW)  //read buttonpress on button1

       {
   //generate a random letter, print it to the Mac:
   
    do {
        currentResult = letters[random(0,randomLetters)];
        } while (currentResult == oldResult);
    oldResult = currentResult;
    Keyboard.print(currentResult);
    Keyboard.print("");
   
    delay(300); //little delay so we only get 1 letter at a time
  }
 

if(digitalRead(button2) == LOW) //read buttonpress on button2

  {
    do {
        currentResult = letters[random(0,randomLetters)];
        } while (currentResult == oldResult);
    oldResult = currentResult;
    Keyboard.print(currentResult);
    Keyboard.print("");
    delay(300);
  }
 

if(digitalRead(button3) == LOW) //read buttonpress on button3
  {
   //generate a random number, print it to the Mac
    do {
        currentResult = numbers[random(0,randomNumbers)];
        } while (currentResult == oldResult);
    oldResult = currentResult;
    Keyboard.print(currentResult);
    Keyboard.print("");
    delay(300);
  } 
}


Send Bitcoin tips to: 1L3CTDoTgrXNA5WyF77uWqt4gUdye9mezN
Send Litecoin tips to : LVtpaq6JgJAZwvnVq3ftVeHafWkcpmuR1e

PSneep

#2
May 06, 2011, 03:57 pm Last Edit: May 06, 2011, 04:06 pm by PSneep Reason: 1
Wow, thanks John! I get the logic in the Do - While loop, however there's an error saying there's an invalid conversion from 'char*' (coming from the 'letters' and 'numbers' arrays I guess) to a 'char' in the following line:
Code: [Select]
currentResult = letters[random(0,randomLetters)];

Is that something I should fix in the arrays part or in the loop part?

Edit: added the '*' to both the char currentResult and char oldResult. It works like a charm now! Thanks again : )

johnwasser

Oops..  I wasn't expecting character strings because you were dealing with individual characters.  You did the right thing by changing the two variables to character pointers.
Send Bitcoin tips to: 1L3CTDoTgrXNA5WyF77uWqt4gUdye9mezN
Send Litecoin tips to : LVtpaq6JgJAZwvnVq3ftVeHafWkcpmuR1e

robtillaart

Quote
That works fine and all, but I need a little more functionality. For example, it should not be possible for two exactly the same letters to show up right after another (aa, bb, etc.).


If you filter such combination out, it is strictly speaking not really random (with dices you throw the same value also 1 in 6) . Can you tell the rationale behind this requirement?

Another way to solve the double letters is just take the next char:

currentResult = letters[random(0,randomLetters)];
if (currentResult == oldResult) currentresult = ( currentresult +1 ) % randomLetters;

The advantage over the while loop is that the if construct is 100% deterministic as it cannot get stuck in the while loop. In theory the while loop can iterate multiple times as a random generator might generate the same number multiple times. This chance however is very small :  order (1/randomLetters) ^ n  where n is the number of iterations.


Rob Tillaart

Nederlandse sectie - http://arduino.cc/forum/index.php/board,77.0.html -
(Please do not PM for private consultancy)

Nick Gammon


For example, it should not be possible for two exactly the same letters to show up right after another (aa, bb, etc.).


Yes, OK, but I warn you that if you try to "improve the randomizer" you are making it less random (as robtillaart said).

As an extreme example, say you did coin tosses but you said "it should not be possible for two exactly the same letters to show up right after another", so you never get head/head or tail/tail. OK so what must you always get? head/tail/head/tail/head/tail

So it isn't at all random. But you reply "I didn't mean that", but you say "I don't mind head/head as long as I don't get head/head/head". Well that still means that if you force a "tail" after two heads, it is completely predictable. As soon as you see two heads you know the next result must be a tail.

Mind you, I have heard of some MMO games filtering their randomizers to make things "look random". For example, in a dungeon, if one person wins all the loot rolls, it might *be* random, but it doesn't "look random". So sometimes they impose corrections on the random generator results so they don't get heaps of complaints the next day.

Please post technical questions on the forum, not by personal message. Thanks!

More info:
http://www.gammon.com.au/electronics

fuh

You could use analogRead() to seed the randomizer; this will use "noise" to create the seed.
http://creativecommons.org/licenses/by-nc-sa/3.0/

AWOL

Quote
You could use analogRead() to seed the randomizer; this will use "noise" to create the seed.

That assumes you're not using the analogue inputs for something else.
And that you've got a nice long antenna on the unused input you're using for randomisation.
"Pete, it's a fool looks for logic in the chambers of the human heart." Ulysses Everett McGill.
Do not send technical questions via personal messaging - they will be ignored.

Drmn4ea

I don't see any reason why "avoid repeats" and "good randomizer" have to be mutually exclusive - the shuffle functions on e.g. CD/MP3 players are random enough for all intents and purposes, but won't play the same song twice in a row. Have a look at the Fisher-Yates shuffle algorithm, "modern version": this basically puts all your items to be randomized into an array and treats it like a deck of cards. Starting at the end of the array and working backwards, swap that element with a randomly-selected element between (including) position 0 and the current position. (This means the item could even be swapped with itself, but the computer doesn't mind.)

This method is mathematically unbiased (even though items near the beginning of the list might appear to get "shuffled more", i.e. swap positions more times), and assuming the 'deck' does not include duplicates of the same item, guarantees no repeats until the deck runs out and has to be reshuffled. You could still get a repeat if the first item in the new deck happened to be the last item in the old deck, but it would be pretty uncommon (and you could still throw it away if it really mattered :-)

Using the Arduino's timer to seed the randomizer upon a button-press seems like it would be good enough to assure the results were unique. Unless the user is a robot and presses the button in an exact (msec-timed) sequence every time!

Coding Badly

Quote
And that you've got a nice long antenna on the unused input you're using for randomisation.


Even with a several centimeter antenna, analogRead does not appear to be a particularly good choice.  In my testing, the values fall into a small subset of the available buckets and follow easily recognizable patterns.  The antenna seems to pick up digital noise from the processor more than anything else.  If the antenna is shielded close to the processor and outside of the processor's influence I suppose the values would be higher quality.

But why bother?  random produces good results.  For seeding, just save the previous value in EEPROM.  That's actually how random (and it's ilk) are meant to be used.

Coding Badly

Quote
Using the Arduino's timer to seed the randomizer upon a button-press seems like it would be good enough to assure the results were unique.


There's a good example in the "old forum" based on that idea.  The person was trying to build a "dice roller".  One value (I think it was "4') had about 2:1 odds of occurring with one value never occurring.  The code looked like it would work but failed horribly.

Nick Gammon

There are subtle problems with fiddling with random numbers, even using rand () can lead to problems (apart from the obvious ones about whether it is implemented properly). For example, if you want to get a number in a range (eg. dice) you might do this:

Code: [Select]
int getrandom (const int x)
{
return (rand () % x);
}   // end of getrandom


But by taking the modulus you are throwing away all the bits from rand() except the lower-order ones. So for example, if you did getrandom(2) and rand() (for some reason) always returned even numbers (but was otherwise random in the other bits) then you will always only get one result.

A better way is:

Code: [Select]
int getrandom (const int x)
{
  return ((double) rand () / (double) (RAND_MAX + 1)) * (double) x;
}   // end of getrandom


This first turns the output of rand() into a number in the range [0,1). That is, including 0 but excluding 1.

Now we multiply this by the argument to get a number in the range 0 to the argument, but excluding the argument.

That uses all the bits in the random number we chose (whether it is from rand(), millis() or whatever).
Please post technical questions on the forum, not by personal message. Thanks!

More info:
http://www.gammon.com.au/electronics

PSneep


Quote
That works fine and all, but I need a little more functionality. For example, it should not be possible for two exactly the same letters to show up right after another (aa, bb, etc.).


If you filter such combination out, it is strictly speaking not really random (with dices you throw the same value also 1 in 6) . Can you tell the rationale behind this requirement?


The reason behind this is that the randomizer will be used for generating hotkeys linked to let's say 36 video's. A push of a button should skip to the next video at random. However, if a user pushes the button and by chance the randomizer generates the same hotkey as the previous one, there will be no noticable change in video and thus leaving the user confused (thinking his input had no result). So direct feedback is a must, and by ruling out the possibility of getting the same result twice in a row we rule out the possible confusion. 

gardner

More out of curiosity than anything, has anyone built a cheap "high" quality RNG for Arduino, for some value of "high"?

I was thinking of connecting a reverse biased Zener to an analogue in and looking for zener noise.  I'm not sure there's enough gain in the ADC comparators.  Another idea I had was to make a 555 oscillator out of low grade parts and feed the trigger voltage into the ADC.

Seeding a PRNG would then collect some entropy from the ADC, and maybe other sources.  Maybe make few hundred A-D readings over a 1 second period and feed all that into a CRC-32 would not be too complicated.

The PRNG could be an Xorshift type generator.  Something that doesn't need to keep too much state, but has good statistical performance.  Better would be something that is suited to feeding extra entropy into over time.

Is this already "done" somewhere?

robtillaart


Begin of this year there was a discussion on the old forum about randomness, using the internal temperature sensor of the UNO as a random seed generator and about fetching a random number/seed from the internet. might be worth reading - http://www.arduino.cc/cgi-bin/yabb2/YaBB.pl?num=1294239019
Rob Tillaart

Nederlandse sectie - http://arduino.cc/forum/index.php/board,77.0.html -
(Please do not PM for private consultancy)

Go Up