Cách làm cho trò chơi Tic Tac Toe của bạn trở nên bất bại bằng cách sử dụng thuật toán minimax

Tôi đã vật lộn hàng giờ để lướt qua các hướng dẫn, xem video và đập đầu vào bàn cố gắng xây dựng trò chơi Tic Tac Toe bất bại với Trí tuệ nhân tạo đáng tin cậy. Vì vậy, nếu bạn đang trải qua một hành trình tương tự, tôi muốn giới thiệu với bạn thuật toán Minimax.

Giống như một người chơi cờ chuyên nghiệp, thuật toán này nhìn thấy trước một vài bước và đặt mình vào vị trí của đối thủ. Nó tiếp tục chơi phía trước cho đến khi nó đạt đến sự sắp xếp cuối cùng của bàn cờ ( trạng thái kết thúc) dẫn đến hòa, thắng hoặc thua. Khi ở trạng thái cuối, AI sẽ ấn định điểm dương tùy ý (+10) cho trận thắng, điểm âm (-10) cho trận thua hoặc điểm trung lập (0) cho trận hòa.

Đồng thời, thuật toán đánh giá các nước đi dẫn đến trạng thái cuối dựa trên lượt của người chơi. Nó sẽ chọn nước đi có điểm tối đa khi đến lượt của AI và chọn nước đi có điểm tối thiểu khi đến lượt của người chơi. Sử dụng chiến lược này, Minimax tránh bị thua trước người chơi.

Hãy thử nó cho chính mình trong trò chơi sau đây, tốt hơn là sử dụng trình duyệt Chrom.

Thuật toán Minimax có thể được định nghĩa tốt nhất là một hàm đệ quy thực hiện những điều sau:

  1. trả về một giá trị nếu trạng thái đầu cuối được tìm thấy (+10, 0, -10)
  2. đi qua các điểm có sẵn trên bảng
  3. gọi hàm minimax trên mỗi vị trí có sẵn (đệ quy)
  4. đánh giá các giá trị trả về từ các lệnh gọi hàm
  5. và trả lại giá trị tốt nhất

Nếu bạn chưa quen với khái niệm đệ quy, tôi khuyên bạn nên xem video này từ CS50 của Harvard.

Để hoàn toàn nắm bắt được quy trình suy nghĩ của Minimax, hãy triển khai nó bằng mã và xem nó hoạt động trong hai phần sau.

Mã tối thiểu

Đối với hướng dẫn này, bạn sẽ làm việc với trạng thái gần kết thúc của trò chơi được hiển thị trong hình 2 bên dưới. Vì minimax đánh giá mọi trạng thái của trò chơi (hàng trăm nghìn), trạng thái gần kết thúc cho phép bạn theo dõi các lệnh gọi đệ quy của minimax dễ dàng hơn (9).

Đối với hình sau, giả sử AI là X và người chơi là O.

Để làm việc với bảng Ti Tac Toe dễ dàng hơn, bạn nên xác định nó là một mảng có 9 mục. Mỗi mục sẽ có chỉ mục của nó như một giá trị. Điều này sẽ hữu ích sau này. Bởi vì bảng trên đã có sẵn một số nước đi X và Y, chúng ta hãy xác định bàn cờ với các nước đi X và Y đã có trong đó ( origBoard ).

var origBoard = ["O",1,"X","X",4,"X",6,"O","O"];

Sau đó tuyên bố aiPlayerhuPlayer biến và đặt chúng vào “X” và “O” tương ứng .

Ngoài ra, bạn cần một hàm tìm kiếm các kết hợp chiến thắng và trả về true nếu tìm thấy một và một hàm liệt kê các chỉ số của các điểm có sẵn trong bảng.

