Rate this post
  • Thuật toán mini-max là một thuật toán recursive hoặc backtrack được sử dụng trong việc ra quyết định và lý thuyết trò chơi. Nó cung cấp một nước đi tối ưu cho người chơi giả sử rằng đối thủ cũng đang chơi một cách tối ưu.
  • Thuật toán Mini-Max sử dụng recursive để tìm kiếm thông qua Game Tree.
  • 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ờ caro, tic-tac-toe, cờ vây và các trò chơi kéo xe 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.
  • Trong thuật toán này, hai người chơi trò chơi, một người được gọi là MAX và người kia được gọi là MIN.
  • Cả hai người chơi chiến đấu với nó vì người chơi đối phương 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 là đối thủ của nhau, trong đó MAX sẽ chọn giá trị tối đa và MIN sẽ chọn giá trị nhỏ nhất.
  • 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á Game Tree hoàn chỉnh.
  • Thuật toán minimax tiến hành tất cả các cách xuống nút đầu cuối của cây, sau đó quay ngược lại cây dưới dạng recursive.

Các bài viết liên quan:

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

function minimax(node, depth, maximizingPlayer) is  
if depth ==0 or node is a terminal node then  
return static evaluation of node  
  
if MaximizingPlayer then      // for Maximizer Player  
maxEva= -infinity            
 for each child of node do  
 eva= minimax(child, depth-1, false)  
maxEva= max(maxEva,eva)        //gives Maximum of the values  
return maxEva  
  
else                         // for Minimizer player  
 minEva= +infinity   
 for each child of node do  
 eva= minimax(child, depth-1, true)  
 minEva= min(minEva, eva)         //gives minimum of the values  
 return minEva  

Hoạt động của thuật toán Min-Max:

  • Có thể dễ dàng mô tả hoạt động của thuật toán minimax bằng cách sử dụng một ví dụ. Dưới đây chúng tôi đã lấy một ví dụ về Game Tree đại diện cho trò chơi hai người chơi.
  • Trong ví dụ này, có hai người chơi, một người được gọi là Maximizer và người khác được gọi là Minimizer.
  • Maximizer sẽ cố gắng đạt được số điểm Tối đa có thể, và Minimizer sẽ cố gắng đạt được số điểm tối thiểu có thể.
  • Thuật toán này áp dụng DFS, vì vậy trong Game Tree này, chúng ta phải đi hết các lá để đến được các nút đầu cuối.
  • Tại nút đầ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à điều chỉnh 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 Game Tree hai người chơi:

Bước 1: Trong bước đầu tiên, thuật toán tạo ra Game Tree và áp dụng hàm tiện ích để nhận các giá trị và các trạng thái kết thúc. 

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

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 mức 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, đến lượt trình thu nhỏ, vì vậy nó sẽ so sánh giá trị tất cả các nút với + ∞ và sẽ tìm giá trị nút lớp thứ 3.

Đối với nút B = min (4,6) = 4

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

Bước 4: Bây giờ đến lượt Maximizer, nó sẽ lại chọn giá trị lớn nhất của tất cả các nút và tìm giá trị lớn nhất cho nút gốc. Trong Game Tree này, chỉ có 4 lớp, do đó chúng tôi truy cập ngay đến nút gốc, nhưng trong trò chơi thực, sẽ có nhiều hơn 4 lớp.

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

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

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

Complete– Thuật toán Min-Max đã hoàn thành. 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– Min-Max là tối ưu nếu cả hai đối thủ đều chơi tối ưu.

Time complexity– Vì nó thực hiện DFS cho Game Tree, do đó độ phức tạp thời gian của thuật toán Min-Max là O (bm), trong đó b là hệ số phân nhánh của Game Tree và m là độ sâu tối đa của cây.

Space Complexity – Độ 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ó thực sự 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ó hệ số phân nhánh rất lớn và người chơi có rất nhiều lựa chọn recursive. Hạn chế này của thuật toán minimax có thể được cải thiện từ việc lược bớt alpha-beta mà chúng ta đã thảo luận trong chủ đề tiếp theo.

Leave a Reply

Call now
%d bloggers like this: