Android: Thuật toán Minimax

Today I would like to write post by Vietnamese for better explanation about Mimimax algorithm - a simple AI algorithm and it's implementation. I re-post from pyimlife.wordpress. 

Mục tiêu: lập trình “máy” chơi trò Tic-Tac-Toe (thể loại game đối kháng chơi luân phiên tương tự trò cờ caro) với con người.

1 – Đầu vào:

Một mảng 3×3 thể hiện các nước đi luân phiên của người chơi (X) và máy (O).

Hình minh họa: Người chơi (X) chơi trước, máy (O) chơi sau. Kết thúc ván không bên nào điền được 3 ô thẳng hàng ngang, dọc hay đường chéo nên kết quả là hòa.

2 – Thuật toán của máy:

Minimax là thuật toán đệ quy. Ở mỗi lượt chơi, máy dựa vào mảng đầu vào 3×3 để “duyệt vét cạn”:
Thử lần lượt các nước đi có thể;

• Với mỗi phép thử nó tiếp tục gọi vòng đệ quy mới để thử hết các lựa chọn kế tiếp của người chơi;
• Với mỗi lựa chọn đó, lại tiếp tục phép thử với lượt của máy…;
• => lặp lại cho tới khi bàn cờ kết thúc (X thắng, hòa, O thắng).

Sau khi thử hết các trường hợp, máy sẽ chọn ra nước đi nào là tối ưu nhất. Vậy làm sao để biết nước đi nào tối ưu nhất?

Bằng cách tính điểm cho mỗi bước đi.

• MAX : tấn công => chọn nước đi mà máy có điểm cao nhất
• MIN : phòng thủ => chọn nước đi sao cho người chơi có điểm thấp nhất.
• Lựa chọn tối ưu: [tấn công + phòng thủ] Máy tấn công thì chọn nước MAX, còn phòng thủ thì chọn MIN

Giả sử: khi duyệt đến một bước: (O = máy; X = người chơi)

• O thắng: +1 điểm
• Hòa game: 0 điểm
• X thắng: +1 điểm => O thua: -1 điểm

Vậy, nếu O đi thì chọn nước có điểm lớn nhất (ưu tiên O = 1 => 0 => -1 điểm).

Ví dụ:

Với mảng ban đầu, máy (O) có 2 cách đi là a và b.

• Nếu máy đi (a), người chơi sẽ chọn ô còn lại và chiến thắng => X là 1 điểm. Do O thua nên số điểm cho lượt đi (a) của O là -1 điểm.
• Nếu máy đi (b), người chơi sẽ chọn ô còn lại, kết quả hòa => X và O là 0 điểm.

So sánh (a) và (b) thấy cách đi (b) thì O có điểm cao hơn (0 > -1) => máy sẽ chọn nước đi (b).

3. Cài đặt và Pseudo code

Triển khai thuật toán getBestMove() cho máy là cài đặt duyệt vét cạn lần lượt các nước đi có thể cho tới khi:
1 - Nếu tìm thấy một bước đi có điểm là 1 thì trả về kết quả ngay (máy thắng luôn).
2 - Trong quá trình duyệt thì lưu lại điểm “lớn nhất” của từng bước đi vào mảng (điểm sẽ là 0 hoặc -1, vì nếu là 1 thì đã trả về luôn kết quả rồi)
3 - Sau khi duyệt xong, xử lý mảng tìm được:

• [a] xếp ngẫu nhiên
• [b] sắp xếp theo thứ tự điểm từ cao xuống thấp
• [c] Trả về nước đi ở vị trí đầu tiên của mảng

Bước 3 này đảm bảo rằng máy sẽ chơi một cách ngẫu nhiên chứ không chỉ theo một lựa chọn duy nhất đối với mỗi thế cờ (Vì giả sử có 2 cách đi bằng điểm nhau, thì chúng đã được sắp xếp ngẫu nhiên ở [3 - a] nên một trong hai có thể nằm ở vị trí đầu tiên của mảng).


Code có thể viết như sau:
Một bước đi thì đại diện bởi 3 giá trị: row – column – score.
<div class="code">
public class MOVE {
    int row;
    int col;
    int score;
}
</div>

Hàm getBestMove()
<div class="code">
MOVE getAIsBestMove(int[][] board, boolean currentPlayerX) {
    MOVE[] availableMovesAndScores = new MOVE[BOARD_SIZE * BOARD_SIZE];
    int count = 0;

    // try each available move
    for (int i = 0; i < BOARD_SIZE; i++)
        for (int j = 0; j < BOARD_SIZE; j++)
            if (board[i][j] == PLAYER.none) {
                // copy to new board
                int[][] tempBoard = copyBoard(board);
                // make a move
                if (currentPlayerX) {
                    tempBoard[i][j] = PLAYER.x;
                } else {
                    tempBoard[i][j] = PLAYER.y;
                }

                // checkWin
                RESULT result = checkResult(tempBoard);
                int score = 0;
                if (result == RESULT.TIE) {
                    score = 0;
                }
                else if (result == RESULT.WIN) {
                    score = 1;
                }
                else {
                    MOVE nextMove = getAIsBestMove(tempBoard, !currentPlayerX);
                    score = - (nextMove.score);
                }

                // new move
                availableMovesAndScores[count] = new MOVE();
                availableMovesAndScores[count].row = i;
                availableMovesAndScores[count].col = j;
                availableMovesAndScores[count].score = score;
                if (score == 1) {
                    return availableMovesAndScores[count];
                }
                count++;
            }

    // shuffled the availableMovesAndScores array
    for (int i = count - 1; i > 0; i--) {
        int j = rd.nextInt(i + 1);
        MOVE tempMove = availableMovesAndScores[i];
        availableMovesAndScores[i] = availableMovesAndScores[j];
        availableMovesAndScores[j] = tempMove;
    }

    // sorted from high to low
    for (int i = 0; i < count - 1; i++)
        for (int j = i + 1; j < count; j++)
            if (availableMovesAndScores[i].score < availableMovesAndScores[j].score) {
                MOVE tempMove = availableMovesAndScores[i];
                availableMovesAndScores[i] = availableMovesAndScores[j];
                availableMovesAndScores[j] = tempMove;
            }

    // return the move
    return availableMovesAndScores[0];
}
</div>

4 – Ứng dụng nhỏ

Game Tic-Toe trên Playstore (Android).
https://play.google.com/store/apps/details?id=blog.pyimlife.a03_simpletictoe

Please give it a try and leave your comment.
Thank you!

Tham khảo:

[1] https://medium.freecodecamp.org/building-an-ai-algorithm-for-the-tic-tac-toe-challenge-29d4d5adee07