/* the original board O | | X --------- X | | X --------- | O | O */ var origBoard = [“O”,1 ,”X”,”X”,4 ,”X”, 6 ,”O”,”O”]; // human var huPlayer = “O”; // ai var aiPlayer = “X”; // returns list of the indexes of empty spots on the board function emptyIndexies(board){ return board.filter(s => s != "O" && s != "X"); } // winning combinations using the board indexies function winning(board, player){ if ( (board[0] == player && board[1] == player && board[2] == player) || (board[3] == player && board[4] == player && board[5] == player) || (board[6] == player && board[7] == player && board[8] == player) || (board[0] == player && board[3] == player && board[6] == player) || (board[1] == player && board[4] == player && board[7] == player) || (board[2] == player && board[5] == player && board[8] == player) || (board[0] == player && board[4] == player && board[8] == player) || (board[2] == player && board[4] == player && board[6] == player) ) { return true; } else { return false; } }

Bây giờ chúng ta hãy đi sâu vào các phần tốt bằng cách xác định hàm Minimax với hai đối số newBoardplayer . Sau đó, bạn cần tìm chỉ mục của các điểm có sẵn trong bảng và đặt chúng thành một biến có tên là availSpots .

// the main minimax function function minimax(newBoard, player){ //available spots var availSpots = emptyIndexies(newBoard);

Ngoài ra, bạn cần kiểm tra các trạng thái đầu cuối và trả về một giá trị tương ứng. Nếu O thắng, bạn nên trả về -10, nếu X thắng, bạn nên trả về +10. Bên cạnh đó, nếu chiều dài của availableSpots mảng là số không, điều đó có nghĩa không có nhiều chỗ để chơi, các trò chơi đã dẫn đến một cà vạt, và bạn phải trả lại bằng không.

 // checks for the terminal states such as win, lose, and tie //and returning a value accordingly if (winning(newBoard, huPlayer)){ return {score:-10}; } else if (winning(newBoard, aiPlayer)){ return {score:10}; } else if (availSpots.length === 0){ return {score:0}; }

Tiếp theo, bạn cần thu thập điểm của từng chỗ trống để đánh giá sau. Do đó, hãy tạo một mảng gọi là di chuyển và lặp qua các điểm trống trong khi thu thập chỉ số và điểm của mỗi bước di chuyển trong một đối tượng được gọi là di chuyển .

Sau đó, đặt số chỉ mục của vị trí trống đã được lưu trữ dưới dạng số trong origBoard thành thuộc tính chỉ mục của đối tượng di chuyển . Sau đó, thiết lập các chỗ trống trên newboard để các cầu thủ hiện tại và gọi minimax chức năng với máy nghe nhạc khác và mới được thay đổi newboard . Tiếp theo, bạn nên lưu trữ đối tượng kết quả từ lệnh gọi hàm minimax bao gồm thuộc tính điểm vào thuộc tính điểm của đối tượng di chuyển .

Nếu hàm minimax không tìm thấy trạng thái đầu cuối, nó sẽ tiếp tục đệ quy từng cấp độ sâu hơn vào trò chơi. Đệ quy này xảy ra cho đến khi nó đạt đến trạng thái cuối và trả về điểm một khi tăng một cấp.

Cuối cùng, Minimax đặt lại newBoard về những gì trước đó và đẩy đối tượng di chuyển vào mảng di chuyển .

// an array to collect all the objects var moves = []; // loop through available spots for (var i = 0; i < availSpots.length; i++){ //create an object for each and store the index of that spot var move = {}; move.index = newBoard[availSpots[i]]; // set the empty spot to the current player newBoard[availSpots[i]] = player; /*collect the score resulted from calling minimax on the opponent of the current player*/ if (player == aiPlayer){ var result = minimax(newBoard, huPlayer); move.score = result.score; } else{ var result = minimax(newBoard, aiPlayer); move.score = result.score; } // reset the spot to empty newBoard[availSpots[i]] = move.index; // push the object to the array moves.push(move); }

Sau đó, thuật toán minimax cần phải đánh giá là tốt nhất di chuyển trong di chuyển mảng. Nó nên chọn di chuyển với số điểm cao nhất khi AI đang chơi và di chuyển với số điểm thấp nhất khi con người đang phát. Do đó, nếu người chơiaiPlayer , nó đặt một biến gọi là bestScore đến một số lượng rất thấp và vòng qua động thái mảng, nếu một động thái có một cao điểm hơn bestScore , các cửa hàng thuật toán di chuyển . Trong trường hợp có các nước đi có số điểm tương tự nhau thì chỉ lưu nước đi đầu tiên.

