Satunnaislukujen nopea ja tehokas generointi on ollut pitkään tärkeä haaste. Onnenpelit ovat vuosisatojen ajan perustuneet nopan heittämiseen, kolikon heittämiseen tai korttien sekoittamiseen tuodakseen satunnaisuutta prosessiin. 20-luvun jälkipuoliskolla tietokoneet alkoivat ottaa tämän roolin salaus-, tilasto- ja tekoälysovelluksiin sekä erilaisiin simulaatioihin - ilmastollisiin, epidemiologisiin, taloudellisiin ja niin edelleen.

MIT-tutkijat ovat nyt kehittäneet tietokonealgoritmin, joka voi ainakin joissakin tehtävissä tuottaa satunnaisia ​​lukuja parhaalla nopeuden, tarkkuuden ja alhaisten muistivaatimusten yhdistelmällä, joka on saatavilla nykyään. Algoritmin, nimeltä Fast Loaded Dice Roller (FLDR), loivat MIT:n jatko-opiskelija Feras Saad, tutkija Cameron Freer, professori Martin Rinard ja johtava tutkija Vikash Mansinghka, ja se esitellään ensi viikolla 23. kansainvälisessä konferenssissa. Tekoälystä ja tilastoista. 

Yksinkertaisesti sanottuna FLDR on tietokoneohjelma, joka simuloi noppaa heittääkseen satunnaisia ​​kokonaislukuja. Nopalla voi olla mikä tahansa määrä sivuja, ja ne on "kuormattu" tai painotettu, jotta jotkut puolet nousevat todennäköisemmin esiin. Ladattu noppi voi silti tuottaa satunnaislukuja - koska ei voi ennustaa etukäteen, kumpi puoli nousee - mutta satunnaisuus on pakotettu vastaamaan ennalta asetettua todennäköisyysjakaumaa. Voisi esimerkiksi käyttää ladattuja noppaa pesäpallopelin lopputuloksen simuloimiseen; vaikka parempi joukkue voittaa todennäköisemmin, jonakin päivänä kumpi tahansa joukkue voi päätyä kärkeen.

FLDR:llä nopat ovat "täydellisesti" ladattuja, mikä tarkoittaa, että ne saavuttavat täsmälleen määritetyt todennäköisyydet. Esimerkiksi nelisivuisella meistillä voisi järjestää asiat niin, että luvut 1,2,3, 4, 23 ja 34 kääntyvät täsmälleen 17 prosenttia, 26 prosenttia, XNUMX prosenttia ja XNUMX prosenttia ajasta.

Simuloidakseen ladattujen noppien heittoa, joissa on suuri määrä sivuja, MIT-tiimin oli ensin hyödynnettävä yksinkertaisempaa satunnaisuuden lähdettä – se on tietokoneistettu (binääri) versio kolikonheitosta, joka tuotti joko 0:n tai 1:n. jokainen 50 prosentin todennäköisyydellä. Niiden menetelmän tehokkuus, joka on keskeinen suunnittelukriteeri, riippuu siitä, kuinka monta kertaa heidän on napautettava tätä satunnaista lähdettä - toisin sanoen "kolikonheittojen" määrää - simuloidakseen jokaista nopanheittoa. 

Vuoden 1976 merkittävässä artikkelissa tietojenkäsittelytieteilijät Donald Knuth ja Andrew Yao kehittivät algoritmin, joka voisi simuloida ladattujen noppien heittämistä teoreettisesti saavutettavissa olevalla maksimaalisella tehokkuudella. "Vaikka heidän algoritminsa oli optimaalisesti tehokas ajan suhteen", Saad selittää, mikä tarkoittaa, että kirjaimellisesti mikään ei voisi olla nopeampaa, "se on tehoton näiden tietojen tallentamiseen tarvittavan tilan tai tietokoneen muistin suhteen." Itse asiassa tarvittavan muistin määrä kasvaa eksponentiaalisesti, riippuen nopan sivujen määrästä ja muista tekijöistä. Tämä tekee Knuth-Yaon menetelmästä epäkäytännöllisen, hän sanoo, lukuun ottamatta erityistapauksia, huolimatta sen teoreettisesta merkityksestä.

FLDR on suunniteltu lisäämään käytettävyyttä. "Olemme melkein yhtä aikaa tehokkaita", Saad sanoo, "mutta suuruusluokkaa parempia muistin tehokkuuden kannalta." FLDR voi käyttää jopa 10,000 1.5 kertaa vähemmän muistitilaa kuin Knuth-Yao-lähestymistapa, mutta kestää enintään XNUMX kertaa kauemmin toimintoa kohden.

Toistaiseksi FLDR:n pääkilpailija on Alias-menetelmä, joka on ollut alan hallitseva tekniikka vuosikymmeniä. Teoreettisesti analysoituna Freerin mukaan FLDR:llä on yksi selvä etu Aliaan verrattuna: Se käyttää tehokkaammin satunnaista lähdettä - "kolikonheittoja" jatkaakseen tällä metaforalla - kuin Alias. Tietyissä tapauksissa FLDR on lisäksi nopeampi kuin Alias ​​luodessaan ladattujen noppien heittoja.

FLDR on tietysti vielä aivan uusi, eikä sitä ole vielä käytetty laajalti. Mutta sen kehittäjät miettivät jo tapoja parantaa sen tehokkuutta sekä ohjelmisto- että laitteistosuunnittelun avulla. Heillä on myös erityisiä sovelluksia mielessään yleisen, jatkuvasti läsnä olevan satunnaislukujen tarpeen lisäksi. Mansinghka ehdottaa, että FLDR voi auttaa eniten tehostamalla niin sanottuja Monte Carlo -simulaatioita ja Monte Carlo -päättelytekniikoita. Aivan kuten FLDR käyttää kolikoiden heittämistä simuloidakseen monimutkaisempaa painotettujen, monipuolisten noppien heittoa, Monte Carlo -simulaatiot käyttävät nopanheittoa monimutkaisempien satunnaislukumallien luomiseen. 

Esimerkiksi Yhdistyneet Kansakunnat ajaa seismisen toiminnan simulaatioita, jotka osoittavat, milloin ja missä maanjäristyksiä, vapinaa tai ydinkokeita tapahtuu maapallolla. Yhdistyneet Kansakunnat tekee myös Monte Carlo -päätelmiä: suorittaa satunnaisia ​​simulaatioita, jotka luovat mahdollisia selityksiä todellisille seismisille tiedoille. Tämä toimii suorittamalla toinen sarja Monte Carlo -simulaatioita, joissa testataan satunnaisesti vaihtoehtoisia parametreja taustalla olevalle seismiselle simulaatiolle löytääkseen parametriarvot, jotka todennäköisimmin toistavat havaitut tiedot. Nämä parametrit sisältävät tietoa siitä, milloin ja missä maanjäristyksiä ja ydinkokeita on saatettu todella tapahtua. 

"Monte Carlo -päättely voi vaatia satoja tuhansia kertoja enemmän satunnaislukuja kuin Monte Carlo -simulaatiot", Mansinghka sanoo. ”Se on yksi suuri pullonkaula, jossa FLDR voisi todella auttaa. Monte Carlo -simulaatiot ja päättelyalgoritmit ovat myös keskeisiä todennäköisyyspohjaisessa ohjelmoinnissa, joka on tekoälyn nouseva alue, jolla on laajat sovellukset. 

Ryan Rifkin, Googlen tutkimusjohtaja, näkee FLDR:lle suuria mahdollisuuksia tässä suhteessa. "Monte Carlon päättelyalgoritmit ovat keskeisiä nykyaikaisessa tekoälytekniikassa… ja laajamittaisessa tilastollisessa mallintamisessa", sanoo Rifkin, joka ei ollut mukana tutkimuksessa. "FLDR on erittäin lupaava kehitystyö, joka voi johtaa tapoihin nopeuttaa satunnaislukujen luomisen peruselementtejä ja saattaa auttaa Googlea tekemään Monte Carlo -päätelmästä huomattavasti nopeamman ja energiatehokkaamman."

Valoisalta vaikuttavasta tulevaisuudestaan ​​huolimatta FLDR ei melkein tullut ilmi. Vihjeitä siitä tuli ensimmäisen kerran esille a edellinen paperi samat neljä MIT-tutkijaa julkaisivat tammikuussa pidetyssä symposiumissa, jossa esiteltiin erillinen algoritmi. Tuossa työssä kirjoittajat osoittivat, että jos tietokoneohjelmalle varattaisiin ennalta määrätty määrä muistia ladattujen noppien heiton simuloimiseksi, heidän algoritminsa voisi määrittää mahdollisen "virheen" vähimmäismäärän - eli kuinka lähellä kohtaamista ollaan. määrätyt todennäköisyydet nopan molemmille puolille. 

Jos muistia ei rajoita etukäteen, virhe voidaan pienentää nollaan, mutta Saad huomasi nollavirheen muunnelman, joka käytti huomattavasti vähemmän muistia ja oli lähes yhtä nopea. Aluksi hän ajatteli, että tulos saattoi olla liian vähäpätöinen vaivautuakseen. Mutta hän mainitsi sen Freerille, joka vakuutti Saadille, että tämä tie oli jatkamisen arvoinen. FLDR, joka on samassa suhteessa virheetön, syntyi noista vaatimattomista lähtökohdista, ja sillä on nyt mahdollisuus tulla johtavaksi teknologiaksi satunnaislukujen luomisen alalla. Se ei ole vähäpätöinen asia, kun otetaan huomioon, että elämme maailmassa, jota hallitsevat suurelta osin satunnaiset prosessit - periaate, joka koskee galaksien jakautumista universumissa, samoin kuin hengästyneen roskapelin tuloksia.