AI 算法

游戏 AI 的核心目标是：在有限资源内做出"看起来聪明"的决策。本章介绍棋牌类游戏中最常用的 AI 算法，从基础的 Minimax 到高效的蒙特卡洛树搜索。

7.1 Minimax 算法

Minimax 是二人零和博弈（一方赢就是另一方输）的经典算法，适用于国际象棋、五子棋、井字棋等棋盘游戏。

核心思想：AI（最大化方）假设对手总会做出对自己最有利的选择（最小化方），在此前提下找到最优决策。

C#

using Godot;
using System.Collections.Generic;

// 以井字棋为例演示 Minimax
public class TicTacToeAI
{
    // 棋盘：0=空, 1=玩家, 2=AI
    private int[] _board = new int[9];

    // 评估函数：返回局面得分
    private int Evaluate(int[] board)
    {
        // 检查所有获胜组合
        int[][] lines = {
            new[]{0,1,2}, new[]{3,4,5}, new[]{6,7,8}, // 横
            new[]{0,3,6}, new[]{1,4,7}, new[]{2,5,8}, // 竖
            new[]{0,4,8}, new[]{2,4,6}                // 斜
        };

        foreach (var line in lines)
        {
            if (board[line[0]] != 0 && board[line[0]] == board[line[1]] && board[line[1]] == board[line[2]])
                return board[line[0]] == 2 ? 10 : -10; // AI赢=+10, 玩家赢=-10
        }
        return 0; // 平局或未结束
    }

    // Minimax 算法核心
    private int Minimax(int[] board, int depth, bool isMaximizing)
    {
        int score = Evaluate(board);

        // 终止条件：有人赢了，或棋盘满了
        if (score != 0) return score - depth * (score > 0 ? 1 : -1); // 深度惩罚（更快赢）
        if (!HasEmptyCell(board)) return 0;

        if (isMaximizing)
        {
            int best = int.MinValue;
            for (int i = 0; i < 9; i++)
            {
                if (board[i] != 0) continue;
                board[i] = 2; // AI 落子
                best = Mathf.Max(best, Minimax(board, depth + 1, false));
                board[i] = 0; // 撤销
            }
            return best;
        }
        else
        {
            int best = int.MaxValue;
            for (int i = 0; i < 9; i++)
            {
                if (board[i] != 0) continue;
                board[i] = 1; // 玩家落子
                best = Mathf.Min(best, Minimax(board, depth + 1, true));
                board[i] = 0;
            }
            return best;
        }
    }

    // 找到最佳落子位置
    public int FindBestMove(int[] board)
    {
        int bestScore = int.MinValue;
        int bestMove = -1;

        for (int i = 0; i < 9; i++)
        {
            if (board[i] != 0) continue;
            board[i] = 2;
            int score = Minimax(board, 0, false);
            board[i] = 0;

            if (score > bestScore)
            {
                bestScore = score;
                bestMove = i;
            }
        }
        return bestMove;
    }

    private bool HasEmptyCell(int[] board)
    {
        foreach (var cell in board)
            if (cell == 0) return true;
        return false;
    }
}

GDScript

class_name TicTacToeAI

const LINES := [
    [0,1,2], [3,4,5], [6,7,8],  # 横
    [0,3,6], [1,4,7], [2,5,8],  # 竖
    [0,4,8], [2,4,6]             # 斜
]

func evaluate(board: Array) -> int:
    for line in LINES:
        if board[line[0]] != 0 and board[line[0]] == board[line[1]] and board[line[1]] == board[line[2]]:
            return 10 if board[line[0]] == 2 else -10
    return 0

func minimax(board: Array, depth: int, is_maximizing: bool) -> int:
    var score := evaluate(board)
    if score != 0:
        return score - depth * (1 if score > 0 else -1)
    if not _has_empty(board):
        return 0

    if is_maximizing:
        var best := -9999
        for i in 9:
            if board[i] != 0: continue
            board[i] = 2
            best = maxi(best, minimax(board, depth + 1, false))
            board[i] = 0
        return best
    else:
        var best := 9999
        for i in 9:
            if board[i] != 0: continue
            board[i] = 1
            best = mini(best, minimax(board, depth + 1, true))
            board[i] = 0
        return best

