[js] Math.random() lijkt niet random - Softwareontwikkeling

donderdag 21 augustus 2008 00:14

Acties:

Topicstarter

Een plaatje zegt heel veel:

Afbeeldingslocatie: http://spookpaard.nl/host/files/tetris.gif

Ik ben bezig met het programmeren van Tetris en het probleem is dat ik opvallend veel dezelfde blokken achter elkaar krijg. Wat dezelfde blokken zijn verschilt per spel en level. Het level regelt de gamespeed.

Zou dit kunnen komen doordat de gamespeed een vaste interval (setTimeout) is? Want Math.random() gebruikt default tijd als seed, en misschien is daardoor de seed minder random dan hier praktisch is.

Op deze manier haal ik een random block op:

JavaScript:

1	Math.floor(Math.random() * this.blocks().length)

Is hier wat aan te doen?

donderdag 21 augustus 2008 00:56

Acties:

.oisyn

Moderator Devschuur®

Demotivational Speaker

Het lijkt me niet dat random() op elke timeout re-seed, dat zou wel heel suf zijn.

Een korte test laat ook zien dat bij het genereren van random getallen van 0 t/m 9 de frequenties van die nummers convergeren naar 10%, wat je mag verwachten bij een uniform verdeelde (pseudo) RNG.

HTML:

<html>
<head>
<title>test</title>

<script>
freq = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0];
total = 0;

function ping()
{
    var r = Math.floor(Math.random() * 10);
    freq[r]++;
    total++;
        
    var t = r + "<br/><br/>";

    for (var i = 0; i < 10; i++)
    {
        var p = Math.floor(100 * freq[i] / total);
        t += i + ": " + freq[i] + " (" + p + "%)<br>";
    }
    
    document.body.innerHTML = t;
    
    setTimeout(ping, 1);
}

function load()
{
    setTimeout(ping, 250);
}

</script>
</head>
<body onload="load()">
hoi
</body>
</html>

Ik denk dus eerder dat er iets mis is met je blok-selectie-code.

[ Voor 3% gewijzigd door .oisyn op 21-08-2008 00:58 ]

Give a man a game and he'll have fun for a day. Teach a man to make games and he'll never have fun again.

donderdag 21 augustus 2008 02:15

Acties:

Blaise

Topicstarter

Met de blok selectie kan weinig misgaan:

JavaScript:

block = {
     blocks : function(){
          return [
               [[1,1,1],   // J,0
                [0,0,1]],
               [[1,1,1,1]],// I,1
               [[1,1,1],   // L,2
                [1,0,0]],
               [[1,1],     // O,3
                [1,1]],
               [[0,1,1],   // S,4
                [1,1,0]],
               [[1,1,1],   // T,5
                [0,1,0]],
               [[1,1,0],   // Z,6
                [0,1,1]]
          ];
     },

     getRandom : function(rotations) {

          blockID = Math.floor(Math.random() * this.blocks().length);

          if (typeof rotations == 'undefined') rotations = Math.floor((Math.random() * 3));

          ( ... )
     }
}

getRandom() wordt aangevraagd aan het begin van het spel en als een blok geplaatst is.

In jouw voorbeeld zie je dat pas na verloop van tijd de frequenties naar de 10% gaan. In het begin verschillen de frequenties veel meer (wel even timer wat langzamer zetten)

Als je Tetris speelt wil je afwisseling in opeenvolgende blokken, en doet het er minder toe of na 500 blokken alle blokken ongeveer even vaak zijn langsgekomen.

Maar als dit inherent is aan random() moet ik misschien gewoon gaan bijhouden hoe vaak blokken langskomen, en als een bepaald blok te vaak langskomt dan vraag ik een andere. Kan ik het ook gelijk de speler lastig maken met irritante combinaties

donderdag 21 augustus 2008 02:26

Acties:

.oisyn

Moderator Devschuur®

Demotivational Speaker

