Cờ vua Android đấu máy: negamax, alpha–beta và AI chạy nền

Viết máy đánh ngoại tuyến có ba mức khó, tìm sâu dần, ngân sách thời gian và cơ chế chặn kết quả từ ván cũ. Các tệp nguồn, Gradle wrapper, hướng dẫn chạy và kiểm thử đi kèm trong ZIP.

Xem trọn bộ 5 dự án Android · Tải dự án Android đầy đủ (.zip) · Tải APK debug 1.1 để cài thử

1. AI của game cần giải quyết điều gì?

Dự án này cho một người cầm Trắng đấu với máy Đen trên cùng điện thoại, không cần Internet. AI ở đây là tìm kiếm trong cây nước đi và đánh giá vị trí, không phải mô hình ngôn ngữ hay mạng nơ-ron được huấn luyện. Cách tiếp cận giúp quan sát được vì sao máy chọn nước, đo số nút đã duyệt và thay từng giả thiết mà không phụ thuộc dịch vụ bên ngoài.

Tải ZIP ở đầu bài, giải nén rồi mở thư mục có settings.gradle bằng Android Studio. Trong SDK Manager cài Android SDK Platform 35; chọn Gradle JDK 17. Dự án khóa Android Gradle Plugin 8.6.1 và Gradle 8.7, minSdk 26. Chờ Sync rồi chạy module app trên Android 8.0 trở lên. Lần đầu cần mạng để tải công cụ; bản ứng dụng sau khi cài hoạt động ngoại tuyến. Không cần khóa API, .NET hay dịch vụ AI trả phí.

Windows:       gradlew.bat assembleDebug
Linux/macOS:   chmod +x gradlew
               ./gradlew assembleDebug
APK: app/build/outputs/apk/debug/app-debug.apk

Nếu báo không tìm thấy SDK, mở lại dự án bằng Android Studio để tạo local.properties theo máy; không chép đường dẫn SDK từ máy khác. Nếu Gradle báo sai phiên bản Java, kiểm tra Gradle JDK thay vì chỉ kiểm tra lệnh java -version. Cấu hình này là một bộ phiên bản tương thích để học, không khẳng định là phiên bản Android mới nhất.

2. Đọc dự án và chạy ván đầu tiên

Đọc ChessEngine.java để hiểu hợp đồng legalMoves/after/evaluate, sau đó mở ChessAi.java và cuối cùng ChessActivity.java. Trên màn hình, chạm quân Trắng rồi chạm ô vàng; khi máy suy nghĩ, không nhận nước đi của người. Dễ/Vừa/Khó đặt độ sâu tối đa 1/2/3 ply và ngân sách 300/700/1200 ms. Một ply là một lượt của một bên; 2 ply không phải hai nước của mỗi bên.

Số ply hiển thị là độ sâu đã tìm xong, không chỉ mức người dùng yêu cầu. Thiết bị chậm có thể hết ngân sách ở mức 2 dù đã chọn Khó. Điều đó là hành vi được thiết kế: phản hồi kịp thời và dùng kết quả hoàn chỉnh gần nhất, thay vì lấy kết quả thiên lệch từ một vòng chỉ mới xét vài nước gốc.

3. Từ minimax tới negamax

Giả sử điểm của một vị trí đo theo bên sắp đi. Nếu đổi sang đối phương thì lợi thế đổi dấu, nên giá trị một nước bằng số đối của giá trị vị trí con. Negamax gom hai nhánh tối đa/tối thiểu của minimax thành một quy tắc. Trong engine, material và vị trí quân được cộng theo Trắng rồi nhân với side, đúng với quy ước này. Nếu quên đổi dấu ở một lớp, máy có thể chủ động tặng Hậu dù bảng giá quân hoàn toàn đúng.

value = -negamax(child, depth - 1, -beta, -alpha, ply + 1);
best = Math.max(best, value);
alpha = Math.max(alpha, value);
if (alpha >= beta) break;

Alpha là mức tốt nhất đã biết cho bên hiện tại trong cửa sổ đang xét; beta là ngưỡng khiến đối phương không cần chọn nhánh này nữa. Cắt tỉa không đổi nghiệm minimax ở độ sâu cố định khi triển khai đúng. Nó chỉ bỏ những nhánh không thể cải thiện quyết định trong cửa sổ. Thứ tự duyệt ảnh hưởng số nút và thời gian, không biến nước bất hợp lệ thành hợp lệ.

4. Điểm cuối ván và hàm đánh giá

Trước khi đánh giá vật chất ở độ sâu 0, chương trình kiểm tra hết nước. Bị chiếu và không còn nước là thua, điểm gần −100000; không bị chiếu và hết nước trong cờ vua là hòa. Thành phần + ply trong điểm thua làm máy ưu tiên thắng sớm và trì hoãn thua khi các lựa chọn đều dẫn đến cùng loại kết quả. Điểm chiếu hết phải lớn hơn mọi chênh lệch vật chất có thể có.

