[c++] random getal lijkt niet te lukken

[fromalk]

Hallo,

uit verveling en als uitdaging heb ik beslist een soort zeelsag te maken, nu doe ik dit jaar (5 informaticabeheer) voor het eerst c++ en is mijn kennis nog niet zo uitgebreid toch tracht ik er met deze 'basis' kennis door te komen...
Probleem is dat ik nu graag een array 2 cijfers had toegewezen (die later nog gecontroleerd zullen worden om een geldig coordinaat te zijn), deze cijfers dienen willekeurig te zijn, daarvoor heb ik dit script:

code:

clrscr();

                        cout << "Preparing AI" <<endl;
                        srand(time(NULL));

                        for(c=0;c<2;c++)
                        {
                            ai_b1_cn[c] = rand();
                            cout << ai_b1_cn[c] <<endl;
                        }

Ik heb die cout in de for lus gezet om de waardes even te testen alleen kreeg op de 30progingen slechts 1* een output, wat doe ik mis? :-s
MVG fromalk

[Nick_S]

Van welk type is je array? De meeste random generators geven een waarde tussen 0 en 1 terug. Als je array van het type int is, komt daar dus altijd een 0 of een 1 in te staan. Misschien dat je daar eens naar kunt kijken?

[fromalk]

het zijn inderdaad int's

code:

int a, b, c, ai_b1_cn[2], ai_b2_cn[3], ai_b3_cn[3], ai_b4_cn[4], ai_b5_cn[5];

nu je kan toch best meerdere digits in één vakje van de array steken?

[MrBucket]

Nick_S schreef op maandag 14 maart 2005 @ 20:00:
Van welk type is je array? De meeste random generators geven een waarde tussen 0 en 1 terug. Als je array van het type int is, komt daar dus altijd een 0 of een 1 in te staan. Misschien dat je daar eens naar kunt kijken?

Nee, dat is het niet, rand() geeft een int terug die tussen 0 en RAND_MAX ligt. Voor MSVC is RAND_MAX gedefinieerd als 0x7FFF (=32767).

Maar zelfs als je array uit chars bestaat (en de kans op overflow erg groot is), zou je nog steeds de laagste 8 bits terug moeten zien in je uitvoer...

Trouwens, om je random numbers te beperken tot het bereik [0, x) kan je "rand() % x" schrijven.

[Reptile209]

Probeer die ai_bl_cn[] eens als float te declareren, ik denk dat je dan een boel meer te zien krijgt. Check je helpfile eens op je declaratie van rand(): wat voor type geeft 'ie terug?
En anders is de stap-voor-stap debugger (met een watch op je variabelen) je vriend.

[ Voor 20% gewijzigd door Reptile209 op 14-03-2005 20:07 ]

[MrBucket]

fromalk schreef op maandag 14 maart 2005 @ 20:03:
het zijn inderdaad int's

code:

int a, b, c, ai_b1_cn[2], ai_b2_cn[3], ai_b3_cn[3], ai_b4_cn[4], ai_b5_cn[5];

nu je kan toch best meerdere digits in één vakje van de array steken?

Nu ben ik toch wel heel nieuwsgierig wat je met die array-declaraties wilt gaan doen... het ziet er nogal onorthodox uit

[fromalk]

hehe,

ik dacht wel dat mn mijn manier van aanpakken vreem zou vinden, wel even uitleggen:
Ik heb dus telkens een variabele alsvolgt (abc hebben geen uitleg ndoig )
ai_bx_cn[y], wel het is vrij simpel:
ai -> ai of artificial intelligence, dit gewoon om het onderscheid te maken met de door de speler ingevuld boor coordinaten.
b()x -> b = boat; x=bootnummer
cn -> coordinaat nummeriek (heb ook alpha coordinaten nl)

nu zijn er schepen van 2,3,3,4,5 blokken wat de y verklaard.
De bedoeling is dat ik in de eerder geposte for lus 2 coordinaten bereken voor boot 1.
daarom dat c<2.
zo krijg je dus uiteindelijk:
ai_b1_cn[8;9] bv, later zal ik ook nog zorgen dat de getallen horizontaal of verticaal moeten langs elkaar liggen.
Hoop dat het wat duidelijk is nu, we spreken hier nog niet over de letter van elk coordinaat die men kan ingeven

[MrBucket]

Mag ik een suggestie doen waarmee het misschien makkelijker wordt om de juiste random posities te genereren?

Ten eerste zou ik een aparte struct willen voorstellen voor een boot, omdat het een aparte entiteit binnen je spel is waar je nog vaak gebruik van zult maken. (Evt. zou je ook een datatype voor positie kunnen maken, aangezien je daar ook veel gebruik van zult maken en het de programmacode waarschijnlijk duidelijker leesbaar maakt.)

C++:

enum Orientation{
  HORIZONTAL,
  VERTICAL
};

