Something is UP.

[Simons Mith]

I'm repeating other people, but

According to the comp.lang.c faq Q. 13.16 and 13.18 the low-order bits from the rand() function on many platforms are distressingly non-random. This might give just the sort of short-term clustering people are complaining about. A way to get a better [Edit: make that 'marginally less bad'] random numbers out of the rand() function is also provided in the FAQ.

Here's a reasonably straightforward discussion of what's wrong:

http://www.azillionmonkeys.com/qed/random.html

rand() % 100 really is /not/ good enough for Wesnoth IMO, and while I personally don't have any gripes with the RNG - yet, I am certainly sympathetic to those who think it should be changed.

From my own experiemce, it never does to place too much trust in supplied RNG functions. Some of them really are pretty poor. As a wise man once said 'the production of random numbers is far too important to be left to chance.'

[zaimoni]

between people's anectodal evidence and the vagueries of stats... I wouldn't have a clue how to do it other than my old fashioned way...

Start by graphing consecutive pairs of RNG values in a plane. [Actually, you can do the calculation for longer sequences, it's just not graphable.] A perfect RNG won't grossly cluster. E.g., for rolling a d6: it should not affect the probability of getting a 6, whether there was a 6 one iteration ago. [Mentioned because the classic linear congruential RNG, IBM RANDU, fails this. I expect the C standard library to pass this much] Of course, the usual caveat of having to adjust alpha when running too many tests applies.

Unless the C library implemention committee did their homework, it'll break down for sequences of length three or four.

[ott]

Unless the C library implemention committee did their homework, it'll break down for sequences of length three or four.

This was precisely what we saw when we last discussed the RNG. Unfortunately, no-one has provided a large enough data sample to allow rigorous analysis.

I have posted previously about damage distribution: http://www.wesnoth.org/forum/viewtopic. ... 3150#53150 , http://www.wesnoth.org/forum/viewtopic. ... 5416#45416 as well as the posts starting with http://www.wesnoth.org/forum/viewtopic. ... 3968#53968 and especially http://www.wesnoth.org/forum/viewtopic. ... 4923#54923 with its attached st script to analyse saved game statistics. Note that st version 1.10 will highlight statistically significant deviations from expected clustering in actual savegames, but it needs 30 observations for any one pattern of swings (eg. 4 hits out of 4 swings or 4 misses out of 4 swings) for that pattern to be highlighted as anomalous. This means it needs a savegame from late in a long campaign like HttT or TRoW, or a replay from one of the last few games from a multiplayer session spanning dozens of games.

Previously, I wrote:

The data therefore supports a hypothesis that there are more 4-miss sequences than there should be, at least for certain values of P.

and

I think this may provide some evidence for the RNG creating too many long sequences of misses.

based on an old 0.8 savegame for HttT. These statements are highly qualified -- the RNG on the Linux system I was using at the time may have exhibited this behaviour, but the results were not clear enough that anyone felt we needed to take remedial action. (At the time, I instead looked more deeply at our method of damage calculation, and found some issues warranting more immediate attention, which led to the RATE damage model introduced in 0.8.10.)

I do support including our own RNG even if rand() is actually good enough for our purposes, since that would make the game more consistent across different platforms.

[Uppi]

I decided to hunt for these "clusters" of luck, and wrote a programm to search these clusters in wesnoth-like combat.

Code: Select all

#include <cstdlib>
#include <ctime>
#include <iostream>

int main()
{
	srand(time(NULL));
	int combats = 1000000;
	int mclusters = 0;
	int hclusters = 0;
	int miss;
	int hit;
	int chance = 30;
	int strikes=4;
	for(int i = 0; i < combats; i++)
	{
		miss = 0;
		hit = 0;
		for(int j = 0; j < strikes; j++)
		{
			if( rand() % 100 < chance) ++miss;
			if( rand() % 100 < chance) ++hit;

		}
		
		if (hit == strikes) ++hclusters;

		if (miss == strikes) ++mclusters;
	}
	

	std::cout<<mclusters<<" "<<strikes<<"-miss clusters in "<<combats<< " combats = "<< float(mclusters) / float(combats)<<std::endl;
	std::cout<<hclusters<<" "<<strikes<<"-hit clusters in "<<combats<< " combats = "<< float(hclusters) / float(combats)<<std::endl;
	
	return 0;
}

It basically simulates one million combatts between a unit of your own with 70% defense and 4 strikes attacking a unit with 30% defense and 4 strikes. It records every incident where either you miss 4 times or get hit 4 times in a row.

I ran this program several times on linux and did not notice any relevant differences between the expected number of these clusters and the real number. This seems to prove that in the long rand() % 100 does not (at least on linux) result in more "clusters" than it should.

[SL]

Code: Select all

if( rand() % 100 < chance) ++miss;
if( rand() % 100 < chance) ++hit; 

That's not correct, is it?

Code: Select all

			add_random_separator();
			const int ran_num = get_random();
			bool hits = (ran_num%100) < stats.chance_to_hit_defender;

			//make sure that if we're serializing a game here,
			//we got the same results as the game did originally

Notice the comment there. It then proceeds to call get_random_results() and check to make sure it matches what we rolled previously.


And remember, get_random() isn't just rand(). It also &0x7FFFFFFF's it, and does a bunch of other stuff which doesn't look like it impacts the return value at all (besides buffering several randomly generated numbers instead of generating each on the fly when one is needed).

[xtifr]

I do support including our own RNG even if rand() is actually good enough for our purposes, since that would make the game more consistent across different platforms.

Well, along those lines, the libg++ libraries (class libraries which used to be bundled with g++ before the STL made them mostly obsolete) included some very high-quality pseudo-RNGs. I imagine some of the code is still floating out there somewhere, and, of course, it's pretty much guaranteed to be GPL-compatible, since it's from the FSF.

[SL]

I've modified my test program to only seed once, and to do more rolls, so that I can more easily test for runs here.

Here're the results, seeded from time(NULL):
For rand:

CHANCE=30
300546 hits out of 1000000 total swings (30.05):
We struck 0 times in a row 489272 times.
We struck 1 times in a row 147057 times.
We struck 2 times in a row 44114 times.
We struck 3 times in a row 13260 times.
We struck 4 times in a row 4014 times.
We struck 5 times in a row 1210 times.
We struck 6 times in a row 379 times.
We struck 7 times in a row 101 times.
We struck 8 times in a row 33 times.
We struck 9 times in a row 10 times.
We struck 10 times in a row 4 times.
We struck 11 times in a row 0 times.
[Everything after that was 0]

And from the MT:

299693 hits out of 1000000 total swings (29.97):
We struck 0 times in a row 490343 times.
We struck 1 times in a row 147015 times.
We struck 2 times in a row 44096 times.
We struck 3 times in a row 13330 times.
We struck 4 times in a row 3877 times.
We struck 5 times in a row 1131 times.
We struck 6 times in a row 346 times.
We struck 7 times in a row 118 times.
We struck 8 times in a row 39 times.
We struck 9 times in a row 8 times.
We struck 10 times in a row 1 times.
We struck 11 times in a row 1 times.
We struck 12 times in a row 1 times.
We struck 13 times in a row 0 times.
We struck 14 times in a row 1 times.
We struck 15 times in a row 0 times.
[Everything after that was 0]

Now we just need to calculate what the average number of runs for each amount of hits should be.

Here's the entire code, and I've slapped a BSD license on it in case anyone wants to modify it. Note that you'll need source for the MT to compile this, but that's also under something resembling a BSD license. (Note: num_misses isn't really used, and we don't currently check for runs of misses)
My code:

Code: Select all

/*
Copyright (c) 2003-2004, Richard Dillingham
All rights reserved.

Redistribution and use in source and binary forms, with or without modification, are permitted provided that the following conditions are met:

    * Redistributions of source code must retain the above copyright notice, this list of conditions and the following disclaimer.
    * Redistributions in binary form must reproduce the above copyright notice, this list of conditions and the following disclaimer in the documentation and/or other materials provided with the distribution.
    * Neither the name of the copyright holder nor the names of contributors may be used to endorse or promote products derived from this software without specific prior written permission.

THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDER(S) AND CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
*/

#include <stdio.h>
#include <math.h>
#include <time.h>
#include <stdlib.h>
#include "mt.hpp"

#define MAX_TEST_VALUE 100
#define NUM_SRAND_TESTS 1
#define NUM_RAND_TESTS 1000000
#define CHANCE 30

int seeds[NUM_SRAND_TESTS];
int results[MAX_TEST_VALUE];
int all_results[MAX_TEST_VALUE];

#define MAX_HITS 100
int num_hits;
int num_misses;
int num_runs[MAX_HITS];
int total_hits;
int total_misses;
int total_swings;

int bitcycling=0;
int notbitcycling=0;
int all_bitcycling=0;
int all_notbitcycling=0;

#define ALG_RAND 0
#define ALG_MT 1

void randTest(int algorithm) {
    int startTime = clock();
    //Clear the variables which hold the total results.
    all_bitcycling=0;
    all_notbitcycling=0;
    for (int a=0; a<MAX_TEST_VALUE; a++) {
        all_results[a]=0;
    }
    
    for (int srand_test=0; srand_test<NUM_SRAND_TESTS; srand_test++) {
		//printf("\n\nTest %i:\n", srand_test);
		//Clear the results array.
		for (int a=0; a<MAX_TEST_VALUE; a++) {
			results[a]=0;
		}
		if (algorithm==ALG_RAND) {
            seeds[srand_test]=time(NULL);	//srand_test; //time(NULL);
			srand(seeds[srand_test]);
        } else if (algorithm==ALG_MT) {
            init_genrand(seeds[srand_test]);
        }
		num_misses=0;
		num_hits=0;
		total_hits=0;
		total_misses=0;
		total_swings=0;
		for (int a=0; a<MAX_HITS; a++) {
			num_runs[a]=0;
		}
		int lastbit=0;
		
		for (int rand_test=0; rand_test<NUM_RAND_TESTS; rand_test++) {
			int res;
			if (algorithm==ALG_RAND) {
                res = rand() & 0x7FFFFFFF;
            } else if (algorithm==ALG_MT) {
                res = genrand_int31();
            }
            
			lastbit=res&0x1;
			//Test for bit cycling.
			if (lastbit!=(res&0x1)) {
				bitcycling++;
			} else {
				notbitcycling++;
			}
			//Test rand() % value
			int num = res % MAX_TEST_VALUE;
			results[num]++;
			all_results[num]++;
			bool hits = (num<CHANCE);
			if (hits) {
				num_hits++;
				total_hits++;
			} else {
				if (num_hits<MAX_HITS) {
					num_runs[num_hits]++;
				}
				num_hits=0;
				num_misses++;
				total_misses++;
			}
			total_swings++;
		}
		
		printf("CHANCE=%i\n", CHANCE);
		printf("%i hits out of %i total swings (%0.2f):\n", total_hits, total_swings, (total_hits*100.0)/((double)total_swings));
		for (int a=0; a<MAX_HITS; a++) {
			printf("We struck %i times in a row %i times.\n", a, num_runs[a]);
		}
		all_bitcycling+=bitcycling;
		all_notbitcycling+=notbitcycling;

		bitcycling=0;
		notbitcycling=0;
	}
	printf("\nTotal results for algorithm %s:\n", (algorithm==ALG_RAND?"rand":"MT"));
	//Show the results array
	double sum = 0;
	double mean = 0;
	for (int a=0; a<MAX_TEST_VALUE; a++) {
		//printf("We got %0.2i this many times: %i\n", a, all_results[a]);
		sum+=all_results[a];
	}
	mean=sum/MAX_TEST_VALUE;
	printf("bitcycling=%i\n", all_bitcycling);
	printf("notbitcycling=%i\n", all_notbitcycling);
	
	printf("Mean: %f\n", mean);
	
	double varsum = 0;
	for (int a=0; a<MAX_TEST_VALUE; a++) {
		double diff = all_results[a] - mean;
		varsum += diff*diff;
	}
	double stddev = sqrt(varsum / ((double)MAX_TEST_VALUE));
	
	printf("Standard deviation: %f\n", stddev);
	int endTime = clock();
    printf("Time taken: %i\n", endTime-startTime);
}

int main() {
	randTest(ALG_RAND);
	randTest(ALG_MT);
	
	printf("\n\nPress any key to continue.\n");
	return 0;	
}

[silene]

Code: Select all

         lastbit=res&0x1;
         //Test for bit cycling.
         if (lastbit!=(res&0x1)) {

Hmm...

[Uppi]

Code: Select all

if( rand() % 100 < chance) ++miss;
if( rand() % 100 < chance) ++hit; 

That's not correct, is it?

it is correct!

Code: Select all

			add_random_separator();
			const int ran_num = get_random();
			bool hits = (ran_num%100) < stats.chance_to_hit_defender;

			//make sure that if we're serializing a game here,
			//we got the same results as the game did originally

Notice the comment there. It then proceeds to call get_random_results() and check to make sure it matches what we rolled previously.

Yes it makes sure it maches what we rolled previously, but only if it is playing a replay (or else it wouldn't make sense)

And remember, get_random() isn't just rand(). It also &0x7FFFFFFF's it, and does a bunch of other stuff which doesn't look like it impacts the return value at all (besides buffering several randomly generated numbers instead of generating each on the fly when one is needed).

If you look closely at the code you will notice, that usually get_random() only returns rand(). The other stuff there is only to get the random numbers saved in a replay, because we don't want new random numbers in a replay.

[SL]

Code: Select all

         lastbit=res&0x1;
         //Test for bit cycling.
         if (lastbit!=(res&0x1)) {

Hmm...

Oops, shuffled that around accidentally. It used to be:

Code: Select all

if (lastbit!=(res&0x1)) {
	bitcycling++;
} else {
	notbitcycling++;
}
lastbit=res&0x1;		

Looks like I accidentally deleted 'lastbit=res&0x1;' and then later noticed and put it back later, but in the wrong place.

Code: Select all

if( rand() % 100 < chance) ++miss;
if( rand() % 100 < chance) ++hit; 

That's not correct, is it?

it is correct!

That rolls once to see if it misses, and then rolls again to see if it hits. And it also uses the same chance for both. You're certain that's correct? I'd have thought you would do this:

Code: Select all

if (rand() % 100 < chance) {
miss++;
} else {
hit++
}

[Uppi]

That rolls once to see if it misses, and then rolls again to see if it hits. And it also uses the same chance for both. You're certain that's correct? I'd have thought you would do this:

Code: Select all

if (rand() % 100 < chance) {
miss++;
} else {
hit++
}

Well the most common complaint was either "The enemy has 30% defense and i miss all strikes" or "I have 70% defense and i get hit every time". This was what i was aiming for. Basically i was looking at a very favorable situation for the attacker and how often this better position doesn't result in victory because of bad luck.
I included the hits of the defender just to make sure that the omission of it doesn't interfere with the results (And it does not make a difference). I could have taken different chances but I was to lazy and it doesn't matter anyway.

[dms]

Start by graphing consecutive pairs of RNG values in a plane. [Actually, you can do the calculation for longer sequences, it's just not graphable.]

So how do you check if longer sequences are OK? Take the Fourier transform and graph that?

[Doc Paterson]

SL, I love your avatar!