Как эта функция оценки работает в игре Connect 4? (Джава)

Question

Я исследую, как алгоритм Minimax может быть использован в игре "соединяй четыре" с отсечкой альфа-бета.

Поэтому я просматривал исходный код стратегии игрока Connect4 и нашел эту функцию оценки:

/**
* Get the score of a board
*/
public int score(){
    int score = 0;
    for (int r= 0; r < ROWS; r++) {
        if (r <= ROWS-4) {
            for (int c = 0; c < COLS; c++) {
                score += score(r, c);
            }
        } else {
            for (int c = 0; c <= COLS-4; c++) {
                score += score(r, c);
            }
        }
    }
    return score;
}


/**
* Helper method to get the score of a board
*/
public int score(int row, int col){
    int score = 0;
    boolean unblocked = true;
    int tally = 0;
    //int r, c;
    if (row < ROWS-3) {
        //check up
        unblocked = true;
        tally = 0;

        for (int r=row; r<row+4; r++) {
            if (board[r][col] == CHECKERS[1-playerToMoveNum]) {
                unblocked = false;
            }
            if (board[r][col] == CHECKERS[playerToMoveNum]) {
                tally ++;
            }
        }
        if (unblocked == true) {
            score = score + (tally*tally*tally*tally);
        }
        if (col < COLS-3) {
            //check up and to the right
            unblocked = true;
            tally = 0;
            for (int r=row, c=col; r<row+4; r++, c++) {
                if (board[r][c] == CHECKERS[1-playerToMoveNum]) {
                    unblocked = false;
                }
                if (board[r][c] == CHECKERS[playerToMoveNum]) {
                    tally ++;
                }
            }
            if (unblocked == true) {
                score = score + (tally*tally*tally*tally);
            }
        }
    }
    if (col < COLS-3) {
        //check right
        unblocked = true;
        tally = 0;
        for (int c=col; c<col+4; c++) {
            if (board[row][c] == CHECKERS[1-playerToMoveNum]) {
                unblocked = false;
            }
            if (board[row][c] == CHECKERS[playerToMoveNum]) {
                tally ++;
            }
        }
        if (unblocked == true) {
            score = score + (tally*tally*tally*tally);
        }
        if (row > 2) {
            //check down and to the right
            unblocked = true;
            tally = 0;
            for (int r=row, c=col; c<col+4; r--, c++) {
                if (board[r][c] == CHECKERS[1-playerToMoveNum]) {
                    unblocked = false;
                }
                if (board[r][c] == CHECKERS[playerToMoveNum]) {
                    tally ++;
                }
            }
            if (unblocked == true) {
                score = score + (tally*tally*tally*tally);
            }
        }
    }
    return score;
}

Я нашел весь этот код в этом PDF: http://ryanmaguiremusic.com/media_files/pdf/ConnectFourSource.pdf

Я просто хочу понять, как работает эта функция оценки, и решает, какой шаг лучше сделать... Кто-нибудь может мне помочь? Это будет с благодарностью.

Answer 1

Вот общий ответ:

Оценка должна дать лучшие значения для лучших позиций. В играх положение часто оценивается путем вычисления оценки следующим образом: увеличивайте оценку для желаемых конфигураций / событий и уменьшайте ее для нежелательных. Решить, насколько оцениваемый объект должен изменить значение (= балансирование весов), может быть очень сложно.

Если мы применяем это для подключения четырех, то одной из функций может быть количество живых угроз. Но для действительно хорошего алгоритма (который решает 7x6) вы должны посмотреть, находится ли выигрышный ход на нечетной или четной линии. И затем есть некоторые правила, такие как "если у 2-го игрока есть 2 даже угрозы, которые он выиграл в игре" (все сводится к тому, что при заполнении игрового поля и при принудительных ходах данное правило немного упрощается: 2-й игрок будет должен убить четную угрозу, если он не может заполнить другие столбцы, если у 1-го игрока есть нечетная угроза).

Простой пример для данного правила (О = первый игрок, Х = второй игрок), Х выигрывает:

  * X X X *
O   O X O   O
1 2 3 4 5 6 7

Когда-то об этом была очень подробная научная статья. Самое близкое, что я мог найти на данный момент: http://web.mit.edu/sp.268/www/2010/connectFourSlides.pdf Должен дать вам несколько идей.

Btw. Вводные книги (обычно предопределенная мудрость в любой форме, например, joseki, fuseki) и специальные оценщики конечных игр могут значительно улучшить производительность минимакса.