Способ получения ускорения на компьютерном решении в С

Question

Я пытаюсь выяснить алгоритмы игры в Гомоку (версия 5 на 5 из tictactoe) с компьютерами. В этом случае я обнаружил, что наиболее часто используемые алгоритмы - это Min-Max(или Alpha-beta), но они слишком сложны для меня. Поэтому я решил использовать следующие коды, которые довольно просты для понимания, но занимают много времени. Это показывает, как компьютеры делают разумный выбор.

//------------------------------------------------------------
// computer_move() checks for all legal moves in the current  |
// position. then for each of them it calls the dfs_search()  |
// function to get the moves' score. And finally it returns   |
// the move with the best score.                              |
//------------------------------------------------------------

int computer_move()  //
{
    int best_move;  // best move so far
    int best_score = -100;  // best score so far 
    int score;  // current score
    int i;

    for (i = 0; i < 16; ++i) { //
        if (pos[i] == EMPTY) {  // if a legal move can be made 
            pos[i] = COMPUTER;  // mark the move
            score = -dfs_search(HUMAN); // 
            pos[i] = EMPTY; // take back the move

            if (score > best_score) {
                best_score = score;
                best_move = i;
            }
        }
    }

    printf("Computer's move: %d\n", best_move);
    return best_move;   // return the best move found
}


//------------------------------------------------------------
// dfs_search() gets the side to move, find all legal moves   |
// for him, and for each move, it recursively calls itself.   |
// It returns a score for the position.                       |
// This recursive function continues on each variation until  |
// the game's end is found in that variation. Which means     |
// that the variation continues until check_result() returns  |
// a value other than CONTINUE.                                   |
// Note that this can be done in tic-tac-toe, since it's a    |
// deterministic game. For games like chess or checkers we    |
// can't continue the variation until reaching the game's end |
// so we have to cut the variation at some point.             |
//------------------------------------------------------------

int dfs_search(int player) // 
{
    int best_score = -100;
    int score;
    int result;
    int i;

    result = check_result(player);
    if (result != CONTINUE) return result;  // return the result

    for (i = 0; i < 16; ++i) {
        if (pos[i] == EMPTY) {
            pos[i] = player;
            score = -dfs_search(CHANGE_PLAYER(player)); // 
            pos[i] = EMPTY;

            if (score > best_score)
                best_score = score;
        }
    }

    return best_score;  // return the best score
}

Для матрицы 3 на 3 это работает довольно хорошо. Однако для 4 на 4 требуется слишком много времени, чтобы покинуть следующий камень. Поскольку причина длительного времени - первые три или четыре решения, я подумал, что просто заставить компьютер искать лучшие точки только вокруг последнего выбора (точки) человека будет решением. После первых трех или четырех решений вышеуказанный формальный алгоритм будет хорошо работать для немногих оставшихся точек. Как вы думаете об этом? И дать несколько советов, чтобы изменить текущий алгоритм.

Answer 1

Вы пытаетесь решить все дерево игры. На доске 3х3 их 9! = 362880 узлов в дереве, которое достаточно мало для вашего компьютера, однако на плате 4x4 их 16! = 20922789888000 (20,9 триллионов) узлов, что слишком много для посещения за разумное время.

Подумайте о реализации алгоритма поиска, который может вернуть разумную оценку оценки текущей позиции, не решая всего дерева игры. Для GoMoku я рекомендую Monte Carlo Tree Search. Он был успешно применен ко многим играм, таким как Go, и в его оригинальной форме не требует написания статической функции оценки, как это требуется для поиска с фиксированной глубиной min-max и его вариантов, таких как альфа-бета.