Hàm đánh giá bản mẫu dùng giá trị quân, mức tiến của Tốt và ưu tiên trung tâm đơn giản. Nó đủ để biểu diễn một máy đánh có định hướng nhưng chưa hiểu đầy đủ an toàn Vua, cấu trúc Tốt, tàn cuộc hay chiến lược dài hạn. Một máy bỏ quân ở đường chân trời không nhất thiết sai alpha–beta: cây có thể dừng ngay trước nước bắt lại. Đây là lý do nên thêm quiescence như một bài tiếp theo, sau khi bộ luật ổn định.

5. Tìm sâu dần và giới hạn thời gian

Iterative deepening giải lần lượt từ độ sâu 1 đến mức yêu cầu. Chỉ sau khi xét xong mọi nước gốc ở một mức mới cập nhật completedMove/completedDepth. Nếu hết giờ hoặc luồng bị yêu cầu ngắt, vòng hiện tại dừng, giữ kết quả của vòng trước. Khi chưa hoàn thành cả mức 1, fallback là nước hợp lệ đầu tiên; giao diện sẽ báo 0 ply thay vì ngụ ý máy đã tìm đủ một mức.

Dùng System.nanoTime cho hạn tìm kiếm vì đây là đo khoảng thời gian, không phải lịch ngày giờ. Kiểm tra deadline ở các nút và giữa các nước gốc. Ngân sách là giới hạn mềm: một phép sinh toàn bộ nước hoặc lịch của hệ điều hành vẫn có thể làm thời gian thực tế vượt một ít. Không nên hứa phản hồi đúng tuyệt đối 700 ms trên mọi điện thoại.

Sắp xếp ưu tiên nước bắt quân và phong cấp giúp có cận tốt sớm. Heuristic hiện dựa trên loại quân và phần thưởng phong cấp, chưa phải bảng trao đổi tĩnh hoàn chỉnh. Muốn so hai heuristic, dùng cùng tập vị trí, cùng độ sâu và đo cả số nút lẫn lựa chọn nước; chỉ so thời gian của hai lần chơi ngẫu nhiên không đủ cơ sở.

6. Luồng nền và kết quả AI đã cũ

Activity tạo ExecutorService một luồng. Khi máy đến lượt, nó giữ một ảnh chụp bất biến và token thế hệ, rồi gửi công việc tìm kiếm. Kết quả quay lại main thread chỉ được áp dụng nếu Activity còn sống, đang được tiếp tục, token chưa đổi và vị trí vẫn đúng ảnh chụp ban đầu. Chỉ kiểm tra “máy đã xong” là thiếu vì người dùng có thể bấm Ván mới trong lúc máy tính.

final GamePosition snapshot = position;
final int token = ++generation;
job = worker.submit(() -> {
    ChessAi.Result r = new ChessAi().choose(snapshot, 3, 1200);
    runOnUiThread(() -> {
        if (token != generation || position != snapshot) return;
        // Mã đầy đủ còn kiểm tra vòng đời và nước hợp lệ.
    });
});

Khi onPause, hủy Future và tăng generation. Khi onResume, nếu vẫn đến lượt Đen thì khởi chạy lại từ vị trí đã lưu. Đi lại khôi phục tới lượt người; các kết quả đang bay từ lượt cũ bị chặn bằng token. Thread interruption giúp dừng tính toán, còn token bảo vệ giao diện ngay cả khi việc hủy chưa được luồng nền quan sát.

7. Mã nguồn AI và kiểm thử quyết định

package vn.kienutt.chess;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;

/** Negamax + alpha-beta, iterative deepening, time budget and cancellation. */
public final class ChessAi {
  public static final class Result {
    public final Move move;
    public final int depth, score;
    public final long nodes;

    Result(Move m, int d, int s, long n) {
      move = m;
      depth = d;
      score = s;
      nodes = n;
    }
  }

  private static final int MATE = 100000, INF = 1000000;
  private long deadline, nodes;

  private static final class Stop extends RuntimeException {
    Stop() {
      super(null, null, false, false);
    }
  }

  private void budget() {
    if (Thread.currentThread().isInterrupted() || System.nanoTime() - deadline >= 0)
      throw new Stop();
  }

  private int order(GamePosition p, Move m) {
    return Math.abs(p.pieceAt(m.to)) * 100 + m.promotion * 80;
  }

  private List<Move> ordered(GamePosition p, List<Move> moves) {
    List<Move> copy = new ArrayList<>(moves);
    copy.sort(Comparator.comparingInt((Move m) -> order(p, m)).reversed());
    return copy;
  }

