Random Nummer zwischen 1 und 100 generieren

volkard

TNA schrieb:

volkard schrieb:
TNA schrieb:
Menschen die so etwas hinschreiben wie
int a = std::rand() % 100 + 1;
erwarten davon doch in aller Regel, dass die Zahlen 1 bis 100 mit der gleichen Wahrscheinlichkeit auftreten. Das markt man insbesondere bei der üblichen Implementierung des Würfelwurfs.
Merkt man das??? Lass uns das mal testen.
Lies bitte nochmal was ich geschrieben habe. Man merkt daran, dass eigentlich eine Gleichverteilung erwartet wurde.

volkard schrieb:
Ich habe mal den alten und neuen Weg programmiert und 10-mal laufen lassen. 5-mal alt, 5-mal neu.
Wie http://ideone.com/Z93nQd aber anderer Steuerstring p.
Meine Ausgabe ist
166759 165815 166622 166696 167660 166448
166321 167016 166208 167186 166949 166320
166396 165704 167432 166344 167246 166878
165775 166800 167044 166489 167100 166792
167233 166934 166505 166346 166438 166544
166270 167389 166803 166002 166313 167223
166976 166806 166511 166162 167146 166399
166702 166154 166646 167392 167004 166102
166114 166453 166813 166996 166401 167223
166452 166328 167152 166764 166371 166933
Würdest Du mir bitte sagen, was in p stand, und wie Du es abgelesen hast?
N=5 ist hier viel zu klein, als das man das statistisch mit genügender Wahrscheinlichkeit bestimmen könnte. Ändert allerdings trotzdem nichts daran, das deine alte Methode unfaire Ergebnisse produziert. Jetzt kann man sich lange darüber streiten, wie praxisrelevant das in konkreten Fällen ist. Für mich wäre es allerdings nicht ausreichend, dass ein Programm nur ein bisschen falsch ist.

Du hast so getan, als sei es fürchterlich relevant. Isses offenbar nicht, wenn man viel größere samples braucht, um mit statistischen Methoden etwas herauslesen zu können.

Ich habe halt was gegen solche Gebäude, wo Leute sich gegenseitig Unfug beibringen und keiner zweifelt mal ein wenig dran.

TNA

volkard schrieb:

Ich habe halt was gegen solche Gebäude, wo Leute sich gegenseitig Unfug beibringen und keiner zweifelt mal ein wenig dran.

Ich auch, genau darum habe es ja mal gewagt, die "Standardmethode" zu hinterfragen. Ich sehe halt nicht, warum man eine Methode wählen sollte die weniger korrekt, weniger flexibel, weniger zukunftssicher und nicht mal signifikant einfacher ist nur mit der Begründung, die sei in vielen Fällen ausreichend.

volkard

TNA schrieb:

Was auch sehr praktisch bei den Engines ist ist, das sich der State speichern und wiederherstellen lässt. Das ist bei der Spieleprogrammierung recht hilfreich.

Meinste Du jetzt das Mitabspeichern des Zufallszahlengenerators bei rundenbasierten Einpersonen-Strategiespielen, damit der Spieler genau den gleichen Spielverlauf hat, wenn er zurücklädt und anders vorgeht, damit er nach 250 Versuchen endlich die Festung erobert?[/quote]
An so etwas in der Art habe ich gedacht.[/quote]
Musst aber zugeben, daß das auch ein wenig wie vor 20 Jahren ist.

Ich kenne noch einen hübschen Fall. Bei Programmierspielen.
Mein Bot macht

Zug berechneZug(){
   Zug z=berechneZugPrivat();
   for(int c=0;c<3;++c)
      if(rand()!=17)//mal angenommen, im zyklus kommt nur einmal ...17,17,17... vor
         c=0;
   //ätsch, der Gegner ist ab jetzt berechenbar, weil ich seinen "Zufall" sabotiert habe. 
   return z;
}

Jockelx

volkard schrieb:

Musst aber zugeben, daß das auch ein wenig wie vor 20 Jahren ist.

Wie alt ist eigentlich Civ5
(Lässt dem Spieler die Wahl, ob neuer Seed beim Laden generiert werden soll).

TNA

Jockelx schrieb:

volkard schrieb:

Musst aber zugeben, daß das auch ein wenig wie vor 20 Jahren ist.

Wie alt ist eigentlich Civ5

Ich oute mich hier gerne als Liebhaber von rundenbasierten Strategiespielen wie CIV, Battle for Wesnoth und UFO: Alien Invasion. Natürlich ist das kein Mainstream.

Werner Salomon

