αBeta剪枝优化

Question

我做了一个类，在40度的二叉树上做αβ剪枝。然而，一次移动的时间限制为30秒。我要对抗我的教授和他的对手班。我试着降低6级，但我会输掉的。我试着降低7级，但我花的时间太长了。有办法让我的代码运行得更快吗？如果可能的话，您也可以检查我的逻辑中的alpha beta剪枝部分，看看我是否遗漏了什么，导致它运行的时间比它应该的时间长。我将包括所有的类，但我只需要帮助的球员类，因为这是我唯一的工作。其他的都是教授给的。我希望它跑得更快，这样我就能深入到树下，这样我就有了优势并赢得了比赛。如果我最后得到一个正数，游戏就赢了。

播放器：

import java.util.ArrayList;

public class Player {

    private Tree t;

    public Player(Tree t) {
        this.t = t;
    }

    // play will take in the moves and the player (in this case the maximizer)
    // and return the best possible move
    public boolean play(ArrayList<Boolean> moves, boolean maxNode) {
        float alpha = Float.NEGATIVE_INFINITY;
        float beta = Float.POSITIVE_INFINITY;
        // a will be the two possible moves that this node can take
        ArrayList<Boolean> a = (ArrayList<Boolean>) moves.clone();
        a.add(true);
        int level = 0; // Level is how far down it would go

        if (moves.size() < 14) {
            level = 19 - moves.size();
        } else if (moves.size() >= 14 && moves.size() < 34) {
            level = 6;
        } else if (moves.size() >= 34) {
            level = 39 - moves.size();
        }
        //System.out.println(moves.size() + "     " + level);
        alpha = Math.max(alpha, prun(level, a, maxNode, alpha, beta));
        a.remove(a.size() - 1);
        float al;
        al = alpha;
        alpha = Float.NEGATIVE_INFINITY;
        a.add(false);
        alpha = Math.max(alpha, prun(level, a, maxNode, alpha, beta));
        if (al > alpha) {
            return true;
        } else {
            return false;
        }
    }

    // prun is a recursive function that will determine alpha and beta
    public float prun(int level, ArrayList<Boolean> m, boolean maxNode, float a, float b) {
        if (level <= 0) {
            return t.value(m);
        }
        level--;
        ArrayList<Boolean> moves = (ArrayList<Boolean>) m.clone();
        ArrayList<Boolean> moves1 = (ArrayList<Boolean>) m.clone();
        // Child is all possible moves for a node.
        ArrayList<ArrayList<Boolean>> child = new ArrayList<ArrayList<Boolean>>();
        child.add(moves);
        child.add(moves1);
        child.get(0).add(true);
        child.get(1).add(false);
        float score;
        for (ArrayList c : child) {
            score = prun(level, c, !maxNode, a, b);
            if (maxNode) {
                if (score > a) {
                    a = score;
                }
            } else if (!maxNode) {
                if (score < b) {
                    b = score;
                }
            }
            if (a >= b) {
                break;
            }
        }
        if (maxNode) {
            return a;
        } else {
            return b;
        }
    }
}

树：

import java.util.ArrayList;
import java.util.Random;

public class Tree {
    public final int TOTALNODES=2097152;
    public final float EPSILON=0.00001f;
    public final float distribution=10.0f;

    public long randomSeed=0L;
    public float[] topTree=new float[TOTALNODES];
    private Random r=new Random();
    public long height=40;

    public Tree(long rs) {
        randomSeed=rs;
        r.setSeed(randomSeed);
        topTree[0]=topTree[1]=0.0f;
        int current=2; int levelNodes=2; float factor=1.0f;
        while (current<TOTALNODES) {
            for (int i=0; i<levelNodes; i++) {
                int parent=current/2;
                float sign=0.0f;
                if (r.nextBoolean()&&r.nextBoolean())
                    if (topTree[parent]>EPSILON) sign=1.0f; else sign=-1.0f;
                else if (topTree[parent]>EPSILON) sign=-1.0f; else sign=1.0f;
                float offset=((Math.abs(topTree[parent])<EPSILON)?(r.nextFloat()*2.0f*distribution-distribution):(r.nextFloat()*distribution*factor*sign));
                topTree[current]=topTree[parent]+offset;
                current++; }
            levelNodes*=2; factor*=0.9f; }
    }

