Alpha Beta修剪打破Minimax

所以我实现了我的基于国际象棋的益智游戏的极大极小搜索。 在这种情况下，搜索确定AI片段的下一步移动。

在它自己的作品上的极小值很好，它会返回预期的移动，但是当我执行alpha beta修剪时，极小极值每回合会为每一块返回相同的两个值。 例如，目前在（0,0）处的AI Rook可能会收到（1,0），因为它正在从最小极大值移动，并且下一次它询问极小极大值时它将接收（0,0）。 不管我在评估函数中改变了什么，都会发生这个循环。

游戏状态由用户的位置，棋子的位置和表示棋盘本身的棋盘阵列组成。 我在这里使用我自己的节点类（实际上应该称为Pair），以便将评估函数给出的各个值分别存储到每个Tile中。

我是如何实施Alpha测试修剪的吗？ 任何意见是极大的赞赏。 如果需要更多信息，请提问并提供我所能提供的信息。

//Here is my call to the minimax
Min(depth, user, piece, new Node((int) (Double.NEGATIVE_INFINITY)), new Node((int) Double.POSITIVE_INFINITY), tiles));

Node Max(int depth, Piece user, Piece piece, Node alpha, Node beta, Tile[][] tiles)
{
    if(depth <= 0||gameOver(piece))
    {
        return new Node(evaluation(user,piece,tiles));
    }
    LinkedList<Tile> moves = user.getMoves(tiles,1);
    for(Tile t:moves)
    {
        Tile temp= new Tile(user);
        tiles= user.changePos(t,tiles);
        Node val = Min(depth - 1, user, piece, alpha, beta, tiles);
        val.addTile(t);
        tiles= user.changePos(temp,tiles);
        if(val.getValue()>=beta.getValue())
            return beta;
        if(val.getValue() >= alpha.getValue())
        {
            if(alpha.getTile()==null)
                alpha = val;
            else if(val.getValue()==alpha.getValue()){
                if(r.nextInt(2)==1)//adds an element of randomness 
                    alpha=val;
            }
            else
                alpha=val;
        }
    }
    return alpha;
}
Node Min(int depth, Piece user, Piece piece, Node alpha, Node beta, Tile[][] tiles)
{
    updateGoal(user);
    if(depth <= 0||gameOver(piece))
    {
        return new Node(evaluation(user,piece,tiles));
    }
    LinkedList<Tile> moves = piece.getMoves(tiles,1);
    for(Tile t:moves)
    {

        Tile temp= new Tile(piece);
        tiles= piece.changePos(t,tiles);
        Node val = Max(depth - 1, user, piece, alpha, beta,tiles);
        val.addTile(t);
        tiles= piece.changePos(temp,tiles);
        if(val.getValue() <= alpha.getValue())
            return alpha;
        if(val.getValue() <= beta.getValue())
        {
            if(beta.getTile()==null)
                beta = val;
            else if(val.getValue()==beta.getValue()){
                if(r.nextInt(2)==1)
                    beta=val;
            }
            else
                beta=val;
        }
    }
    return beta;
}

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

上一篇: Alpha Beta Pruning Breaking Minimax

下一篇: minimax algorithm returning different value with alpha beta pruning