func find_best_move(board: Array) -> int:
    var best_score := -9999
    var best_move := -1
    for i in 9:
        if board[i] != 0: continue
        board[i] = 2
        var score := minimax(board, 0, false)
        board[i] = 0
        if score > best_score:
            best_score = score
            best_move = i
    return best_move

func _has_empty(board: Array) -> bool:
    return board.any(func(x): return x == 0)

7.2 Alpha-Beta 剪枝

Alpha-Beta 剪枝是 Minimax 的优化版本，通过提前剪掉不可能被选中的分支，大幅减少计算量。在相同时间内，Alpha-Beta 可以搜索比 Minimax 多两倍深度的棋局。

C#

using Godot;

public class AlphaBetaAI
{
    // Alpha: 当前最大化方已找到的最优值（下限）
    // Beta: 当前最小化方已找到的最优值（上限）
    private int AlphaBeta(int[] board, int depth, int alpha, int beta, bool isMaximizing)
    {
        int score = EvaluateBoard(board);
        if (score != 0 || depth == 0 || IsTerminal(board))
            return score;

        if (isMaximizing)
        {
            int value = int.MinValue;
            foreach (int move in GetLegalMoves(board))
            {
                ApplyMove(board, move, 2);
                value = Mathf.Max(value, AlphaBeta(board, depth - 1, alpha, beta, false));
                UndoMove(board, move);

                alpha = Mathf.Max(alpha, value);
                // Beta 剪枝：最大化方找到比 beta 更大的值，最小化方不会选这条路
                if (alpha >= beta) break;
            }
            return value;
        }
        else
        {
            int value = int.MaxValue;
            foreach (int move in GetLegalMoves(board))
            {
                ApplyMove(board, move, 1);
                value = Mathf.Min(value, AlphaBeta(board, depth - 1, alpha, beta, true));
                UndoMove(board, move);

                beta = Mathf.Min(beta, value);
                // Alpha 剪枝：最小化方找到比 alpha 更小的值，最大化方不会选这条路
                if (alpha >= beta) break;
            }
            return value;
        }
    }

    public int FindBestMoveWithAB(int[] board, int maxDepth)
    {
        int bestMove = -1;
        int bestScore = int.MinValue;

        foreach (int move in GetLegalMoves(board))
        {
            ApplyMove(board, move, 2);
            int score = AlphaBeta(board, maxDepth - 1, int.MinValue, int.MaxValue, false);
            UndoMove(board, move);

            if (score > bestScore)
            {
                bestScore = score;
                bestMove = move;
            }
        }
        return bestMove;
    }

    // 以下为抽象方法，需根据具体游戏实现
    protected virtual int EvaluateBoard(int[] board) => 0;
    protected virtual bool IsTerminal(int[] board) => false;
    protected virtual System.Collections.Generic.IEnumerable<int> GetLegalMoves(int[] board) => new int[0];
    protected virtual void ApplyMove(int[] board, int move, int player) { }
    protected virtual void UndoMove(int[] board, int move) { }
}

GDScript

class_name AlphaBetaAI

func alpha_beta(board: Array, depth: int, alpha: int, beta: int, is_maximizing: bool) -> int:
    var score := evaluate_board(board)
    if score != 0 or depth == 0 or is_terminal(board):
        return score

    if is_maximizing:
        var value := -9999
        for move in get_legal_moves(board):
            apply_move(board, move, 2)
            value = maxi(value, alpha_beta(board, depth - 1, alpha, beta, false))
            undo_move(board, move)
            alpha = maxi(alpha, value)
            if alpha >= beta:
                break  # Beta 剪枝
        return value
    else:
        var value := 9999
        for move in get_legal_moves(board):
            apply_move(board, move, 1)
            value = mini(value, alpha_beta(board, depth - 1, alpha, beta, true))
            undo_move(board, move)
            beta = mini(beta, value)
            if alpha >= beta:
                break  # Alpha 剪枝
        return value

