Giới thiệu về Thuật toán Minimax với Triển khai Java

1. Khái quát chung

Trong bài viết này, chúng ta sẽ thảo luận về thuật toán Minimax và các ứng dụng của nó trong AI. Vì nó là một thuật toán lý thuyết trò chơi, chúng tôi sẽ triển khai một trò chơi đơn giản bằng cách sử dụng nó.

Chúng tôi cũng sẽ thảo luận về những lợi thế của việc sử dụng thuật toán và xem nó có thể được cải thiện như thế nào.

2. Giới thiệu

Minimax là một thuật toán ra quyết định, thường được sử dụng trong trò chơi hai người chơi theo lượt . Mục tiêu của thuật toán là tìm ra nước đi tiếp theo tối ưu.

Trong thuật toán, một người chơi được gọi là người tối đa hóa và người chơi còn lại là người tối thiểu hóa. Nếu chúng tôi ấn định điểm đánh giá cho hội đồng trò chơi, một người chơi sẽ cố gắng chọn trạng thái trò chơi có điểm tối đa, trong khi người kia chọn trạng thái có điểm tối thiểu.

Nói cách khác, bộ tăng tối đa hoạt động để đạt điểm cao nhất, trong khi bộ thu nhỏ cố gắng đạt điểm thấp nhất bằng cách cố gắng chống lại các bước di chuyển .

Nó dựa trên khái niệm trò chơi có tổng bằng không. Trong trò chơi có tổng bằng không, tổng điểm tiện ích được chia cho những người chơi. Điểm số của một người chơi tăng lên dẫn đến giảm điểm số của người chơi khác. Vì vậy, tổng điểm luôn bằng không. Đối với một người chơi để giành chiến thắng, người còn lại phải thua. Ví dụ về các trò chơi như vậy là cờ vua, poker, cờ caro, tic-tac-toe.

Một sự thật thú vị - vào năm 1997, máy tính chơi cờ Deep Blue của IBM (được chế tạo bằng Minimax) đã đánh bại Garry Kasparov (nhà vô địch thế giới về cờ vua).

3. Thuật toán Minimax

Mục tiêu của chúng tôi là tìm ra nước đi tốt nhất cho người chơi. Để làm như vậy, chúng tôi chỉ có thể chọn nút có điểm đánh giá tốt nhất. Để làm cho quá trình thông minh hơn, chúng tôi cũng có thể nhìn trước và đánh giá các bước đi của đối thủ tiềm năng.

Đối với mỗi bước đi, chúng ta có thể nhìn về phía trước bao nhiêu bước đi nếu khả năng tính toán của chúng ta cho phép. Thuật toán giả định rằng đối thủ đang chơi một cách tối ưu.

Về mặt kỹ thuật, chúng tôi bắt đầu với nút gốc và chọn nút tốt nhất có thể. Chúng tôi đánh giá các nút dựa trên điểm đánh giá của chúng. Trong trường hợp của chúng tôi, chức năng đánh giá có thể chỉ định điểm cho các nút kết quả (lá). Do đó, chúng tôi tiếp cận một cách đệ quy các lá với điểm số và truyền ngược lại điểm số.

Hãy xem xét cây trò chơi dưới đây:

Maximizer bắt đầu với nút gốc và chọn nước đi với số điểm tối đa. Thật không may, chỉ các lá có điểm đánh giá với chúng và do đó thuật toán phải tiếp cận các nút lá một cách đệ quy. Trong cây trò chơi đã cho, hiện tại đến lượt người thu nhỏ chọn nước đi từ các nút lá , vì vậy các nút có điểm tối thiểu (ở đây, nút 3 và 4) sẽ được chọn. Nó tiếp tục chọn các nút tốt nhất tương tự, cho đến khi nó đạt đến nút gốc.

Bây giờ, hãy chính thức xác định các bước của thuật toán:

  1. Xây dựng cây trò chơi hoàn chỉnh
  2. Đánh giá điểm cho các lá bằng chức năng đánh giá
  3. Điểm sao lưu từ lá đến gốc, xem xét loại người chơi:
    • Đối với người chơi tối đa, hãy chọn trẻ có điểm tối đa
    • Đối với người chơi tối thiểu, hãy chọn con có số điểm tối thiểu
  4. Tại nút gốc, chọn nút có giá trị lớn nhất và thực hiện bước di chuyển tương ứng

4. Thực hiện

Bây giờ, hãy thực hiện một trò chơi.

Trong trò chơi, chúng ta có một đống với n số xương . Cả hai người chơi phải nhặt 1,2 hoặc 3 xương trong lượt của họ. Một người chơi không thể lấy bất kỳ xương nào sẽ thua trò chơi. Mỗi người chơi đều chơi một cách tối ưu. Với giá trị của n , hãy viết một AI.

Để xác định các quy tắc của trò chơi, chúng tôi sẽ triển khai lớp GameOfBones :

