MiniMax到Alpha Beta搜索转换问题

Question

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

• 我实现了MiniMax算法的一种变体（返回移动而不是最小/最大值）
• 我还尝试将其设置为alpha beta版，尽管最终完全失败

这是我的极大极小码：

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;
}

提示（以避免任何误解）：

>

此-

减INF和加INF分别被定义为一些任意大小的值。

这不像是一个家庭作业或任何东西（如果是的话，我很可能从来没有任何兴趣玩这样的东西…哈哈）

移动是一个简单的类，包含移动的详细信息以及相应的值（由eval函数指定）。

HASHMAKE和UNHASHMAKE只是2个move-（un）制作和move-（un）散列宏，应该不会有太大区别。

定义MAXMOVE如下：\define MAXMOVE（A，B）（（A）-




Answer 1

不确定是不是这样，但我认为在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中的类似变化。