nanocode/happy-games/games/chinese-chess/app/lib/astarAI.ts

import { Piece, Position, Color, Difficulty, AIMove, PIECE_VALUES } from "../types/chess";
import { getAllPossibleMoves, makeMove, isInCheck, isCheckmate, getPieceAt } from "./chessRules";

// 位置价值表（鼓励棋子占据有利位置）
const POSITION_BONUS: Record<string, number[][]> = {
  // 帅/将 - 待在九宫格中心
  "帅": [
    [0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 10, 20, 10, 0, 0, 0],
    [0, 0, 0, 20, 30, 20, 0, 0, 0],
    [0, 0, 0, 10, 20, 10, 0, 0, 0],
  ],
  "将": [
    [0, 0, 0, 10, 20, 10, 0, 0, 0],
    [0, 0, 0, 20, 30, 20, 0, 0, 0],
    [0, 0, 0, 10, 20, 10, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0],
  ],
  // 车 - 控制中路和横线
  "车": [
    [50, 40, 40, 40, 50, 40, 40, 40, 50],
    [40, 30, 30, 30, 40, 30, 30, 30, 40],
    [40, 30, 30, 30, 40, 30, 30, 30, 40],
    [40, 30, 30, 30, 40, 30, 30, 30, 40],
    [40, 30, 30, 30, 40, 30, 30, 30, 40],
    [40, 30, 30, 30, 40, 30, 30, 30, 40],
    [40, 30, 30, 30, 40, 30, 30, 30, 40],
    [40, 30, 30, 30, 40, 30, 30, 30, 40],
    [40, 30, 30, 30, 40, 30, 30, 30, 40],
    [50, 40, 40, 40, 50, 40, 40, 40, 50],
  ],
  // 马 - 活跃位置
  "马": [
    [20, 30, 40, 30, 20, 30, 40, 30, 20],
    [30, 40, 50, 40, 30, 40, 50, 40, 30],
    [30, 50, 60, 50, 40, 50, 60, 50, 30],
    [30, 40, 50, 40, 30, 40, 50, 40, 30],
    [20, 30, 40, 30, 20, 30, 40, 30, 20],
    [20, 30, 40, 30, 20, 30, 40, 30, 20],
    [30, 40, 50, 40, 30, 40, 50, 40, 30],
    [30, 50, 60, 50, 40, 50, 60, 50, 30],
    [30, 40, 50, 40, 30, 40, 50, 40, 30],
    [20, 30, 40, 30, 20, 30, 40, 30, 20],
  ],
  // 炮 - 需要好的位置
  "炮": [
    [30, 30, 30, 30, 35, 30, 30, 30, 30],
    [30, 40, 40, 40, 45, 40, 40, 40, 30],
    [30, 40, 50, 50, 50, 50, 50, 40, 30],
    [30, 40, 50, 50, 50, 50, 50, 40, 30],
    [35, 45, 50, 50, 50, 50, 50, 45, 35],
    [35, 45, 50, 50, 50, 50, 50, 45, 35],
    [30, 40, 50, 50, 50, 50, 50, 40, 30],
    [30, 40, 50, 50, 50, 50, 50, 40, 30],
    [30, 40, 40, 40, 45, 40, 40, 40, 30],
    [30, 30, 30, 30, 35, 30, 30, 30, 30],
  ],
  // 相/象 - 防守位置
  "相": [
    [0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 20, 0, 0, 0, 20, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0],
    [20, 0, 0, 0, 30, 0, 0, 0, 20],
    [0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 20, 0, 0, 0, 20, 0, 0],
  ],
  "象": [
    [0, 0, 20, 0, 0, 0, 20, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0],
    [20, 0, 0, 0, 30, 0, 0, 0, 20],
    [0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 20, 0, 0, 0, 20, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0],
  ],
  // 仕/士 - 九宫格内
  "仕": [
    [0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 20, 0, 20, 0, 0, 0],
    [0, 0, 0, 0, 30, 0, 0, 0, 0],
    [0, 0, 0, 20, 0, 20, 0, 0, 0],
  ],
  "士": [
    [0, 0, 0, 20, 0, 20, 0, 0, 0],
    [0, 0, 0, 0, 30, 0, 0, 0, 0],
    [0, 0, 0, 20, 0, 20, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0],
  ],
  // 兵/卒 - 过河后价值增加
  "兵": [
    [0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0],
    [40, 0, 40, 0, 40, 0, 40, 0, 40],
    [50, 0, 50, 0, 50, 0, 50, 0, 50],
    [60, 0, 60, 0, 60, 0, 60, 0, 60],
    [70, 0, 70, 0, 70, 0, 70, 0, 70],
    [80, 0, 80, 0, 80, 0, 80, 0, 80],
    [90, 0, 90, 0, 90, 0, 90, 0, 90],
    [100, 0, 100, 0, 100, 0, 100, 0, 100],
  ],
  "卒": [
    [100, 0, 100, 0, 100, 0, 100, 0, 100],
    [90, 0, 90, 0, 90, 0, 90, 0, 90],
    [80, 0, 80, 0, 80, 0, 80, 0, 80],
    [70, 0, 70, 0, 70, 0, 70, 0, 70],
    [60, 0, 60, 0, 60, 0, 60, 0, 60],
    [50, 0, 50, 0, 50, 0, 50, 0, 50],
    [40, 0, 40, 0, 40, 0, 40, 0, 40],
    [0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0],
  ],
};

