Generasi angka acak yang cepat dan efisien telah lama menjadi tantangan penting. Selama berabad-abad, permainan-permainan kebetulan mengandalkan gulungan dadu, lemparan koin, atau pengocokan kartu untuk membawa keacakan dalam proses. Pada paruh kedua abad ke-20, komputer mulai mengambil alih peran itu, untuk aplikasi dalam kriptografi, statistik, dan kecerdasan buatan, serta untuk berbagai simulasi - iklim, epidemiologi, keuangan, dan sebagainya.

Peneliti MIT sekarang telah mengembangkan algoritma komputer yang mungkin, setidaknya untuk beberapa tugas, menghasilkan angka acak dengan kombinasi terbaik dari kecepatan, akurasi, dan persyaratan memori rendah yang tersedia saat ini. Algoritma, yang disebut Fast Loaded Dice Roller (FLDR), diciptakan oleh mahasiswa pascasarjana MIT Feras Saad, Ilmuwan Riset Cameron Freer, Profesor Martin Rinard, dan Ilmuwan Riset Utama, Vikash Mansinghka, dan akan dipresentasikan minggu depan pada Konferensi Internasional ke-23 tentang Kecerdasan Buatan dan Statistik. 

Sederhananya, FLDR adalah program komputer yang mensimulasikan gulungan dadu untuk menghasilkan bilangan bulat acak. Dadu dapat memiliki sejumlah sisi, dan mereka "dimuat," atau berbobot, untuk membuat beberapa sisi lebih mungkin muncul daripada yang lain. Die yang dimuat masih dapat menghasilkan angka acak - karena orang tidak dapat memprediksi sebelumnya sisi mana yang akan muncul - tetapi keacakan dibatasi untuk memenuhi distribusi probabilitas yang telah ditetapkan. Seseorang mungkin, misalnya, menggunakan dadu yang dimuat untuk mensimulasikan hasil pertandingan bisbol; sementara tim yang unggul lebih cenderung menang, pada hari tertentu kedua tim bisa berakhir di puncak.

Dengan FLDR, dadu “dimuat dengan sempurna”, yang berarti mereka benar-benar mencapai probabilitas yang ditentukan. Sebagai contoh, dengan dadu empat sisi, seseorang dapat mengatur semuanya sehingga angka 1,2,3, dan 4 muncul tepat masing-masing 23 persen, 34 persen, 17 persen, dan 26 persen.

Untuk mensimulasikan gulungan dadu yang dimuat yang memiliki banyak sisi, tim MIT pertama-tama harus menggunakan sumber keacakan yang lebih sederhana - yaitu versi lemparan koin yang terkomputerisasi, menghasilkan 0 atau 1, masing-masing dengan probabilitas 50 persen. Efisiensi metode mereka, kriteria desain utama, tergantung pada berapa kali mereka harus memanfaatkan sumber acak ini - jumlah "lemparan koin," dengan kata lain - untuk mensimulasikan setiap lemparan dadu. 

Dalam makalah penting tahun 1976, para ilmuwan komputer Donald Knuth dan Andrew Yao merancang sebuah algoritma yang dapat mensimulasikan gulungan dadu yang dimuat dengan efisiensi maksimum yang dapat dicapai secara teoritis. "Walaupun algoritme mereka secara optimal efisien sehubungan dengan waktu," Saad menjelaskan, artinya secara harfiah tidak ada yang bisa lebih cepat, "itu tidak efisien dalam hal ruang, atau memori komputer, diperlukan untuk menyimpan informasi itu." Bahkan, jumlah memori yang dibutuhkan tumbuh secara eksponensial, tergantung pada jumlah sisi pada dadu dan faktor lainnya. Itu membuat metode Knuth-Yao tidak praktis, katanya, kecuali untuk kasus-kasus khusus, meskipun penting secara teoritis.

FLDR dirancang untuk utilitas yang lebih besar. "Kami hampir sama efisiennya dengan waktu," kata Saad, "tetapi urutan besarnya lebih baik dalam hal efisiensi memori." FLDR dapat menggunakan ruang penyimpanan memori hingga 10,000 kali lebih sedikit daripada pendekatan Knuth-Yao, sementara mengambil tidak lebih dari 1.5 kali lebih lama per operasi.