Quá trình đánh giá tương tự cũng xảy ra khi người chơihuPlayer , nhưng lần này bestScore sẽ được đặt thành số cao và Minimax tìm kiếm nước đi có điểm thấp nhất để lưu trữ.

Cuối cùng, Minimax trả về đối tượng được lưu trữ trong bestMove .

// if it is the computer's turn loop over the moves and choose the move with the highest score var bestMove; if(player === aiPlayer){ var bestScore = -10000; for(var i = 0; i  bestScore){ bestScore = moves[i].score; bestMove = i; } } }else{ // else loop over the moves and choose the move with the lowest score var bestScore = 10000; for(var i = 0; i < moves.length; i++){ if(moves[i].score < bestScore){ bestScore = moves[i].score; bestMove = i; } } } // return the chosen move (object) from the moves array return moves[bestMove]; }
Đó là nó cho hàm minimax. :) bạn có thể tìm thấy thuật toán trên trên github và codepen. Chơi xung quanh với các bảng khác nhau và kiểm tra kết quả trong bảng điều khiển.

Trong phần tiếp theo, chúng ta hãy xem qua từng dòng mã để hiểu rõ hơn về cách hàm minimax hoạt động với bảng được hiển thị trong hình 2.

Mức tối thiểu trong hành động

Sử dụng hình sau, hãy lần lượt theo dõi các lệnh gọi hàm của thuật toán ( FC ).

Lưu ý: Trong hình 3, các số lớn đại diện cho mỗi lệnh gọi hàm và các cấp cho biết thuật toán đang chơi bao nhiêu bước trước trò chơi.

1. origBoard aiPlayer được cung cấp cho thuật toán. Thuật toán tạo danh sách ba điểm trống mà nó tìm thấy, kiểm tra trạng thái đầu cuối và lặp lại mọi điểm trống bắt đầu từ điểm đầu tiên. Sau đó, nó thay đổi newBoard bằng cách đặt aiPlayer vào vị trí trống đầu tiên.Sau đó,nó gọi chính nó với newBoardhuPlayer và đợi FC trả về một giá trị.

2. Trong khi FC đầu tiên vẫn đang chạy, FC thứ hai bắt đầu bằng cách lập danh sách hai điểm trống mà nó tìm thấy, kiểm tra trạng thái đầu cuối và lặp qua vị trí trống bắt đầu từ điểm đầu tiên. Sau đó, nó thay đổi newBoard bằng cách đặt huPlayer vào vị trí trống đầu tiên.Sau đónó gọi chính nó với newBoardaiPlayer và đợi FC trả về một giá trị.

3. Cuối cùng, thuật toán tạo một danh sách các điểm trống và tìm ra chiến thắng cho người chơi sau khi kiểm tra trạng thái cuối. Do đó, nó trả về một đối tượng có thuộc tính điểm và giá trị là -10.

Vì FC thứ hai liệt kê hai vị trí trống, Minimax thay đổi NewBoard bằng cách đặt huPlayer vào vị trí trống thứ hai. Sau đó, nó tự gọi nó với bảng mới và aiPlayer .

4. Thuật toán tạo danh sách các điểm trống và tìm chiến thắng cho người chơi sau khi kiểm tra trạng thái cuối. Do đó, nó trả về một đối tượng có thuộc tính điểm và giá trị là -10.

Trên FC thứ hai, thuật toán thu thập các giá trị đến từ các cấp thấp hơn (FC thứ 3 và thứ 4). Vì lượt của huPlayer dẫn đến hai giá trị, nên thuật toán chọn giá trị thấp nhất trong hai giá trị. Bởi vì cả hai giá trị đều giống nhau, nó chọn giá trị đầu tiên và trả về giá trị FC đầu tiên. Tại thời điểm này, FC đầu tiên đã đánh giá điểm của aiPlayer di chuyển ở vị trí trống đầu tiên. Tiếp theo, nó thay đổi newBoard bằng cách đặt aiPlayer vào vị trí trống thứ hai. Sau đó, nó tự gọi nó với newBoard huPlayer .

