Giới thiệu

Alpha-Beta Pruning là một phiên bản sửa đổi của thuật toán minimax. Nó là một kỹ thuật tối ưu hóa cho thuật toán minimax.

Như chúng ta đã thấy trong thuật toán tìm kiếm minimax rằng số lượng trạng thái trò chơi mà nó phải kiểm tra là cấp số nhân theo chiều sâu của cây. Vì chúng ta không thể loại bỏ số mũ, nhưng chúng ta có thể cắt nó thành một nửa. Do đó, có một kỹ thuật mà không cần kiểm tra từng nút của cây trò chơi, chúng ta có thể tính ra quyết định minimax chính xác và kỹ thuật này được gọi là cắt tỉa. Điều này liên quan đến hai tham số ngưỡng Alpha và beta để mở rộng trong tương lai, vì vậy nó được gọi là Alpha-Beta Pruning. Nó còn được gọi là Thuật toán Alpha-Beta.

Thuật toán Alpha-Beta Pruning

Alpha – beta pruning là một thuật toán tìm kiếm nâng cao của minimax, thuật toán này làm giảm số lượng các node cây được đánh giá bởi thuật toán minimax trong cây tìm kiếm. Thuật toán này dựa theo tìm kiếm đối nghịch trong một số trò chơi với máy (Tic-tac-toe, Cờ vua, v.v.).

Alpha-Beta Pruning có thể được áp dụng ở bất kỳ độ sâu nào của cây, và đôi khi nó không chỉ cắt tỉa lá cây mà còn cắt tỉa toàn bộ cây phụ.

Hai tham số có thể được định nghĩa là:

• Alpha: Sự lựa chọn tốt nhất (giá trị cao nhất) mà chúng tôi đã tìm thấy cho đến nay tại bất kỳ điểm nào trên con đường của Maximizer. Giá trị ban đầu của alpha là -∞.
• Beta: Lựa chọn tốt nhất (giá trị thấp nhất) mà chúng tôi đã tìm thấy cho đến nay tại bất kỳ điểm nào dọc theo đường dẫn của Minimizer. Giá trị ban đầu của beta là + ∞.

Việc Alpha-Beta Pruning thành một thuật toán minimax tiêu chuẩn trả lại cùng một động thái như thuật toán tiêu chuẩn, nhưng nó loại bỏ tất cả các nút không thực sự ảnh hưởng đến quyết định cuối cùng nhưng làm cho thuật toán bị chậm. Do đó, bằng cách lược bỏ các nút này, thuật toán sẽ nhanh hơn.

Lưu ý: Để hiểu rõ hơn về chủ đề này, vui lòng nghiên cứu thuật toán minimax.

Điều kiện để Alpha-Beta Pruning:

Điều kiện chính cần thiết để Alpha-Beta Pruning là:

α> = β

Những điểm chính về việc Alpha-Beta Pruning:

• Max player sẽ chỉ cập nhật giá trị của alpha.
• Min player sẽ chỉ cập nhật giá trị của phiên bản beta.
• Trong khi backtracking lại cây, các giá trị của nút sẽ được chuyển đến các nút phía trên thay vì các giá trị của alpha và beta.
• Chúng tôi sẽ chỉ chuyển các giá trị alpha, beta cho các nút con.

Làm việc của Alpha-Beta Pruning:

Hãy lấy một ví dụ về cây tìm kiếm hai người chơi để hiểu hoạt động của việc Alpha-Beta Pruning

Bước 1: Ở bước đầu tiên, người chơi Max sẽ bắt đầu di chuyển đầu tiên từ nút A nơi α = -∞ và β = + ∞, những giá trị alpha và beta này được truyền lại cho nút B nơi lại α = -∞ và β = + ∞ và Nút B chuyển cùng một giá trị cho nút con D của nó.

Bước 2: Tại nút D, giá trị của α sẽ được tính theo lượt của nó cho Max. Giá trị của α được so sánh với đầu tiên là 2 và sau đó là 3, và max (2, 3) = 3 sẽ là giá trị của α tại nút D và giá trị của nút cũng sẽ là 3.

Bước 3: Bây giờ thuật toán quay ngược lại nút B, trong đó giá trị của β sẽ thay đổi vì đây là lượt của Min, Bây giờ β = + ∞, sẽ so sánh với giá trị của các nút tiếp theo có sẵn, tức là min (∞, 3) = 3, do đó tại nút B bây giờ α = -∞ và β = 3.

Trong bước tiếp theo, thuật toán duyệt qua nút kế tiếp tiếp theo của nút B là nút E, và các giá trị của α = -∞ và β = 3 cũng sẽ được chuyển.

Bước 4: Tại nút E, Max sẽ đến lượt, và giá trị của alpha sẽ thay đổi. Giá trị hiện tại của alpha sẽ được so sánh với 5, vì vậy max (-∞, 5) = 5, do đó tại nút E α = 5 và β = 3, trong đó α> = β, vì vậy kế thừa bên phải của E sẽ bị lược bỏ, và thuật toán sẽ không đi qua nó, và giá trị tại nút E sẽ là 5.

