Đang thực hiện
Tên đăng nhập
Mật khẩu
 
Hoặc đăng nhập bằng:
Nhập lại mật khẩu

Trang chủ Tin tổng hợp
Tin tổng hợp

Thuật toán Mini-Max trong Trí tuệ nhân tạo

Cập nhật: 14/06/2019 Lượt xem: 114
Thuật toán mini-max là thuật toán đệ quy hoặc quay lui được sử dụng trong lý thuyết trò chơi và ra quyết định. Nó cung cấp một nước đi tối ưu cho người chơi giả định rằng đối thủ cũng đang chơi tối ưu.

Thuật toán Mini-Max sử dụng đệ quy để tìm kiếm thông qua cây trò chơi.

Thuật toán Min-Max chủ yếu được sử dụng để chơi trò chơi trong AI. Chẳng hạn như Cờ vua Cờ đam, tic-tac-toe, cờ vây và các trò chơi kéo khác nhau. Thuật toán này tính toán quyết định minimax cho trạng thái hiện tại.

 
Lập trình viên quốc tế ( AI )

Mini-Max Algorithm in Artificial Intelligence

 

Trong thuật toán này hai người chơi chơi trò chơi một người được gọi là MAX và người khác được gọi là MIN.

Cả hai người chơi chiến đấu với nó khi người chơi đối thủ nhận được lợi ích tối thiểu trong khi họ nhận được lợi ích tối đa.

Cả hai Người chơi của trò chơi đều là đối thủ của nhau trong đó MAX sẽ chọn giá trị tối đa và MIN sẽ chọn giá trị tối thiểu.

Thuật toán minimax thực hiện thuật toán tìm kiếm theo chiều sâu để khám phá cây trò chơi hoàn chỉnh.

Thuật toán minimax tiến hành tất cả các cách xuống nút cuối của cây sau đó quay lại cây dưới dạng đệ quy.

Mã giả cho thuật toán MinMax:
 

giải mã thuật toán minmax

Cuộc gọi ban đầu:

Minimax (nút, 3, đúng)
 

Hoạt động của thuật toán tối thiểu:

 

Hoạt động của thuật toán minimax có thể được mô tả dễ dàng bằng một ví dụ. Dưới đây chúng tôi đã lấy một ví dụ về cây trò chơi đại diện cho trò chơi hai người chơi.

Trong ví dụ này có hai người chơi được gọi là Maximizer và người chơi khác được gọi là Minimizer.

Maximizer sẽ cố gắng để có được số điểm tối đa có thể và Minimizer sẽ cố gắng để có được số điểm tối thiểu có thể.

Thuật toán này áp dụng DFS vì vậy trong cây trò chơi này, chúng ta phải đi hết các lá để đến các nút cuối.

Tại nút thiết bị đầu cuối, các giá trị đầu cuối được đưa ra vì vậy chúng tôi sẽ so sánh các giá trị đó và quay lại cây cho đến khi trạng thái ban đầu xảy ra. Sau đây là các bước chính liên quan đến việc giải quyết cây trò chơi hai người chơi:


>> Khóa học lập trình viên quốc tế chuyên nghiệp được NIIT - ICT Hà Nội kết hợp với Doanh nghiệp giảng dạy 100% thực hành thực thế. Nhanh tay đăng ký ngay để nhận ưu đãi khủng nào <<

 


Bước 1: Trong bước đầu tiên, thuật toán tạo toàn bộ cây trò chơi và áp dụng hàm tiện ích để lấy các giá trị tiện ích cho các trạng thái đầu cuối. 

Trong sơ đồ cây bên dưới, hãy coi A là trạng thái ban đầu của cây. Giả sử công cụ tối đa hóa lần lượt đầu tiên có giá trị ban đầu trong trường hợp xấu nhất = - vô cực và công cụ tối thiểu hóa sẽ thực hiện lần lượt tiếp theo có giá trị ban đầu trong trường hợp xấu nhất = + vô cùng.

 

Bước 2: Bây giờ, đầu tiên chúng ta tìm giá trị tiện ích cho Maximizer, giá trị ban đầu của nó là -∞, vì vậy chúng ta sẽ so sánh từng giá trị ở trạng thái đầu cuối với giá trị ban đầu của Maximizer và xác định các giá trị nút cao hơn. Nó sẽ tìm thấy tối đa trong số tất cả.
 

  • Đối với nút D max (-1, - -∞) => max (-1,4) = 4
  • Đối với nút E max (2, -∞) => max (2, 6) = 6
  • Đối với nút F max (-3, -∞) => max (-3, -5) = -3
  • Đối với nút G max (0, -∞) = max (0, 7) = 7


Bước 3: Trong bước tiếp theo, đó là một lần lượt cho minimizer, vì vậy nó sẽ so sánh tất cả các giá trị nút với + ∞, và sẽ tìm ra 3 thứ giá trị nút lớp.
 

  • Đối với nút B = min (4,6) = 4
  • Đối với nút C = min (-3, 7) = -3


Bây giờ đến lượt Maximizer và một lần nữa nó sẽ chọn tối đa của tất cả các giá trị nút và tìm giá trị tối đa cho nút gốc. 

Trong cây trò chơi này, chỉ có 4 lớp, do đó chúng ta tiếp cận ngay với nút gốc, nhưng trong các trò chơi thực tế, sẽ có hơn 4 lớp.

 

Đối với nút A tối đa (4, -3) = 4


Đó là quy trình làm việc hoàn chỉnh của trò chơi hai người chơi minimax.
 

Thuộc tính của thuật toán Mini-Max:

 

Hoàn thành - Thuật toán tối thiểu hoàn tất. Nó chắc chắn sẽ tìm thấy một giải pháp (nếu tồn tại), trong cây tìm kiếm hữu hạn.

Optimal- thuật toán Min-Max là tối ưu nếu cả hai đối thủ đang chơi một cách tối ưu.

Độ phức tạp thời gian - Vì nó thực hiện DFS cho cây trò chơi, nên độ phức tạp thời gian của thuật toán Min-Max là O (b m ) , trong đó b là hệ số phân nhánh của cây trò chơi và m là độ sâu tối đa của cây.

Độ phức tạp không gian - Độ phức tạp không gian của thuật toán Mini-max cũng tương tự như DFS là O (bm) .


Giới hạn của thuật toán minimax:
 

Hạn chế chính của thuật toán minimax là nó rất chậm đối với các trò chơi phức tạp như Cờ vua, cờ vây, v.v. Loại trò chơi này có yếu tố phân nhánh rất lớn và người chơi có rất nhiều sự lựa chọn để quyết định. 

Hạn chế này của thuật toán minimax có thể được cải thiện từ việc cắt tỉa alpha-beta mà chúng ta đã thảo luận trong chủ đề tiếp theo.

 

Tư vấn viên 1: Nguyễn Thu Huyền
Tư vấn viên 2: Thu Huyền
Tuyển sinh lập trình viên quốc tế - MMS new vision
Khóa học C&B Excel - Trần Văn Hải