struct Boat{
  int iTopLeftX;  //Top left x-coord of this Boat on the board
  int iTopLeftY; //Top left x-coord of this Boat on the board
  int iSize;    //Nr of fields that this Boat occupies on the board
  Orientation orientation; //Orientation of the Boat
};

Een boot is dan makkelijker op een willekeurige plek te positioneren, omdat je maar 1 coordinaat en een richting hoeft te genereren. Als je zorgt dat, afhankelijk van de richting, je de coordinaten zo genereert dat de boot nooit buiten het bord kan vallen, ben je d'r al bijna

[MSalters]

MrBucket schreef op maandag 14 maart 2005 @ 20:05:
[...]
Trouwens, om je random numbers te beperken tot het bereik [0, x) kan je "rand() % x" schrijven.

Nee. Dan krijg je een afwijking. Stel dat RAND_MAX ==100 en x=99, dan komt 0 twee keer zo vaak voor als andere getallen.

boost::random heeft een oplossing die wel een uniforme verdeling [x,y) garandeert.

[MrBucket]

MSalters schreef op dinsdag 15 maart 2005 @ 10:37:
[...]

Nee. Dan krijg je een afwijking. Stel dat RAND_MAX ==100 en x=99, dan komt 0 twee keer zo vaak voor als andere getallen.

Als je bereik klein genoeg houdt (zoals hier, een bord is 10 vakjes breed), is die afwijking verwaarloosbaar voor alles behalve simulatiesoftware.
Kom op, d'r zijn 3 situaties die elk 3276 keer gegenereerd worden, en 7 situaties die elk 3277 gegenereerd kunnen worden. Dat verschil merk je echt niet.

[Zoijar]

Je moet het gewoon casten naar een double, en delen door rand_max, en dan vermenigvuldigen met je range. Dus zoiets:

C++:

// random integer in [a, b]
int r = a + static_cast<int>((b-a) * (rand() / static_cast<double>(RAND_MAX)));

Alleen vraag ik me dan af of je met de afronding niet precies hetzelfde doet...int in [0, 10] geeft nl.

[0, 0.5) = 0
[0.5 - 1.5) = 1
[1.5 - 2.5) = 2
[2.5, 3.5) = 3
[3.5, 4.5) = 4
[4.5, 5.5) = 5
[5.5, 6.5) = 6
[6.5, 7.5) = 7
[7.5, 8.5) = 8
[8.5, 9.5) = 9
[9.5, 10) = 10

Dus moet je het nog schuiven als je afrondt. Komma afhakken is beter?

