RPG Combat

RPG Combat

spellcaster

Member #1,493

September 2001

I know
That's something I realized after posting.
But anyway, in the above example I've around 0.1% variation for the most often / least often rolled die.

It's not a real issue here.
If you need higher precision, just grab one of the many existing generators from the net, or use a floating point generator. But then your distribution might be even worse...

For your normal RPG issues, it's not a big problem. Hope you agree here

--
There are no stupid questions, but there are a lot of inquisitive idiots.

Korval

Member #1,538

September 2001

Quote:

For your normal RPG issues, it's not a big problem.

So, let me get this right.

Rather than taking a minimal amount of effort to correct the random function, you'd rather just do it the wrong way and live with the slightly skewed probability? It's not like you even have to think of a solution; it's right here in this thread! You're arguing against chaning one line of code from doing something that's slightly wrong to doing something that perfectly right.

Um, OK, whatever you want to do. It's your code.

spellcaster

Member #1,493

September 2001

Quote:

Rather than taking a minimal amount of effort to correct the random function, you'd rather just do it the wrong way and live with the slightly skewed probability?

Nope.
I'd simply choose another random number generator.
Please feel free to use your algo in my program above... I'd like to see what distribution you get -and how long it takes to calculate it.

As I said, I had always around 0.1 percent fluctation. And that's good enough for me
I'm not really convinced that you get a better distribution.

[EDIT]
Ok, I tried your function.

Quote:

Doing 4294967294 rolls...
Rand max is:32767
Number most often rolled: 1 (42991616 times == 1.00 per cent)
Number least often rolled: 68 (42860544 times == 1.00 per cent)

Doing 4294967294 rolls the Korval way...
Rand max is:32767
Number most often rolled: 0 (42991616 times == 1.00 per cent)
Number least often rolled: 48 (42860543 times == 1.00 per cent)

In other words... there's no difference.
The funny thing is, that if I use less iterations, the variation in both algos is the same amount.
Which leads to the though that the basic RNG is the thriving factor.
But, just for the record... it took really long to calculate your rand value.

Never assume. Always test

--
There are no stupid questions, but there are a lot of inquisitive idiots.

Korval

Member #1,538

September 2001

Quote:

Ok, I tried your function.

It isn't my function or your function. There is simply the right way and the wrong way.

Quote:

Never assume. Always test

Whatever.

All your "tests" have shown is a lack of understanding of probability, statistics, and statistical variance. You aren't even doing the right tests (and you don't even use "srand" to seed the generator beforehand).

The fact is that, given a roll between 0 and 99, using a RAND_MAX of 0x7FFF, using the %100 method, the chance of rolling a number greater than 67 is precisely 31.93% (32 numbers greater than 67 * 327/32767). However, that's not what it should be. The chance of rolling a number greater than 67 should be precisely 32%. You are off by a 0.07%. This is not something that came up through testing. This number is an absolute, incontrovertible fact.

0.07% may not seem like much, but it is significant. And I can even make it show up in your program, simply by doing the right test.

Add up all counts <= 67. Add up all counts > 67. Divide both by MAX_TEST and * 100.0f to get percent. Given sufficient tests (0xFFFFFFF works and is faster than the full MAX_INT), you will never get the percentages you should. In fact, you will get precisely what the math says you should (ie, skewed probabilities). And if you switch to the right random method, you'll get the right probabilities.

Bob

Free Market Evangelist

September 2000

Let's not resort to flames, shall we?

--
- Bob
[ -- All my signature links are 404 -- ]

dudaskank

Member #561

July 2000

dudaskank: FireBlast!!!

hehehe

Hmm... I will test the codes tomorrow... my idea too...

I don't like much statistics :-P

see you space cowboy

^__^

Toque a balada do amor inabalável, eterna love song de nós dois
Eduardo "Dudaskank"
[ Home Page (ptbr) | Blog (ptbr) | Tetris 1.1 (ptbr) | Resta Um (ptbr) | MJpgAlleg 2.3 ]

spellcaster

Member #1,493

September 2001

