AI - Giải thuật Minimax và một con game tự chế quá vui

Giới thiệu về thuật toán Minimax

Thuật toán Minimax là một phương pháp đệ quy được sử dụng để lựa chọn nước đi tiếp theo trong các trò chơi có nhiều người chơi, mà điển hình là các trò chơi đối kháng giữa hai người. Mục đích cốt lõi của thuật toán này là giảm thiểu khả năng thua cuộc lớn nhất có thể xảy ra cho người chơi hiện tại. Trong bối cảnh mà các kết quả được đánh giá bằng lợi nhuận thay vì tổn thất, thuật toán này còn được biết đến với tên gọi "maximin", với mục tiêu là tối đa hóa lợi nhuận tối thiểu mà người chơi có thể đạt được. Để đạt được điều này, Minimax gán một giá trị số học cho mỗi vị trí hoặc trạng thái có thể có của trò chơi. Giá trị này thường được xác định thông qua một hàm đánh giá vị trí, có chức năng ước tính mức độ thuận lợi của trạng thái hiện tại đối với một người chơi cụ thể.

Giả định cơ bản của Minimax là cả người chơi và đối thủ đều hành động một cách tối ưu để đạt được mục tiêu của mình. Do đó, khi một AI sử dụng thuật toán Minimax, nó không chỉ xem xét các nước đi tiềm năng của bản thân mà còn dự đoán và đánh giá các phản ứng tối ưu có thể có của đối thủ đối với từng nước đi đó. Cách tiếp cận này cho phép AI đưa ra quyết định không chỉ dựa trên lợi ích trực tiếp mà còn dựa trên việc lường trước các động thái và chiến lược của đối thủ.

Cách thức AI suy nghĩ trong Minimax

Để quyết định đi nước đi nào tiếp theo, máy tính sẽ làm các việc sau:

• Sinh ra tất cả các nước nước đi mà nó có thể đi

• Đối với mỗi nước đi ấy, tiếp tục sinh ra tất cả các nước đi mà con người có thể đi

• Lại tiếp tục sinh ra tất cả các nước đi có thể từ các nước đi của con người đi và cứ tiếp diễn như vậy cho đến khi đạt đến trạng thái cuối cùng (thắng, thua, hoặc hòa). Tuy nhiên vệc liên tục sinh nước đi sẽ có thể dẫn đến bùng nổ không gian trạng thái và tính toán. Do đó, để tránh điều này, người ta thường giới hạn độ sâu tính toán ở một ngưỡng mà chương trình có thể chấp nhận được và đánh giá các trạng thái bàn cờ tại điểm đó thông qua một hàm lượng giá (heuristic).

• Chọn nước đi có lợi nhất.

Dựa trên ý tưởng đó, ta xây dựng lên một cấu trúc cây trò chơi (game tree) mà trong đó mỗi nút (node) đại diện cho một trạng thái của bàn cờ, mỗi nút có chứa một tập hợp các nút con đại diện cho các trạng thái có thể sinh ra từ nút cha. Để đánh giá một nước đi là tốt hay xấu, mỗi nút sẽ có một số điểm để thể hiện mức độ tốt xấu cho chính nó.

Thuật toán Minimax

Thuật toán Minimax được xây dựng trên cây trò chơi. Có một điểm đặc biệt ở thuật toán này đó là chúng ta chỉ quan tâm đến đánh giá điểm ở các nút lá của cây để quyết định số điểm của các nút cha. Thật vậy, tưởng tượng bạn chơi cờ tướng hay cờ vua cũng vậy, giả sử bạn có thể suy tính trước 3 nước, thì trạng thái ở bước thứ 3 mới là cơ sở bạn chọn nước đi nào tiếp theo. Ví dụ, bạn có thể ăn xe hoặc lên mã ở bước tiếp theo, và nếu tính toán được rằng 3 nước tiếp thì lên mã sẽ chiếu hết cờ, bạn sẽ lên mã thay vì ăn xe. Vì vậy, hàm heuristic sẽ được thực hiện để đánh giá trạng thái của các nút lá. Hàm heuristic đóng vai trò then chốt trong việc lựa chọn nước đi và quyết định máy tính có thông minh hay không.