func find_best_move(board: Array, max_depth: int) -> int:
    var best_move := -1
    var best_score := -9999
    for move in get_legal_moves(board):
        apply_move(board, move, 2)
        var score := alpha_beta(board, max_depth - 1, -9999, 9999, false)
        undo_move(board, move)
        if score > best_score:
            best_score = score
            best_move = move
    return best_move

# 子类实现以下方法
func evaluate_board(_board: Array) -> int: return 0
func is_terminal(_board: Array) -> bool: return false
func get_legal_moves(_board: Array) -> Array: return []
func apply_move(_board: Array, _move: int, _player: int) -> void: pass
func undo_move(_board: Array, _move: int) -> void: pass

7.3 蒙特卡洛树搜索（MCTS）

MCTS 不需要精确的评估函数，通过大量随机模拟来评估局面。它是围棋、麻将等复杂游戏 AI 的核心算法。

C#

using Godot;
using System.Collections.Generic;
using System;

public class MCTSNode
{
    public int[] Board;
    public int Move;           // 到达此节点的操作
    public int Player;         // 当前玩家
    public int Wins;           // 此节点赢的次数
    public int Visits;         // 访问次数
    public MCTSNode Parent;
    public List<MCTSNode> Children = new();

    public float UCB1(float explorationConst = 1.414f)
    {
        if (Visits == 0) return float.MaxValue;
        return (float)Wins / Visits + explorationConst * Mathf.Sqrt(Mathf.Log(Parent.Visits) / Visits);
    }
}

public class MCTS
{
    private Random _rng = new Random();
    private int _iterations;

    public MCTS(int iterations = 1000) { _iterations = iterations; }

    public int FindBestMove(int[] board, int currentPlayer)
    {
        var root = new MCTSNode { Board = (int[])board.Clone(), Player = currentPlayer };

        for (int i = 0; i < _iterations; i++)
        {
            // 1. 选择（Selection）：根据 UCB1 选择最有潜力的节点
            var node = Select(root);

            // 2. 扩展（Expansion）：为未完全扩展的节点添加子节点
            if (node.Visits > 0 && !IsTerminal(node.Board))
                node = Expand(node);

            // 3. 模拟（Simulation）：随机模拟到游戏结束
            int result = Simulate(node);

            // 4. 反向传播（Backpropagation）：更新节点统计信息
            Backpropagate(node, result);
        }

        // 选择访问次数最多的子节点（最稳健的选择）
        var bestChild = root.Children[0];
        foreach (var child in root.Children)
            if (child.Visits > bestChild.Visits) bestChild = child;

        return bestChild.Move;
    }

    private MCTSNode Select(MCTSNode node)
    {
        while (node.Children.Count > 0)
        {
            MCTSNode best = node.Children[0];
            foreach (var child in node.Children)
                if (child.UCB1() > best.UCB1()) best = child;
            node = best;
        }
        return node;
    }

    private MCTSNode Expand(MCTSNode node)
    {
        var moves = GetLegalMoves(node.Board);
        var usedMoves = new HashSet<int>(node.Children.ConvertAll(c => c.Move));
        foreach (int move in moves)
        {
            if (usedMoves.Contains(move)) continue;
            var childBoard = (int[])node.Board.Clone();
            ApplyMove(childBoard, move, node.Player);
            var child = new MCTSNode
            {
                Board = childBoard, Move = move,
                Player = 3 - node.Player, Parent = node
            };
            node.Children.Add(child);
            return child;
        }
        return node;
    }

    private int Simulate(MCTSNode node)
    {
        var board = (int[])node.Board.Clone();
        int player = node.Player;
        while (!IsTerminal(board))
        {
            var moves = GetLegalMoves(board);
            if (moves.Count == 0) break;
            int move = moves[_rng.Next(moves.Count)];
            ApplyMove(board, move, player);
            player = 3 - player;
        }
        return EvaluateResult(board);
    }

