Thuật toán Minimax (AI trong Game) -Nguyễn Công Trình st
Minimax là giải thuật là một thuật toán đệ quy lựa chọn bước đi kế tiếp trong một trò chơi có hai người bằng cách định giá trị cho các Node trên cây trò chơi sau đó tìm Node có giá trị phù hợp để đi bước tiếp theo.
***Vậy đệ quy là gì ?
Trong lập trình, phương thức là tập hợp các lệnh với tham số truyền vào để máy tính thao tác lệnh theo ý muốn của người viết, đệ quy xảy ra khi người viết các phương thức tự gọi (hoạc định nghĩa lại) chính nó.
Xem ví dụ đơn giản sau nhé. Đề bài: Tính lũy tiến từ 0 đến n.
public int sum(int n) {
if (n >= 1) {
return sum(n - 1) + n;
}
return n;
}
Giải thích:
- Bạn truyền một tham số n vào phương thức sum(), lệnh trong phương thức sum sẽ trả về tham số n bạn truyền vào khi chạy hết chương trình “return n”.
- Để đến được bước đó, chương trình sẽ chạy qua các lệnh điều kiện “if(n>=1)” để định nghĩa lại phương thức sum một lần nữa “sum(n-1) + n”, phương thức mới sẽ khiến giá trị n sẽ thay đổi theo từng vòng của điều kiện cho đến khi không còn thỏa mãn điều kiện được cho.
- Khi chương trình “return n” thì n chính là giá trị đã được tính ở phương thức ta đặt điều kiện bên trên.
Như vậy, hai yếu tố cần để tiến hành một phương thức đệ quy là:
- Có điều kiện dừng: Xác định quy luật của phương thức và tìm giá trị cụ thể khi thỏa mãn một điều kiện nhất định, ở bước này vẫn chưa có phương thức đệ quy nào được gọi.
- Phương thức đệ quy: Phương thức đệ quy sẽ gọi lại chính nó cho đến khi nó trả về điều kiện dừng ở bước 1.
 |
| 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. |
Bài viết tham khảo từ : https://topdev.vn/blog/thuat-toan-minimax-ai-trong-game/?fbclid=IwAR3j5btFm_ywOPXgbt33v_m5Qb2lZj-KAYAqSGw9N6ZF-R6OJbEhoxg8-5w
xem thêm :
Comments
Post a Comment