Giải thuật heuristic và bài toán trò chơi năm 2024
Đã đăng vào thg 1 18, 2017 6:29 SA 6 phút đọc Vừa qua mình có làm game dạng như caro và đã làm AI cho nó có dùng thuật toán minimax thấy hay hay nên post lên chia sẻ cho mọi người cùng tham khảo. Bài viết này mình chỉ viết về những cái cơ bản của thuật toán có thể áp dụng cho những game đơn giản dạng này như caro, tictactoe.. Phần mở đầu sơ qua thế là xong. Và bây giờ là bắt đầu nào.
Giờ mình đi vào ví dụ để dễ hiểu như khái niệm ở trên. Game TicTacToe
Vậy là chúng ta implement được thuật toán minimax. 6. Thuật toán Minimax với độ sâu
Áp dụng nâng cấp trên thì ta sẽ có giá trị mới của node 1,2,3 tương ứng là -9,+8,+10 => Max = +10 giá trị của node 3. Vậy node 3 là node cần tìm. 7. Tối ưu thuật toán minimax Đánh giá thuật toán: Giả sử số nhánh của cây game là a. Xét độ sâu depth b thì số nút cần phải tính là a^b. Đây là con số khá lớn. Nên sinh ra thuật toán để tối ưu thuật toán minimax là cắt tỉa Alpha Beta. (Sẽ được update vào các bài sau Và bài viết mình đến đây cũng đã khá dài. Mình xin kết thúc bài này tại đây. All rights reserved |