Ini latihan yang tampak sederhana: Siapkan nomor telepon acak. Tujuh digit secara berurutan, dipilih agar setiap digit memiliki kemungkinan yang sama, dan agar pilihan satu digit Anda tidak memengaruhi digit berikutnya. Kemungkinannya, Anda tidak bisa. (Tapi jangan percaya kata-kata saya: Studi yang berasal dari tahun 1950-an mengungkapkan betapa kita secara matematis nonrandom.
Jangan masuk ke hati. Komputer juga tidak menghasilkan keacakan dengan baik. Mereka tidak seharusnya: Perangkat lunak dan perangkat keras komputer dijalankan dengan logika Boolean, bukan probabilitas. “Budaya komputasi berpusat pada determinisme,” kata Vikash Mansinghka, yang menjalankan Proyek Komputasi Probabilistik di Massachusetts Institute of Technology, “dan itu muncul di hampir setiap level.”
Tetapi ilmuwan komputer menginginkan program yang dapat menangani keacakan karena terkadang itulah yang dibutuhkan oleh masalah. Selama bertahun-tahun, beberapa telah mengembangkan algoritme baru yang ramping yang, meskipun tidak menghasilkan angka acak sendiri, menawarkan cara yang cerdas dan efisien untuk menggunakan dan memanipulasi keacakan. Salah satu upaya terbaru datang dari grup Mansinghka di MIT, yang akan mempresentasikan algoritme yang disebut Fast Loaded Dice Roller, atau FLDR, di Konferensi Internasional online tentang Kecerdasan Buatan dan Statistik Agustus ini.
Sederhananya, FLDR menggunakan urutan acak untuk mensimulasikan dengan sempurna pengguliran dadu yang dimuat. (Atau koin tertimbang, atau dek kartu yang dicurangi.) “Ini menunjukkan bagaimana mengubah lemparan koin yang acak sempurna menjadi lemparan koin yang bias,” kata ahli matematika Peter Bierhorst dari Universitas New Orleans. Bierhorst tidak berkontribusi pada penelitian tetapi menggambarkan premis di balik kesuksesan FLDR sebagai “menarik”.
FLDR tidak akan memberi Anda keunggulan dalam Monopoli atau meningkatkan peluang Anda di meja dadu Las Vegas. Tetapi penciptanya mengatakan itu menyarankan cara untuk mengintegrasikan bilangan acak ke dalam perangkat lunak dan perangkat keras, yang dibangun untuk menjadi deterministik. Memasukkan ketidakpastian semacam ini akan membantu mesin membuat prediksi yang mirip manusia dan lebih baik mensimulasikan fenomena yang bergantung pada probabilitas seperti iklim atau pasar keuangan.
Keacakan adalah konsep yang lebih rumit dari yang terlihat. Dalam urutan angka acak, yang tidak memiliki pola yang terlihat, setiap digit memiliki kemungkinan kemunculan yang sama. Pi itu sendiri bukan bilangan acak, misalnya, tetapi digit pi diyakini acak dengan cara ini (yang digambarkan oleh ahli matematika sebagai “normal”): Setiap bilangan bulat dari 0 sampai 9 muncul dalam jumlah yang hampir sama.
Meskipun Anda dapat menemukan “generator nomor acak” di Google, keacakan murni bukanlah yang Anda dapatkan. Prosesor, mesin telusur, dan pembuat sandi saat ini menggunakan pendekatan “pseudorandom” yang cukup mirip untuk sebagian besar tujuan. Urutan tersebut dibuat berdasarkan rumus yang rumit, tetapi secara teori jika Anda mengetahui rumusnya, Anda mungkin dapat memprediksi urutannya.
Para ilmuwan telah mencoba membuat keacakan yang sebenarnya menjadi mesin selama setidaknya 80 tahun. (Sebelumnya, nomor acak berasal dari standby lama seperti dadu yang digulung, bola bernomor yang diambil dari tas yang dicampur dengan baik atau latihan mekanis lainnya. Pada tahun 1927, seorang ahli statistik mengambil sampel data sensus untuk menghasilkan tabel yang terdiri dari 40.000 digit acak.)
Sumber utama nomor acak adalah mesin fisik. Mesin penghasil angka acak pertama adalah gagasan ahli statistik Inggris Maurice George Kendall dan Bernard Babington Smith, yang mendeskripsikannya pada tahun 1938. Mesin itu ditempatkan di ruangan gelap, di mana ia memutar sebuah cakram yang dibagi menjadi 10 bagian berbentuk baji yang sama besar. berlabel 0 hingga 9. Saat seseorang mengetuk tombol dengan interval yang tidak menentu, lampu kilat atau percikan neon singkat akan menerangi disk sehingga tampak membeku, dengan hanya satu nomor yang terlihat. Mesin yang lebih baru, yang disebut Ernie, menggunakan gangguan sinyal pada tabung neon; mulai tahun 1957 memilih nomor pemenang dalam lotere Inggris.
Baru-baru ini, untuk urutan yang benar-benar acak, Bierhorst mengatakan, ilmuwan komputer harus melihat fenomena alam seperti radiasi latar belakang kosmik atau perilaku sistem kuantum yang tidak dapat diprediksi. “Ada proses acak di alam yang dapat dimanfaatkan yang benar-benar tidak dapat diprediksi,” katanya. Elektron yang mengelak ke kiri atau ke kanan bahkan tidak tahu apa yang akan dilakukannya sebelumnya.
Tapi keacakan hanya bisa membawa Anda sejauh ini. Pada akhir 1940-an, fisikawan mulai menghasilkan bilangan acak agar sesuai dengan distribusi probabilitas tertentu. Alat semacam itu – versi teoritis dari penggulungan dadu yang dimuat – dapat digunakan secara lebih akurat untuk memodelkan situasi dunia nyata, seperti arus lalu lintas atau reaksi kimia. Pada tahun 1976, ilmuwan komputer perintis Donald Knuth dan Andrew Yao memperkenalkan algoritme yang dapat menggunakan rangkaian bilangan acak untuk menghasilkan sampel acak dari berbagai hasil pembobotan apa pun. “Itu adalah algoritme paling efisien waktu yang pernah ada,” kata Feras Saad, seorang mahasiswa doktoral di lab Mansinghka yang memimpin pekerjaan baru di FLDR.
Sayangnya, Saad mengatakan bahwa algoritme membuat trade-off yang diketahui oleh ilmuwan komputer: Banyak aplikasi yang berjalan dengan cepat menggunakan banyak memori, dan aplikasi yang menggunakan sedikit memori dapat memiliki waktu proses yang lama. Algoritme Knuth dan Yao termasuk dalam kategori pertama, membuatnya elegan tetapi terlalu intensif memori untuk penggunaan praktis apa pun.
Tapi musim semi lalu, Saad menemukan solusi yang cerdas. Dia menyadari bahwa ketika bobot pada dadu ditambahkan hingga pangkat 2, algoritme tersebut efisien dalam waktu dan memori. Jadi untuk dadu bersisi enam, bayangkan kemungkinan menggulung angka 1 hingga 6, masing-masing, diberi bobot 1, 2, 3, 4, 5 dan 1. Itu berarti probabilitas untuk menggulung angka 1, misalnya, adalah 1/16, dan kemungkinan melempar 2 adalah 2/16. Karena bobot dijumlahkan hingga pangkat 2 – 16 adalah 24 – algoritme untuk sistem ini efisien dalam waktu dan memori.
Tetapi bayangkan bahwa bobotnya adalah 1, 2, 3, 2, 4, 2, yang berjumlah 14. Karena 14 bukanlah pangkat 2, algoritme Knuth-Yao memerlukan lebih banyak memori secara signifikan. Saad menyadari bahwa dia dapat memasukkan bobot tambahan sehingga bobot tersebut selalu dijumlahkan menjadi pangkat 2. Dalam hal ini, ia hanya akan menambahkan wajah hipotetis lain – satu dengan bobot 2 – sehingga bobotnya bertambah menjadi 16. Jika algoritme memilih satu dari wajah aslinya, nilainya telah direkam. Jika memilih wajah ekstra, nilainya akan dibuang, dan algoritme dijalankan kembali.
Ini adalah kunci efisiensi FLDR, menjadikannya alat yang ampuh dalam simulasi: Jumlah memori ekstra yang diperlukan untuk gulungan tambahan minimal dibandingkan dengan memori besar yang biasanya dibutuhkan dalam aslinya.
FLDR makes the Knuth-Yao algorithm efficient and suggests ways to improve a wide swath of applications. Climate change simulations, crop yield predictions, particle behavior simulations, financial market models and even the detecting of underground detonations of nuclear weapons depend on random numbers in weighted probability distributions. Random numbers also form the backbone of cryptography schemes that protect data sent over the internet.
Mansinghka says FLDR may also help researchers find ways to integrate probability into computer processors — the focus of his lab’s work at MIT. The algorithm could help inform the design of software libraries and new hardware architectures that can generate random numbers and use them in efficient ways. That would be a dramatic departure from the deterministic Boolean machines we’re used to.