Alpha Dogs' Tricks: Monte Carlo Algorithm, đọc xong thì hiểu!

Những con chó Alpha: Các thuật toán Monte Carlo, hãy xem và bạn sẽ hiểu!

Vào ngày 9-15 tháng 3 năm nay, một sự kiện lớn đã xảy ra trong thế giới Go khi một cuộc chiến tranh giữa con người và máy móc kéo dài 5 vòng diễn ra tại Seoul, Hàn Quốc. Kết quả của cuộc thi là con người đã thua, và nhà vô địch thế giới Go-go Lee Hye-Soo đã thua 1-4 trước chương trình trí tuệ nhân tạo AlphaGo của Google. Vậy AlphaGo là gì và chìa khóa để chiến thắng ở đâu?

• AlphaGo và thuật toán Monte Carlo

Theo Xinhua, chương trình AlphaGo là một chương trình chơi ván ván người máy đối với con người được phát triển bởi nhóm DeepMind thuộc Google, được người hâm mộ Trung Quốc gọi là ván ván Alpha Shit.

Trong bài viết trước, chúng tôi đã đề cập đến một thuật toán mạng thần kinh mà Google đang phát triển để cho phép máy học tự động, AlphaGo là một sản phẩm tương tự.

Phó chủ tịch Hiệp hội Tự động hóa Trung Quốc, Tổng thư ký Wang Fuyue, nói rằng các lập trình viên không cần phải có kiến thức về trò chơi, chỉ cần hiểu các quy tắc cơ bản của trò chơi. Đằng sau AlphaGo là một nhóm các nhà khoa học máy tính xuất sắc, đúng hơn là các chuyên gia trong lĩnh vực học máy. Các nhà khoa học sử dụng các thuật toán mạng thần kinh để nhập hồ sơ trận đấu của các chuyên gia cờ vua vào máy tính và để máy tính tự thi đấu với chính nó, trong quá trình này liên tục học tập.

Vậy thì chìa khóa để AlphaGo tự học trở thành một thiên tài là gì? Đó là thuật toán Monte Carlo.

Các thuật toán của Monte Carlo là gì?Trong khi đó, các nhà nghiên cứu đã phát hiện ra rằng, một số người sử dụng thuật toán Monte Carlo. Nếu có 1000 quả táo trong giỏ, hãy nhắm mắt mỗi lần để chọn quả táo lớn nhất, bạn có thể chọn không giới hạn số lần. Vì vậy, bạn có thể nhắm mắt và chọn ngẫu nhiên một quả, sau đó chọn ngẫu nhiên một quả so với lần đầu tiên, để lại một quả lớn, và chọn ngẫu nhiên một quả so với lần trước, để lại một quả lớn.

Nói cách khác, thuật toán Monte Carlo là càng có nhiều mẫu thì càng có thể tìm ra giải pháp tốt nhất, nhưng không đảm bảo là tốt nhất, bởi vì nếu có 10.000 quả táo thì chắc chắn bạn sẽ tìm thấy một giải pháp lớn hơn.

Một số người cho rằng nó là một sự thay đổi lớn trong cuộc sống của họ. Theo truyền thống, nếu có một chiếc khóa, có 1000 chìa khóa để lựa chọn, nhưng chỉ có một cái đúng. Vì vậy, mỗi lần ngẫu nhiên lấy một chìa khóa để thử, không mở được, thay đổi một cái khác. Càng nhiều lần thử, cơ hội mở tốt nhất càng lớn, nhưng trước khi mở, những chìa khóa sai đều vô dụng.

Vì vậy, thuật toán Las Vegas là giải pháp tốt nhất có thể, nhưng không thể tìm thấy. Giả sử trong 1000 chìa khóa, không có một khóa nào có thể mở khóa, chìa khóa thực sự là khóa số 1001, nhưng trong mẫu không có thuật toán số 1001, thuật toán Las Vegas không thể tìm thấy chìa khóa mở khóa.

Các thuật toán Monte Carlo của AlphaGoKhó khăn của trò chơi Go là đặc biệt lớn đối với AI, bởi vì có quá nhiều cách chơi Go và máy tính khó phân biệt. Ông nói: "Đầu tiên, khả năng chơi Go là quá nhiều. Mỗi bước của Go có rất nhiều khả năng, người chơi bắt đầu với 19 × 19 = 361 lựa chọn. Một vòng 150 vòng chơi Go có thể xuất hiện tới 10.170 tình huống. Thứ hai, quy tắc quá tinh tế, và một số khả năng chọn Go dựa trên trực giác được hình thành từ kinh nghiệm tích lũy.

AlphaGo không chỉ là một thuật toán Monte Carlo, mà còn là một phiên bản nâng cấp của thuật toán Monte Carlo.

AlphaGo đã hoàn thành cờ vua bằng cách sử dụng thuật toán tìm kiếm cây Monte Carlo và hai mạng lưới thần kinh sâu. Trước khi đối đầu với Lee Si-Soon, Google đã huấn luyện hệ thống thần kinh của AlphaGo bằng gần 30 triệu bước đi của con người đối với con voi để nó có thể dự đoán người chơi chuyên nghiệp của con người sẽ thất bại như thế nào.