  private int negamax(GamePosition p, int depth, int alpha, int beta, int ply) {
    budget();
    nodes++;
    List<Move> moves = p.legalMoves();
    if (moves.isEmpty()) return p.inCheck() || p.lossOnStalemate() ? -MATE + ply : 0;
    if (p.drawn()) return 0;
    if (depth == 0) return p.evaluate();
    int best = -INF;
    for (Move m : ordered(p, moves)) {
      int value = -negamax(p.after(m), depth - 1, -beta, -alpha, ply + 1);
      if (value > best) best = value;
      if (value > alpha) alpha = value;
      if (alpha >= beta) break;
    }
    return best;
  }

  public Result choose(GamePosition p, int maxDepth, int millis) {
    if (maxDepth < 1 || millis < 1) throw new IllegalArgumentException("Ngân sách không hợp lệ");
    deadline = System.nanoTime() + millis * 1000000L;
    nodes = 0;
    List<Move> roots = p.legalMoves();
    if (roots.isEmpty() || p.drawn()) return new Result(null, 0, 0, nodes);
    Move completedMove = roots.get(0);
    int completedDepth = 0, completedScore = 0;
    for (int depth = 1; depth <= maxDepth; depth++) {
      Move best = null;
      int value = -INF, alpha = -INF;
      try {
        for (Move m : ordered(p, roots)) {
          budget();
          int v = -negamax(p.after(m), depth - 1, -INF, -alpha, 1);
          if (v > value) {
            value = v;
            best = m;
          }
          alpha = Math.max(alpha, v);
        }
        completedMove = best;
        completedDepth = depth;
        completedScore = value;
      } catch (Stop stop) {
        break;
      }
    }
    return new Result(completedMove, completedDepth, completedScore, nodes);
  }
}

ZIP chứa cả UI, engine và kiểm thử. Với AI, các bất biến quan trọng là: nước trả về thuộc legalMoves, vị trí đầu vào không bị thay đổi, vị trí kết thúc không phát sinh nước, và độ sâu công bố chỉ tăng sau vòng hoàn chỉnh. Các ca engine/perft trong bài trước vẫn phải chạy sau mỗi lần tối ưu. Một engine tìm rất nhanh trên cây sai luật không tạo ra AI đáng tin cậy.

8. Thực nghiệm nhỏ để học về độ phức tạp

Bài mở rộng thứ nhất là lưu nước tốt nhất của vòng trước để đưa lên đầu ở vòng sau. Thứ hai là transposition table: khóa phải bao gồm bên đến lượt, quyền nhập thành, en passant và đủ trạng thái cho chính sách hòa; lưu thêm loại cận, độ sâu và điểm. Thứ ba là tập thế chiến thuật có đáp án để phân biệt tối ưu tốc độ với cải thiện chất lượng. Không bỏ lịch sử hòa khỏi khóa chỉ vì hai bàn nhìn giống nhau.

Bản 1.1 đã dựng APK debug bằng bộ công cụ Android đầy đủ; lint không có lỗi. Dự án này đã qua 2 ca JUnit/Robolectric, gồm mở màn hình, pause/resume và tái tạo Activity trên Android API 35 mô phỏng trong JVM. Hai dự án quản lý còn kiểm thử trực tiếp SQLiteOpenHelper với SQLite native. Chưa kiểm tra trên điện thoại thật; hãy chạy thêm checklist thiết bị trong README, nhất là thao tác cảm ứng, cỡ chữ và độ trễ AI.

Đọc thêm tài liệu gốc: bộ công cụ AGP 8.6, vẽ Custom View với Canvas và SQLite trên Android. Các lớp và dữ liệu trong bài được xây dựng cho thực hành, không phải mã của các tổ chức được dẫn nguồn.

Xem nền tảng trong bài xây dựng bộ luật cờ vua. Quy ước hòa và các giới hạn FIDE của dự án được nêu ở bài đó và trong README.

9. Chạy lại kiểm thử và dựng APK

Mở Terminal tại thư mục dự án. Trên Windows chạy lệnh dưới; trên Linux/macOS thay gradlew.bat bằng ./gradlew. assembleDebug tạo APK; lintDebug kiểm tra tĩnh; testDebugUnitTest chạy các ca JUnit và Robolectric. Ba việc này bổ sung cho nhau, không đồng nghĩa đã thử trên mọi điện thoại.

gradlew.bat assembleDebug lintDebug testDebugUnitTest
# APK: app/build/outputs/apk/debug/app-debug.apk
# Test: app/build/reports/tests/testDebugUnitTest/index.html

ZIP có đầy đủ mã kiểm thử trong app/src/test/java và kiểm tra logic/SQL ở thư mục tests. Chỉnh một luật hoặc một truy vấn, chạy lại bộ ca liên quan trước khi dựng APK mới. Thư viện kiểm thử chỉ dùng lúc phát triển, không được đóng vào ứng dụng. APK cung cấp trên trang là bản debug học tập.