Blaise schreef op donderdag 21 augustus 2008 @ 02:15:
In jouw voorbeeld zie je dat pas na verloop van tijd de frequenties naar de 10% gaan. In het begin verschillen de frequenties veel meer (wel even timer wat langzamer zetten)

Ja, nogal wiedes! Er zijn minder trekkingen, dus bij een verschil van 1 hoort een veel groter percentage dan als er veel trekkingen zijn geweest

Als je Tetris speelt wil je afwisseling in opeenvolgende blokken, en doet het er minder toe of na 500 blokken alle blokken ongeveer even vaak zijn langsgekomen.

Dat is juist wat er toe doet, en wat bij jou momenteel niet lijkt te kloppen. De groene en de blauwe blokjes lijken gewoon veel vaker getrokken te worden, en ook heel veel dezelfde achter elkaar. Vergelijk het eens met het gooien van een dobbelsteen - puur random, maar knap lastig om de hele tijd hetzelfde getal te gooien. Soms lukt het om twee keer achter elkaar dezelfde te gooien (1 op de 6), en heel soms drie keer (1 op de 36), maar 4 keer achter elkaar wordt al een zeldzaamheid (1 op de 216 keer). Hetzelfde bij de blokjes van tetris. Af en toe krijg je twee keer dezelfde. En heel soms 3x dezelfde. Maar wat jij nu hebt strookt niet met een degelijke implementatie van random trekkingen. Dus of je code klopt niet, of de implementatie van random() van je browser is gewoon ruk

Overigens kan het best zo zijn dat de blokken in de originele tetris niet allemaal een gelijke kans hebben. Maar elke schoolvoorbeeld-implementatie waarbij gewoon een uniforme verdeling wordt gebruikt speelt vrij fatsoenlijk.

Oh, en eigenlijk is de verdeling van Math.random() over 7 blokken natuurlijk niet geheel uniform. Math.random() heeft namelijk geen oneindige precisie. Bij mij (IE 7) is ie 55 bits, wat het maximale is wat in een floating point getal past. Dat betekent dat de eerste 2⁵⁵ mod 7 = 2 blokken iets vaker worden gekozen. Maar omdat hij 55 bits is is dat mariginaal (1 op de 2⁵⁵ / 7 ~= 5.146.971.002.709.138 meer kans)

[ Voor 42% gewijzigd door .oisyn op 21-08-2008 02:44 ]

Give a man a game and he'll have fun for a day. Teach a man to make games and he'll never have fun again.

donderdag 21 augustus 2008 02:46

Acties:

Blaise

Topicstarter

Ik bedoelde geen open deuren in te schoppen

Ik kwam in mijn eigen tempo (traag) tot het inzicht dat random() bij tetrisblokken niet het gewenste resultaat oplevert. Je edit verduidelijkt het nog eens.

Nu was de situatie op het screenshot wel erg uitzonderlijk (dat ik er maar een screenshot van had gemaakt). Meestal is het niet zó erg, maar toch komen sommige blokken opvallend vaak langs, en doordat ze allemaal een eigen kleur hebben valt dat op. Als je zelf wilt ervaren: http://www.blaisekal.com/tetris/

[ Voor 5% gewijzigd door Blaise op 21-08-2008 02:48 ]

donderdag 21 augustus 2008 04:47

Acties:

LightTwi

Ik heb het spelletje net een beetje getest en het komt gewoon over als een volwaardig tetris spelletje!
Ik zie nou niet echt dat een bepaald blokje veel vaker voorkomt als de ander, dus als je het mij vraagt heb je het probleem opgelost. Ik zeg; gewoon laten zo!

Score: 518 Lines: 29 Level: 6

Afbeeldingslocatie: http://img102.imageshack.us/img102/5394/tetrisjj2.th.jpg

[ Voor 7% gewijzigd door LightTwi op 21-08-2008 04:49 ]

donderdag 21 augustus 2008 09:39

Acties:

_Thanatos_

Ja, en kaal

Doe je nog wel ff een nette melding geven als javascript uitstaat?

日本！🎌

donderdag 21 augustus 2008 11:16

Acties:

.oisyn