// 评估棋盘局面
function evaluateBoard(pieces: Piece[], color: Color): number {
  let score = 0;
  const myPieces = pieces.filter((p) => p.alive && p.color === color);
  const enemyPieces = pieces.filter((p) => p.alive && p.color !== color);
  const enemyColor = color === "red" ? "black" : "red";

  // 计算己方棋子价值
  for (const piece of myPieces) {
    const pieceValue = PIECE_VALUES[piece.type];
    const positionBonus = POSITION_BONUS[piece.type]?.[piece.position.row]?.[piece.position.col] || 0;
    score += pieceValue + positionBonus;

    // 出子奖励 - 鼓励大子出动到有利位置
    score += getDevelopmentBonus(piece, color);

    // 攻击奖励 - 棋子能攻击到对方棋子
    score += getAttackBonus(pieces, piece, enemyPieces);
  }

  // 减去对方棋子价值
  for (const piece of enemyPieces) {
    const pieceValue = PIECE_VALUES[piece.type];
    const positionBonus = POSITION_BONUS[piece.type]?.[piece.position.row]?.[piece.position.col] || 0;
    score -= pieceValue + positionBonus;
  }

  // 机动性奖励 - 己方棋子总移动数
  const myMobility = getAllPossibleMoves(pieces, color).length;
  const enemyMobility = getAllPossibleMoves(pieces, enemyColor).length;
  score += (myMobility - enemyMobility) * 10;

  // 将军奖励
  if (isInCheck(pieces, enemyColor)) {
    score += 800;
  }
  if (isInCheck(pieces, color)) {
    score -= 800;
  }

  // 将死奖励/惩罚
  if (isCheckmate(pieces, enemyColor)) {
    score += 100000;
  }
  if (isCheckmate(pieces, color)) {
    score -= 100000;
  }

  // 控制中心奖励
  score += getCenterControlBonus(pieces, color);

  return score;
}

// 出子奖励 - 鼓励大子从初始位置出动
function getDevelopmentBonus(piece: Piece, color: Color): number {
  const initialPositions: Record<string, Position[]> = {
    "车": color === "red" 
      ? [{row: 9, col: 0}, {row: 9, col: 8}] 
      : [{row: 0, col: 0}, {row: 0, col: 8}],
    "马": color === "red"
      ? [{row: 9, col: 1}, {row: 9, col: 7}]
      : [{row: 0, col: 1}, {row: 0, col: 7}],
    "炮": color === "red"
      ? [{row: 7, col: 1}, {row: 7, col: 7}]
      : [{row: 2, col: 1}, {row: 2, col: 7}],
  };

  const type = piece.type as keyof typeof initialPositions;
  if (!initialPositions[type]) return 0;

  const isAtInitial = initialPositions[type].some(
    pos => pos.row === piece.position.row && pos.col === piece.position.col
  );

  // 如果还在初始位置，惩罚；如果已经出动，奖励
  if (isAtInitial) {
    return -30; // 还在原位，减分鼓励出动
  } else {
    // 根据前进程度给予奖励
    const progress = color === "red" 
      ? 9 - piece.position.row  // 红方：行号越小越靠前
      : piece.position.row;     // 黑方：行号越大越靠前
    return 50 + progress * 10;  // 出动奖励 + 前进奖励
  }
}

// 攻击奖励 - 棋子能攻击到对方棋子
function getAttackBonus(pieces: Piece[], piece: Piece, enemyPieces: Piece[]): number {
  let bonus = 0;
  const enemyColor = piece.color === "red" ? "black" : "red";
  
  // 检查这个棋子能攻击到哪些敌方棋子
  for (const enemy of enemyPieces) {
    // 简化检查：如果敌方棋子在这个棋子的攻击范围内
    const rowDiff = Math.abs(piece.position.row - enemy.position.row);
    const colDiff = Math.abs(piece.position.col - enemy.position.col);
    
    // 根据棋子类型判断攻击可能性
    switch (piece.type) {
      case "车":
        // 车在同一条线上就有威胁
        if (piece.position.row === enemy.position.row || piece.position.col === enemy.position.col) {
          bonus += PIECE_VALUES[enemy.type] * 0.1; // 潜在吃子威胁
        }
        break;
      case "马":
        // 马走日
        if ((rowDiff === 2 && colDiff === 1) || (rowDiff === 1 && colDiff === 2)) {
          bonus += PIECE_VALUES[enemy.type] * 0.1;
        }
        break;
      case "炮":
        // 炮在同一条线上
        if (piece.position.row === enemy.position.row || piece.position.col === enemy.position.col) {
          bonus += PIECE_VALUES[enemy.type] * 0.08;
        }
        break;
    }
  }
  
  return bonus;
}