Bước 5: Ở bước tiếp theo, thuật toán lại chiếu ngược cây, từ nút B đến nút A. Tại nút A, giá trị của alpha sẽ được thay đổi giá trị lớn nhất có sẵn là 3 như max (-∞, 3) = 3 và β = + ∞, hai giá trị này bây giờ được chuyển đến người kế nhiệm bên phải của A là Nút C.

Tại nút C, α = 3 và β = + ∞, và các giá trị tương tự sẽ được chuyển cho nút F.

Bước 6: Tại nút F, một lần nữa giá trị của α sẽ được so sánh với nút con bên trái là 0 và max (3,0) = 3, sau đó so sánh với nút con bên phải là 1 và max (3,1) = 3 vẫn còn α vẫn là 3, nhưng giá trị nút của F sẽ trở thành 1.

Bước 7: Nút F trả về giá trị nút 1 cho nút C, tại C α = 3 và β = + ∞, ở đây giá trị beta sẽ được thay đổi, nó sẽ so sánh với 1 nên min (∞, 1) = 1. Bây giờ tại C, α = 3 và β = 1, và một lần nữa nó thỏa mãn điều kiện α> = β, vì vậy con tiếp theo của C là G sẽ bị lược bớt, và thuật toán sẽ không tính toàn bộ cây con G.

Bước 8: C bây giờ trả về giá trị từ 1 đến A ở đây giá trị tốt nhất cho A là max (3, 1) = 3. Sau đây là cây trò chơi cuối cùng là hiển thị các nút được tính toán và các nút chưa bao giờ tính toán. Do đó, giá trị tối ưu cho bộ cực đại là 3 cho ví dụ này.

Di chuyển thứ tự trong Alpha-Beta Pruning:

Hiệu quả của việc Alpha-Beta Pruning phụ thuộc nhiều vào thứ tự mà mỗi nút được kiểm tra. Thứ tự di chuyển là một khía cạnh quan trọng của việc Alpha-Beta Pruning.

Nó có thể có hai loại:

Worst ordering: Trong một số trường hợp, thuật toán Alpha-Beta Pruning không cắt tỉa bất kỳ lá nào của cây và hoạt động chính xác như thuật toán minimax. Trong trường hợp này, nó cũng tiêu tốn nhiều thời gian hơn vì các yếu tố alpha-beta, động thái cắt tỉa như vậy được gọi là thứ tự tồi tệ nhất. Trong trường hợp này, chuyển động tốt nhất xảy ra ở phía bên phải của cây. Độ phức tạp về thời gian cho một lệnh như vậy là O (bm).

Ideal ordering: Thứ tự lý tưởng để Alpha-Beta Pruning xảy ra khi nhiều lần cắt tỉa diễn ra trên cây và các động thái tốt nhất xảy ra ở phía bên trái của cây. Chúng tôi áp dụng DFS do đó nó tìm kiếm đầu tiên bên trái của cây và đi sâu gấp đôi so với thuật toán minimax trong cùng một khoảng thời gian. Độ phức tạp trong thứ tự lý tưởng là O (bm / 2).

Các quy tắc để tìm thứ tự tốt:

Sau đây là một số quy tắc để tìm thứ tự tốt trong việc Alpha-Beta Pruning:

• Xảy ra nước đi tốt nhất từ ​​nút nông nhất.
• Thứ tự các nút trong cây sao cho các nút tốt nhất được kiểm tra trước.
• Sử dụng kiến ​​thức miền trong khi tìm ra nước đi tốt nhất. Ví dụ: đối với Cờ vua, hãy thử thứ tự: bắt trước, sau đó đe dọa, sau đó tiến lên, lùi lại.
• Chúng tôi có thể ghi sổ các trạng thái, vì có khả năng các trạng thái đó có thể lặp lại.

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.

Xem thêm Thuật toán Alpha-Beta Pruning

Một số câu hỏi phổ biến về thuật toán minimax

1. Thuật toán minimax là gì?

Thuật toán minimax là một thuật toán đánh giá giá trị của các nút trong cây trò chơi, để tìm ra nước đi tối ưu cho một người chơi. Thuật toán này được sử dụng rộng rãi trong trò chơi có hai người, như cờ vua, cờ tướng và tic-tac-toe.

2. Làm thế nào để sử dụng thuật toán minimax trong trò chơi?

Để sử dụng thuật toán minimax trong trò chơi, cần xây dựng một cây trò chơi, trong đó mỗi nút đại diện cho một trạng thái của trò chơi và mỗi cạnh đại diện cho một nước đi. Các nút ở độ sâu chẵn đại diện cho các nước đi của người chơi đang chơi, trong khi các nút ở độ sâu lẻ đại diện cho các nước đi của đối thủ.