    private void Backpropagate(MCTSNode node, int result)
    {
        while (node != null)
        {
            node.Visits++;
            if (result == node.Player) node.Wins++;
            node = node.Parent;
        }
    }

    protected virtual List<int> GetLegalMoves(int[] board) => new List<int>();
    protected virtual void ApplyMove(int[] board, int move, int player) { }
    protected virtual bool IsTerminal(int[] board) => false;
    protected virtual int EvaluateResult(int[] board) => 0;
}

GDScript

class_name MCTSNode

var board: Array
var move: int
var player: int
var wins: int = 0
var visits: int = 0
var parent: MCTSNode
var children: Array[MCTSNode] = []

func ucb1(exploration: float = 1.414) -> float:
    if visits == 0:
        return INF
    return float(wins) / visits + exploration * sqrt(log(parent.visits) / visits)

7.4 行为树（Behavior Tree）

行为树是动作游戏 AI 的主流架构，通过树形结构组合简单行为，实现复杂的 AI 逻辑。

C#

using Godot;

// 行为树节点状态
public enum BtStatus { Success, Failure, Running }

// 行为节点基类
public abstract class BtNode
{
    public abstract BtStatus Tick(double delta);
}

// 序列节点：所有子节点成功才成功（AND）
public class SequenceNode : BtNode
{
    private readonly BtNode[] _children;
    private int _currentIndex = 0;

    public SequenceNode(params BtNode[] children) { _children = children; }

    public override BtStatus Tick(double delta)
    {
        while (_currentIndex < _children.Length)
        {
            var status = _children[_currentIndex].Tick(delta);
            if (status == BtStatus.Failure) { _currentIndex = 0; return BtStatus.Failure; }
            if (status == BtStatus.Running) return BtStatus.Running;
            _currentIndex++;
        }
        _currentIndex = 0;
        return BtStatus.Success;
    }
}

// 选择节点：任一子节点成功即成功（OR）
public class SelectorNode : BtNode
{
    private readonly BtNode[] _children;

    public SelectorNode(params BtNode[] children) { _children = children; }

    public override BtStatus Tick(double delta)
    {
        foreach (var child in _children)
        {
            var status = child.Tick(delta);
            if (status != BtStatus.Failure) return status;
        }
        return BtStatus.Failure;
    }
}

// 条件节点示例：检查是否发现玩家
public class IsPlayerInRangeNode : BtNode
{
    private readonly Node3D _enemy;
    private readonly float _range;

    public IsPlayerInRangeNode(Node3D enemy, float range)
    {
        _enemy = enemy;
        _range = range;
    }

    public override BtStatus Tick(double delta)
    {
        // 查找玩家（简化示例）
        var player = _enemy.GetTree().GetFirstNodeInGroup("player") as Node3D;
        if (player == null) return BtStatus.Failure;

        float dist = _enemy.GlobalPosition.DistanceTo(player.GlobalPosition);
        return dist <= _range ? BtStatus.Success : BtStatus.Failure;
    }
}

GDScript

class_name BtNode
enum Status { SUCCESS, FAILURE, RUNNING }
func tick(_delta: float) -> Status: return Status.FAILURE

# ---

class_name SequenceNode extends BtNode

var _children: Array[BtNode]
var _current: int = 0

func _init(children: Array[BtNode]) -> void:
    _children = children

func tick(delta: float) -> Status:
    while _current < _children.size():
        var s := _children[_current].tick(delta)
        if s == Status.FAILURE:
            _current = 0
            return Status.FAILURE
        if s == Status.RUNNING:
            return Status.RUNNING
        _current += 1
    _current = 0
    return Status.SUCCESS

算法选择建议

• 井字棋/五子棋（小棋盘）：使用 Minimax + Alpha-Beta，可搜索完整博弈树
• 国际象棋/中国象棋：Alpha-Beta + 开局库 + 残局库
• 围棋/麻将（状态空间巨大）：使用 MCTS，模拟次数越多越强
• 动作/RPG 敌人：使用行为树，灵活组合各种行为