Tư tưởng chủ đạo của thuật toán này nằm ở việc giả định rằng ở mỗi nước tính toán, người chơi luôn luôn tối ưu lợi thế của mình, nghĩa là, bạn luôn sẽ đi nước đi đạt số điểm cao nhất (MAX) và ngược lại, đối thủ của bạn cũng sẽ đi nước đi bất lợi với bạn nhất (MIN).

Hãy cùng xem một mô tả về cách đánh giá điểm trên cây trò chơi dưới đây:

Ví dụ hàm heuristic cho trò chơi Tic-Tac-Toe:

Tic-Tac-Toe là một trò chơi cờ giống như trò caro với kích thước bàn cờ là \(3\times 3\). Hai bên quân xanh và đỏ lần lượt điền vào các ô trống, bên nào tạo ra \(1\) hàng hoặc \(1\) cột hoăc \(1\) đường chéo liên tiếp \(3\) quân của mình đứng cạnh nhau thì bên ấy thắng.

• Nếu AI thắng, điểm thưởng là \(+10\)

• Nếu AI thua, điểm thưởng là \(-10\)

• Nếu hòa, điểm thưởng là \(0\)

• Nếu trò chơi chưa kết thúc, điểm thưởng của nước đi sẽ là số tiềm năng các đường tạo thành \(3\) quân liên tiếp mà nước đi vào ô đó có thể tạo ra.

Ví dụ, khởi đầu bàn cờ, AI đi trước thì số điểm mà hàm heuristic đánh giá cho từng ô sẽ như sau:

Còn đây là số điểm mà hàm heuristic đánh giá cho quân xanh ở thời điểm đã qua 3 lượt

Kỹ thuật tỉa nhánh Alpha - Beta

Mặc dù Minimax có nhiều ưu điểm, chẳng hạn như đảm bảo tìm được chiến lược tối ưu và dễ hiểu, nó cũng có một số nhược điểm. Độ phức tạp tính toán của thuật toán tăng theo cấp số nhân với kích thước của cây trò chơi, làm cho nó trở nên không thực tế cho các trò chơi lớn với nhiều nước đi tiềm năng. Hơn nữa, Minimax cần phải tính toán toàn bộ cây trò chơi (hoặc ít nhất là đến một độ sâu nhất định) trước khi đưa ra quyết định, điều này có thể tốn rất nhiều thời gian và tài nguyên tính toán.

Để giải quyết vấn đề về độ phức tạp tính toán của thuật toán Minimax, một kỹ thuật tối ưu hóa mạnh mẽ đã được phát triển, đó là tỉa nhánh Alpha-Beta (Alpha-Beta prunning). Mục tiêu chính của kỹ thuật này là giảm số lượng nút trong cây trò chơi mà thuật toán Minimax cần phải đánh giá. Alpha-Beta pruning giúp loại bỏ các nhánh của cây trò chơi mà không cần phải khám phá, vì chúng không có khả năng ảnh hưởng đến quyết định cuối cùng của thuật toán.

Kỹ thuật Alpha-Beta prunning sử dụng hai tham số để theo dõi các giá trị tốt nhất mà mỗi người chơi có thể đảm bảo dọc theo đường đi hiện tại trong cây trò chơi :

• Alpha \(\alpha\): Đại diện cho giá trị tốt nhất (cao nhất) mà người chơi MAX đã tìm thấy cho đến nay tại bất kỳ điểm lựa chọn nào trên đường đi. Ban đầu, Alpha \(\alpha\) được đặt thành giá trị vô cực âm \(- \infty\).

• Beta \(\beta\): Đại diện cho giá trị tốt nhất (thấp nhất) mà người chơi MIN đã tìm thấy cho đến nay tại bất kỳ điểm lựa chọn nào trên đường đi. Ban đầu, Beta \(\beta\) được đặt thành giá trị vô cực dương \(+\infty\).

