Random Nummer zwischen 1 und 100 generieren

[TNA]

volkard schrieb:

Weitverbreiteter Fehler, daß man echte Gleichverteilung überall brauchen würde.

Man kann sich sicherlich darüber streiten, wie störend das im Einzelfall ist, aber 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.

[volkard]

Arcoth schrieb:

volkard schrieb:

Warum ist sie besser?

Vielleicht ein besserer PRNG. default_random_engine ist ja nicht standardmäßig der lineare Kongruenzgenerator.

In der nächsten GCC-Version ist aber default_random_engine der der verhasste lineare Kongruenzgenerator und rand einer, an dem Du mehr Freude hast.

[TNA]

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.

[Columbo]

Das ist bei der Spieleprogrammierung recht hilfreich.

Bei Spieleprogrammierung reicht fast immer rand() . Da braucht keiner einen Mersenne-Twister.

Der MT ist nach meinen Messungen einfach nur lahm. Schon immer.

[TNA]

Arcoth schrieb:

Bei Spieleprogrammierung reicht fast immer rand() . Da braucht keiner einen Mersenne-Twister.

Es ging bei der Aussage um das Wiederherstellen des States. Viele Spieleprogrammierer programmieren tatsächlich noch C++ wie vor 20 Jahren üblich, aber nicht, weil das besser wäre.

[TNA]

Siehe z.B. auch http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2013/n3547.pdf

[volkard]

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.

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?

[knivil]

Wenn dein Hauptkriterium Geschwindigkeit ist, dann wird wohl alles langsamere eben immer schlecht dastehen. Der grosse Nachteil mit rand/srand fuer mit ist, dass der Zufallsgenerator global ist. Das vertraegt sich schlecht mit mehreren Threads.

[Fytch]

dsdsds schrieb:

std::srand hat keinen tatsächlichen Member "srand"

richtig, funktionen können nie member haben!

volkard schrieb:

TNA schrieb:

Die Zahlen sind wirklich gleichverteilt, was bei der Modolovariante nicht der Fall ist (weitverbreiteter fehler).

Weitverbreiteter Fehler, daß man echte Gleichverteilung überall brauchen würde.

TNA schrieb:

Zudem ist der Seed nicht global, man kann die Random Engine austauschen und vieles mehr.

Zu >99% meines Zufallszahlenbedarfs auch irrelevant, genauso wie die genaue Gleichverteilung, sorry.

Sagem wir, die C++11-Variante ist "moderner", klingt auch toll positiv. So ein hartes "besser" würde ich da meiden.

das hat mir gerade die worte aus dem mund genommen.

[TNA]

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.

[volkard]

TNA schrieb:

Das tolle an std::random ist ja, dass jeder die Engine wählen kann, die er möchte.

Nein. Meine Lieblingsengine ist nicht im Standard.
Muss ich mir also selber bauen.

Aber oh, Wunder! Man kann sich auch eine eigene globale rand-Funktion bauen und sie benutzen.

Für Dich ist der Vorteil, daß der MT eingebaut ist, mehr aber auch nicht, gell?

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?

[TNA]

volkard schrieb:

TNA schrieb:

Das tolle an std::random ist ja, dass jeder die Engine wählen kann, die er möchte.

Nein. Meine Lieblingsengine ist nicht im Standard.
Muss ich mir also selber bauen.

Aber zumindest kann man damit dann die ganze andere Fuktionalität nutzen, die Random bereitstellt.

volkard schrieb:

Für Dich ist der Vorteil, daß der MT eingebaut ist, mehr aber auch nicht, gell?

Nicht nur. Auch das es recht einfach ist, verschiedene Verteilungen zu erzeigen finde ich sehr praktisch.

volkard schrieb:

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?

An so etwas in der Art habe ich gedacht.

[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?