5. Ở FC thứ năm, Thuật toán lập danh sách các điểm trống và tìm ra chiến thắng cho người chơi sau khi kiểm tra các trạng thái cuối. Do đó, nó trả về một đối tượng có thuộc tính điểm và giá trị là +10.

Sau đó, FC đầu tiên tiếp tục bằng cách thay đổi NewBoard và đặt aiPlayer vào vị trí trống thứ ba. Sau đó, nó tự gọi nó với bảng mới và huPlayer .

6. FC thứ 6 bắt đầu bằng cách lập danh sách hai điểm trống mà nó tìm thấy, kiểm tra trạng thái đầu cuối và lặp qua hai điểm trống bắt đầu từ điểm đầu tiên. Sau đó, nó thay đổi newBoard bằng cách đặt huPlayer vào vị trí trống đầu tiên.Sau đó,it calls itself with newBoard and the aiPlayer and waits for the FC to return a score.

7. Now the algorithm is two level deep into the recursion. It makes a list of the one empty spot it finds, checks for terminal states, and changes the newBoard by placing the aiPlayer in the empty spot.After that,it calls itself with newBoard and the huPlayer and waits for the FC to return a score so it can evaluate it.

8. On the 8th FC,thuật toán tạo một danh sách trống các điểm trống và tìm phần thắng cho aiPlayer sau khi kiểm tra trạng thái đầu cuối. Do đó, nó trả về một đối tượng có thuộc tính điểm và giá trị là +10 một cấp (FC thứ 7).

FC thứ 7 chỉ nhận được một giá trị dương từ các cấp độ thấp hơn (FC thứ 8). Vì lượt của aiPlayer dẫn đến giá trị đó, nên thuật toán cần trả về giá trị cao nhất mà nó đã nhận được từ các cấp thấp hơn. Do đó, nó trả về giá trị dương duy nhất (+10) khi tăng một cấp (FC thứ 6). Vì FC thứ 6 liệt kê hai vị trí trống, Minimax thay đổi newBoard bằng cách đặt huPlayer vào vị trí trống thứ hai. Sau đó, tự gọi nó với bảng mới và aiPlayer .

9. Next, the algorithm makes a list of the empty spots, and finds a win for the aiPlayer after checking for terminal states. Therefore, it returns an object with score properties and value of +10.

Tại thời điểm này, 6 FC phải lựa chọn giữa điểm số (+10) được gửi từ FC thứ 7 (trả về ban đầu từ FC 8) và điểm số (-10) được trả về từ FC thứ 9. Vì lượt của huPlayer dẫn đến hai giá trị trả về đó, nên thuật toán tìm điểm tối thiểu (-10) và trả về điểm đó như một đối tượng chứa các thuộc tính điểm và chỉ số. Cuối cùng, cả ba nhánh của FC đầu tiên đã được đánh giá (-10, +10, -10). Nhưng vì lượt của aiPlayer dẫn đến các giá trị đó, thuật toán trả về một đối tượng có chứa điểm cao nhất (+10) và chỉ số của nó (4).

Trong trường hợp trên, Minimax kết luận rằng việc di chuyển X vào giữa bàn cờ sẽ mang lại kết quả tốt nhất. :)

Kết thúc!

Bây giờ bạn có thể hiểu logic đằng sau thuật toán Minimax. Sử dụng logic này, hãy thử tự triển khai thuật toán Minimax hoặc tìm mẫu trên trêngithub hoặc codepen và tối ưu hóa nó.

Cảm ơn vì đã đọc! Nếu bạn thích câu chuyện này, đừng quên chia sẻ nó trên phương tiện truyền thông xã hội.

Đặc biệt cảm ơn Tuba Yilmaz, Rick McGavin và Javid Askerov đã đánh giá bài viết này.