Công bố thuật toán học sâu mới giúp giải quyết khối Rubik lập phương
Khối Rubik lập phương được phát minh bởi nhà điêu khắc và kiến trúc sư người Hungary Erno Rubik nằm 1974. Nhóm các nhà nghiên cứu của UC Irvine đã phát triển thuật toán có khả năng giải khối Rubik mà không đến sự hỗ trợ của con người. Đây là một bước tiến của học sâu tăng cường (DRL) – là sự kết hợp của học sâu và Monte Carlo Tree Search (MCTS). Kết quả nghiên cứu đã được công bố trong bài báo “Solving the Rubik’s Cube Without Human Knowledge” xuất bản trên arXiv.
“Các thuật toán của chúng tôi có thể giải quyết 100% các khối ngẫu nhiên trong khi đạt được độ phân giải trung bình 30 di chuyển – nhỏ hơn hoặc bằng các giải pháp sử dụng kiến thức của con người” theo kết luận của bài báo.
Khối Rubik lập phương có một không gian trạng thái lớn, với khoảng 4.3 × 10^19 trạng thái. Rubik đã dành một tháng để tìm ra thuật toán đầu tiên để giải quyết khối lập phương. “Kể từ đó, Cube của Rubik đã trở nên phổ biến trên toàn thế giới và nhiều thuật toán định hướng con người để giải quyết nó đã được phát hiện. Các thuật toán này rất đơn giản để ghi nhớ và dạy cho con người cách giải quyết khối lập phương theo cách có cấu trúc, từng bước”. Tuy nhiên, việc giải bài toán này bằng máy là vô cùng phức tạp vì không gian trạng thái lớn và số lượng trạng thái phần thưởng rất nhỏ. Dưới đây là mô tả ngắn gọn về cách các nhà nghiên cứu tấn công vấn đề được trích từ bài báo:
To overcome a sparse reward in a model-based environment with a large state space, we introduce Autodidactic Iteration (ADI): an algorithm inspired by policy iteration for training a joint value and policy network. ADI trains the value function through an iterative supervised learning process. In each iteration, the inputs to the neural network are created by starting from the goal state and randomly taking actions. The targets seek to estimate the optimal value function by performing a breadth-first search from each input state and using the current network to estimate the value of each of the leaves in the tree. Updated value estimates for the root nodes are obtained by recursively backing up the values for each node using a max operator. The policy network is similarly trained by constructing targets from the move that maximizes the value. After the network is trained, it is combined with MCTS to efficiently solve the Rubik’s Cube.
Mạng đào tạo sử dụng phương pháp ADI vói 2.000.000 lần lặp. Số lượng dữ liệu đào khoảng 8 tỷ trường hợp (bao gồm các trương lặp lại) và được huấn luyện trong 44 giờ. Nhóm nghiên cứu đã sử dụng một máy chủ với Intel Xeon E5-2620 (32 nhân) và 3 GPU NVIDIA Titan XP.
Thông qua nghiên cứu này, nhóm tác giả đã chứng minh mạng học sâu có thể được đào tạo để hiểu các khái niệm toán học. Từ đó, các nhà khoa học có thẻ hiểu rõ hơn và tối ưu phương pháp này.
Nguồn: hpcwire