问题与MiniMax到Alpha

好的，对于任何玩过桌面游戏编程的人来说，我的问题应该听起来很熟悉，所以这里是：

我实现了MiniMax算法的一个变体（返回移动而不是最小/最大值）。

我也尝试将它设置为alpha-beta，尽管它最终导致完全失败。

所以，这是我的MiniMax代码：

Move* Board::miniMax(int depth)
{
    return this->maxMove(1, depth);
}

Move* Board::maxMove(int ply, int depth)
{
    vector<Move*> moves = this->possibleMoves();
    int movesSize = moves.size();

    Move* maxMove = new Move(MINUS_INF);

    for (int i=0; i<movesSize; i++)
    {
        Move* move = moves[i];
        HASHMAKE(move,this);

        move->value = (ply<depth) ? (this->minMove(ply+1, depth))->value 
                                  : this->eval();

        maxMove = MAXMOVE(maxMove,move);

        UNHASHMAKE(move,this);
    }

    return maxMove;
}

Move* Board::minMove(int ply, int depth)
{
    vector<Move*> moves = this->possibleMoves();
    int movesSize = moves.size();

    Move* minMove = new Move(PLUS_INF);

    for (int i=0; i<movesSize; i++)
    {
        Move* move = moves[i];
        HASHMAKE(move,this);

        move->value = (ply<depth) ? (this->maxMove(ply+1, depth))->value 
                                  : this->eval();

        minMove = MINMOVE(minMove,move);

        UNHASHMAKE(move,this);
    }

    return minMove;
}

任何想法如何可以调整上述事情，以便它是一个Alpha-Beta搜索？

---

这是我对Alpha-Beta转换的尝试（它失败了）：

Move* Board::alphaBeta(int depth)
{
    return this->alphaMax(1,depth,MINUS_INF,PLUS_INF);
}

Move* Board::alphaMax(int ply, int depth, int a, int b)
{
    vector<Move*> moves = this->possibleMoves();
    int movesSize = moves.size();

    Move* maxMove = new Move(MINUS_INF);

    for (int i=0; i<movesSize; i++)
    {
        Move* move = moves[i];
        HASHMAKE(move,this);

        move->value = (ply<depth) ? (this->alphaMin(ply+1, depth,a,b))->value 
                                  : this->eval();

        maxMove = MAXMOVE(maxMove,move);
        if (maxMove->value>=b) return maxMove;
        a = MAXVAL(a,maxMove->value);

        UNHASHMAKE(move,this);
    }

    return maxMove;
}

Move* Board::alphaMin(int ply, int depth, int a, int b)
{
    vector<Move*> moves = this->possibleMoves();
    int movesSize = moves.size();

    Move* minMove = new Move(PLUS_INF);

    for (int i=0; i<movesSize; i++)
    {
        Move* move = moves[i];
        HASHMAKE(move,this);

        move->value = (ply<depth) ? (this->alphaMax(ply+1, depth,a,b))->value 
                                  : this->eval();

        minMove = MINMOVE(minMove,move);
        if (minMove->value<=a) return minMove;
        b = MINVAL(b,minMove->value);

        UNHASHMAKE(move,this);
    }

    return minMove;
}

---

提示（避免任何误解）：

this->eval()函数从玩家A的角度返回一个分数。 例如，+100得分意味着该位置有利于玩家A，而-100得分意味着该位置有利于玩家B.

MINUS_INF和PLUS_INF分别被定义为一些任意小的和大的值。

这不是什么像家庭作业或任何东西（如果这是我最有可能从来没有兴趣玩这种东西......大声笑）

Move是一个简单的类，其中包含有关移动的详细信息以及相应的值（由eval函数分配）。

HASHMAKE和UNHASHMAKE只是两个移动（不）制作和移动（不）哈希宏，这应该没有多大区别。

MAXMOVE的定义如下： #define MAXMOVE(A,B) (((A)->value>=(B)->value)?(A):(B))

MINMOVE定义如下： #define MINMOVE(A,B) (((A)->value<=(B)->value)?(A):(B))

---

不知道这是否是，但我认为在alphaMin

if (minMove->value<=a) return minMove;
b = MINVAL(b,minMove->value);
UNHASHMAKE(move,this);

应该

UNHASHMAKE(move,this);
if (minMove->value<=a) return minMove;
b = MINVAL(b,minMove->value);

还有alphaMax的类似变化。

链接地址: http://www.djcxy.com/p/9631.html

上一篇: Issue with MiniMax to Alpha

下一篇: How to use principal variation search for checkers game along with negamax?