当前位置： 首页 > article >正文

数据结构与算法分析：专题内容——人工智能中的寻路6之NegMax（代码详解）

article 2025/3/1 18:37:28

一、算法描述

NegMax算法不再使用Minimax的MAX和MINI层级，而是每一级都使用同样的方法。这种思想也形成了另外一种算法，AlphaBeta，我们在稍后会讨论这个算法。在Minimax中，局面状态是一直从玩家的视角来观察，然后选择走法（需要存储棋子的信息以供评价函数使用）。
此算法不再将博弈树划分为多个层级，NegMax对走法采取一致的评价策略，从最坏的角度来评价子节点。从本质上来说，玩家走完之后，对手肯定会试着做出最好的决定，因此，算法指导玩家选择最好的走法，限制对手的可行走法。如果你比较Minimax和NegMax，你将会看到两个几乎相同的博弈树，唯一的区别就是局面状态是如何被评分的。注意，对玩家来说，两个可行走法中的第一个是最好的，因为这个走法对对手的限制最多。

二、复杂度分析

在这里插入图片描述

下图是一字棋游戏中，玩家O采取NegMax搜索时的追寻深度为2的轨迹。注意这里会扩展出所有可能的棋面状态，即使确定玩家X可以稳赢时。每个叶子局面状态的得分都是从玩家的角度出发。我们看到初始局面状态的得分是-2，因为这是所有其子节点的最大负分。
NegMax探测的状态数目和Minimax一样，如果追寻深度为d，每个局面状态的可行走法为b个，那么数目近似于bd。
最后我们可以看到NegMax是如何处理博弈树的叶子节点的。你同样可以在下例的代码中看到，这些叶子状态节点都是从玩家的角度出发，也就是说双亲节点从叶子节点选择的MoveEvaluation只是简单的最大化这些叶子节点的得分。
NegMax的操作好似流水线一般，它不需要来回切换MAX或者MIN层级。我们回忆一下Minimax是如何要求评估函数要从将要走棋的玩家的观点来进行评估的。在NegMax中，局面状态是基于走棋之后的玩家的视角。因为算法是选择“负分最大的子节点”。
在这里插入图片描述

三、适用情况

适用情况同Minimax算法。
NegMax是非常实用的算法，如果需要，可以扩展成AlphaBeta算法。因为每个棋面的得分都是负数，我们只需要仔细地区分胜利和失败状态。尤其是最小值必须是最大值的负数。注意Integer.MIN_VALUE（在Java中，这个定义为0x80000000或者-2147483648 ）并不是Integer.MAX_VALUE（在Java中，这个定义为0x7fffffff或者2 147483647）的负值。因此，我们将最小值定义为Integer.MIN_VALUE+1 ， 这 个 值 可 以 调 用 静 态 函 数MoveEvaluation.minimum()获得。从完整性来看，我们也提供了MoveEvaluation.maximum()函数。

四、算法实现

  • 输入
    算法从博弈树中的一个初始位置开始，假设它能够（a）选择某个局面状态的所有可行走法，以及（b）评价某个局面状态，表示从玩家来看这个状态的质量。得分越少则质量越差。算法会预测固定步数，这个数目叫做追寻深度。
  • 输出
    返回所有可行走法中最能使得玩家赢得比赛的走法，由评估函数决定。
  • 假设
    评估局面状态是非常复杂的，程序员需要依靠评估函数来选择最好的局面状态。事实上，在设计智能程序中，开发一个精确的评估函数，例如象棋、跳棋，或者黑白棋，是一件非常困难的事情。我们假设已经有一些这样的函数。
    每一个MoveEvaluation的得分是简单地以走棋的玩家角度来评价棋面状态。这样能够简化算法的实现。
#include <iostream>
#include <vector>
#include <memory>
#include <limits>
#include <algorithm>

// Forward declarations
class IGameState;
class IGameMove;
class IPlayer;
class IEvaluation;

// Interface for game state
class IGameState {
public:
    virtual std::shared_ptr<IGameState> copy() = 0;
    virtual ~IGameState() = default;
};

// Interface for game move
class IGameMove {
public:
    virtual void execute(std::shared_ptr<IGameState> state) = 0;
    virtual void undo(std::shared_ptr<IGameState> state) = 0;
    virtual ~IGameMove() = default;
};

// Interface for player
class IPlayer {
public:
    virtual std::vector<std::shared_ptr<IGameMove>> validMoves(std::shared_ptr<IGameState> state) = 0;
    virtual int eval(std::shared_ptr<IGameState> state) = 0;
    virtual ~IPlayer() = default;
};

// Interface for evaluation
class IEvaluation {
public:
    virtual std::shared_ptr<IGameMove> bestMove(std::shared_ptr<IGameState> s,
        std::shared_ptr<IPlayer> player,
        std::shared_ptr<IPlayer> opponent) = 0;
    virtual ~IEvaluation() = default;
};

// Move evaluation class
class MoveEvaluation {
public:
    std::shared_ptr<IGameMove> move;
    int score;

    // Constructor for leaf nodes (just score)
    explicit MoveEvaluation(int score) : move(nullptr), score(score) {}

    // Constructor for internal nodes (move and score)
    MoveEvaluation(std::shared_ptr<IGameMove> m, int s) : move(m), score(s) {}