Nhiệm vụ của chúng là hợp tác và chọn ra những bước chơi có triển vọng hơn, bỏ qua những trục trặc rõ ràng, để kiểm soát lượng tính toán trong phạm vi mà máy tính có thể thực hiện. Về cơ bản, điều này giống như những gì người chơi chơi chơi.

Theo nhà nghiên cứu của Viện Tự động hóa Viện Khoa học Trung Quốc, Yue Yuenqing, các phần mềm ván cờ truyền thống, thường sử dụng tìm kiếm bạo lực, bao gồm máy tính màu xanh lá cây, nó là xây dựng cây tìm kiếm cho tất cả các kết quả có thể (mỗi kết quả là một quả trên cây), tìm kiếm theo nhu cầu. Phương pháp này cũng có một số khả năng thực hiện trong cờ vua, ván cờ nhảy, ván cờ ván, ván cờ ván, nhưng không thể thực hiện cho Go, bởi vì Go ván 19 đường, và khả năng rơi quá lớn để máy tính không thể xây dựng trái cây này để thực hiện tìm kiếm xuyên suốt. Alpha Go sử dụng một phương pháp rất thông minh, giải quyết vấn đề này một cách hoàn hảo.

Dungach tiếp tục giải thích rằng một trong những đơn vị cơ bản nhất của mạng thần kinh sâu tương tự như các tế bào thần kinh trong não người, với nhiều lớp kết nối giống như mạng thần kinh trong não người. Hai mạng thần kinh của AlphaGo là mạng chiến lược và mạng đánh giá.

Mạng lưới chiến lược của con người chủ yếu được sử dụng để tạo ra các chiến lược rơi xuống. Trong quá trình chơi cờ vua, nó không nghĩ về việc mình nên chơi như thế nào, mà nghĩ về những gì người chơi giỏi của con người sẽ làm. Đó là, nó sẽ dự đoán vị trí của con người tiếp theo dựa trên trạng thái hiện tại của bàn cờ, đưa ra một số kế hoạch khả thi phù hợp nhất với tư duy của con người.

Tuy nhiên, mạng chiến lược không biết mình sẽ chơi tốt hay không, nó chỉ biết liệu nó có giống như con người hay không, khi đó nó cần đánh giá mạng để có thể hoạt động.

Các giá trị này sẽ được phản hồi vào thuật toán tìm kiếm cây Monte Carlo để đưa ra đường đi có tỷ lệ thắng cao nhất bằng cách lặp lại quá trình như trên. Các thuật toán tìm kiếm cây Monte Carlo quyết định rằng mạng chiến lược sẽ chỉ tiếp tục đưa ra ở những nơi có tỷ lệ thắng cao hơn, để loại bỏ một số tuyến đường, không sử dụng một đường dẫn để đi đến màu đen.

AlphaGo sử dụng hai công cụ này để phân tích tình huống và đánh giá ưu điểm và nhược điểm của mỗi chiến lược tiếp theo, giống như người chơi ván cờ sẽ đánh giá tình huống hiện tại và suy luận về tình huống tương lai.

Tuy nhiên, không có nghi ngờ gì rằng thuật toán Monte Carlo là một trong những cốt lõi của AlphaGo.

Hai thí nghiệm nhỏ Cuối cùng, hãy xem hai thí nghiệm nhỏ của thuật toán Monte Carlo.

• 1.计算圆周率pi。

Nguyên tắc: Đầu tiên vẽ một hình vuông, vẽ vòng tròn bên trong, sau đó vẽ một điểm vẽ ngẫu nhiên trong hình vuông, đặt điểm nằm trong vòng tròn là khoảng P, sau đó P = diện tích hình vuông / diện tích hình vuông. P= ((Pi)RR) / ((2R * 2R) = Pi / 4, tức là Pi = 4P

Các bước: 1. Đặt trung tâm của hình tròn ở điểm gốc, làm tròn với bán kính R, thì diện tích 1/4 của hình vuông đầu tiên là PiRR/4 2. Làm cho hình vuông bên ngoài của vòng tròn 1/4, tọa độ là ((0,0) ((0,R) ((R,0) ((R,R), thì diện tích của hình vuông là RR 3. Điểm ngẫu nhiên ((X, Y), làm cho 0 <= X <= R và 0 <= Y <= R, tức là điểm trong hình vuông 4. Bằng công thức XX+YYXác định điểm R nằm trong vòng tròn 1/4. 5. Đặt tất cả các điểm (tức là số lần thử nghiệm) là N, số điểm nằm trong vòng 1/4 (tức là các điểm đáp ứng bước 4) là M,

P = M/N, Pi = 4 * N/M.Hình 1

M_C ((10000) chạy kết quả là 3.1424

• 2.蒙特卡洛模拟求函数极值，可避免陷入局部极值

# Xác định một số ngẫu nhiên trên khoảng [-2,2], tìm y tương ứng của nó và tìm ra giá trị lớn nhất trong đó được coi là giá trị cực lớn của hàm trên [-2,2]Hình 2

Sau 1000 lần mô phỏng, chúng tôi đã tìm thấy một giá trị cực lớn là 185.12292832389875 ((cũng chính xác)

Nhìn vào đây, bạn đã hiểu rồi. Mã có thể viết bằng tay, thật thú vị! Được chuyển từ WeChat