Застрял на алгоритме minmax с обрезкой альфа-бета

Я пытаюсь реализовать алгоритм minmax с обрезкой альфа-бета в игре крестики-нолики в java. Когда я закончил его кодировать, я сразу же обнаружил исключение ArrayIndexOutOfBounds, поэтому я попытался вывести некоторые выходные данные терминала, чтобы найти ошибку самостоятельно, и обнаружил, что это было вызвано неправильным результатом в окончательном возврате: алгоритм, наконец, возвращает [-1][-1] со счетом -2147483646 и вызывает исключение, когда остальная часть кода пытается сделать ход и ввести координаты в поле. Я сделал некоторую схему для имитации некоторых ходов и некоторого возможного дерева, но я не могу найти ошибку.

   /*
   * int field[][] is the board array, it may contains 0(empty), 1(opponent's seed), 2(computer's seed)
   * nComputer = 2 (computer's seed)
   * nPlayer = 1 (opponent's seed)
   * computerMove = new int[3]
   * remainingMoves has been calculated before the main call
   */

   // Main call
   computerMove = cMove(remainingMoves, nComputer,Integer.MIN_VALUE + 1, Integer.MAX_VALUE - 1);
   field[computerMove[1]][computerMove[2]] = nComputer; // This line cause the exception!!
   // MinMax alpha-beta pruning algorithm
   private static int[] cMove(int depth, int player, int alpha, int beta) {

       int[][] moveList = new int[3][10];
       moveList = generateMoves(field); // See below for details

       int temp;
       int score;
       int bestR = -1;
       int bestC = -1;

       // check function retunrns 1(opponent wins), 2(computer wins), 0(draw) or -1(nothing)
       if(moveList[0][0] == 0 || depth == 0) {
           score = cScore(player);

           return new int[] { score, bestR, bestC };
       } else {
           for (int i = 1;i < moveList[0][0]; i++) {
               // Trying to make a move
               field[moveList[1][i]][moveList[2][i]] = player;

               if(player == nComputer) { // Maximazing player
                   score = cMove(depth -1, nPlayer, alpha, beta)[0];
                   if(score > alpha) {
                       alpha = score;
                       bestR = moveList[1][i];
                       bestC = moveList[2][i];
                   } 
               } else { // Minimizing player
                   score = cMove(depth -1, nComputer, alpha, beta)[0];
                   if(score < beta) {
                       beta = score;
                       bestR = moveList[1][i];
                       bestC = moveList[2][i];
                   } 
               }

               field[moveList[1][i]][moveList[2][i]] = 0; // Undo move
               if(alpha >= beta) i = 10; // Cut-off
           }

           if(player == nComputer) temp = alpha; 
           else temp = beta;

           return new int[] { temp, bestR, bestC };

       }
   }

   /*
   * generateMoves function returns an array 3x10 where [0][0] is the number
   * of possible moves and [0,1,2][1-9] are the score and the
   * coordinates(rows and columns) of all the possible moves
   */
   private static int[][] generateMoves(int[][] field) {
       int[][] result = new int[3][10];
       int k = 0;

       if(check(4) != -1) {
           return result;
       }

       for (int i = 0; i < field.length; i++) {
           for (int j = 0; j < field[0].length; j++) {
               if (field[i][j] == 0) {
                   k++;
                   result[1][k] = i;
                   result[2][k] = j;
               }
           }
       }

       result[0][0] = k;

       return result;
   }

   // cScore function assign a score for the actual node with an heuristic evaluation
private static int cScore(int p) {
    int score = 0;
    score += cRow(p, 0, 0, 0, 1, 0, 2);
    score += cRow(p, 1, 0, 1, 1, 1, 2);
    score += cRow(p, 2, 0, 2, 1, 2, 2);
    score += cRow(p, 0, 0, 1, 0, 2, 0);
    score += cRow(p, 0, 1, 1, 1, 2, 1);
    score += cRow(p, 0, 2, 1, 2, 2, 2);
    score += cRow(p, 0, 0, 1, 1, 2, 2);
    score += cRow(p, 0, 2, 1, 1, 2, 0);
    return score;
 }

