Độ Ngẫu Nhiên Của Số Ngẫu Nhiên Đến Đâu?
Giống như một tri thức phổ thông, mỗi lập trình viên khi mới học lập trình đều được thầy cô nhấn mạnh: Hàm số ngẫu nhiên trong ngôn ngữ lập trình thực chất chỉ tạo ra “số giả ngẫu nhiên”. Chúng ẩn chứa quy luật nội tại, chỉ có thể mô phỏng gần đúng các sự kiện ngẫu nhiên trong thế giới thực. Tiếp đó, chúng ta sẽ được giới thiệu khái niệm về “hạt giống ngẫu nhiên” - sử dụng các đại lượng vật lý biến đổi thất thường làm đầu vào như thời gian hệ thống, khoảng cách giữa các lần gõ phím, quỹ đạo di chuyển chuột, hay thậm chí cả mã lỗi hệ thống…
Là một chuyên gia thiết kế số liệu game, ngoài các phép tính cơ bản, khái niệm toán học thường xuyên sử dụng nhất chính là số ngẫu nhiên. Một nhà thiết kế giàu kinh nghiệm có thể được đồng nghiệp đi trước cảnh báo về độ tin cậy hạn chế của số ngẫu nhiên máy tính; hoặc họ từng học qua lập trình. Nếu dự án game may mắn hơn, người đảm nhiệm vị trí này là một người say mê toán học từng đọc qua các tác phẩm kinh điển như “Nghệ thuật lập trình máy tính”, lúc đó mọi chuyện sẽ tốt đẹp hơn nhiều. Đáng tiếc trong đa phần trường hợp, các nhà thiết kế thường bỏ qua chi tiết kỹ thuật phía sau số ngẫu nhiên, cũng chẳng mấy quan tâm đến việc “giả” này thực sự “giả” đến mức nào.
Vài ngày trước, có nhân viên kiểm thử phàn nàn rằng một số tỷ lệ trong game của chúng tôi có biểu hiện kỳ kỳ, dường như không khớp với tài liệu mô tả. Tình huống này không hiếm gặp - game thủ khắp nơi cũng thường xuyên tranh luận về độ ngẫu nhiên của hệ thống. Người thiện chí đổ lỗi cho “vận may cá nhân”, kẻ hoài nghi lại cáo buộc hệ thống gian lận. Phía sau hậu trường, các kỹ sư và nhà thiết kế số liệu biết rõ nỗi khổ tâm này.
Nhân dịp này, tôi xin chia sẻ một số kiến thức toán học cơ bản, đồng thời ghi lại những điều học được từ sách vở cuối tuần. Vì phần lớn các nhà thiết kế game tôi từng tiếp xúc có trình độ toán học không cao lắm (kể cả bản thân tôi vốn đã yếu toán), bài viết sẽ tránh dùng công thức, chỉ trình bày các nguyên lý phổ thông. Nếu có đề cập định lý toán học, tôi cũng sẽ bỏ qua phần chứng minh.
Lấy ví dụ từ trò tung đồng xu: Nếu đồng xu hoàn hảo, mỗi lần tung sẽ có 50% xác suất xuất hiện mặt ngửa và 50% mặt sấp.
Lưu ý cho độc giả đang nghĩ “tôi vừa tung 10 lần toàn mặt ngửa, lần thứ 11 chắc chắn mặt sấp dễ ra hơn”: Theo lý thuyết xác suất, các lần thử nghiệm độc lập không ảnh hưởng lẫn nhau. Dù trước đó ra bao nhiêu mặt ngửa, lần thử kế tiếp vẫn giữ nguyên 50% cơ hội. Tuy nhiên nếu thực tế xảy ra hiện tượng này, tôi sẽ nghi ngờ đồng xu bị làm giả - có thể cả hai mặt đều là mặt ngửa, khi đó lần thứ 11 vẫn có khả năng cao tiếp tục ra mặt ngửa!
Dù không thể dự đoán chính xác từng lần thử nghiệm độc lập, chúng ta lại có thể thống kê ra một giá trị ổn định qua số lần thử nghiệm lớn. Ví dụ, khi tung đồng xu n lần, khi n càng lớn, số lần ra mặt ngửa và mặt sấp sẽ tiến sát nhau.
Tuy nhiên, một điểm thường bị lãng quên: Nếu số lần ra hai mặt bằng nhau tuyệt đối sau hàng nghìn thử nghiệm lại là điều cực kỳ hiếm gặp. Chẳng hạn, tung 10.000 lần mà đúng 5.000 mặt ngửa xảy ra ít hơn cả khả năng trúng giải nhỏ trong xổ số.
Bổ sung thú vị: Trong 10.000 lần tung thử nghiệm, khả năng xuất hiện đúng 5.000 mặt ngửa vẫn lớn hơn các khả năng khác (5.001, 4.999… thậm chí 0 lần mặt ngửa), nhưng xác suất tuyệt đối vẫn không cao (khoảng vài phần trăm).
Trước đây tôi từng viết một bài blog về thuật toán xáo bài bằng phương pháp hoán đổi, trong đó trích dẫn một nghiên cứu chỉ ra rằng:
“Khi N ≥ 18, phương pháp xáo bài này lại khiến hoán vị đồng nhất (identity permutation - vị trí bài không thay đổi) trở thành kết quả dễ xảy ra nhất.”
Cần hiểu rõ: “Xác suất cao nhất” không đồng nghĩa với “dễ xảy ra”. Giống như việc tung 10.000 lần mà ra đúng 5.000 mặt ngửa cũng khó khăn như vậy.
Làm thế nào để kiểm tra một máy phát số phân bố đều có thực sự ngẫu nhiên? Chỉ dựa vào phân bố số liệu là chưa đủ. Hãy cùng khám phá kiểm định Chi-bình phương (χ²) - công cụ thống kê nổi tiếng nhất.
Ví dụ cụ thể với xúc xắc 6 mặt: Nếu xúc xắc cân đối, xác suất mỗi mặt từ 1-6 đều là 1/6. Giả sử chúng ta mô phỏng bằng hàm random(1,6), làm thế nào kiểm tra chất lượng số ngẫu nhiên?
Tiến hành n lần thử nghiệm (n lớn, ví dụ 10.000 lần), thống kê số lần xuất hiện từng mặt: Y1-Y6. Trong tình huống lý tưởng, mỗi Yx đều gần bằng p = n/6.
Tính giá trị V theo công thức:
|
|
Rút gọn: V = (6/n)(Y1² + Y2² + … + Y6²) - n
Giá trị V này sẽ phản ánh chất lượng ngẫu nhiên: V quá lớn nghĩa là xúc xắc bị lệch về một số mặt; V quá nhỏ chứng tỏ chuỗi ngẫu nhiên có quy luật ẩn. Với xúc xắc “thực thụ”, V sẽ dao động trong khoảng nhất định.
Theo lý thuyết, nếu dùng số ngẫu nhiên thực sự:
- 1% khả năng V < 0.5543
- 5% khả năng V < 1.1455
- 25% khả năng V < 2.675
- 50% khả năng V < 4.351
- 75% khả năng V < 6.626
- 95% khả năng V < 11.07
- 99% khả năng V < 15.09
Tôi đã kiểm tra hàm random trong gcc 3.4.2 bằng cách mô phỏng xúc xắc 5 lần với số lần thử nghiệm lần lượt 2.000; 4.000; 6.000; 8.000;