TNA schrieb:

Die bessere Methode nach C++11 wäre

#include <random>

std::default_random_engine e;
std::uniform_int_distribution<int> d(1, 100);
int a =  d(e);

.. hatte ich auch gedacht. Sollte auch so sein! Ist aber nicht so, wenn man die C++-Library aus dem Visual Studio 10 verwendet.

Es wurde hier schon viel über den Generator, aber noch gar nicht über die Distribution diskutiert. Man sollt doch annehmen, dass die Distribution gleich verteilte Zufallszahlen liefert, wenn der Generator bereits gleich verteilte Werte liefert. Bei boost.random ist das auch so - dazu habe ich mal einen kleine Test mit einem (schwachen) Generator geschrieben, der aber garantiert gleich verteilte Zahlen liefert.

Ergebnis einer Würfelsimulation mit E={1,2,3,4,5,6} ist

nach 42 Wuerfen:
Wurfzahl 1: 7-mal
Wurfzahl 2: 7-mal
Wurfzahl 3: 7-mal
Wurfzahl 4: 7-mal
Wurfzahl 5: 7-mal
Wurfzahl 6: 7-mal

also alles gut. Genau wie erwartet.

macht man exakt das selbe mit der Distribution mit dem std:: davor - implementiert im Auftrag der komischen Firma aus Redmond - so ist der Output:

nach 42 Wuerfen:
Wurfzahl 1: 12-mal
Wurfzahl 2: 6-mal
Wurfzahl 3: 6-mal
Wurfzahl 4: 6-mal
Wurfzahl 5: 6-mal
Wurfzahl 6: 6-mal

und das ist auch in einem Spiel nicht mehr egal

anbei das Testprogramm

#include <algorithm> // random_shuffle
#include <cstdlib> // rand
#include <iostream>
#include <map>
#include <numeric> // partial_sum
#include <random>
#include <vector>

#include <boost/random.hpp>

template< unsigned N >
struct Gleichverteilt // ein 'Zufalls'-Generator, garantiert gleich verteilt
{
    typedef std::size_t result_type;
    static result_type min() { return 1; }
    static result_type max() { return N; }

    Gleichverteilt()
        : idx_()
        , data_(N,1)
    {
        std::partial_sum( begin(data_), end(data_), begin(data_) ); // erzeugt 1,2,3,..,N
        std::random_shuffle( begin(data_), end(data_) );
    }

    result_type operator()()
    {
        if( ++idx_ == data_.size() )
        {
            std::swap( data_[std::rand()%data_.size()], data_[std::rand()%data_.size()] );
            idx_ = 0;
        }
        return data_[idx_];
    }

private:
    std::size_t idx_;
    std::vector< int > data_;
};

int main()
{
    using namespace std;

    map< int, int > histo;
    Gleichverteilt< 7 > gen;

    boost::random::uniform_int_distribution< int > wuerfel(1, 6);
    // std::uniform_int_distribution< int > wuerfel(1, 6);
    const int N = 42;
    for( int i=0; i<N; ++i )
        ++histo[ wuerfel(gen) ];

    cout << "nach " << N << " Wuerfen:" << endl;
    for( auto i = begin(histo); i != end(histo); ++i )
        cout << "Wurfzahl " << i->first << ": " << i->second << "-mal" << endl;
    return 0;
}

Gruß
Werner

otze

volkard schrieb:

Nein. Meine Lieblingsengine ist nicht im Standard.

Meiner auch nicht. Ändert aber leider nichts dran, dass ein MT immer noch richtig fix ist:
http://www.thesalmons.org/john/random123/papers/random123sc11.pdf

Tabelle Seite 12. Hardware AES hab ich nicht, und Threefry möchte ich gerad nicht effizient implementieren müssen. und XORWOW hab ich vorher noch nie gehört.

//edit wenn jemand einen RNG nennen kann, der mindestens so schnell wie MT ist, aber nicht bei hochdimensionalen Normalvertielungen versagt: her damit.

volkard

otze schrieb:

//edit wenn jemand einen RNG nennen kann, der mindestens so schnell wie MT ist, aber nicht bei hochdimensionalen Normalvertielungen versagt: her damit.

Wie teste ich das?

otze

volkard schrieb:

otze schrieb:

//edit wenn jemand einen RNG nennen kann, der mindestens so schnell wie MT ist, aber nicht bei hochdimensionalen Normalvertielungen versagt: her damit.

Wie teste ich das?