class GameOfBones { static List getPossibleStates(int noOfBonesInHeap) { return IntStream.rangeClosed(1, 3).boxed() .map(i -> noOfBonesInHeap - i) .filter(newHeapCount -> newHeapCount >= 0) .collect(Collectors.toList()); } }

Hơn nữa, chúng ta cũng cần triển khai cho các lớp NodeTree :

public class Node { int noOfBones; boolean isMaxPlayer; int score; List children; // setters and getters } public class Tree { Node root; // setters and getters }

Bây giờ chúng ta sẽ triển khai thuật toán. Nó yêu cầu một cây trò chơi để nhìn về phía trước và tìm ra nước đi tốt nhất. Hãy thực hiện điều đó:

public class MiniMax { Tree tree; public void constructTree(int noOfBones) { tree = new Tree(); Node root = new Node(noOfBones, true); tree.setRoot(root); constructTree(root); } private void constructTree(Node parentNode) { List listofPossibleHeaps = GameOfBones.getPossibleStates(parentNode.getNoOfBones()); boolean isChildMaxPlayer = !parentNode.isMaxPlayer(); listofPossibleHeaps.forEach(n -> { Node newNode = new Node(n, isChildMaxPlayer); parentNode.addChild(newNode); if (newNode.getNoOfBones() > 0) { constructTree(newNode); } }); } }

Bây giờ, chúng tôi sẽ triển khai phương pháp checkWin sẽ mô phỏng một lượt chơi, bằng cách chọn các nước đi tối ưu cho cả hai người chơi. Nó đặt điểm thành:

  • +1, nếu công cụ tối đa hóa thắng
  • -1, nếu trình thu nhỏ thắng

Các checkWin sẽ trả về true nếu cầu thủ đầu tiên (trong trường hợp của chúng tôi - công cụ tối đa) đá:

public boolean checkWin() { Node root = tree.getRoot(); checkWin(root); return root.getScore() == 1; } private void checkWin(Node node) { List children = node.getChildren(); boolean isMaxPlayer = node.isMaxPlayer(); children.forEach(child -> { if (child.getNoOfBones() == 0) { child.setScore(isMaxPlayer ? 1 : -1); } else { checkWin(child); } }); Node bestChild = findBestChild(isMaxPlayer, children); node.setScore(bestChild.getScore()); }

Ở đây, phương thức findBestChild tìm nút có điểm tối đa nếu người chơi là người tối đa. Nếu không, nó trả về đứa trẻ với số điểm tối thiểu:

private Node findBestChild(boolean isMaxPlayer, List children) { Comparator byScoreComparator = Comparator.comparing(Node::getScore); return children.stream() .max(isMaxPlayer ? byScoreComparator : byScoreComparator.reversed()) .orElseThrow(NoSuchElementException::new); }

Cuối cùng, hãy triển khai một trường hợp thử nghiệm với một số giá trị của n (số lượng xương trong một đống):

@Test public void givenMiniMax_whenCheckWin_thenComputeOptimal() { miniMax.constructTree(6); boolean result = miniMax.checkWin(); assertTrue(result); miniMax.constructTree(8); result = miniMax.checkWin(); assertFalse(result); }

5. Cải tiến

Đối với hầu hết các vấn đề, việc xây dựng toàn bộ một cây trò chơi là không khả thi. Trong thực tế, chúng ta có thể phát triển một phần cây (chỉ xây dựng cây cho đến một số cấp độ được xác định trước) .

Sau đó, chúng tôi sẽ phải triển khai một chức năng đánh giá, chức năng này sẽ có thể quyết định trạng thái hiện tại tốt như thế nào đối với người chơi.

Ngay cả khi chúng tôi không xây dựng các cây trò chơi hoàn chỉnh, việc tính toán các bước di chuyển cho các trò chơi có hệ số phân nhánh cao có thể tốn nhiều thời gian.

May mắn thay, có một tùy chọn để tìm ra nước đi tối ưu, mà không cần khám phá mọi nút của cây trò chơi. Chúng ta có thể bỏ qua một số nhánh bằng cách tuân theo một số quy tắc và nó sẽ không ảnh hưởng đến kết quả cuối cùng. Quá trình này được gọi là cắt tỉa . Cắt tỉa alpha – beta là một biến thể phổ biến của thuật toán minimax.

6. Kết luận

Thuật toán Minimax là một trong những thuật toán phổ biến nhất cho trò chơi hội đồng máy tính. Nó được áp dụng rộng rãi trong các trò chơi theo lượt. Nó có thể là một lựa chọn tốt khi người chơi có thông tin đầy đủ về trò chơi.

Nó có thể không phải là lựa chọn tốt nhất cho các trò chơi có hệ số phân nhánh đặc biệt cao (ví dụ: trò chơi GO). Tuy nhiên, nếu được triển khai đúng cách, nó có thể là một AI khá thông minh.

Như mọi khi, mã hoàn chỉnh cho thuật toán có thể được tìm thấy trên GitHub.