private static int cRow(int player, int rOne, int cOne, int rTwo, int cTwo, int rThr, int cThr) {
    int score = 0;

    if (field[rOne][cOne] == nComputer) {
        score = 1;
    } else if (field[rOne][cOne] == nPlayer) {
        score = -1;
    }

    if (field[rTwo][cTwo] == nComputer) {
        if (score == 1) {
            score = 10;
        } else if (score == -1) {
            return 0;
        } else {
            score = 1;
        }
    } else if (field[rTwo][cTwo] == nPlayer) {
        if (score == -1) {
            score = -10;
        } else if (score == 1) {
            return 0;
        } else {
            score = -1;
        }
    }

    if (field[rThr][cThr] == nComputer) {
        if (score > 0) {
            score *= 10;
        } else if (score < 0) {
            return 0;
        } else {
            score = 1;
        }
    } else if (field[rThr][cThr] == nPlayer) {
        if (score < 0) {
            score *= 10;
        } else if (score > 1) {
            return 0;
        } else {
            score = -1;
        }
    }

    return score;
}

Я застрял на этой проблеме в течение одной недели, и я схожу с ума! Заранее спасибо и извините за плохой английский, но это не мой основной язык, и я медленно пытаюсь его выучить.

-------------------------------------------------- ---------------РЕДАКТИРОВАТЬ---------------------------------- --------------------------

Добавление функции проверки по запросу:

// check function first check the state of 5 cells that needs to be filled to won([0,0][0,1][0,2][1,0][2,0])
public static int check(int nMove) {
    int state = -1;

    if(field[0][0] != 0) {
        state = col(0,1);
        if(state == 1 || state == 2) return state; // Win on first col
        state = row(0,1);
        if(state == 1 || state == 2) return state; // Win on first row
        state = diagonal(1);
        if(state == 1 || state == 2) return state; // Win on first diagonal
    }
    if (field[0][1] != 0) {
        state = col(1,2);
        if(state == 1 || state == 2) return state; // Win on second col
    }
    if (field[0][2] != 0) {
        state = col(2,3);
        if(state == 1 || state == 2) return state; // Win on third col
        state = diagonal(2);
        if(state == 1 || state == 2) return state; // Win on second diagonal
    }
    if (field[1][0] != 0) {
        state = row(1,2);
        if(state == 1 || state == 2) return state; // Win on second row
    }
    if (field[2][0] != 0) {
        state = row(2,3);
        if(state == 1 || state == 2) return state; // Win on third row
    }

    if(nMove == 8) return 0; // Draw

    return state;
}
// Check if the entire row is filled (check rows from starting to n points)
private static int row(int start, int n) {
    int s = -1;
    int k = 0;
    int h = 0;

    for (int i = start; i < n; i++) {
        for (int j = 0; j < (field[0]).length; j++) {
            if(field[i][j] == 1) {
                k++;
                if(k==3) s = 1;
            } else if(field[i][j] == 2) {
                    h++;
                    if(h==3) s = 2;
            }
        }
        k=0;
        h=0;
    }

    return s;
}
// Check if the entire col is filled (check cols from starting to n points)
private static int col(int start, int n) {
    int s = -1;
    int k = 0;
    int h = 0;

    for (int i = start; i < n; i++) {
        for (int j = 0; j < (field).length; j++) {
            if(field[j][i] == 1) {
                k++;
                if(k==3) s = 1;
            } else if(field[j][i] == 2) {
                    h++;
                    if(h==3) s = 2;
            }
        }
        k=0;
        h=0;
    }

    return s;
}
// Check if the entire diagonal is filled (check first diagonal if n=1 and second diagonal if n=2)
private static int diagonal(int n) {
    int s = -1;
    int k = 0;
    int h = 0;

    if(n == 1) {
        for (int i = 0; i < (field).length; i++) {
            int j = i;
            if(field[i][j]== 1) {
                k++;
                if(k==3) s = 1;
            } else if(field[i][j] == 2) {
                h++;
                if(h==3) s = 2;
            }
        }
    } else if (n == 2) {
        int j = 2;
        for (int i = 0; i < (field).length; i++) {
            if(field[i][j] == 1) {
                k++;
                if(k==3) s = 1;
            }
            else if(field[i][j] == 2) {
                h++;
                if(h==3) s = 2;
            }
            j--;
        }
    } else { }

    return s;
}