    public float value(ArrayList<Boolean> moves) {
        // low and high will both be values between 0 and 2^21-1=TOTALNODES.
        // The depth will be the number of bits examined, starting with the low order bit of the low int.
        // A depth of 0 will indicate the root.
        int position=1;
        for (int i=0; i<Math.min(20, moves.size()); i++) {
            if (moves.get(i).booleanValue()) position=position*2+1; else position*=2; }
        if (moves.size()<=20) return topTree[position];
        r.setSeed(randomSeed+position);

        float[] bottomTree=new float[TOTALNODES];
        bottomTree[0]=bottomTree[1]=topTree[position];
        int current=2; int levelNodes=2; float factor=0.12157665459056928801f;
        while (current<TOTALNODES) {
            for (int i=0; i<levelNodes; i++) {
                int parent=current/2;
                float sign=0.0f;
                if (r.nextBoolean()&&r.nextBoolean())
                    if (bottomTree[parent]>EPSILON) sign=1.0f; else sign=-1.0f;
                else if (bottomTree[parent]>EPSILON) sign=-1.0f; else sign=1.0f;
                float offset=((Math.abs(bottomTree[parent])<EPSILON)?(r.nextFloat()*2.0f*distribution-distribution):(r.nextFloat()*distribution*factor*sign));
                bottomTree[current]=bottomTree[parent]+offset;
                current++; }
            levelNodes*=2; factor*=0.9f; }

        position=1;
        for (int i=20; i<moves.size(); i++) {
            if (moves.get(i).booleanValue()) position=position*2+1; else position*=2; }
        return bottomTree[position];
    }
}

主要：

import java.util.ArrayList;

public class Main {


    public static void main(String[] args) {
        final long randomSeed=564715140;

        Tree t=new Tree(randomSeed);
        ArrayList<Boolean> moves=new ArrayList<Boolean>();

        Player player=new Player(t);
        Opponent other=new Opponent(t);
        int turn=0;
        for (int i=0; i<t.height; i++) {
            long before=System.currentTimeMillis();
            boolean maxNode=(turn==0);
            Boolean newMove=((maxNode)?player.play(moves, maxNode):other.play(moves, maxNode));
            if (newMove==null) throw new RuntimeException("No decision made.");
            moves.add(newMove);
            long after=System.currentTimeMillis();
            if ((after-before)>30000) {
                if (maxNode) System.out.println("The maximizer took too long: "+(after-before));
                else System.out.println("The minimizer took too long: "+(after-before));
                System.exit(0); }
            System.out.println("Time: "+(after-before));
            turn=1-turn;
        }
        System.out.println("Final score: "+t.value(moves));
    }

}

对手：(这将是教授的课，我没有，所以我只是让它随机返回)

import java.util.ArrayList;

public class Opponent {
    private Tree t;

    public Opponent(Tree t) {
        this.t = t;
    }
    // play will take in the moves and the player (in this case the maximizer)
    // and return the best possible move
    public boolean play(ArrayList<Boolean> moves, boolean maxNode) {
        int rand = (int)(Math.random() * 10) + 1;
        return (rand%2 == 0);
    }
}

Answer 1

克隆与复制构造函数

ArrayList<Boolean> moves = (ArrayList<Boolean>) m.clone();

而不是 clone()-ing，您应该使用构造函数ArrayList(Collection)创建由与原始元素相同的元素支持的新List实例。这对于在新创建的实例上添加或删除元素是安全的。

基于实现的

接口

建议使用诸如List之类的接口类型，而不是实现类型，即ArrayList，因为变量的用户应该只需要使用List API提供的方法，而不必理解底层实现。这也被称为松耦合。此外，从Java 7开始，您可以使用泛型推理保存一些击键：

List<AVeryLongType> list = new ArrayList<>();
// instead of
// ArrayList<AVeryLongType> list = new ArrayList<AVeryLongType>();

// instead of ArrayList<T>
public static void methodName(List<T> list) {
    // ...
}

布尔比较与三元条件

在您的Player类中：

public boolean play(ArrayList<Boolean> moves, boolean maxNode) {
    // ...
    if (al > alpha) {
        return true;
    } else {
        return false;
    }
}

public float prun(int level, ArrayList<Boolean> m, boolean maxNode, float a, float b) {
    // ...
    if (maxNode) {
        return a;
    } else {
        return b;
    }
}

您还可以考虑使用直接布尔比较和三元运算符在这里简化表达式：

public boolean play(List<Boolean> moves, boolean maxNode) {
    // ...
    return al > alpha;
}

public float prun(int level, List<Boolean> m, boolean maxNode, float a, float b) {
    // ...
    return maxNode ? a : b;
}

代码格式样式

Player类的代码格式是传统的，经验丰富的Java应该能够很容易地理解，这与Tree和Main类有着奇怪的不同。为了保持一致性，您应该使Player类看起来更像rest，或者使其他两个类的代码格式更加传统。