Nguyên tắc cơ bản của Alpha-Beta prunning như sau: tại một nút MAX, nếu giá trị của một nút con lớn hơn hoặc bằng giá trị Beta của nút cha MIN, thì các nút con còn lại của nút MAX đó không cần phải được khám phá thêm (cắt tỉa Beta). Điều này là do người chơi MIN đã có một lựa chọn tốt hơn (giá trị Beta thấp hơn) ở một nơi khác trong cây. Tương tự, tại một nút MIN, nếu giá trị của một nút con nhỏ hơn hoặc bằng giá trị Alpha của nút cha MAX, thì các nút con còn lại của nút MIN đó có thể bị bỏ qua (cắt tỉa Alpha). Điều này xảy ra vì người chơi MAX đã có một lựa chọn tốt hơn (giá trị Alpha cao hơn) ở một nơi khác. Điều kiện để thực hiện việc cắt tỉa là khi giá trị Alpha trở nên lớn hơn hoặc bằng giá trị Beta \((\alpha \ge \beta)\). Khi điều kiện này được đáp ứng tại một nút, thuật toán có thể ngừng khám phá các nút con còn lại của nút đó và quay trở lại nút cha.

Xin mời bạn tham khảo hình animation mà mình đã lấy từ wikipedia ở dưới để hiểu rõ hơn cách hoạt động của Alpha-Beta Prunning

Trò chơi áp dụng giải thuật Minimax

Một bàn cờ ô vuông \(n \times n\), hai người chơi ở 2 góc bàn cờ vị trí \((1,1)\) và \((n,n)\). Trên bàn cờ có các viên kim cương nằm ở vị trí ngẫu nhiên. Mỗi người chơi tuần tự đi theo lượt, mỗi lượt được đi 1 bước theo một trong 4 hướng: TRÊN, DƯỚI, TRÁI, PHẢI. Mỗi khi đi vào ô có kim cương, người ấy sẽ được cộng thêm 1 điểm. Trò chơi sẽ kết thúc khi:

• Hết kim cương trên bàn, người chơi có nhiều kim cương hơn sẽ chiến thắng

• Hoặc người này “ăn“ được người kia, nghĩa là, đi vào ô người kia đang đứng

Hàm lượng giá

Hàm lượng giá cho một trạng thái của bàn cờ được thiết kế như sau

• Nếu người chơi hiện tại đi vào ô người kia đang đứng: \(+1,000,000 \) điểm

• Nếu người chơi hiện tại đi vào ô mà người kia đang đứng cạnh: \(-1,000,000\) điểm

• Ngoài ra điểm số sẽ được tính theo công thức \(s = (2n - d) + cs*100\), với

  • \(n\) là kích thước của bàn cờ

  • \(d\) là khoảng cách ngắn nhất mà người chơi hiện tại có thể ăn được kim cương

  • \(cs\) là điểm số đạt được

  • Ý tưởng của công thức này là khuyến khích con bot chạy về nơi có kim cương gần nhất

Source code:

evaluate() {
        let currentPlayer = this.players[this.currentPlayerIndex];
        let opponentPlayer = this.players[1 - this.currentPlayerIndex];

        // Nếu người chơi hiện tại di chuyển vào ô người chơi khác thì người chơi này sẽ thắng ngay lập tức
        // đánh giá điểm số là 1000000
        if (currentPlayer.x === opponentPlayer.x && currentPlayer.y === opponentPlayer.y) {
            return 1000000;
        }

        // Nếu người chơi hiện tại di chuyển vào ô cách ô người chơi khác 1 ô thì người chơi này sẽ bất lợi
        // đánh giá điểm số là -1000000
        if (Math.abs(currentPlayer.x - opponentPlayer.x) <= 1 && Math.abs(currentPlayer.y - opponentPlayer.y) <= 1) {
            return -1000000;
        }

        // Tìm viên kim cương gần nhất với người chơi hiện tại
        let closestDistance = Infinity;
        for (let diamond of this.board.diamonds) {
            let distance = Math.abs(currentPlayer.x - diamond.x) + Math.abs(currentPlayer.y - diamond.y);
            if (distance < closestDistance) {
                closestDistance = distance;
            }
        }

        // Công thức tính điểm số là
        // (kích thước bàn cờ * 2 - khoảng cách gần nhất giữa người chơi và viên kim cương)**2 + điểm số của người chơi hiện tại * 100
        return (this.board.size * 2 - closestDistance) + currentPlayer.score * 100;
    }

Demo