Random Nummer zwischen 1 und 100 generieren

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.

Columbo

Also ein Indikator für Muster in den Zahlenfolgen?

denn echter Zufall hätte dies nicht

Woher weißt du das? Echter Zufall ist doch zufällig?
Edit: Wer weiß schon, wie sich echter Zufall verhält? Den gibt es doch laut der klassischen Mechanik in diesem Universum gar nicht, oder?

es gibt auch durchaus konkrete, negative Effekte, die auftreten können, wenn man Zufallszahlen mit solchen Korrelationen in bestimmten Anwendungen einsetzt.

Also das ist ein sehr überzeugendes Argument. Habe mir noch gar nicht Gedanken darüber gemacht, dass natürlich je nach Anwendungsfall eine bestimmte Korrelation der Werte von Bedeutung sein kann (ich nahm an, nur das Große und Ganze zählt, also der Durchschnitt).

SeppJ

Arcoth schrieb:

Also ein Indikator für Muster in den Zahlenfolgen?

Die hier angegebene Anzahl der Hyperebenen ist so etwas wie die Anzahl aufeinander folgender Werte, in denen man keine solchen Muster erkennen kann.

denn echter Zufall hätte dies nicht

Woher weißt du das? Echter Zufall ist doch zufällig?

Das ist per Definition so. Wenn die Zahlen Muster zeigen, sind sie nicht zufällig.

Bashar

Das ist nicht ganz richtig. Muster müssen auch zufällig entstehen können. Beispielsweise ist es ja auch möglich, 100mal hintereinander die 6 zu würfeln. Man kann alledings die Wahrscheinlichkeiten dafür, dass das zufällig passiert und dass das aufgrund gezinkter Würfel passiert, miteinander vergleichen und je nachdem einer der beiden Erklärungen den Vorzug geben...

SeppJ

Bashar schrieb:

Das ist nicht ganz richtig.

Da hast du mich auch anders verstanden, als es gemeint ist.