Tính xem mặt ngửa sẽ xuất hiện bao nhiêu lần khi tung đồng xu một nghìn lần không phải là việc khó. Nhưng với những bài toán có quá nhiều khả năng, chẳng hạn xác suất thắng trò chơi bài một người dùng 52 lá bài, việc giải bằng công thức lại khiến ta lúng túng. Trong những trường hợp này, thay vì từ bỏ việc tính toán, có một cách là trực tiếp thử nhiều lần rồi đếm kết quả. Đó chính là “phương pháp Monte Carlo (Monte Carlo Method)”.
Nói một cách đơn giản, phương pháp Monte Carlo là “cách tính ước lượng đáp án bằng cách lặp lại rất nhiều phép thử ngẫu nhiên, sau đó tổng hợp kết quả và lấy trung bình”. Nền tảng của phương pháp này là ý tưởng rằng dù không biết công thức chính xác, nếu tích lũy đủ nhiều kết quả ngẫu nhiên thì ta vẫn có thể tiến gần đến đáp án thực.
Trong tài liệu này, chúng ta sẽ lần lượt tìm hiểu bối cảnh ra đời của phương pháp Monte Carlo, nguyên lý hoạt động, các ví dụ tiêu biểu, những lĩnh vực ứng dụng hiện nay và các điểm cần lưu ý.
Cách tính gom góp sự ngẫu nhiên để tìm lời giải
Phương pháp Monte Carlo ra đời như thế nào?
Năm 1946, nhà toán học gốc Ba Lan Stanisław Ulam nảy ra một thắc mắc khi chơi bài một người trong thời gian hồi phục sau một trận ốm. Ông tự hỏi xác suất thắng trò chơi này là bao nhiêu. Mệt mỏi vì cố tính toán bằng cách xét các khả năng, ông nghĩ: “Liệu trực tiếp chơi khoảng một trăm lần rồi đếm số lần thắng có thực tế hơn không?”.
Ulam kể ý tưởng này cho John von Neumann, người cùng làm việc với ông tại Phòng thí nghiệm Los Alamos ở Mỹ. Hai người quyết định áp dụng phương pháp này vào bài toán khuếch tán neutron chưa giải được khi đó. Vì nghiên cứu được giữ bí mật nên cần có mật danh; đồng nghiệp Nicholas Metropolis đã lấy tên từ sòng bạc Monte Carlo ở Monaco, nơi chú của Ulam thường vay tiền người thân để đến đánh bạc. Vào mùa xuân năm 1948, việc tính toán tự động lần đầu tiên được thực hiện trên máy tính điện tử đời đầu ENIAC.
Nguyên lý hoạt động qua 4 bước của phương pháp Monte Carlo
Dù chi tiết ở từng cách thực hiện có khác nhau, phương pháp Monte Carlo nhìn chung đều tuân theo một quy trình giống nhau.
(1) Xác định phạm vi có thể xảy ra
Trước hết, xác định phạm vi mà các giá trị đầu vào có thể nằm trong đó để tìm lời giải. Chẳng hạn, đây là bước xác định các biến ảnh hưởng đến kết quả, như lượng hàng bán ra, giá nguyên liệu và thời tiết, cùng phạm vi của chúng.
(2) Chọn ngẫu nhiên các giá trị
Chọn ngẫu nhiên các giá trị đầu vào theo xác suất trong phạm vi đã xác định. Ngày nay, người ta dùng số ngẫu nhiên do máy tính tạo ra; nếu việc chọn không đồng đều, kết quả có thể sai lệch rất lớn.
(3) Tính toán từng lần
Đưa các giá trị đã chọn vào và tính kết quả theo cách đã định. Lặp lại quá trình này hàng nghìn, hàng triệu lần.
(4) Tổng hợp kết quả
Tổng hợp tất cả kết quả để tính trung bình hoặc xác định phân phối. Theo luật số lớn, số lần thử càng nhiều thì giá trị trung bình càng tiến gần đến giá trị thực. Ưu điểm lớn là ngoài việc thu được một giá trị trung bình, ta còn có thể xem kết quả phân bố như thế nào, chẳng hạn “xác suất bị thua lỗ là bao nhiêu phần trăm”.
Hiểu phương pháp Monte Carlo qua những ví dụ đơn giản
Ví dụ dễ hiểu nhất về phương pháp Monte Carlo là tính số pi.
[Ví dụ 1] Rải điểm để tính số pi
Vẽ một phần tư hình tròn có bán kính 1 bên trong hình vuông có cạnh 1. Tỷ lệ giữa hai diện tích bằng số pi chia cho 4. Sau đó, rải các điểm ngẫu nhiên và đồng đều trên hình vuông, rồi đếm tỷ lệ điểm nằm trong một phần tư hình tròn. Nhân tỷ lệ này với 4 sẽ cho giá trị gần với số pi; càng rải nhiều điểm, giá trị càng tiến gần đến 3.14. Khi có khoảng 100 điểm, kết quả dễ dao động như 3.0 hay 3.3, nhưng khi vượt quá hàng trăm nghìn điểm, kết quả thường đúng đến hai chữ số sau dấu phẩy hơn. Như vậy, ta đã tính được số pi chỉ bằng cách đếm điểm mà không cần tính toán phức tạp.
[Ví dụ 2] Thí nghiệm thả kim
Ý tưởng tương tự đã xuất hiện từ rất lâu trước đó. Vào thế kỷ 18, nhà tự nhiên học người Pháp Comte de Buffon đã tính xác suất một chiếc kim cắt một đường kẻ khi được thả xuống mặt sàn có các đường thẳng song song. Vì xác suất này có chứa số pi, ta có thể ước lượng số pi bằng cách thả kim vô số lần rồi đếm số lần kim cắt đường kẻ. Bài toán “kim Buffon (Buffon's Needle)” này được xem là một dạng sơ khai của phương pháp Monte Carlo.
Ứng dụng và giới hạn của phương pháp Monte Carlo
Phương pháp Monte Carlo đặc biệt phát huy hiệu quả trong những bài toán có nhiều biến và mức độ bất định cao. Khi số biến tăng lên hàng chục, hàng trăm, việc tính toán bằng cách xét từng khả năng nhanh chóng trở nên bất khả thi, trong khi cách lấy mẫu ngẫu nhiên vẫn có thể áp dụng theo cùng một cách bất kể số lượng biến.
- Tài chính (Finance): Tạo ra vô số quỹ đạo biến động có thể xảy ra của giá cổ phiếu và lãi suất để đánh giá rủi ro đầu tư và giá quyền chọn.
- Dự báo thời tiết (Weather Forecasting): Là nền tảng của dự báo tổ hợp, trong đó nhiều dự báo với điều kiện ban đầu thay đổi đôi chút được chạy đồng thời.
- Đồ họa máy tính (Computer Graphics): Dò ngẫu nhiên các đường đi của ánh sáng để dựng những cảnh chân thực như ảnh chụp.
- Trí tuệ nhân tạo chơi cờ vây (Game AI): Dùng tìm kiếm cây Monte Carlo để chơi vô số ván cờ giả lập và chọn nước đi tốt.
- Tìm kiếm trên biển (Search and Rescue): Lực lượng Tuần duyên Mỹ tính đến gió và dòng biển để tạo ra hàng nghìn vị trí có thể có của tàu mất tích, từ đó xác định khu vực tìm kiếm.
Tuy nhiên, những giới hạn cũng rất rõ ràng. Vì sai số giảm theo tỷ lệ nghịch với căn bậc hai của số lần thử, muốn giảm sai số xuống một nửa thì phải tăng số lần thử lên gấp bốn. Nếu mỗi lần tính toán đều tốn nhiều tài nguyên, quá trình có thể mất rất nhiều thời gian. Ngoài ra, nếu xác định sai phạm vi hoặc xác suất của các giá trị đầu vào, dù lặp lại bao nhiêu lần, ta cũng chỉ tiến gần đến một đáp án sai.
Phương pháp Monte Carlo cho thấy rằng khi không thể tìm ngay đáp án đúng, việc tích lũy đủ nhiều kết quả ngẫu nhiên có thể giúp ta tiến gần đến một đáp án đáng tin cậy. Một thắc mắc nhỏ bắt đầu từ trò chơi bài đã làm thay đổi cả vật lý hạt nhân, tài chính và trí tuệ nhân tạo.
Không dừng lại chỉ vì thiếu một công thức hoàn hảo, mà trực tiếp thử nghiệm vô số khả năng: đó chính là bước đầu tiên của sự sáng suốt để đưa ra những phán đoán tốt hơn trong một thế giới bất định.
