Số ngẫu nhiên giả là dãy số do máy tính sinh ra bằng một công thức tất định, trông như ngẫu nhiên nhưng thật ra hoàn toàn đoán được nếu biết điểm xuất phát. Điểm xuất phát đó gọi là "hạt giống" (seed): cùng một hạt giống thì luôn ra cùng một dãy số, và vì thế cùng một bộ bài sau khi xáo. Đây vừa là điểm mạnh (lặp lại được, kiểm lỗi được) vừa là điểm yếu (hạt giống quá ít thì số bộ bài có thể xáo ra cũng ít).
Máy tính không biết tung đồng xu
Một chương trình máy tính chạy theo từng lệnh xác định. Cho cùng đầu vào, nó luôn cho cùng đầu ra. Vậy làm sao nó "chọn ngẫu nhiên" một lá bài? Có hai cách:
- Ngẫu nhiên vật lý: đo một hiện tượng khó đoán bên ngoài, như nhiễu nhiệt trong mạch điện, thời điểm gõ phím, chuyển động chuột. Cách này cho ngẫu nhiên thật nhưng chậm và có giới hạn.
- Ngẫu nhiên giả: dùng một công thức biến một con số thành con số tiếp theo, chọn sao cho dãy kết quả vượt qua mọi phép thử thống kê thông thường. Nhanh, rẻ, sinh hàng tỷ số mỗi giây.
Trong thực tế hai cách thường đi đôi: lấy một ít ngẫu nhiên vật lý làm hạt giống, rồi để công thức ngẫu nhiên giả sinh tiếp phần còn lại.
Bộ sinh đầu tiên: bình phương lấy giữa
Khoảng năm 1946, John von Neumann đề xuất một cách rất đơn giản, gọi là phương pháp bình phương lấy giữa. Lấy một số 4 chữ số, bình phương lên được một số 8 chữ số (thêm số 0 phía trước nếu thiếu), lấy 4 chữ số ở giữa làm số tiếp theo.
Chạy tay với hạt giống 1234
- 1234 bình phương = 01 5227 56, lấy giữa ra 5227.
- 5227 bình phương = 27 3215 29, ra 3215.
- 3215 bình phương = 10 3362 25, ra 3362.
- Tiếp theo là 3030, 1809, 2724, 4201, 6484, 0422, 1780…
Trông khá lộn xộn. Nhưng chạy tiếp, sau 57 bước dãy rơi vào số 0 và kẹt ở đó mãi mãi, vì 0 bình phương vẫn là 0. Thử toàn bộ 10 000 hạt giống 4 chữ số, không hạt giống nào đi được quá 111 bước trước khi lặp lại; trung bình chỉ khoảng 44 bước. Rất nhiều hạt giống rơi vào vòng lặp ngắn 6100 → 2100 → 4100 → 8100 → 6100. Von Neumann biết rõ những khuyết điểm này. Ông vẫn dùng nó vì máy tính thời đó rất ít bộ nhớ, và vì phương pháp hỏng theo kiểu dễ nhận ra.
Bộ sinh đồng dư tuyến tính
Năm 1949, nhà toán học Derrick Lehmer đề xuất kiểu bộ sinh dùng phép nhân và chia lấy dư, về sau mở rộng thành bộ sinh đồng dư tuyến tính: số tiếp theo bằng (a × số hiện tại + c), lấy phần dư khi chia cho m. Chọn a, c, m khéo, dãy sẽ đi qua đủ m giá trị trước khi lặp lại.
Ví dụ nhỏ tính tay được
Lấy m = 16, a = 5, c = 3, hạt giống 7. Số tiếp theo là (5 × 7 + 3) chia 16 dư 6. Rồi (5 × 6 + 3) = 33, dư 1. Cứ thế, dãy ra:
7, 6, 1, 8, 11, 10, 5, 12, 15, 14, 9, 0, 3, 2, 13, 4, rồi lại 7, 6…
Đủ 16 số từ 0 tới 15, mỗi số một lần, rồi lặp. Đó gọi là chu kỳ đầy đủ. Nhưng nhìn kỹ sẽ thấy quy luật: số chẵn và số lẻ luân phiên đều đặn. Bộ sinh đồng dư với m là lũy thừa của 2 luôn có những bit cuối kém ngẫu nhiên như vậy.
Bài học RANDU
Ví dụ nổi tiếng về bộ sinh tồi là RANDU, phổ biến trên máy IBM từ thập niên 1960, với a = 65 539 và m = 2^31. Nếu lấy ba số liên tiếp làm toạ độ một điểm trong không gian, mọi điểm đều nằm trên đúng 15 mặt phẳng song song, thay vì rải đều trong khối lập phương. Nhiều kết quả mô phỏng khoa học thời đó dùng RANDU và phải xem lại. Bài học: một bộ sinh có thể qua phép thử từng số một mà vẫn hỏng khi xét theo nhóm.
Bộ sinh hiện đại và chu kỳ khổng lồ
Năm 1998, Makoto Matsumoto và Takuji Nishimura công bố Mersenne Twister, bộ sinh có chu kỳ 2^19937 − 1, một số có hơn 6 000 chữ số. Nó trở thành bộ sinh mặc định trong nhiều ngôn ngữ lập trình và phần mềm thống kê. Trạng thái bên trong của nó gồm 624 số 32 bit, khoảng 20 000 bit, quá đủ để về lý thuyết đạt tới mọi thứ tự của bộ bài 52 lá, vốn chỉ cần khoảng 226 bit.
Nhưng Mersenne Twister không được thiết kế để chống đoán. Ai quan sát đủ 624 số liên tiếp ở đầu ra là có thể dựng lại trạng thái và đoán mọi số sau đó. Với những việc cần chống gian lận hoặc bảo mật, người ta dùng bộ sinh an toàn mật mã do hệ điều hành cung cấp, được thiết kế để không thể suy ngược.
Hạt giống quyết định có bao nhiêu bộ bài
Đây là chỗ toán của bộ bài gặp toán của máy tính. Giả sử một ứng dụng xáo bài bằng thuật toán Fisher–Yates chuẩn, nhưng hạt giống chỉ là một số 32 bit, chẳng hạn lấy từ đồng hồ. Khi đó chỉ có tối đa 2^32 ≈ 4,3 tỷ dãy số khác nhau, nghĩa là tối đa 4,3 tỷ thứ tự bài khác nhau.
| Độ dài hạt giống | Số hạt giống khả dĩ | Phần của 52! đạt được |
|---|---|---|
| 32 bit | khoảng 4,3 × 10^9 | khoảng 5 × 10^−59 |
| 64 bit | khoảng 1,8 × 10^19 | khoảng 2 × 10^−49 |
| 128 bit | khoảng 3,4 × 10^38 | khoảng 4 × 10^−30 |
| 226 bit trở lên | vượt 52! | có thể phủ mọi thứ tự |
Với hạt giống 32 bit, gần như toàn bộ 52! thứ tự sẽ không bao giờ xuất hiện. Tệ hơn, nếu hạt giống lấy từ số giây của đồng hồ, ai biết gần đúng thời điểm xáo chỉ cần thử vài nghìn khả năng là tìm ra cả bộ bài. Với một ván bài vui giữa bạn bè trên điện thoại, điều đó chẳng sao. Nhưng nó cho thấy "xáo bằng máy" không tự động đồng nghĩa với "xáo hoàn hảo".
Hạt giống có ích thế nào
Tính tất định của hạt giống không chỉ là nhược điểm. Nó là công cụ:
- Cùng bộ bài cho mọi người: nhiều ứng dụng xây bộ bài có thử thách hằng ngày, trong đó mọi người nhận đúng cùng một chuỗi lá. Cách làm là dùng ngày tháng làm hạt giống. Không cần gửi cả bộ bài qua mạng, chỉ cần một con số.
- Chia sẻ một ván hay: gửi cho bạn mã hạt giống, bạn mở ra là thấy y nguyên bản đồ, bộ bài, thứ tự rút.
- Tìm lỗi phần mềm: lỗi chỉ xảy ra "thỉnh thoảng" là ác mộng của lập trình viên. Ghi lại hạt giống, lỗi xảy ra lần nào cũng tái hiện được.
- Khoa học lặp lại được: bài báo khoa học dùng mô phỏng thường ghi hạt giống để người khác chạy lại ra đúng kết quả.
Góc nhìn hôm nay: tự thử và đọc thêm
- Chạy tay phương pháp bình phương lấy giữa với hạt giống của riêng bạn, chẳng hạn bốn số cuối năm sinh, cho tới khi lặp. Đếm số bước.
- Dựng bộ sinh đồng dư với m = 16, thử các giá trị a khác nhau. Bạn sẽ thấy a = 5 cho đủ 16 số, còn a = 4 thì kẹt rất nhanh.
- Trong bảng tính, hàm sinh số ngẫu nhiên thường không cho nhập hạt giống; trong các ngôn ngữ lập trình thì có. Đặt cùng một hạt giống hai lần, xáo cùng một danh sách, kiểm chứng kết quả giống nhau.
Tài liệu kinh điển là chương 3 tập 2 bộ The Art of Computer Programming của Donald Knuth, trình bày cả bộ sinh đồng dư lẫn các phép thử thống kê. Bài báo gốc về Mersenne Twister năm 1998 đăng trên ACM Transactions on Modeling and Computer Simulation.
Câu hỏi thường gặp
Số ngẫu nhiên giả là gì?
Là dãy số do một công thức tất định sinh ra, trông như ngẫu nhiên và qua được các phép thử thống kê, nhưng hoàn toàn xác định khi biết hạt giống. Máy tính dùng nó vì nhanh và lặp lại được.
Seed (hạt giống) trong máy tính là gì?
Là con số khởi đầu của bộ sinh số ngẫu nhiên giả. Cùng hạt giống thì cùng dãy số, nên cùng một bộ bài sau khi xáo. Ứng dụng dùng nó để cho mọi người cùng một thử thách hoặc để tái hiện lỗi.
Máy tính xáo bài có ngẫu nhiên thật không?
Tuỳ bộ sinh số. Thuật toán xáo đúng mà hạt giống chỉ 32 bit thì chỉ đạt khoảng 4,3 tỷ thứ tự trong số 52! ≈ 8 × 10^67. Muốn phủ được mọi thứ tự, trạng thái bộ sinh phải lớn hơn khoảng 226 bit.
Mersenne Twister là gì?
Là bộ sinh số ngẫu nhiên giả do Makoto Matsumoto và Takuji Nishimura công bố năm 1998, có chu kỳ 2^19937 − 1. Nó rất phổ biến trong phần mềm khoa học nhưng không an toàn về mật mã vì có thể đoán được từ 624 số đầu ra liên tiếp.
Phương pháp bình phương lấy giữa của von Neumann hỏng ở đâu?
Dãy số nhanh chóng rơi vào vòng lặp ngắn hoặc kẹt ở 0. Với số 4 chữ số, không hạt giống nào đi quá 111 bước trước khi lặp, trung bình chỉ khoảng 44 bước.
