1

我正在尝试在 java 中实现 Mini Max & Alpha Beta Pruning 算法,由于某种原因,尽管算法访问了 24,911 个节点,但 Pruning 算法不执行单个修剪。GameNode 值初始化为 MaxNodes 的 -99 和 MinNodes 的 99 以及 Alpha=-99 \ Beta=99。游戏称为“Nim”,数值为 1 或 -1,输赢,不得分。知道为什么修剪不会发生吗?

这是修剪的代码:

public static int Prune(GameNode n){




    if(n.getSuccessors()==null)
        return n.GetUtilityValue();

    else if(n.getPlayer().equals(GameNode.Player.MAX)) // A's move
    {
        int value;

        if(n.getFather()!=null){

            if(n.getFather().getAlpha()>n.getAlpha())
                n.setAlpha(n.getFather().getAlpha());//Pass down alpha value 

            if(n.getFather().getBeta()<n.getBeta())
                n.setBeta(n.getFather().getBeta());//Pass down beta value 

        }

        for(GameNode s : n.getSuccessors())
        {
            if(n.getValue() > n.getBeta()) // if Current value > Beta => then prune this node
            {
                GameNode.prune++;
                break;
            }


                if(s!=null){
                GameNode.counter++;
                value = MiniMax(s);

                if(value>n.getValue()){// Is leaf bigger then current value ? then set value and Alpha value

                    n.setValue(value);
                    if(value > n.getAlpha())
                        n.setAlpha(value);

                    }
                }

        }

    return n.getValue();

    }
    else // B's move
    {
        int value;

        if(n.getFather().getAlpha()>n.getAlpha())
            n.setAlpha(n.getFather().getAlpha());//Pass down alpha value 

        if(n.getFather().getBeta()<n.getBeta())
            n.setBeta(n.getFather().getBeta());//Pass down beta value 

        for(GameNode s : n.getSuccessors())
        {   
            if(n.getValue() < n.getAlpha())// if Current value < Alpha => then prune this node
            {
                GameNode.prune++;
                break;
            }


                if(s!=null) {
                GameNode.counter++;
                value = MiniMax(s);

                if(value<n.getValue()){// Is leaf smaller then current value ? then set value and Beta value

                    n.setValue(value);
                    if(value < n.getBeta())
                        n.setBeta(value);

                    }
                }

        }


    return n.getValue();

    }
}
4

0 回答 0