[0, 1) = 0
[1, 2) = 1
[2, 3) = 2
[3, 4) = 3
[4, 5) = 4
[5, 6) = 5
[6, 7 ) = 6
[7, = 7
[8, 9) = 8
[9, 10) = 9
10 = 10

Dan moet je een special case inbouwen voor RAND_MAX. Maar in principe is het dan zo:

C++:

// met "komma afhak afronding"
int ra;
do {ra = rand();} while (ra == RAND_MAX);
int r = a + static_cast<int>((b-a+1)*(ra / static_cast<double>(RAND_MAX)));

[ Voor 71% gewijzigd door Zoijar op 15-03-2005 12:10 ]

[Soultaker]

Zoijar: dat lost het fundamentele probleem niet op; je verdeelt de uniforme uitvoer van rand() (zeg, N == RAND_MAX mogelijke, even waarschijnlijke getallen) dan nog steeds in M gebieden.

Zowel bij de modulo-truc als met vermenigvuldigen en afronden beeld je gewoon waarden van N af op waarden van M; als N niet exact deelbaar is door M dan is er geen enkele afbeelding die uniforme waarden van M oplevert.

[Zoijar]

Dat onderste werkt toch? Volgens mij wel...

[Soultaker]

Ik reageerde op je ongëeditte post. Die onderste zie ik helemaal niet werken, want je komt nu altijd uit op ra == RAND_MAX. Of bedoelde je nog wat anders?

Een manier die wel goed werkt (volgens mij) is het bereik 'afkappen' zodat je een uniforme verdeling krijgt over k*M getallen met k een heel getal. Concreet, als je een getal van 0 tot 10 wilt (M==10) en RAND_MAX=65535 (bijvoorbeeld), dan neem je N=65530 (een veelvoud van M) en gooi je waarden die er niet aan voldoen gewoon weg:

C:

int r;
do { r = rand(); } while(r > 65530);
return r % 10;

De essentie is dat je het fundamentele probleem moet oplossen dat je N uniforme willekeurige getallen niet 'zomaar' in M hokjes kan duwen, tenzij N deelbaar is door M. Anders hou je altijd een afwijking (en dan is de verdeling van M hokjes dus niet uniform), hoe je ook op de indeling in hokjes uitkomt (modulo, converteren naar double en afronden, enzovoorts.) Vandaar dat ik voorstel om waarden weg te gooien. _{(Maar dit is puur kansrekeningtechnisch beredeneerd; voor de meeste praktische doel zal het waarschijnlijk niet zoveel uitmaken, zoals MrBucket al zei.)}

[ Voor 41% gewijzigd door Soultaker op 15-03-2005 12:09 ]

[MSalters]

Alle N->M projecties waarbij N%M !=0 zijn niet uniform. De oplossing van Soultaker is dus correct: bepaal eerst een getal in de range [0, N-(N%M) ) en projecteer dat vervolgens uniform op de range [ 0,M )

[Zoijar]

Hehe ja, == natuurlijk

Dat is volgens mij hetzelfde, alleen moet je dan iets langer randomizen. Maar wel makkelijker. Hoewel, je moet natuurlijk wel nog die N vinden, maar dat is wel te doen. Je kan RAND_MAX delen door 10 en dan de komma er af hakken en het weer terug vermenigvuldigen. Klinkt als hetzelfde idee.

[Soultaker]

Mja, wat MSalters ook zegt dus. Je moet trouwens weer allerlei kunstgrepen uithalen als je een getal wil hebben dat groter is dan RAND_MAX, maar als RAND_MAX*RAND_MAX niet in je integers past. (Converteren naar long long ofzoiets is misschien wel het makkelijkste dan.)

[Zoijar]

Ja, ik snap het idee wel Maar mijn laatste oplossing die ik gaf is ook correct, toch? En probabilistisch sneller Ik zit alleen nog een beetje met machine preciesie, maar ik geloof dat dat wegvalt... dat weet ik dus niet zeker.

[Soultaker]

Volgens mij klopt die tweede ook niet, want je gooit alleen RAND_MAX weg. Dat lost het probleem niet op, want als RAND_MAX-1 niet deelbaar is door M (het aantal getallen in de uitvoer) dan kun je geen afbeelding maken die een uniforme verdeling oplevert.

[.oisyn]

Idd, probeer het maar eens met een random getal van bijvoorbeeld 4 bits. Die 16 combinaties kun je nooit op een uniforme manier over de 10 resultaten verdelen, er zullen 6 resultaten zijn die een grotere kans hebben dan de overige 4. Alleen de RAND_MAX case wegwerken zorgt ervoor dat je 5 resultaten hebt met een hogere kans dan de overige 5, nog steeds niet eerlijk dus.

[MrBucket]

C++:

//Generate uniform random nr r in [0, n)
int iUniformRangeMax = (RAND_MAX / n) * n;
int iRnd;
do{
  iRnd = rand();
}while(iRnd > iUniformRangeMax);
r = iRnd % n;

Stel dat RAND_MAX 32 is, en is n = 10, dan wordt iUniformRangeMax (32 / 10) * 10 = 3 * 10 = 30. De loop blijft zich dus herhalen totdat een random nummer in [0, 30) gevonden wordt. Dan is het wel 'veilig' om 'm modulo n te doen.

[ Voor 4% gewijzigd door MrBucket op 15-03-2005 13:33 ]

[.oisyn]

Niet helemaal goed, je wilt een while (iRnd >= iUniformRangeMax), anders krijgt 0 een extra kans
.edit: ah dat zeg je zelf ook al met de notatie [0, 30), alleen je code matcht dus niet met wat je zegt

[ Voor 36% gewijzigd door .oisyn op 15-03-2005 13:58 ]

[Zoijar]

.oisyn schreef op dinsdag 15 maart 2005 @ 13:29:
Idd, probeer het maar eens met een random getal van bijvoorbeeld 4 bits. Die 16 combinaties kun je nooit op een uniforme manier over de 10 resultaten verdelen, er zullen 6 resultaten zijn die een grotere kans hebben dan de overige 4. Alleen de RAND_MAX case wegwerken zorgt ervoor dat je 5 resultaten hebt met een hogere kans dan de overige 5, nog steeds niet eerlijk dus.

Je hebt gelijk, het loopt dan dus wel stuk op machine preciesie. Ok, duidelijk, het was leuk om er even over te denken waarom iets niet klopt

[.oisyn]

Nou ja, niet machine precisie, maar meer het feit dat er gewoon een eindige precisie aan rand() zit

[MSalters]

MrBucket schreef op dinsdag 15 maart 2005 @ 13:33:

C++:

//Generate uniform random nr r in [0, n)
int iUniformRangeMax = (RAND_MAX / n) * n;
int iRnd;
do{
  iRnd = rand();
}while(iRnd > iUniformRangeMax);
r = iRnd % n;

Wat ik zei. iUniformRangeMax is een veelvoud van n en dus is iRnd % n ook uniform.

[Zoijar]

.oisyn schreef op dinsdag 15 maart 2005 @ 14:27:
Nou ja, niet machine precisie, maar meer het feit dat er gewoon een eindige precisie aan rand() zit

uhh ja, dat is dus machine preciesie