typischerweise spectral test auf deinem uniformen Rng auf [0,1]^d wobei d irgendwie beliebig groß ist. >500 wäre vorteilhaft. Spectral tests gibt es nur für die LCG Klasse.

Am besten einmal hier drauf jagen:

http://en.wikipedia.org/wiki/TestU01

SeppJ

otze schrieb:

//edit wenn jemand einen RNG nennen kann, der mindestens so schnell wie MT ist, aber nicht bei hochdimensionalen Normalvertielungen versagt: her damit.

Nach eigener (aber zugegeben: uralter) Aussage der GSL-Doku: Tausworthe Generator.
http://www.gnu.org/software/gsl/manual/html_node/Random-Number-Generator-Performance.html
Der verträgt es zwar nicht gut, wenn man ihn manuell mit 0 initialisiert, aber das lässt man eben einfach bleiben. Dann erfüllt er deine Anforderungen.

otze

Da steht aber nichts über die Qualität. MT gibt mir gute zufallszahlen auf >500 dimensionen.

//edit und hier steht halt noch was anderes:
http://www.cs.indiana.edu/~kapadia/project2/node9.html

Marthog

TNA schrieb:

Das tolle an std::random ist ja, dass jeder die Engine wählen kann, die er möchte. Was auch sehr praktisch bei den Engines ist ist, das sich der State speichern und wiederherstellen lässt. Das ist bei der Spieleprogrammierung recht hilfreich.

Wobei man bedenken muss, dass die Algorithmen für die distributions vom Standard nicht vorgeschrieben sind. Es kann also sein, dass mit einem einfachen neu compilen, z.B. für eine andere Plattform, für einen Patch, etc die Spielstände nicht mehr kompatibel sind.

SeppJ

otze schrieb:

Da steht aber nichts über die Qualität.

Ich war jetzt davon ausgegangen, dass du selber in der Lage bist, diese zu prüfen, wenn du mir nicht glaubst.

Columbo

Ich habe zwar keine Ahnung, was es heisst, jedoch sprach Michael E. mal von Hyperebenen bei PRNGs. Nun, wieviele hat den die MT19937?

Fytch

Arcoth schrieb:

Ich habe zwar keine Ahnung, was es heisst, jedoch sprach Michael E. mal von Hyperebenen bei PRNGs. Nun, wieviele hat den die MT19937?

620 soviel mir ist.

otze

Arcoth schrieb:

Ich habe zwar keine Ahnung, was es heisst, jedoch sprach Michael E. mal von Hyperebenen bei PRNGs. Nun, wieviele hat den die MT19937?

Genug, dass sie im einheitswürfel [0,1]^623 nicht statisch signifikant auffallen.
Cas Problem ist nur, dass unsere evolutionären algorithmen auch gerne mal 1000 dimensionale Zufallsverteilungen am laufen haben.

Und hyperebenen bei einem schlechten RNG shen halt so aus:

http://en.wikipedia.org/wiki/File:Randu.png

Columbo

Sind Hyperebenen ein Faktor dafür, wie gleichverteilt die Werte eines RNGs sind?

Columbo

Das ist also ein dreidimensionaler Plot der generierten Zufallszahlen mit RANDU, ja?

One of us recalls producing a "random" plot with only 11 planes, and being told by his computer center's programming consultant that he had misused the random number generator: "We guarantee that each number is random individually, but we don't guarantee that more than one of them is random." Figure that out.

:'D

volkard

otze schrieb:

Am besten einmal hier drauf jagen:
http://en.wikipedia.org/wiki/TestU01

Lauter Linkerfehler. Das gebe ich mir nicht weiter.

edit: Doch, geht, wenn ich sein Makefile und seine libs einfach ignoriere und sich dafür seine *.c alle ins Projekt haut. Ich lass dann man std::rand, std::default_random_engine, std::mt19937, XORSHIFT und MWC antreten.

SeppJ

Arcoth schrieb:

Sind Hyperebenen ein Faktor dafür, wie gleichverteilt die Werte eines RNGs sind?

Nein, es geht um eine bestimmte Art von Korrelation zwischen aufeinander folgenden Werten (ganz simpel ausgedrückt so etwas wie "wenn der vorherige wert klein war, dann wird der nächste Wert eher groß"). Teilweise eben auch von Werten, die hunderte von Ziehungen auseinander liegen. Bei guten Zufallszahlengeneratoren darf es so etwas natürlich nicht geben (denn echter Zufall hätte dies nicht) und es gibt auch durchaus konkrete, negative Effekte, die auftreten können, wenn man Zufallszahlen mit solchen Korrelationen in bestimmten Anwendungen einsetzt.