Альфа-бета-обрезка с бинарным деревом поиска - PullRequest
Новая
       93

Альфа-бета-обрезка с бинарным деревом поиска

0 голосов
/ 14 октября 2018

Я работаю по алгоритму Minimax с найденным примером альфа-бета-отсечения здесь .В этом примере они используют массив для реализации дерева поиска.Я последовал примеру, но также попытался реализовать его с помощью двоичного дерева поиска.Вот значения, которые я использую в дереве: 3, 5, 6, 9, 1, 2, 0, -1.

Оптимальное значение в конце должно быть 5. С реализацией BST,Я продолжаю получать 2.

Я думаю, что это проблема, но я не знаю, как обойти это:
Я написал код для возврата из рекурсии, если он видит конечный узел для остановкиот получения исключений нулевого указателя при попытке проверить следующее значение.Но вместо этого, я думаю, что он останавливает поиск слишком рано (основываясь на том, что я вижу при просмотре кода с помощью отладчика).Если я уберу проверку, код потерпит неудачу при нулевом указателе.

Может ли кто-нибудь указать мне правильное направление?Что я делаю не так?

Вот код: 

public class AlphaBetaMiniMax {

    private static BinarySearchTree myTree = new BinarySearchTree();
    static int MAX = 1000;
    static int MIN = -1000;
    static int opt;

    public static void main(String[] args) {
        //Start constructing the game
        AlphaBetaMiniMax demo = new AlphaBetaMiniMax();

        //3, 5, 6, 9, 1, 2, 0, -1
        demo.myTree.insert(3);
        demo.myTree.insert(5);
        demo.myTree.insert(6);
        demo.myTree.insert(9);
        demo.myTree.insert(1);
        demo.myTree.insert(2);
        demo.myTree.insert(0);
        demo.myTree.insert(-1);

        //print the tree
        System.out.println("Game Tree: ");
        demo.myTree.printTree(demo.myTree.root);

        //Print the results of the game
        System.out.println("\nGame Results:");

        //run the  minimax algorithm with the following inputs
        int optimalVal = demo.minimax(0, myTree.root, true, MAX, MIN);
        System.out.println("Optimal Value: " + optimalVal);

    }

    /**
     * @param alpha = 1000
     * @param beta = -1000
     * @param nodeIndex - the current node
     * @param depth - the depth to search
     * @param maximizingPlayer - the current player making a move
     * @return - the best move for the current player
     */
    public int minimax(int depth, MiniMaxNode nodeIndex, boolean maximizingPlayer, double alpha, double beta) {

        //Base Case #1: Reached the bottom of the tree
        if (depth == 2) {
            return nodeIndex.getValue();
        }

        //Base Case #2: if reached a leaf node, return the value of the current node
        if (nodeIndex.getLeft() == null && maximizingPlayer == false) {
            return nodeIndex.getValue();
        } else if (nodeIndex.getRight() == null && maximizingPlayer == true) {
            return nodeIndex.getValue();
        }

        //Mini-Max Algorithm
        if (maximizingPlayer) {
            int best = MIN;

            //Recur for left and right children
            for (int i = 0; i < 2; i++) {

                int val = minimax(depth + 1, nodeIndex.getLeft(), false, alpha, beta);
                best = Math.max(best, val);
                alpha = Math.max(alpha, best);

                //Alpha Beta Pruning
                if (beta <= alpha) {
                    break;
                }
            }
            return best;
        } else {
            int best = MAX;

            //Recur for left and right children
            for (int i = 0; i < 2; i++) {

                int val = minimax(depth + 1, nodeIndex.getRight(), true, alpha, beta);
                best = Math.min(best, val);
                beta = Math.min(beta, best);

                //Alpha Beta Pruning
                if (beta <= alpha) {
                    break;
                }
            }
            return best;
        }
    }
}

Вывод: 

Game Tree: 
-1 ~ 0 ~ 1 ~ 2 ~ 3 ~ 5 ~ 6 ~ 9 ~ 
Game Results:
Optimal Value: 2

1 Ответ

0 голосов
/ 14 октября 2018

Ваша проблема в том, что ваши итерации зависят от элемента управления циклом 2, а не от узла == поиск нуля для nodeIndex.getRight () (для макс.) GetLeft (для мин.)

Запомните деревоимеет 1 голову (первый уровень)

2-й уровень = 2

3-й уровень = 4

4-й 8 и так далее.Таким образом, ваш алгоритм зацикливания даже не опустится на 3 уровня.

for (int i = 0; i < 2; i++) {

     int val = minimax(depth + 1, nodeIndex.getLeft(), false, alpha, beta);
                best = Math.max(best, val);
                alpha = Math.max(alpha, best);

                //Alpha Beta Pruning
                if (beta <= alpha) {
                    break;
                }

Измените ваши циклы, чтобы правильно управлять итерацией, и вы должны легко найти самое высокое значение.

...