Xây dựng hàm đánh giá caro 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 Như hình trên ta thấy là trạng thái hiện tại của game đang đến lượt đánh của người chơi X đại diện cho MAX. Ta tạm quy định giá trị MAX lúc game thắng cho X = +10 và MIN lúc game thua cho X = -10 và lúc game hòa = 0. Lúc này ở lượt 1, MAX có thể đi được 1 trong 3 nước như hình. Vậy làm sao để chọn 1 trong 3 nước đó nước nào là tốt nhất để đi. Chúng ta dựa vào giá trị của từng nước để chọn nước tốt nhất, như ở đây 3 node đó thuộc lớp MAX nên chọn giá trị lớn nhất. Chúng ta bắt đầu tìm giá trị của từng node đó. Ở lớp MAX trong lượt 1, thì ta có node 1,2,3 được đánh số từ trái sáng phải như hình. Node 3 chúng ta đã là node lá (X win game ) và có giá trị là +10. Còn 2 node 1,2 thì chưa biết giá trị của nó tại lượt 1 nên chúng ta dựa vào giá trị của các node con để định giá trị và bằng giá trị bé nhất của các node con ở lớp MIN tại lượt 2. Cứ tiếp tục tương tự như vậy đến lúc gặp node lá thì từ node lá đó ta suy ngược lại và ta tính được node 1 có giá trị là -10 và node 2 là 0. Vậy nước đi tốt nhất ở đây là như node 3 có giá trị lớn nhất là +10. 5. Áp dụng vào code
Vậy là chúng ta implement được thuật toán minimax. 6. Thuật toán Minimax với độ sâu Như ở hình này ta cần tìm giá trị lớn nhất của các node con. Mà ta tính được giá trị node 1,2,3 tương ứng là -10, +10, +10. Vậy giá trị ở node 2,3 là bằng nhau = +10. Nên ta đang phân vân giữa 2 node 2,3. Từ đó ta nâng cấp thuật toán minimax với độ sâu depth:
Á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 |