gobang/lib/ai/ai.dart

import 'package:gobang/constants.dart';
import 'package:gobang/flyweight/chess_flyweight_factory.dart';
import 'package:gobang/flyweight/position.dart';

/// 五子棋 AI：五元组评分算法
/// 参考：https://blog.csdn.net/u011587401/article/details/50877828
class Ai {
  Ai._() {
    chessboard = List.generate(
      kBoardSize,
      (_) => List.filled(kBoardSize, 0),
    );
    score = List.generate(
      kBoardSize,
      (_) => List.filled(kBoardSize, 0),
    );
  }

  static final Ai instance = Ai._();

  static Ai getInstance() => instance;

  /// 先手：1 人类，-1 机器
  int first = 1;

  late final List<List<int>> chessboard;
  late final List<List<int>> score;

  void init() {
    first = 1;
    for (var i = 0; i < kBoardSize; i++) {
      for (var j = 0; j < kBoardSize; j++) {
        chessboard[i][j] = 0;
        score[i][j] = 0;
      }
    }
  }

  void addChessman(int x, int y, int owner) {
    if (x < 0 || x >= kBoardSize || y < 0 || y >= kBoardSize) return;
    chessboard[x][y] = owner;
  }

  bool isLegal(int x, int y) {
    return x >= 0 &&
        x < kBoardSize &&
        y >= 0 &&
        y < kBoardSize &&
        chessboard[x][y] == 0;
  }

  /// 判断 [owner] 在 (x,y) 落子后是否五连
  bool isWin(int x, int y, int owner) {
    const directions = [
      (1, 0),
      (0, 1),
      (1, 1),
      (1, -1),
    ];
    for (final (dx, dy) in directions) {
      var count = 1;
      count += _countDirection(x, y, dx, dy, owner);
      count += _countDirection(x, y, -dx, -dy, owner);
      if (count >= 5) return true;
    }
    return false;
  }

  int _countDirection(int x, int y, int dx, int dy, int owner) {
    var count = 0;
    var cx = x + dx;
    var cy = y + dy;
    while (cx >= 0 &&
        cx < kBoardSize &&
        cy >= 0 &&
        cy < kBoardSize &&
        chessboard[cx][cy] == owner) {
      count++;
      cx += dx;
      cy += dy;
    }
    return count;
  }

  /// 选取评分最高的空位作为落子点
  Position searchPosition() {
    for (var i = 0; i < kBoardSize; i++) {
      for (var j = 0; j < kBoardSize; j++) {
        score[i][j] = 0;
      }
    }

    _scoreRows();
    _scoreColumns();
    _scoreDiagDown();
    _scoreDiagUp();

    var goalX = -1;
    var goalY = -1;
    var maxScore = -1;

    for (var i = 0; i < kBoardSize; i++) {
      for (var j = 0; j < kBoardSize; j++) {
        if (chessboard[i][j] == 0 && score[i][j] > maxScore) {
          goalX = i;
          goalY = j;
          maxScore = score[i][j];
        }
      }
    }

    final black = ChessFlyweightFactory.getInstance().getChess('black');
    if (goalX != -1 && goalY != -1) {
      return Position(goalX.toDouble(), goalY.toDouble(), black);
    }
    return Position(-1, -1, black);
  }

  void _scoreRows() {
    for (var i = 0; i < kBoardSize; i++) {
      for (var j = 0; j <= kBoardSize - 5; j++) {
        var human = 0;
        var machine = 0;
        for (var k = j; k < j + 5; k++) {
          final cell = chessboard[i][k];
          if (cell == -1) {
            machine++;
          } else if (cell == 1) {
            human++;
          }
        }
        final s = tupleScore(human, machine);
        for (var k = j; k < j + 5; k++) {
          score[i][k] += s;
        }
      }
    }
  }

  void _scoreColumns() {
    for (var i = 0; i < kBoardSize; i++) {
      for (var j = 0; j <= kBoardSize - 5; j++) {
        var human = 0;
        var machine = 0;
        for (var k = j; k < j + 5; k++) {
          final cell = chessboard[k][i];
          if (cell == -1) {
            machine++;
          } else if (cell == 1) {
            human++;
          }
        }
        final s = tupleScore(human, machine);
        for (var k = j; k < j + 5; k++) {
          score[k][i] += s;
        }
      }
    }
  }

  /// 左上 → 右下
  void _scoreDiagDown() {
    for (var i = 0; i <= kBoardSize - 5; i++) {
      for (var j = 0; j <= kBoardSize - 5; j++) {
        var human = 0;
        var machine = 0;
        for (var k = 0; k < 5; k++) {
          final cell = chessboard[i + k][j + k];
          if (cell == -1) {
            machine++;
          } else if (cell == 1) {
            human++;
          }
        }
        final s = tupleScore(human, machine);
        for (var k = 0; k < 5; k++) {
          score[i + k][j + k] += s;
        }
      }
    }
  }

  /// 左下 → 右上
  void _scoreDiagUp() {
    for (var i = 4; i < kBoardSize; i++) {
      for (var j = 0; j <= kBoardSize - 5; j++) {
        var human = 0;
        var machine = 0;
        for (var k = 0; k < 5; k++) {
          final cell = chessboard[i - k][j + k];
          if (cell == -1) {
            machine++;
          } else if (cell == 1) {
            human++;
          }
        }
        final s = tupleScore(human, machine);
        for (var k = 0; k < 5; k++) {
          score[i - k][j + k] += s;
        }
      }
    }
  }

  /// 五元组评分表
  int tupleScore(int humanChessmanNum, int machineChessmanNum) {
    if (humanChessmanNum > 0 && machineChessmanNum > 0) return 0;
    if (humanChessmanNum == 0 && machineChessmanNum == 0) return 7;

    const machineScores = {1: 35, 2: 800, 3: 15000, 4: 800000};
    const humanScores = {1: 15, 2: 400, 3: 1800, 4: 100000};

    if (machineChessmanNum > 0) {
      return machineScores[machineChessmanNum] ?? -1;
    }
    if (humanChessmanNum > 0) {
      return humanScores[humanChessmanNum] ?? -1;
    }
    return -1;
  }
}