    static int minimum() {
        return std::numeric_limits<int>::min();
    }
};

// NegMax evaluation class
class NegMaxEvaluation : public IEvaluation {
private:
    std::shared_ptr<IGameState> state;
    int ply;

    MoveEvaluation negmax(int ply, std::shared_ptr<IPlayer> player,
        std::shared_ptr<IPlayer> opponent) {
        // Get valid moves for current player
        auto moves = player->validMoves(state);

        // If no moves or leaf node, return evaluation
        if (ply == 0 || moves.empty()) {
            return MoveEvaluation(player->eval(state));
        }

        // Initialize best move with minimum possible score
        MoveEvaluation best(MoveEvaluation::minimum());

        // Try all possible moves
        for (const auto& move : moves) {
            // Make move
            move->execute(state);

            // Recursively evaluate position from opponent's perspective
            MoveEvaluation me = negmax(ply - 1, opponent, player);

            // Undo move
            move->undo(state);

            // Update best move if we found a better score
            if (-me.score > best.score) {
                best = MoveEvaluation(move, -me.score);
            }
        }

        return best;
    }

public:
    explicit NegMaxEvaluation(int searchPly) : ply(searchPly) {}

    std::shared_ptr<IGameMove> bestMove(std::shared_ptr<IGameState> s,
        std::shared_ptr<IPlayer> player,
        std::shared_ptr<IPlayer> opponent) override {
        state = s->copy();
        MoveEvaluation me = negmax(ply, player, opponent);
        return me.move;
    }
};

// Example concrete implementations for testing
class SimpleGameState : public IGameState {
public:
    std::vector<int> board;

    SimpleGameState() : board(9, 0) {} // 3x3 board initialized with zeros

    std::shared_ptr<IGameState> copy() override {
        auto newState = std::make_shared<SimpleGameState>();
        newState->board = this->board;
        return newState;
    }
};

class SimpleGameMove : public IGameMove {
public:
    int position;
    int player; // 1 or -1

    SimpleGameMove(int pos, int p) : position(pos), player(p) {}

    void execute(std::shared_ptr<IGameState> state) override {
        auto gameState = std::dynamic_pointer_cast<SimpleGameState>(state);
        gameState->board[position] = player;
    }

    void undo(std::shared_ptr<IGameState> state) override {
        auto gameState = std::dynamic_pointer_cast<SimpleGameState>(state);
        gameState->board[position] = 0;
    }
};

class SimplePlayer : public IPlayer {
private:
    int playerMark; // 1 or -1

public:
    explicit SimplePlayer(int mark) : playerMark(mark) {}

    std::vector<std::shared_ptr<IGameMove>> validMoves(std::shared_ptr<IGameState> state) override {
        auto gameState = std::dynamic_pointer_cast<SimpleGameState>(state);
        std::vector<std::shared_ptr<IGameMove>> moves;

        for (int i = 0; i < 9; i++) {
            if (gameState->board[i] == 0) {
                moves.push_back(std::make_shared<SimpleGameMove>(i, playerMark));
            }
        }
        return moves;
    }

    int eval(std::shared_ptr<IGameState> state) override {
        // Simple evaluation: count pieces
        auto gameState = std::dynamic_pointer_cast<SimpleGameState>(state);
        int score = 0;
        for (int val : gameState->board) {
            if (val == playerMark) score++;
            else if (val == -playerMark) score--;
        }
        return score;
    }
};

int main() {
    // Create game state
    auto gameState = std::make_shared<SimpleGameState>();

    // Create players
    auto player1 = std::make_shared<SimplePlayer>(1);
    auto player2 = std::make_shared<SimplePlayer>(-1);

    // Create evaluator with search depth of 3
    NegMaxEvaluation evaluator(3);

    // Get best move for player1
    auto bestMove = evaluator.bestMove(gameState, player1, player2);

    if (bestMove) {
        auto move = std::dynamic_pointer_cast<SimpleGameMove>(bestMove);
        std::cout << "Best move for Player 1: position " << move->position << std::endl;
    }
    else {
        std::cout << "No valid moves available" << std::endl;
    }

    return 0;
}

五、引用及参考文献

1.《算法设计手册》


http://www.kler.cn/a/518703.html

相关文章：

  • 链式存储结构
  • 详解生成对抗网络（GAN）模型
  • Oracle迁移DM数据库
  • Facebook 元宇宙与全球文化交流的新趋势
  • 1.CSS的三大特性
  • 【Address Overfitting】解决过拟合的三种方法
  • 刷题总结 回溯算法
  • python3+TensorFlow 2.x（二） 回归模型
  • 理解神经网络：Brain.js 背后的核心思想
  • TMC2224替换DRV8824
  • win32汇编环境,函数的编写与调用、传值或返回值等
  • PyQt4 的图片切割编辑器
  • RocketMQ优势剖析-集成云原生环境
  • 【知识】可视化理解git中的cherry-pick、merge、rebase
  • Python爬虫基础总结笔记
  • wangEditor富文本编辑器，Laravel上传图片配置和使用
  • Kimi 1.5解读：国产AI大模型的创新突破与多模态推理能力（内含论文地址）
  • 在 Vue 项目中快速引入和使用 ECharts
  • Golang 中除了加锁还有哪些安全读写共享变量的方式？
  • 计算机网络-运输层