Moderator Devschuur®

Demotivational Speaker

Ik merk idd ook geen abnormale blok-herhalingen oid

Overigen zit er een bugje in het kiezen van een random rotatie - je doet Math.random() * 3 ipv * 4

Give a man a game and he'll have fun for a day. Teach a man to make games and he'll never have fun again.

donderdag 21 augustus 2008 11:34

Acties:

H004

Ik merk ook geen regelmatigheden in het type blokjes.

Wel is het na level 11 vrijwel niet meer mogelijk om nog verplaatsingen van blokjes aan te geven, omdat toetsen niet meer reageren. Misschien vraagt het animeren van het vallen teveel van de browser? (FF3)

donderdag 21 augustus 2008 12:18

Acties:

André

Analytics dude

Doet me denken aan een DHTML contest van een paar jaar terug

Daar heb ik dit relikwie nog aan over gehouden: http://andrescholten.nl/astris/

donderdag 21 augustus 2008 12:31

Acties:

jeanj

F5 keeps me alive

Even getest, geen problemen met de random

Even feedback op de implementatie
1. het grid maakt het wel erg makkelijk, misschien uit zetten (of anders op een hoger level, uitzetten?
2. ik ben gewend als je een blok laat vallen dat ie helemaal naar beneden valt, maar dat is natuurlijk een keuze. Ik zou het handiger vinden pijl naar benden 1x in drukken om te laten vallen en pijl naar boven om het te onderbreken (en dus niet pijl naarbenede ingedrukt houden)
3. een nieuw blok verschijnt bij mij eerst links boven in het speel veld even heel snel, je ziet het even verschijnen

Ik heb het in ff2 getest, op win xp sp2

Ziet er verder leuk uit

Everything is better with Bluetooth

donderdag 21 augustus 2008 19:22

Acties:

Blaise

Topicstarter

Poeee wat een boel reacties!

Doe je nog wel ff een nette melding geven als javascript uitstaat?

Wie heeft er nou js uitstaan

Overigen zit er een bugje in het kiezen van een random rotatie - je doet Math.random() * 3 ipv * 4

Rotatie begint bij mij bij 0 (geen rotatie), dus 0 - 3

Daar heb ik dit relikwie nog aan over gehouden: http://andrescholten.nl/astris/

Je die had ik destijds ook gezien, met groot ontzag! Ik keek net even in de broncode van astris. Jouw toetsafhandeling als je een knop ingedrukt houdt, dat die meerdere keren firet, is erg handig. In Opera en in browsers op de Mac heb je dat namelijk niet by default, die firen maar 1x waardoor je een knop niet ingedrukt kan houden.

Wel is het na level 11 vrijwel niet meer mogelijk om nog verplaatsingen van blokjes aan te geven, omdat toetsen niet meer reageren. Misschien vraagt het animeren van het vallen teveel van de browser? (FF3)

Ik kan nog wel bewegen in level 12 (FF3 / redelijk snelle PC), maar het gaat dan zo snel dat ik af ga. Ik ben nog wel bezig met de snelheid / opbouw. Die neemt nu sequentieel per level toe, maar bij hogere levels is die toename te groot. Bij level 12 komt de timer in de buurt van de 0 (timer = 750 - ((level / 1.2) * 70); // 50) waardoor je CPU het zwaar krijgt. Ik ga nog maken dat de toename van de snelheid steeds verder afneemt, dan komt dit hopelijk goed.

Even feedback op de implementatie
1. het grid maakt het wel erg makkelijk, misschien uit zetten (of anders op een hoger level, uitzetten?
2. ik ben gewend als je een blok laat vallen dat ie helemaal naar beneden valt, maar dat is natuurlijk een keuze. Ik zou het handiger vinden pijl naar benden 1x in drukken om te laten vallen en pijl naar boven om het te onderbreken (en dus niet pijl naarbenede ingedrukt houden)
3. een nieuw blok verschijnt bij mij eerst links boven in het speel veld even heel snel, je ziet het even verschijnen

1. Oorspronkelijk is het grid er omdat ik dat mooi vind, maar ik vind ook bevorderlijk voor het speelplezier omdat het duidelijker is waar je blok gaat komen en je dus een beter gevoel van controle hebt.
2. Dit is ook een persoonlijke keuze: ik heb liever een speedup-toets dan een drop-toets, zeker aan het begin van het spel als de blokken traag vallen en je misschien een blok onderaan nog wil schuiven of draaien. Je kan die knop ook ingedrukt houden, dus ik zie het niet echt als een gemis.
3. Bedankt voor het melden, ik zal het verbeteren.

donderdag 21 augustus 2008 19:52

Acties:

André

Analytics dude

Blaise schreef op donderdag 21 augustus 2008 @ 19:22:

Je die had ik destijds ook gezien, met groot ontzag! Ik keek net even in de broncode van astris. Jouw toetsafhandeling als je een knop ingedrukt houdt, dat die meerdere keren firet, is erg handig. In Opera en in browsers op de Mac heb je dat namelijk niet by default, die firen maar 1x waardoor je een knop niet ingedrukt kan houden.

Mwah, met groot ontzag valt ook wel mee hoor. Ik dacht toen dat ik iets leuk had totdat clay met een roterende tetris kwam waar die van mij bij in het niet viel. En net toen ik dat cool vond kwam crisp met dhtml lemmings aanzetten. Ik durfde mijn Astris niet meer te vertonen

donderdag 21 augustus 2008 20:10

Acties:

Blaise

Topicstarter

Ik kon toen nog nauwelijks Javascript dus mijn perspectief was anders. Lemmings is tovenarij! Daar valt alles bij in het niet.

donderdag 21 augustus 2008 22:57

Acties:

.oisyn

Moderator Devschuur®

Demotivational Speaker

Blaise schreef op donderdag 21 augustus 2008 @ 19:22:
Rotatie begint bij mij bij 0 (geen rotatie), dus 0 - 3

Klopt, en Math.random() geeft een waarde tussen 0 en 1. Vervolgens doe je een floor, dus 3 zul je nooit krijgen (precies 1 zal Math.random() ook nooit zijn)

Dus Math.floor(Math.random() * 3) geeft een waarde van 0 t/m 2

.
En als je toch overtuigd bent van je eigen redenatie mag je uitleggen waarom het dan met blocks().length wel klopt

Give a man a game and he'll have fun for a day. Teach a man to make games and he'll never have fun again.

vrijdag 22 augustus 2008 00:55

Acties:

Blaise

Topicstarter

Je hebt gelijk, ik was weer eigenwijs

[ Voor 5% gewijzigd door Blaise op 22-08-2008 00:57 ]

vrijdag 22 augustus 2008 01:37

Acties:

crisp

Devver

Pixelated

Waarom is blocks een method en geen property? het is toch static neem ik aan?

Intentionally left blank

vrijdag 22 augustus 2008 01:53

Acties:

Martinspire

Awesomeness

Doet me denken aan de volgende comics:

Afbeeldingslocatie: http://imgs.xkcd.com/comics/random_number.png

en

Afbeeldingslocatie: http://content3.clipmarks.com/image_cache/xofxof/512/405B2A78-5499-474D-89B9-17F420F175C5.gif

Martinspire - PC, PS5, XSX

vrijdag 22 augustus 2008 01:55

Acties:

RocketKoen

speel werkt hier prima.
alleen bij level 12 wordt het wel onspeelbaar snel...

TheS4ndm4n#1919

vrijdag 22 augustus 2008 09:17

Acties:

Clay

cookie erbij?

André schreef op donderdag 21 augustus 2008 @ 12:18:
Doet me denken aan een DHTML contest van een paar jaar terug

Daar heb ik dit relikwie nog aan over gehouden: http://andrescholten.nl/astris/

Jaaa

weer eens eentje doen?

Kunnen het alleen geen dhtml meer noemen uiteraard, dat is zo 1.0.

Instagram | Flickr | "Let my music become battle cries" - Frédéric Chopin

vrijdag 22 augustus 2008 09:49

Acties:

Verwijderd

Clay schreef op vrijdag 22 augustus 2008 @ 09:17:
Jaaa weer eens eentje doen?
Kunnen het alleen geen dhtml meer noemen uiteraard, dat is zo 1.0.

Ik doe mee! (Maar alleen als het wel DHTML heet

)

vrijdag 22 augustus 2008 11:17

Acties:

.oisyn

Moderator Devschuur®

Demotivational Speaker

Hmm dan moet ik m'n wolfenstein eens helemaal gaan implementeren en zorgen dat het op de meeste browsers draait...

Give a man a game and he'll have fun for a day. Teach a man to make games and he'll never have fun again.

vrijdag 22 augustus 2008 11:35

Acties:

BCC

Het is een bekend probleem dat mensen random niet als random ervaren.
00001111 is even random als 01010101 en 10011010, maar mensen zullen de eerste reeksen als niet willekeurig beschouwen.

Er zijn wat truuks die je kan toepassen, zodat het beter voelt.
Bijvoorbeeld wanneer 'random' dezelfde kleur gekozen word, nog een keer kleur kiezen.
Hetzelfde geld voor de vorm.

Zo komt het minder vaak voor dat dezelfde kleur of vorm herhaalt wordt, waardoor het geheel willekeuriger aanvoelt.

Er zijn heel veel artikelen hierover te vinden op internet met betrekken tot AI.

Na betaling van een licentievergoeding van €1.000 verkrijgen bedrijven het recht om deze post te gebruiken voor het trainen van artificiële intelligentiesystemen.

vrijdag 22 augustus 2008 11:44

Acties:

Marcks

BCC schreef op vrijdag 22 augustus 2008 @ 11:35:
Het is een bekend probleem dat mensen random niet als random ervaren.
00001111 is even random als 01010101 en 10011010, maar mensen zullen de eerste reeksen als niet willekeurig beschouwen.

Niet waar, de eerste twee bitreeksen heb je doelbewust opgesteld op een manier waarop ze niet random lijken, en ze zijn daardoor minder willekeurig dan de laatste.

Ik veronschuldig mij bij voorbaat voor het bovenstaande.

vrijdag 22 augustus 2008 12:05

Acties:

jeanj

F5 keeps me alive

Blaise schreef op donderdag 21 augustus 2008 @ 19:22:
Wie heeft er nou js uitstaan

Ik dus, FF 2 met no script. Ben een beetje paranoide/voorzichtig

Everything is better with Bluetooth

vrijdag 22 augustus 2008 12:13

Acties:

BtM909

Watch out Guys...

Marcks schreef op vrijdag 22 augustus 2008 @ 11:44:
[...]

Niet waar, de eerste twee bitreeksen heb je doelbewust opgesteld op een manier waarop ze niet random lijken, en ze zijn daardoor minder willekeurig dan de laatste.

Nee hoor, dit komt gewoon uit een random generator waarbij je willekeurig drie entries pakt

Ace of Base vs Charli XCX - All That She Boom Claps (RMT) | Clean Bandit vs Galantis - I'd Rather Be You (RMT)
You've moved up on my notch-list. You have 1 notch
I have a black belt in Kung Flu.

vrijdag 22 augustus 2008 12:24

Acties:

Blaise

Topicstarter

crisp schreef op vrijdag 22 augustus 2008 @ 01:37:
Waarom is blocks een method en geen property? het is toch static neem ik aan?

Ik was eerst van plan om bewerkingen op de array los te laten binnen die method. Dat bleek achteraf onnodig, maar de code is nog niet aangepast.

Clay schreef op vrijdag 22 augustus 2008 @ 09:17:
[...]

Jaaa weer eens eentje doen?
Kunnen het alleen geen dhtml meer noemen uiteraard, dat is zo 1.0.

Ja goed idee! ik doe ook mee dan met iets nieuws. Met de term dhtml heb ik totaal geen probleem, itt web2.0 (bah!)

jeanj schreef op vrijdag 22 augustus 2008 @ 12:05:
[...]

Ik dus, FF 2 met no script. Ben een beetje paranoide/voorzichtig

Ik verberg de tekst nu met js ipv css, dus nu zie je een meldinkje.

vrijdag 22 augustus 2008 15:12

Acties:

BCC

Ik vind deze mooier:
[snip]

Niet alleen al eerder gepost, maar maak altijd eerst ff goede kleine pica's. (1500 pixels is niet echt fijn voor een strip

)

edit:

Sorry, ik lette even niet op

[ Voor 84% gewijzigd door BtM909 op 22-08-2008 15:20 ]

Na betaling van een licentievergoeding van €1.000 verkrijgen bedrijven het recht om deze post te gebruiken voor het trainen van artificiële intelligentiesystemen.

vrijdag 22 augustus 2008 16:28

Acties:

ChessSpider

Ik weet niet, ik speelde een paar minuutjes en ik kreeg toch met enige regelmaat 3 x dezelfde achter elkaar.
Ook kreeg ik 3x zo'n 4x4 blok, 2 anderen, en toen weer 2x die blok achter elkaar.

Maarja, nu lette ik er ook echt op natuurlijk.

vrijdag 22 augustus 2008 16:40

Acties:

BtM909

Watch out Guys...

ChessSpider schreef op vrijdag 22 augustus 2008 @ 16:28:
Ik weet niet, ik speelde een paar minuutjes en ik kreeg toch met enige regelmaat 3 x dezelfde achter elkaar.
Ook kreeg ik 3x zo'n 4x4 blok, 2 anderen, en toen weer 2x die blok achter elkaar.

Maarja, nu lette ik er ook echt op natuurlijk.

Nogmaals, waarom zou dat niet kunnen in een random selectie? Dan kan je net zo goed de volgorde gaan vastleggen

Ace of Base vs Charli XCX - All That She Boom Claps (RMT) | Clean Bandit vs Galantis - I'd Rather Be You (RMT)
You've moved up on my notch-list. You have 1 notch
I have a black belt in Kung Flu.

zaterdag 23 augustus 2008 01:07

Acties:

ChessSpider

BtM909 schreef op vrijdag 22 augustus 2008 @ 16:40:
[...]

Nogmaals, waarom zou dat niet kunnen in een random selectie? Dan kan je net zo goed de volgorde gaan vastleggen

Het kan inderdaad gewoon toeval zijn, maar de kans ^^ is niet zo groot.
Zoals ik al zei, ik lette er nu echt op. Als ik er niet op let valt het waarschijnlijk niet zoveel op, netzoals met andere spellen.

zondag 24 augustus 2008 00:41

Acties:

Spinal

Lijkt het hier (Win XP, Opera 9.52) prima te doen. Nooit 4x hetzelfde blok achter elkaar gehad, en heb toch zeker een kwartier gespeeld.

Full-stack webdeveloper in Groningen

zondag 24 augustus 2008 00:46

Acties:

WeeJeWel

jeanj schreef op vrijdag 22 augustus 2008 @ 12:05:
[...]

Ik dus, FF 2 met no script. Ben een beetje paranoide/voorzichtig

En je bent zeker ook bang om in een auto te rijden omdat je wel eens een ongeluk zou kunnen krijgen?

Homey — Critics are those without skills to create.

zondag 24 augustus 2008 01:02

Acties:

Jaap-Jan

WeeJeWel schreef op zondag 24 augustus 2008 @ 00:46:
[...]

En je bent zeker ook bang om in een auto te rijden omdat je wel eens een ongeluk zou kunnen krijgen?

Nee, maar ik doe wel een gordel om.

| Last.fm | "Mr Bent liked counting. You could trust numbers, except perhaps for pi, but he was working on that in his spare time and it was bound to give in sooner or later." -Terry Pratchett

zondag 24 augustus 2008 01:03

Acties:

WeeJeWel

In dat geval gewoon Firefox of Opera gebruiken

Homey — Critics are those without skills to create.