Quote:

Hm... a random number generator returns random numbers... so I thought the best way to test it would be by using it to create random numbers?
And I am calling srand() once before I use the modulo way to create the numbers, and once before I call yours.
But calling srand will not change the distribution of the numbers generated... so it won't make a big difference

But I must admit that I'm surprised that your way works as good as the modulo way. In fact, I expected it to create worse numbers (due to the lack of precision if using floats).
It's also not as slow as I suspected...

Hm... and given the fact that using floats (your method) generates the same distribution of numbers clearly shows that it doesn't make a big difference.
Maybe it should make a difference, but the fact its: It doesn't.

I'm not sure you understand this:
if I use your formula I get exactly the same distribution of numbers...

So, could you please tell me, if I get exectly the same results with either method, why is your method better?

If you believe it should be better, then this shows that rand() itself is the main problem, not the if you use a modulo or multiplication...

Quote:

What results should I get?
I tried this using both max int and the value you suggested.
Both with modulo and your method (I won't tell you yet that the result is the same with both ways - yet)

I don't get your point.
Do you want to tell me that your version, even if it's slower in prodcuing the same results, is the better way of doing it?

I don't get it.
(really. If I'm slow here, please take the time to explain. I'd like to understand why it's better to use your method. Right now, I don't see a reason ... it's slower and produces the same result).

I even made a version which created buffers showing the distribution of the numbers... I still don't see a difference.
I even used doubles instead of floats to ensure it's not a rounding problem.

Could you please provide me with an example?

Oh, and just in case you want to have the latest version of the test proggy:

1#include <allegro.h>
2#include <stdio.h>
3#include <stdlib.h>
4#include <limits.h>
5#include <time.h>
6 
7#define INSANE_
8 
9#ifdef INSANE
10#define MAX_TEST ((unsigned int)((~0)-1))
11#else
12#define MAX_TEST 100000
13#endif
14 
15BITMAP *buffer;
16 
17int d_100_float(void) {
return (int) ((float)rand() / (float)RAND_MAX) * 100.0;
19}
20 
21int d_100_modulo(void) {
return rand() % 100;
23}
24 
25void perform_test(int (*func)(void), int y, int col) {

unsigned int a;
unsigned int min;
unsigned int max;
float avg;

int value;
int minIndex, maxIndex;
int count[100];  

for (a=0; a < 100; a++) {
  count[a] = 0;
}

/* Make sure we use the same seed for both tests */
srand(100);
for (a=0; a < MAX_TEST; a++) {
  value = rand()%100;
  count[value]++;
}

min = MAX_TEST;
max = 0;
avg = 0;
maxIndex = minIndex = 0;
line(buffer,0,100,buffer->w,100, makecol(128,128,128));
for (a=0; a < 100; a++) {
    if (count[a] > max) {
      max = count[a];
      maxIndex = a;
    }
    if (count[a] < min) {
      min = count[a];
      minIndex = a;
    }
    
    putpixel(buffer, a, 100+ ((int)((count[a]*100.0) / (float) MAX_TEST)), col);
    
    avg += count[a];
}  
avg = avg / 100.0;
textprintf(buffer, font, 0,  0, makecol(255,255,255),"Number most  often rolled: %5i (%5i times == %2.2f per cent)\n", maxIndex, max, max*100.0 / (float) MAX_TEST);
textprintf(buffer, font, 0, 10, makecol(255,255,255),"Number least often rolled: %5i (%5i times == %2.2f per cent)\n", minIndex, min, min*100.0 / (float) MAX_TEST);

70}
71 
72 
73int main(int ragc, char** argv) {


unsigned int a;
unsigned int min;
unsigned int max;
float avg;

int value;
int minIndex, maxIndex;
int count[100];  

allegro_init();
set_color_depth(16);
set_gfx_mode(GFX_AUTODETECT_WINDOWED, 800, 100, 0, 0);
buffer = create_bitmap(800, 200);

clear(buffer);
perform_test(d_100_modulo, 0 , makecol(255,0,0));  
save_bitmap("result1.bmp", buffer, NULL);

clear(buffer);
perform_test(d_100_float , 20, makecol(0,255,0));
save_bitmap("result2.bmp", buffer, NULL);


return 0;
100}
101END_OF_MAIN();

--
There are no stupid questions, but there are a lot of inquisitive idiots.

Korval

Member #1,538

September 2001

I thought I had made the problem appropriately clear in my original post on the subject. So, let me made an addendum to it.

Original:

Quote:

Well, if you went and actually rolled 2D10 several million times (limit as number of rolls approaches infinity), you should hit each number the same number of times. In short, the probability of rolling a 4 is the same as rolling an 86 or a 34, or any other values from 0 to 99.

Keeping that in mind, let's say RAND_MAX is 150. It probably isn't, but let's say it is for the sake of argument.

What is the probability, using rand() % 100, of rolling a 66? The only way rand() % 100 == 66 is if rand() == 66. So, the probability (assuming a perfect rand()) is 1/150.

What is the probability of rolling 8? Well, if rand() == 8, then rand()%100 == 8. But, if rand() == 108, then rand()%100 == 8 too. Therefore, the probability is 2/150.

Your probabilities are now no longer correct. Given this example, it is twice as likely to come up with a number less than 50 than it is to come up with one greater than 50.

The correct way to do this is to check to see if rand() >= (RAND_MAX - RAND_MAX % 100). If it is, then redo the rand() until it is. BTW, good coding practice says that this should be made its own function.

This way, your probabilities will be correct, to the degree that rand() is probabilistically accurate.

Taking the case where RAND_MAX is 32767, there are 327 ways of coming up with the number 99 from "rand()%100". That is ***99, where *** is any number less than 327, including 000. As such, the probability of comping up with 99 is 327/32767. Note that, because 99 is greater than 67, if *** is 327, rand() will never return 99.

Now, the probability of getting 2 is different from 99. This is because, unlike the 99 case, *** can be 327. rand() could return 32702, and this would come up with 2 as a result. Therefore, the number of ways to get 2 from "rand()%100" is 328, not 327 as above. And, therefore, the probability is 328/32767.

Given a probabilistically correct 0-99 roll, the probability of rolling a number less than or equal to n (0 <= n <= 99) is exactly (n+1)%. That is, the probability of rolling a number less than or equal to 67 should be exactly 68%.

BTW, to make sure you follow along, you get this by taking the probability of rolling any number 0-99 (this should be 1/100, one chance in a hundred) and multiply it times the number of values you're checking. Since there are 68 numbers <= 67, you get 68 *1/100, or 68/100, or 68%.

If you use your method to compute the probability (using the following code), then you will find that the chances of rolling a number <= 67 is actually 68.07%. This is because the probability of rolling a number <= 67 is actually 328/32767. This number is slightly more than 1/100. The probability of rolling <= 67 in your method is 68 * 328/32767 which equals 68.07%.

Likewise, the probability of rolling avobe 67 is altered as well (obviously, since the probability of rolling <= or > 68 must be 100% ). Using the correct probability distribution, you get a 32% chance. Using your method, you get 31.93%.

Here's a version of your tester program that will verify this. Note that it computes the probability of rolling <= 67 and > 67. You will find, even under repeated testing, that your method and mine differ significantly. You can change them easily enough by uncommenting my method out.

1#include <stdio.h>
2#include <stdlib.h>
3#include <limits.h>
4 
5//#define INSANE 
6 
7#ifdef INSANE
8#define MAX_TEST ((unsigned int)((~0)-1))
9#else
10#define MAX_TEST 0xFFFFFFF
11#endif
12 
13int main(int ragc, char** argv) {


int a;
int min;
int max;
float avg;
20 
int iCtBelow = 0;
int iCtAbove = 0;

int value;
int minIndex, maxIndex;
int count[100];  

for (a=0; a < 100; a++) {
  count[a] = 0;
}
printf("Doing %u rolls...\n", MAX_TEST);
fflush(stdout);

for (a=0; a < MAX_TEST; a++)
{
  value = rand()%100;
37//    value = (int)(((float)rand() / (float)RAND_MAX) * 100.0);
  count[value]++;
}

min = MAX_TEST;
max = 0;
avg = 0;
maxIndex = minIndex = 0;
for (a=0; a < 100; a++)
{
  if (count[a] > max)
  {
    max = count[a];
    maxIndex = a;
  }
  if (count[a] < min)
  {
    min = count[a];
    minIndex = a;
  }
57 
  if(a <= 67)
  {
    iCtBelow += count[a];
  }
  else
  {
    iCtAbove += count[a];
  }
66 
  avg += count[a];
}  
avg = avg / 100.0;
printf("Number most  often rolled: %5i (%5i times == %2.2f per cent)\n", maxIndex, max, max*100.0 / (float) MAX_TEST);
printf("Number least often rolled: %5i (%5i times == %2.2f per cent)\n", minIndex, min, min*100.0 / (float) MAX_TEST);
printf("In average every number got rolled: %3.2f times. That's %3.2f percent\n",  avg, avg*100.0 / (float) MAX_TEST);
printf("Percent below or equal to 67: %f\n", (iCtBelow * 100.0f) / (float)MAX_TEST);
printf("Percent above 67: %f\n",  (iCtAbove * 100.0f) / (float)MAX_TEST);

return 0;
77}

As for your concerns about precision: don't be. As long as RAND_MAX is only 32767, floats will work just find. Granted, you might want to use doubles anyway, just to be safe (incase some implementation uses an int RAND_MAX rather than a short one). Granted, if RAND_MAX is that huge, the probability skew won't be very significant.

As for your concerns about speed: don't be. After all, how many times are you planning on calling this function per frame? 20? 30? Compared to rendering, this is nothing.

spellcaster

Member #1,493

September 2001

Ok, I understand that theory.
But I also tested it.

10.000 times I rolled 6600000 random numbers using both your method and mine.

Result:

Quote:

Per cent below 67 (spellcaster) : 67.087
Per cent below 67 (korval) : 67.008

But I don't see in which application this would become a problem?

But I bet you're going to say that this distribution will cause a problem, right?
Ok, so I switched my random number generator. If I use a MT19937 algo, we get the following distribution:

Quote:

Per cent below 67 (spellcaster) : 67.006
Per cent below 67 (korval) : 66.987

Oups
The MT genrates equal distribution between 0 and 2^32 -1.
I even switched from float to double for your algo, but it doesn't change anything.

Hm.. guess we have a draw here.
Seems like your algo works better than mine using the current libc rand(). But as soon as a better random number generator will be used... hm...

So, use your method for number genrators with a low RAND_MAX, and use the modulo as soon as you can use better RNGs...

--
There are no stupid questions, but there are a lot of inquisitive idiots.

dudaskank

Member #561

July 2000

Here is the code:

1#include <stdio.h>
2#include <stdlib.h>
3#include <limits.h>
4#include <time.h>
5 
6#define INSANE 
7 
8#ifdef INSANE
9#define MAX_TEST 0x7FFFFFFF
10#else
11#define MAX_TEST RAND_MAX
12#endif
13 
14#define N    20
15 
16int main(void) {
17  
18  
19  int a;
20  int min;
21  int max;
22  
23  int value;
24  int minIndex, maxIndex;
25  int count[N];  
26 
27  FILE *f;
28  f = fopen("dice2.txt", "w");
29 
30  srand(time(NULL));
31  
32  for (a=0; a < N; a++) {
33    count[a] = 0;
34  }
35  fprintf(f, "Doing %u rolls...\n", MAX_TEST);
36  fflush(f);
37 
38  for (a=0; a < MAX_TEST; a++) {
39    value = (int) (N * (float)rand() / (float)RAND_MAX);
40    count[value]++;
41  }
42  
43  min = MAX_TEST;
44  max = 0;
45  maxIndex = minIndex = 0;
46  for (a=0; a < N; a++) {
47      if (count[a] > max) {
48        max = count[a];
49        maxIndex = a;
50      }
51      if (count[a] < min) {
52        min = count[a];
53        minIndex = a;
54      }
55  }
56  fprintf(f, "Number most  often rolled: %5d (%5d times == %f per cent)\n",
57    maxIndex, max, (float)max*100.0 / (float) MAX_TEST);
58  fprintf(f, "Number least often rolled: %5d (%5d times == %f per cent)\n\n",
59    minIndex, min, (float)min*100.0 / (float) MAX_TEST);
60 
61  for(a = 0; a < N; a++) {
62    fprintf(f, "%5d = %5d\n", a, count[a]);
63  }
64 
65  fclose(f);
66  
67  return 0;
68}

And my results, using D20:

1Doing 2147483647 rolls...
2Number most  often rolled:     0 (107413504 times == 5.001831 per cent)
3Number least often rolled:     9 (107347967 times == 4.998779 per cent)
4 
  0 = 107413504
  1 = 107347968
  2 = 107413504
  3 = 107347968
  4 = 107347968
  5 = 107413504
  6 = 107347968
  7 = 107347968
  8 = 107413504
  9 = 107347967
 10 = 107347968
 11 = 107413504
 12 = 107347968
 13 = 107347968
 14 = 107413504
 15 = 107347968
 16 = 107347968
 17 = 107413504
 18 = 107347968
 19 = 107347968
25 
26-------------------
27 
28Doing 32767 rolls...
29Number most  often rolled:     6 ( 1725 times == 5.264443 per cent)
30Number least often rolled:    11 ( 1586 times == 4.840236 per cent)
31 
  0 =  1608
  1 =  1661
  2 =  1596
  3 =  1636
  4 =  1623
  5 =  1627
  6 =  1725
  7 =  1600
  8 =  1723
  9 =  1625
 10 =  1647
 11 =  1586
 12 =  1641
 13 =  1643
 14 =  1669
 15 =  1610
 16 =  1675
 17 =  1627
 18 =  1637
 19 =  1607

and other results, with spellcaster modulo:

1Doing 32767 rolls...
2Number most  often rolled:     2 ( 1724 times == 5.261391 per cent)
3Number least often rolled:     3 ( 1547 times == 4.721213 per cent)
4 
  0 =  1653
  1 =  1560
  2 =  1724
  3 =  1547
  4 =  1594
  5 =  1582
  6 =  1666
  7 =  1674
  8 =  1636
  9 =  1584
 10 =  1612
 11 =  1650
 12 =  1694
 13 =  1612
 14 =  1659
 15 =  1651
 16 =  1689
 17 =  1706
 18 =  1652
 19 =  1622
25 
26-----------
27 
28Doing 2147483647 rolls...
29Number most  often rolled:     0 (107413504 times == 5.001831 per cent)
30Number least often rolled:     8 (107347968 times == 4.998779 per cent)
31 
  0 = 107413504
  1 = 107413504
  2 = 107413504
  3 = 107413503
  4 = 107413504
  5 = 107413504
  6 = 107413504
  7 = 107413504
  8 = 107347968
  9 = 107347968
 10 = 107347968
 11 = 107347968
 12 = 107347968
 13 = 107347968
 14 = 107347968
 15 = 107347968
 16 = 107347968
 17 = 107347968
 18 = 107347968
 19 = 107347968

See, the results is very dependent of the ammount of rolls, because the result of rand() depends of the last result.

Toque a balada do amor inabalável, eterna love song de nós dois
Eduardo "Dudaskank"
[ Home Page (ptbr) | Blog (ptbr) | Tetris 1.1 (ptbr) | Resta Um (ptbr) | MJpgAlleg 2.3 ]

spellcaster

Member #1,493

September 2001

Dudaskank... if you need a good ditribution, use this random number generator:
[url http://www.math.keio.ac.jp/~matumoto/mt19937int.c]

You could also check for other generators, ther're some generators available which are pretty good and really fast.

--
There are no stupid questions, but there are a lot of inquisitive idiots.