Giới thiệu
Cờ tướng là một môn thể thao khá phổ biến ở Việt Nam. Các bạn có thể bắt gặp các bàn cờ ở các con hẻm của mỗi góc phố. Hoặc là khi các bộ bàn ghế đá thì người mua cũng thường nhờ thợ khắc lên bàn cờ tướng để hàng xóm láng giềng giải trí ngày cuối tuần. Trong bài viết này, mình sẽ hướng dẫn step by step ứng dụng chơi game cờ tướng đơn giản với một chút AI. Hi vọng sẽ giúp được các bạn trên con đường thực hành máy học.
Các việc cần làm:
-
Tạo bàn cờ và sinh nước đi
-
Lượng giá bàn cờ
-
Áp dụng minimax
-
Áp dụng cắt tỉa alpha, beta
Bạn có thể chơi thử game cờ tướng mình có post ở đây: https://www.phamduytung.com/games/china_chess/
Bước 1: Tạo bàn cờ và sinh nước đi
Mình không có gỏi lắm trong việc thiết kế mấy icon cho mấy con tướng, sĩ, tượng. Ngoài ra, công việc chính của chúng ta là phần làm sao cho máy tự đánh được, nên phần này mình sẽ xài các open source có sẵn, lượn lờ một chút trên mạng thì mình đã lụm được cái bàn cờ ở link https://github.com/lengyanyu258/xiangqiboardjs và thư viện sinh nước đi xiangqi.js. Thư viện xiangqi.js đã có sẵn các hàm kiểm tra tính hợp lệ của nước đi, nên mình chỉ việc lấy ra rồi dùng thôi, khỏi mất công phải viết lại.
Bàn cờ được chia làm 2 đội, là đội đen (black, ký hiệu b) và đội đỏ (red , ký hiệu r), mỗi đội gồm 16 quân, bao gồm 1 con tướng (General hoặc king , ký hiệu k), 2 con sỹ (Advisor hoặc guards, ministers, ký hiệu là a), 2 con tượng (Elephants hoặc bishops - ký hiệu là b), 2 con mã (Horses hoặc knights - ký hiệu là n, do chữ k trùng với king là con tướng, nên người ta xài chữ n), 2 con xe (Chariot hoặc rooks - ký hiệu là r), 2 con pháo (canons, ký hiệu là c ), 5 con chốt (Soldiers , ký hiệu là p ( do con chốt ở cờ đen và cờ đỏ có phiên âm tiếng trung khác nhau, chốt cờ đen đọc gần giống chữ “zú” (“pawn” hoặc “private” - tiếng anh), còn chốt cờ đỏ đọc là bing (“soldier” - tiếng anh) )).
Tổng cộng, ta có tướng, sỹ, tượng, mã, xe, pháo, chốt, 7 loại quân, tương đương với 7 ký hiệu, tổ hợp với 2 đội là đỏ và đen, tổ hợp với nhau, ta xác định được
Để bắt đầu, chúng ta sẽ code một hàm random bước đi đơn giản. Hàm có nhiệm vụ lấy ngẫu nhiên một bước đi trong danh sách các bước có thể đi, sau đó máy sẽ đánh bước đi đó.
1
2
3function makeRandomMove () {
4 let possibleMoves = game.moves();
5
6 // game over
7 if (possibleMoves.length === 0) return; // Không còn nước nào có thể đi, end game
8
9 let randomIdx = Math.floor(Math.random() * possibleMoves.length); // bốc đại 1 nước đi trong danh sách các bước có thể đi
10 game.move(possibleMoves[randomIdx]);
11 board.position(game.fen());
12}
Do thuật toán chúng ta cho máy chạy khá là ngốc, nên nó đánh cũng hơi ngốc. :)
Bước 2: Hàm lượng giá
Dựa vào mức độ cơ động, tầm quang trọng của mỗi quân lính trên bàn cờ, chúng ta sẽ gán cho mỗi quân cờ một trọng số khác nhau thể hiện điều đó.
Ví dụ, chúng ta set các trọng số như sau:
tướng của ta là 900 điểm, tướng của đối thủ là -900 điểm
sỹ của ta là 20 điểm, sỹ của đối thủ là -20 điểm
tượng của ta là 20 điểm, tượng của đối thủ là -20 điểm
mã của ta là 40 điểm, mã của đối thủ là -40 điểm
xe của ta là 90 điểm, xe của đối thủ là -90 điểm
pháo của ta là 45 điểm, pháo của đối thủ là -45 điểm
chốt của ta là 15 điểm, chốt của đối thủ là -15 điểm
Hàm lượng giá ở trên khá ngây thơ, mọi quân cờ đều có điểm ngang nhau, không quan tâm vị trí đứng của nó.
Trên thực tế, chúng ta thấy rằng, con tướng ở vị trí trung tâm thường là an toàn nhất, một khi tướng leo lên lầu 1 hoặc leo lầu 2, nghĩa là con tướng có khả năng bị đột tử cao hơn, nên chúng ta phải tinh chỉnh lại điểm của con tướng trong trường hợp này.
Một ví dụ nữa là vị trí con mã, mã gần với thành của tướng địch hơn thì khả năng con xe chiếu bí tướng địch sẽ cao hơn con mã chưa qua sông.
Giá trị lượng giá cho cờ tướng, các bạn có thể tham khảo ở link https://github.com/markdirish/xiangqi/blob/master/evaluate.js
Chúng ta sẽ duyệt lần lượt từ trái qua phải, từ trên xuống dưới, tính điểm của bàn cờ hiện tại.
Hàm lượng giá của bàn cờ xét như sau:
1
2
3
4function evaluateBoard(board) {
5 var totalEvaluation = 0;
6 for (var i = 0; i < 10; i++) {
7 for (var j = 0; j < 9; j++) {
8 totalEvaluation = totalEvaluation + getPieceValue(board[i][j], i ,j);
9 }
10 }
11 return totalEvaluation;
12}
13
14
15
16function getPieceValue(piece, x, y) {
17 if (piece === null) {
18 return 0;
19 }
20 var getAbsoluteValue = function (piece, isRed, x ,y) {
21 if (piece.type === 'p') { //chốt
22 return 15 + ( isRed ? pEvalRed[x][y] : pEvalBlack[x][y] );
23 } else if (piece.type === 'r') { //Xe
24 return 90 +( isRed ? rEvalRed[x][y] : rEvalBlack[x][y] );
25 } else if (piece.type === 'c') { //pháo
26 return 45 +( isRed ? cEvalRed[x][y] : cEvalBlack[x][y] );
27 } else if (piece.type === 'n') { // mã
28 return 40 +( isRed ? nEvalRed[x][y] : nEvalBlack[x][y] );
29 } else if (piece.type === 'b') { // tượng
30 return 20 +( isRed ? bEvalRed[x][y] : bEvalBlack[x][y] );
31 } else if (piece.type === 'a') { // sỹ
32 return 20 +( isRed ? aEvalRed[x][y] : aEvalBlack[x][y] );
33 } else if (piece.type === 'k') { // tướng
34 return 900 +( isRed ? kEvalRed[x][y] : kEvalBlack[x][y] );
35 }
36 throw "Unknown piece type: " + piece.type;
37 };
38
39 var absoluteValue = getAbsoluteValue(piece, piece.color === 'r', x ,y);
40 return piece.color === 'r' ? absoluteValue : -absoluteValue;
41}
Bây giờ, chúng ta chỉ cần duyệt qua toàn bộ các nước có thể đi, tính xem nước đi nào có điểm số là lớn nhất, thì máy sẽ đi theo nước đi đó.
1
2
3function getBestMove(game) {
4
5var newGameMoves = game.moves();
6var bestMove = null;
7// set đại một số âm vô hạn
8var bestValue = -9999;
9
10for (var i = 0; i < newGameMoves.length; i++) {
11 var newGameMove = newGameMoves[i];
12 game.move(newGameMove);
13
14 var boardValue = -evaluateBoard(game.board())
15 game.undo();
16 if (boardValue > bestValue) {
17 bestValue = boardValue;
18 bestMove = newGameMove
19 }
20}
21
22return bestMove;
23
24};
Vì vậy, ngoài việc xét điểm cho các loại quân, chúng ta sẽ có một bảng xét điểm cho các con
Kết quả có vẻ tốt hơn so với việc random bước đi trước đó, nhưng thuật toán vẫn còn hơi dốt dốt xíu, do máy chỉ tính 1 nước đi và chọn ra nước đi tốt nhất. Nên máy chưa có cái nhìn dài hơn. Có nhiều cách để cho máy có thể có góc nhìn xa hơn về thế cục của bàn cờ, một trong các cách được giới thiệu ở đây là sử dụng minimax
Bước 3. Tìm kiếm cây sử dụng minimax
Thuật toán minimax thuộc nhóm duyệt theo chiều sâu (depth first search). Hai người chơi, một người được gọi là MAX, người còn lại gọi là MIN. Thuật toán được thiết kế để tìm nước đi tối ưu cho người MAX. Người MAX sẽ giữ node gốc, lần lượt duyệt đệ quy qua tất cả các node con theo chiều sâu nhất định đến khi duyệt qua tất cả các node hoặc là tìm được một đường đi mà đạt MAX.
Chi tiết hơn, người MAX sẽ đi đầu tiên. Nhiệm vụ của MAX là tìm nước đi sao cho điểm số của mình là cao nhất, nhiệm vụ của MIN là tìm nước đi để cực tiểu hoá điểm số của MAX.
Các bạn có thể đọc thêm ở link https://en.wikipedia.org/wiki/Minimax.
Để triển khai minimax, đầu tiên, chúng ta sẽ sửa lại hàm getBestMove ở trên, thay vì gọi lượng giá bàn cờ evaluateBoard, chúng ta sẽ gọi hàm minimax
1
2
3function minimaxRoot(depth, game, isMaximisingPlayer) {
4 var newGameMoves = game.moves();
5 var bestMove = -9999;
6 var bestMoveFound;
7
8 for(var i = 0; i < newGameMoves.length; i++) {
9 var newGameMove = newGameMoves[i]
10 game.move(newGameMove);
11 var value = minimax(depth - 1, game, !isMaximisingPlayer);
12 game.undo();
13 if(value >= bestMove) {
14 bestMove = value;
15 bestMoveFound = newGameMove;
16 }
17 }
18 return bestMoveFound;
19}
với hàm minimax cũng cùng ý tưởng với hàm getBestMove ở trên, nhưng ta sẽ gọi đệ quy, luân phiên tính điểm máy, sau đó tính điểm người … theo độ sâu ta đã thiết lập, để tìm ra đường đi có số điểm là lớn nhất.
1
2function minimax (depth, game, isMaximisingPlayer) {
3 if (depth === 0) {
4 return -evaluateBoard(game.board());
5 }
6 var newGameMoves = game.moves();
7 if (isMaximisingPlayer) {
8 var bestMove = -9999;
9 for (var i = 0; i < newGameMoves.length; i++) {
10 game.move(newGameMoves[i]);
11 bestMove = Math.max(bestMove, minimax(depth - 1, game, !isMaximisingPlayer));
12 game.undo();
13 }
14 return bestMove;
15 } else {
16 var bestMove = 9999;
17 for (var i = 0; i < newGameMoves.length; i++) {
18 game.move(newGameMoves[i]);
19 bestMove = Math.min(bestMove, minimax(depth - 1, game, !isMaximisingPlayer));
20 game.undo();
21 }
22 return bestMove;
23 }
24};
Thuật toán này hoạt động khá hiệu quả, nhưng có một điểm yếu là nó sẽ vét cạn toàn bộ các trường hợp để tìm ra đường đi tối ưu nhất. Vì vậy, với giá trị độ sâu càng lớn thì thuật toán chạy càng chậm.
Bước 4: Cắt tỉa Alpha - Beta
Cắt tỉa Alpha - Beta là một phương pháp tối ưu hoá của thuật toán minimax, phương pháp này giúp chúng ta bỏ qua một vài nhánh trong quá trình tìm kiếm, làm giới hạn phạm vi tìm kiếm, giúp mô hình hoạt động nhanh hơn.
Thuật toán sẽ hoạt động hiệu quả hơn nếu những bước tìm kiếm đầu tiên là những nước đi tốt nhất :)
Hàm minimax với alpla, beta được viết lại như sau
1
2
3
4function minimax(depth, game, alpha, beta, isMaximisingPlayer) {
5 positionCount++;
6 if (depth === 0) {
7 return -evaluateBoard(game.board());
8 }
9
10 var newGameMoves = game.moves();
11
12 if (isMaximisingPlayer) {
13 var bestMove = -9999;
14 for (var i = 0; i < newGameMoves.length; i++) {
15 game.moves(newGameMoves[i]);
16 bestMove = Math.max(bestMove, minimax(depth - 1, game, alpha, beta, !isMaximisingPlayer));
17 game.undo();
18 alpha = Math.max(alpha, bestMove);
19 if (beta <= alpha) {
20 return bestMove;
21 }
22 }
23 return bestMove;
24 } else {
25 var bestMove = 9999;
26 for (var i = 0; i < newGameMoves.length; i++) {
27 game.moves(newGameMoves[i]);
28 bestMove = Math.min(bestMove, minimax(depth - 1, game, alpha, beta, !isMaximisingPlayer));
29 game.undo();
30 beta = Math.min(beta, bestMove);
31 if (beta <= alpha) {
32 return bestMove;
33 }
34 }
35 return bestMove;
36 }
37}
Cảm ơn các bạn đã theo dõi bài viết. Xin chào và hẹn gặp lại các bạn ở bài viết kế tiếp.
Các bạn có thể chơi game ở đây nha , link https://www.phamduytung.com/games/china_chess/
Mình sẽ update dần giao diện để cho game trở nên đẹp đẹp hơn.
Comments