Thuật toán minimax duyệt cây trò chơi và đánh giá giá trị của các nút lá. Nếu nút lá đại diện cho một trạng thái kết thúc của trò chơi, giá trị của nó được tính bằng cách xem ai đã thắng hoặc thua trò chơi. Nếu nút lá đại diện cho một trạng thái không kết thúc, giá trị của nó được tính bằng cách sử dụng một hàm đánh giá, đại diện cho khả năng thắng của người chơi đang chơi.

3. Thuật toán minimax có thể giải quyết được trò chơi nào?

Thuật toán minimax có thể được sử dụng để giải quyết các trò chơi có hai người chơi, có hữu hạn số lượng nước đi và không có yếu tố ngẫu nhiên, ví dụ như cờ vua, cờ tướng, tic-tac-toe và Connect Four.

4. Làm thế nào để tối ưu hóa thuật toán minimax?

Để tối ưu hóa thuật toán minimax, có thể sử dụng một số kỹ thuật như cắt tỉa alpha-beta hoặc sử dụng các phương pháp đánh giá khác nhau để tăng độ chính xác của giá trị đánh giá của các nút. Ngoài ra, việc sử dụng các cấu trúc dữ liệu hiệu quả để lưu trữ cây trò chơi cũng có thể giúp tăng tốc

5. Alpha-beta pruning là gì và nó được sử dụng như thế nào trong thuật toán minimax?

Alpha-beta pruning là một kỹ thuật cắt tỉa được sử dụng để tối ưu hóa thuật toán minimax bằng cách loại bỏ các nút không cần thiết trong cây trò chơi. Kỹ thuật này hoạt động bằng cách sử dụng hai giá trị alpha và beta để giới hạn khoảng giá trị đánh giá của các nút con của một nút cha trong cây trò chơi. Khi giá trị đánh giá của một nút con vượt quá giới hạn này, các nút con còn lại của nút cha đó không cần được kiểm tra nữa.

6. Thuật toán minimax có nhược điểm gì?

Thuật toán minimax có thể có nhược điểm là thời gian tính toán và không gian lưu trữ tăng lên nhanh chóng với số lượng nút trong cây trò chơi. Điều này đặc biệt đúng đối với các trò chơi lớn và phức tạp như cờ vua, khi số lượng nút có thể lên đến hàng tỷ. Ngoài ra, thuật toán minimax không thể xử lý các trò chơi có yếu tố ngẫu nhiên, ví dụ như poker hoặc blackjack.

7. Có những phương pháp thay thế nào cho thuật toán minimax?

Có nhiều phương pháp thay thế cho thuật toán minimax, trong đó phương pháp Monte Carlo là một trong những phương pháp phổ biến nhất. Phương pháp này sử dụng một số lượng lớn các trận đấu mô phỏng để đánh giá giá trị của một nút, thay vì duyệt toàn bộ cây trò chơi. Phương pháp Monte Carlo có thể được sử dụng để giải quyết các trò chơi có yếu tố ngẫu nhiên, như poker hoặc blackjack, và có thể được tối ưu hóa để tăng độ chính xác của kết quả.

8. Làm thế nào để áp dụng thuật toán minimax vào các trò chơi phức tạp hơn?

Các trò chơi phức tạp hơn, ví dụ như cờ vua, thường có số lượng nút lớn hơn rất nhiều so với các trò chơi đơn giản hơn như tic-tac-toe. Để áp dụng thuật toán minimax vào các trò chơi phức tạp hơn, ta cần sử dụng các kỹ thuật cải tiến để giảm số lượng nút trong cây trò chơi, và tối ưu hóa thời gian tính toán.

Một trong những kỹ thuật cải tiến phổ biến là sử dụng bảng tra cứu đánh giá, trong đó các giá trị đánh giá cho các trường hợp đặc biệt đã được tính toán trước và lưu trữ trong bảng. Khi thực hiện thuật toán minimax, ta có thể sử dụng bảng này để tránh tính toán lại các giá trị đánh giá đã được tính toán trước đó.

Ngoài ra, ta cũng có thể sử dụng các kỹ thuật thay thế cho thuật toán minimax, như phương pháp Monte Carlo, để giảm thời gian tính toán và tối ưu hóa thuật toán cho các trò chơi phức tạp hơn.

9. Thuật toán minimax có thể được sử dụng cho những mục đích nào ngoài các trò chơi?

Mặc dù thuật toán minimax thường được sử dụng để giải quyết các trò chơi, nó cũng có thể được áp dụng cho các bài toán tối ưu hóa và quyết định trong các lĩnh vực khác. Ví dụ, thuật toán minimax có thể được sử dụng để tìm kiếm chiến lược tối ưu trong quản lý tài sản và quản lý rủi ro. Thuật toán minimax cũng có thể được sử dụng trong các bài toán tìm kiếm con đường tối ưu trong đường đi tối ưu hoá, tối ưu hóa mạng và tối ưu hóa vận hành của hệ thống.

Code C++

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