Untuk saat ini, pesaing utama FLDR adalah metode Alias, yang telah menjadi teknologi dominan di lapangan selama beberapa dekade. Ketika dianalisis secara teoritis, menurut Freer, FLDR memiliki satu keunggulan jelas atas Alias: Ini membuat penggunaan sumber acak yang lebih efisien - "lemparan koin," untuk melanjutkan metafora itu - daripada Alias. Dalam kasus tertentu, apalagi, FLDR juga lebih cepat daripada Alias ​​dalam menghasilkan gulungan dadu yang dimuat.

FLDR, tentu saja, masih baru dan belum digunakan secara luas. Tetapi pengembangnya sudah memikirkan cara untuk meningkatkan efektivitasnya baik melalui rekayasa perangkat lunak dan perangkat keras. Mereka juga memiliki aplikasi spesifik dalam pikiran, terlepas dari kebutuhan umum, yang selalu ada untuk angka acak. Mansinghka menyarankan, di mana FLDR dapat membantu paling banyak, adalah dengan membuat simulasi yang disebut Monte Carlo dan teknik inferensi Monte Carlo menjadi lebih efisien. Sama seperti FLDR menggunakan koin membalik untuk mensimulasikan gulungan yang lebih rumit dari dadu berbobot banyak sisi, simulasi Monte Carlo menggunakan gulungan dadu untuk menghasilkan pola angka acak yang lebih rumit. 

PBB, misalnya, menjalankan simulasi aktivitas seismik yang menunjukkan kapan dan di mana gempa bumi, getaran, atau uji coba nuklir terjadi di dunia. PBB juga melakukan inferensi Monte Carlo: menjalankan simulasi acak yang menghasilkan kemungkinan penjelasan untuk data seismik aktual. Ini bekerja dengan melakukan seri kedua dari simulasi Monte Carlo, yang secara acak menguji parameter alternatif untuk simulasi seismik yang mendasari untuk menemukan nilai parameter yang paling mungkin untuk mereproduksi data yang diamati. Parameter ini berisi informasi tentang kapan dan di mana gempa bumi dan uji coba nuklir mungkin benar-benar terjadi. 

“Inferensi Monte Carlo dapat membutuhkan ratusan ribu kali angka acak lebih banyak daripada simulasi Monte Carlo,” kata Mansinghka. “Itu adalah satu hambatan besar di mana FLDR benar-benar bisa membantu. Simulasi Monte Carlo dan algoritma inferensi juga merupakan pusat pemrograman probabilistik, area AI yang muncul dengan aplikasi luas. ” 

Ryan Rifkin, Direktur Penelitian di Google, melihat potensi besar untuk FLDR dalam hal ini. "Algoritma inferensi Monte Carlo adalah pusat dari rekayasa AI modern ... dan untuk pemodelan statistik skala besar," kata Rifkin, yang tidak terlibat dalam penelitian ini. "FLDR adalah perkembangan yang sangat menjanjikan yang dapat mengarah pada cara-cara untuk mempercepat blok bangunan mendasar dari generasi angka acak, dan mungkin membantu Google membuat inferensi Monte Carlo secara signifikan lebih cepat dan lebih hemat energi."

Meskipun masa depannya tampak cerah, FLDR hampir tidak terungkap. Petunjuk itu pertama kali muncul dari makalah sebelumnya empat peneliti MIT yang sama diterbitkan pada simposium pada bulan Januari, yang memperkenalkan algoritma terpisah. Dalam karya itu, penulis menunjukkan bahwa jika jumlah memori yang telah ditentukan dialokasikan untuk program komputer untuk mensimulasikan gulungan dadu yang dimuat, algoritme mereka dapat menentukan jumlah minimum "kesalahan" yang mungkin - yaitu, seberapa dekat seseorang dengan rapat probabilitas yang ditentukan untuk setiap sisi dadu. 

Jika seseorang tidak membatasi memori sebelumnya, kesalahan dapat dikurangi menjadi nol, tetapi Saad melihat varian dengan kesalahan nol yang menggunakan memori jauh lebih sedikit dan hampir secepat. Awalnya dia pikir hasilnya mungkin terlalu sepele untuk dipikirkan. Tapi dia menyebutkannya pada Freer yang meyakinkan Saad bahwa jalan ini layak untuk dikejar. FLDR, yang bebas dari kesalahan dalam hal yang sama ini, muncul dari asal-usul yang sederhana itu dan sekarang memiliki peluang untuk menjadi teknologi terkemuka di bidang pembuatan bilangan acak. Itu bukan masalah sepele mengingat bahwa kita hidup di dunia yang diperintah, sebagian besar, dengan proses acak - prinsip yang berlaku untuk distribusi galaksi di alam semesta, serta untuk hasil dari permainan omong kosong yang penuh semangat.