// 控制中心奖励
function getCenterControlBonus(pieces: Piece[], color: Color): number {
  let bonus = 0;
  const centerCols = [3, 4, 5]; // 中心列
  const centerRows = color === "red" ? [5, 6, 7] : [2, 3, 4]; // 对方半场中心
  
  const myPieces = pieces.filter(p => p.alive && p.color === color);
  
  for (const piece of myPieces) {
    // 大子（车、马、炮）在中心区域给予奖励
    if (["车", "马", "炮"].includes(piece.type)) {
      if (centerCols.includes(piece.position.col)) {
        bonus += 30;
      }
      // 过河进入对方半场给予额外奖励
      const crossedRiver = color === "red" ? piece.position.row <= 4 : piece.position.row >= 5;
      if (crossedRiver) {
        bonus += 40;
      }
    }
  }
  
  return bonus;
}

// 节点计数器，用于限制搜索规模
let nodeCount = 0;
const MAX_NODES = 50000; // 最大搜索节点数

// Minimax算法带Alpha-Beta剪枝
function minimax(
  pieces: Piece[],
  depth: number,
  alpha: number,
  beta: number,
  isMaximizing: boolean,
  color: Color,
  originalColor: Color
): number {
  nodeCount++;
  
  // 超过最大节点数，直接返回评估值
  if (nodeCount > MAX_NODES) {
    return evaluateBoard(pieces, originalColor);
  }
  
  if (depth === 0) {
    return evaluateBoard(pieces, originalColor);
  }

  const currentColor = isMaximizing ? originalColor : originalColor === "red" ? "black" : "red";
  const moves = getAllPossibleMoves(pieces, currentColor);

  if (moves.length === 0) {
    if (isInCheck(pieces, currentColor)) {
      return isMaximizing ? -100000 : 100000;
    }
    return 0; // 和棋
  }

  // 限制分支因子，只考虑前20个最佳走法
  const limitedMoves = moves.slice(0, 20);

  if (isMaximizing) {
    let maxEval = -Infinity;
    for (const { piece, to } of limitedMoves) {
      const { pieces: newPieces } = makeMove(pieces, piece.position, to);
      const eval_ = minimax(newPieces, depth - 1, alpha, beta, false, color, originalColor);
      maxEval = Math.max(maxEval, eval_);
      alpha = Math.max(alpha, eval_);
      if (beta <= alpha) break;
    }
    return maxEval;
  } else {
    let minEval = Infinity;
    for (const { piece, to } of limitedMoves) {
      const { pieces: newPieces } = makeMove(pieces, piece.position, to);
      const eval_ = minimax(newPieces, depth - 1, alpha, beta, true, color, originalColor);
      minEval = Math.min(minEval, eval_);
      beta = Math.min(beta, eval_);
      if (beta <= alpha) break;
    }
    return minEval;
  }
}

// 获取难度对应的搜索深度
function getDepthByDifficulty(difficulty: Difficulty): number {
  switch (difficulty) {
    case "容易":
      return 2;
    case "一般":
      return 2;
    case "困难":
      return 3;
    default:
      return 2;
  }
}

// A* AI主函数
export function findBestMove(
  pieces: Piece[],
  color: Color,
  difficulty: Difficulty
): AIMove | null {
  // 重置节点计数器
  nodeCount = 0;
  
  const depth = getDepthByDifficulty(difficulty);
  const moves = getAllPossibleMoves(pieces, color);
  
  // 如果没有可行走法，返回null
  if (moves.length === 0) return null;
  
  // 限制顶层搜索的走法数量，提高性能
  const topMoves = moves.slice(0, 30);
  
  let bestMove: AIMove | null = null;
  let bestScore = -Infinity;
  
  // 对于容易难度，添加一些随机性
  const addRandomness = difficulty === "容易";
  
  for (const { piece, to } of topMoves) {
    const { pieces: newPieces } = makeMove(pieces, piece.position, to);
    const score = minimax(
      newPieces,
      depth - 1,
      -Infinity,
      Infinity,
      false,
      color,
      color
    );

    let finalScore = score;
    if (addRandomness) {
      // 容易难度：添加随机扰动
      finalScore += (Math.random() - 0.5) * 200;
    }

    if (finalScore > bestScore) {
      bestScore = finalScore;
      bestMove = {
        from: piece.position,
        to,
        score: finalScore,
      };
    }
  }

  return bestMove;
}

// 快速评估移动（用于提示）
export function evaluateMove(
  pieces: Piece[],
  from: Position,
  to: Position,
  color: Color
): number {
  const { pieces: newPieces } = makeMove(pieces, from, to);
  return evaluateBoard(newPieces, color);
}