person ludovico    schedule 08.03.2016    source источник
comment
Я поработаю над этим ответом для вас, но не могли бы вы дать мне все свои классы? Много чего не хватает, а что именно, я не знаю. Просто скопируйте и вставьте их все. Дайте мне знать, импортировали ли вы какие-либо банки или что-то в этом роде.   -  person Jon_the_developer    schedule 08.03.2016
comment
Весь код для этого теста очень длинный (около 1 тыс. строк), поэтому для облегчения понимания я решил поделиться только интересующей частью. Эта функция является частью класса IA, и я успешно скомпилировал ее. Но результат всего алгоритма всегда равен [-1][-1] со счетом около 2 * 10^9. Это позволило мне подумать, что проблема в рекурсии, но я не могу понять, где. Если это может быть полезно, я могу опубликовать также алгоритм проверки, а при необходимости и весь код, но я думаю, что это может только запутать. Спасибо за очень быстрый ответ   -  person ludovico    schedule 09.03.2016
comment
Используйте отладчик. Если вы знаете сбой и то, что должен делать ваш код, отладчик фактически даст вам значения, пока вы выполняете код шаг за шагом. Я просто не могу сделать это в своей голове.   -  person Jon_the_developer    schedule 09.03.2016
comment
Я нашел часть кода, которая генерирует исключение, но, будучи рекурсивным, его так сложно отлаживать, и я не могу найти причину, из-за которой он всегда возвращает [-1][-1] со счетом 2147483646   -  person ludovico    schedule 10.03.2016
comment
Конечный результат говорит о том, что cMove вызывается только один раз, поэтому строка if (check(8 - depth) != -1 || depth == 0) { вызывает подозрение. не могли бы вы опубликовать метод проверки?   -  person David Pérez Cabrera    schedule 12.03.2016


Ответы (1)


Предполагая, что ваша доска больше 3x3, в противном случае крестики-нолики с 4 в качестве условия выигрыша не имеют особого смысла, ваше исключение будет вызвано здесь:

for (int i = 0; i < field.length; i++) {
       for (int j = 0; j < field[0].length; j++) {
           if (field[i][j] == 0) {
               k++;
               result[1][k] = i; // out of bounds
               result[2][k] = j; // out of bounds
           }
       }
   }

Для поля размером A x B, когда доска пуста, k станет равным A*B - 1. Для A = B = 7 это будет 48, что больше 9, что является максимальным индексом, допустимым в result[i].

// ====================== РЕДАКТИРОВАТЬ ======================== =========
Я немного запутался и не уверен, что вы пытаетесь оптимизировать (лучший результат для компьютера или плеера?), но я нашел кое-что, что объясняет результат.

В каждом рекурсивном вызове у вас есть переменная player.
В зависимости от ее значения вы обновляете alpha или beta.
В конце рекурсивного шага вы возвращаете alpha или beta в зависимости от значения player.
Но, вы обновляете alpha, если player == 2

if(player == 2) { // Maximazing player
    score = cMove(depth -1, nPlayer, alpha, beta)[0];
    if(score > alpha) {

Но вернуть beta, если player == 2

if(player == 1) temp = alpha;
    else temp = beta;

Таким образом, вы всегда возвращаете MIN_VALUE + 1 вместо alpha или MAX_VALUE - 1 вместо beta.
Поэтому if(score < alpha) { или if(score < beta) { всегда будут ложными для каждого шага, который не вызывает базовый случай. Ваша рекурсия выглядит примерно так:

  • depth = 4, call depth = 3
    • depth = 3, call depth = 2
      • depth = 2, player1 won, score is 42
    • глубина = 3, обновить альфа = 42, вернуть бета = MAX_VALUE - 1 в качестве оценки
  • depth = 4, call3 вернул MAX_VALUE - 1, что является моей бета-версией, так что ничего не изменилось, bestR и bestC остаются -1
person Aracurunir    schedule 08.03.2016
comment
На данный момент я впервые пытаюсь заставить его работать с доской 3x3. Я включил функцию generateMoves только потому, что она может быть источником исключения, выведенного за пределы, в результате алгоритма finally, когда я пытаюсь выполнить результирующий ход, который, будучи [-1] [-1], выходит за пределы границы. Чтобы уточнить, когда я делаю field[cMove[1]][cMove[2]] = nComputer; после вызова функции. В любом случае спасибо за ответ и извините за неточность - person ludovico; 09.03.2016
comment
Я обновил код с предложенными улучшениями, но он по-прежнему возвращает тот же результат, что и раньше. - person ludovico; 10.03.2016