Würfeln



  • Kleines "Würfelprogramm" für Games zum Experimentieren:

    #include <iostream>
    #include <iomanip>
    #include <conio.h>
    #include <ctime>
    
        class Wuerfel
        {
              const unsigned int maxzahl_;
            public:
              Wuerfel(unsigned int maxzahl):maxzahl_(maxzahl){ srand( (unsigned)time( NULL ) ); }
              unsigned int wuerfelt(){ return (rand()%maxzahl_ +1); }
        };
    
        int main()
        {
           const unsigned long long Serie     = 3;
           const unsigned long long Versuche  = 10000000;
           const unsigned int limit           = 200;
           const unsigned int moeglichkeiten  = 6;
    
           Wuerfel w(moeglichkeiten);
           unsigned long long H[moeglichkeiten+1];
    
           for(unsigned long long i=1; i<Serie+1; ++i)
           {
               for(unsigned int j=0; j<moeglichkeiten+1; ++j) 
                   H[j] = 0;
    
               for(unsigned long long k=1; k<Versuche+1; ++k)
               {
                   unsigned int wurf = w.wuerfelt();
                   if(Versuche<limit) std::cout << wurf << " ";
                   ++H[wurf];
               }
    
               for(unsigned int c=1; c<moeglichkeiten+1; ++c)
               {
                   std::cout << std::endl << c << ": " << H[c] << " " << std::setprecision(7) 
                             << 100 * static_cast<float>(H[c]) / Versuche << " %";
                   H[0] += H[c];
               }
               std::cout << std::endl << "Wuerfe insgesamt: " << H[0] << std::endl << std::endl;
           }
           getch();
        }
    

    Fehler? Ideen für Verbesserungen?

    /EDIT: short gegen int ausgetauscht (siehe Shades Vorschlag), da hatte mich "Geiz ist geil" gepackt 😉 .
    long long wird ab MSVC++ 7.1 akzeptiert (ansonsten _int64 oder unsigned long einsetzen)



  • du hast mal unsigned int und mal unsigned short - entscheide dich doch fuer eins 😉

    du initialisierst srand() pro Ctor aufruf. das gefaellt mir nicht - wie waere es mit einer statischen methode:

    static Wuerfel::InitSrand()
    {
      static bool alreay_initialized=false;
      if(!already_initialized)
      {
        srand(static_cast<unsigned>(std::time(0)));
        already_initialized=true;
      }
    }
    

    und diese methode dann immer im Ctor aufrufen...

    weiters ist
    (rand()%maxzahl_ +1)
    nicht optimal.

    du solltest lieber groesse raeume nehmen. zB nicht fuer 1-6 ein %6+1 machen, sondern zB von 0-99 ist es 1, von 100-199 ist es 2,... du verstehst?
    dadurch wird der zufall zufaelliger

    btw: in schleifen immer int fuer die laufvariable nehmen, es sei denn du hast einen guten grund warum du etwas anderes brauchst.



  • Shade Of Mine schrieb:

    du initialisierst srand() pro Ctor aufruf. das gefaellt mir nicht - wie waere es mit einer statischen methode:

    static Wuerfel::InitSrand()
    {
      static bool alreay_initialized=false;
      if(!already_initialized)
      {
        srand(static_cast<unsigned>(std::time(0)));
        already_initialized=true;
      }
    }
    

    und diese methode dann immer im Ctor aufrufen...

    äh.
    dann lieber ne klasse Random, die das im Konstruktor macht. hat sich vortiel, daß es normaler (aus oo-sicht) ist. und daß man sich fein entscheiden kann, ob man das Random-Objekt global macht, als singleton hinlegt, lokal macht oder als (evtl static!) member.
    und daß man den generator auch mal fein gegen nen anderen wie den mersenne prime twin generator austauschen kann. (und natürlich auch gegen einen, der ne c:\randseed.bin beim konstruieren liest und beim destruieren schreibt.)



  • Shade Of Mine schrieb:

    du solltest lieber groesse raeume nehmen. zB nicht fuer 1-6 ein %6+1 machen, sondern zB von 0-99 ist es 1, von 100-199 ist es 2,... du verstehst?
    dadurch wird der zufall zufaelliger

    momentchen!
    sagen wir mal, der zufallszahlengenerator bläst nut 2^15 verschiedene werte raus (MSVC).
    dann ist bei %6 ne schieflage.
    5462 mal die 0 und 1.
    5461 mal die 2,3,4 und 5.

    ich vermute, durch keine funktion, die jeder der 2^15 quellzahlen auf eine der 6 zielzahlen abbildet, kannste das histogramm glatter machen.

    allenfalls kann man die unglattheit vertuschen, indem man statt 0 und 1 lieber die 0 und die 3 bevorzugt. aber ist das wirklich ne verbesserung? es wäre iene bei random-walk-sachen wie posx+=rand%9-4;, aber bei histogrammen?

    da kommt ne frage auf. wie kann man, indem man sich nur auf rand stützt, eine funktion bauen, die wirklich die zahlen von 0 bis 5 fair würfelt (in der annahme, daß rand() fair ist)?



  • @Volkard:
    rand() wäre fair?

    Dann sehe ich die Möglichkeit, einfach für die n Zufallszahlen das größte ganzzahlige Vielfache als Obergrenze zu akzeptieren, die Zahlen zwischen diesem Wert und rand_max alle zu verwerfen, und darunter einfach durch n zu teilen.

    Ansonsten bekommst Du wohl zwangsläufig Ungerechtigkeiten.

    @Shade: ob Du aber das mit Modulo oder mit einem Bereich machst bleibt sich letztlich ja wohl gleich... einmal ist es 0,1,2,3,4,5,0,1,2,..., einmal ist 0,0,0,0,0,0,1,1,1,1,1,...



  • 10.000.000 Würfe mit einem 6er-Würfel ergeben mit obigem Programm eine Verteilung von 16,64 bis 16,69 %. Das zeigt doch, dass rand() "gerecht" funktioniert. Aber nicht perfekt, das ist richtig. Ich weiß nicht, mit wie vielen Würfen das wirklich mit mechanischen Würfeln ausprobiert wurde, weiß das jemand?

    @Shade:
    "du solltest lieber groesse raeume nehmen. zB nicht fuer 1-6 ein %6+1 machen, sondern zB von 0-99 ist es 1, von 100-199 ist es 2,... du verstehst?
    dadurch wird der zufall zufaelliger."

    Das habe ich noch nicht verstanden. Ich sehe das so wie Marc++us (s.o.). Der Modulo sollte doch ausreichen. Kannst Du das erläutern?



  • Erhard Henkes schrieb:

    10.000.000 Würfe mit einem 6er-Würfel ergeben mit obigem Programm eine Verteilung von 16,64 bis 16,69 %. Das zeigt doch, dass rand() "gerecht" funktioniert.

    siehe oben
    5462 mal die 0 und 1.
    5461 mal die 2,3,4 und 5.
    hier steckt ein systematischer fehler drin.
    stell dir rand() vor, was 2^15 werte gibt und die folge aus rand()%10000. nu isses aber so schief, daß man's auch wegschmeißen kann. und du hast ja nicht festgelegt, daß dein prog nur mit winzigen zahlebn arbeiten darf.



  • So ein Dreck, jetzt habe ich meinen Beitrag aus Versehen gelöscht ohne ihn zu senden... ****

    Also, noch mal. Annahme: rand() sei fair.

    Das Problem mit der Schieflage (von Volkard angesprochen) läßt sich doch trivial beheben.

    Sei 32767 die größte Zahl, die der Generator liefert. Dann kann ich die Sache so fair machen:

    (Hinweis: 32766 ist die größte Zahl, die ein ganzzahliges Vielfaches von 6 ist und kleiner als 32767)

    int z;
    int r;
    
    do
    {
       r = rand();
    } while (r >= 32766);
    
    z = r%6 + 1;
    

    z enthält nun die faire Zufallszahl mit Gleichverteilung aller 6 Ziffern.

    Den Zahlenstrom habe ich so aufgeteilt:
    1,2,3,4,5,6,1,2,3,4,5,6,...,1,2,3,4,5,6,ungültig,ungültig

    Damit ist das Problem doch hinreichend gelöst.

    Apropos, theoretisch besteht die Chance, daß die Schleife nicht terminiert. Ist aber extrem unwahrscheinlich. 😉



  • @Marc++us:
    Bildet diese Klasse Deine Idee richtig ab?

    class Wuerfel 
        { 
              const unsigned int maxzahl_;
              const unsigned int maxrandom_;
            public: 
              Wuerfel(unsigned int maxzahl):maxzahl_(maxzahl),maxrandom_(RAND_MAX-(RAND_MAX%maxzahl)){ srand( (unsigned)time( NULL ) ); } 
              unsigned int wuerfelt()
              {  
                unsigned int r;
                do{ r = rand(); } 
                    while ( r >= maxrandom_ );
                return ( r % maxzahl_ +1 ); 
              } 
        };
    


  • Marc++us schrieb:

    ...
    Ansonsten bekommst Du wohl zwangsläufig Ungerechtigkeiten.

    korrekt. ich kenne keinen weg, außer dem von dir genannten, um die ungerechtigkeiten wegzumachen.



  • Bei der Würfel-Funktion findet man manchmal so etwas:

    dRand = rand();
    dRand /= RAND_MAX;
    dRand = dRand * 6 + 1;
    nWuerfel = (int) dRand;
    

    Da gibt es inhaltlich doch keinen Unterschied zur Modulo-Variante?



  • Was ist im Konstruktor richtig? Manche sagen, man soll rand() direkt hinter srand() aufrufen:

    Wuerfel(unsigned int maxzahl):maxzahl_(maxzahl),maxrandom_(RAND_MAX-(RAND_MAX%maxzahl)){ srand( (unsigned)time( NULL ) ); rand(); }
    

    Macht das Sinn?



  • @eh:

    Zur Klasse: grundsätzlich tut sie das, was ich meinte, aber NUR solange Du nur einen einzigen Würfel hast. Bei dieser Konstellation bereits

    Wuerfel w1, w2;
    

    kannst Du Dein blaues Wunder erleben. Das srand hat im Ctor nichts verloren.

    Entweder kapselst Du das wie von Volkard vorgeschlagen ODER Du machst mindestens sowas:

    class Wuerfel
    {
    private:
       static int m_seed;
    ... // wie zuvor
    };
    
    int Wuerfel::m_seed = srand((unsigned)time(0));
    

    Damit stellst Du immerhin sicher, daß der Seed für alle Würfel nur ein einziges Mal gesetzt wird. Somit wird dann der Fall "n Würfel" abgedeckt. Aber wenn noch jemand den Seed verändert, wird es doch lustig. Applikationstechnisch dürfte eine Klasse für den Zufallsgenerator angemessen sein.



  • Erhard Henkes schrieb:

    Bei der Würfel-Funktion findet man manchmal so etwas:

    dRand = rand();
    dRand /= RAND_MAX;
    dRand = dRand * 6 + 1;
    nWuerfel = (int) dRand;
    

    Da gibt es inhaltlich doch keinen Unterschied zur Modulo-Variante?

    schau das schiefe histogramm bei 10000 werten mal mit dieser und mit der anderen version an. dann sollte klar sein, warum manche leute sowas machen.



  • Erhard Henkes schrieb:

    Was ist im Konstruktor richtig? Manche sagen, man soll rand() direkt hinter srand() aufrufen:

    Wuerfel(unsigned int maxzahl):maxzahl_(maxzahl),maxrandom_(RAND_MAX-(RAND_MAX%maxzahl)){ srand( (unsigned)time( NULL ) ); rand(); }
    

    Macht das Sinn?

    ohne rand() danach haste oft den lustigen effekt, daß dieser code:

    for(;;)
    {
       Wuerfel w(1000);
       cout<<w.wuerfle()<<endl;
       Sleep(1*SEKUNDE);
    }
    

    ne simple jeweils um 1 aufsteigende zahlenfolge ausgibt.



  • also im spieleladen gips unter anderem würfel mit den zahlen von 1 bis 4, bis 6, bis 8, bis 12 und bis 20. man erkennt platonische körper, womit die fairness des würfels offensichtlich ist.
    aber wie sieht ein offensichtlich fairer würfel aus, der die zahlen von 1 bis 7 fair hat?



  • Bei einer Funktion Zufallszahl macht man das mit einem Flag. Man könnte in einer Klasse Wuerfel noch ein static seed_flag aufnehmen und damit srand(...) nur einmal beim Konstruktor des ersten Würfels ausführen lassen (analog zur obigen Zufalls-Funktion). IMHO gehört dies nämlich in den Konstruktor. Wäre dies eine korrekte Lösung?



  • Erhard Henkes schrieb:

    Man könnte in einer Klasse Wuerfel noch ein static srand_flag aufnehmen und damit srand(...) nur einmal beim Konstruktor des ersten Würfels ausführen lassen (analog zur obigen Zufalls-Funktion). IMHO gehört dies nämlich in den Konstruktor. Wäre dies eine korrekte Lösung?

    korrekt? korrekt mag sie sein, aber sie ist scheiße.
    nimm den code von rand() und hau ihn in deine klasse rein. und mach den seed zum attribut.



  • Oha, ich sehe gerade, daß srand den Seed gar nicht zurück gibt... das Ding ist ja void. Dann geht mein Vorschlag sowieso nicht, aber ist ohnehin nur 2. Wahl.



  • Also ich poste noch mal die Klasse mit dem seed_flag, damit das kein Singleton werden muss:

    #include <iomanip> 
    #include <conio.h> 
    #include <cstdlib>
    #include <ctime> 
    
    class Wuerfel 
    { 
      const unsigned int maxzahl_;
      const unsigned int maxrandom_;
      static bool seed_flag;
    public: 
      Wuerfel(unsigned int maxzahl):maxzahl_(maxzahl),maxrandom_(RAND_MAX-(RAND_MAX%maxzahl))
      { 
        if(!seed_flag)
        { 
          srand( (unsigned)time( NULL ) ); seed_flag = true; 
          /*std::cout << "seed-flag gesetzt." << std::endl;*/
        } 
      } 
    
      unsigned int wuerfelt()
      {  
        unsigned int r;
        do{ r = rand(); } 
          while ( r >= maxrandom_ );
        return ( r % maxzahl_ +1 ); 
      } 
    }; 
    
    bool Wuerfel::seed_flag = false;
    
    int main() 
    { 
      const unsigned long long Serie     = 3; 
      const unsigned long long Versuche  = 30000000; 
      const unsigned int limit           = 200; 
      const unsigned int moeglichkeiten  = 6; 
    
      Wuerfel w(moeglichkeiten); 
      unsigned long long H[moeglichkeiten+1]; 
    
      for(unsigned long long i=1; i<Serie+1; ++i) 
      { 
        for(unsigned int j=0; j<moeglichkeiten+1; ++j) H[j] = 0; 
    
        for(unsigned long long k=1; k<Versuche+1; ++k) 
        { 
          unsigned int wurf = w.wuerfelt(); 
          if(Versuche<limit) std::cout << wurf << " "; 
          ++H[wurf]; 
        } 
    
        for(unsigned int c=1; c<moeglichkeiten+1; ++c) 
        { 
          std::cout << std::endl << c << ": " << H[c] << " " << std::setprecision(7)  
                    << 100 * static_cast<float>(H[c]) / Versuche << " %"; 
          H[0] += H[c]; 
        } 
        std::cout << std::endl << "Wuerfe insgesamt: " << H[0] << std::endl << std::endl; 
      } 
      getch(); 
    }
    

    Jetzt könnt ihr das Ding wieder konkret zerreißen. 🙂
    Die Differenzen bei der Gleichverteilung liegen jetzt im Promillebereich. Damit sollte man leben können. Wie hoch sind die Abweichungen eigentlich bei mechanischen Würfeln, auch ca. 0,1% ?

    Geschichte des Würfels: http://www.uni-magdeburg.de/MWJ/MWJ2002/ineichen.pdf


Anmelden zum Antworten