Алгоритм минимаксного альфа-бета-отсечения занимает слишком много времени, чтобы решить Tic Tac Toe (доска 10х10)

Question

Я сделал игру Tic Tac Toe двух типов в Javascript. Один 3х3, а другой 10х10.

Я использую алгоритм Minimax с Alpha Beta Pruning для решения обеих игр. В 3х3, где дерево игры действительно маленькое, алгоритм работает отлично.

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

В нескольких статьях я читал, что Minimax с альфа-бета-обрезкой может легко решить Tic Tac Toe 10x10 или больше. Это неверно, или Мой код плохой?

Вот мой код, но я думаю, что это будет трудно понять. Но код не имеет значения, я думаю. Я применил Minimax + Alpha Beta Pruning. Что еще я могу сделать?

function makeBotMove(newBoard, availMoves, XorO, firstCall) { // newBoard stores board state in an array. availMoves stores Available moves in an array (0-99). XorO store either "X" or "O" depending on whoes turn it is. firstCall is used to find out If the call is made inside the function or not. I need it for Alpha Beta Pruning. It helps in storing the length of the total available moves when the call was made for
    if (firstCall)
    {
        var originalAvailMovesLength = availMoves.length;
        if (originalAvailMovesLength == board.length)
            var maxPossibleResult = 0.5; // OriginalAvailMoves will be only 100, if it is the first move. And if it is first move, it is impossible to get reward of 1. The best the computer can do is, draw (0.5 reward). 
        else
            var maxPossibleResult = 1;
    }

    availMoves = getAvailableMoves(newBoard);

    var result = checkResult(newBoard, false); // It can return 4 values. 1 = Win, 0.5 = Draw, 0 = Game is on, -1 = Lose.
    if (result != 0) 
        return [result];

    var movesIndex = []; 
    var movesScore = []; 
    for (var i = 0; i < availMoves.length; i++)
    {

        var move = availMoves[i];  
        newBoard[move] = XorO; 
        availMoves.splice(availMoves.indexOf(Number(move)),1); 
        if (XorO == "O") // 1.) Yes 
            var reward = makeBotMove(newBoard, availMoves, "X", false); 
        else 
            var reward = makeBotMove(newBoard, availMoves, "O", false); 

        newBoard[move] = "-"; 

        availMoves.push(move);
        availMoves.sort();


        movesIndex.push(move); 
        movesScore.push(reward[0]); 
        var bestMove = [];
        if (originalAvailMovesLength == availMoves.length && Math.max(...movesScore) == maxPossibleResult)
        {
            bestMove[0] = Math.max(...movesScore);
            bestMove[1] = movesScore.indexOf(bestMove[0]);
            bestMove[1] = movesIndex[bestMove[1]];
            return bestMove;
        }
    }


    if (XorO == "O") 
        bestMove[0] = Math.max(...movesScore);
    else 
        bestMove[0] = Math.min(...movesScore);

    bestMove[1] = movesScore.indexOf(bestMove[0]);
    bestMove[1] = movesIndex[bestMove[1]];

    return bestMove;

}

Если минимаксный алгоритм, не может сделать работу. Какой алгоритм вы, ребята, рекомендуете? Это не должно быть очень сложно, я не очень хороший кодер до сих пор.

Редактировать: В 10x10 игроку нужно сделать 5 ходов подряд, чтобы выиграть вместо 3.

Answer 1

Ваш код показывает, что вы продолжаете делать рекурсивные вызовы до тех пор, пока у вас не получится выигрыш / проигрыш или пока доска не заполнится. Поскольку создание 5-в-рядов не является тривиальным в игре между экспертами, этот поиск потенциально должен был бы посещать большинство позиций рисования, которые, по моим оценкам, составили бы около 10¹⁰⁰ позиций на доске 10х10, учитывая, что 100! почти 10¹⁵⁸ (но мы должны вычесть из этих всех побед и поражений). В любом случае, такое количество досок нереально найти, так как количество атомов в видимой вселенной меньше. Так что не ждите завершения кода. Это не будет в вашей жизни.

Существует два основных способа сократить время, затрачиваемое на вычисление хорошего хода:

1. Уменьшить глубину дерева поиска
2. Уменьшить ширину дерева поиска

Для первого действия вы можете определить жестко заданную максимальную глубину рекурсивного поиска. Если вы достигли такой глубины и игра еще не закончена, то вызовите функцию оценки, которая должна давать оценку текущей доске, не играя больше ходов. Поэтому следует взглянуть на несколько простых шаблонов, например, "3 в ряд", и позволить им внести свой вклад в окончательный счет. Это эвристика, что означает (надеюсь) хорошее предположение: значение должно быть где-то между двумя крайностями: выигрыш и проигрыш.

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

Кроме того, вы можете создать хеш-таблицу (новую после каждого действительно сыгранного хода), в которой хранятся доски, которые вы уже оценили, так что вы больше не будете выполнять эту работу, если попадете туда через обмен ходами одного игрока в дереве поиска., Удостоверьтесь, что хеш-таблица также ловит зеркальные или перевернутые доски, что уменьшит первые пару ходов игры.

Есть много других методов, таких как отслеживание "убийственных" ходов во время поиска. Если в одной ветви дерева поиска выясняется, что есть ход, который может принести выигрыш или избежать проигрыша, попробуйте этот ход в первую очередь и в альтернативных ветвях. Это может привести к быстрой обрезке по альфа-бета-механизму. В более общем плане важно посещать ваши ходы в порядке убывания "качества". Конечно, вы не знаете, насколько хорош ход, пока не проанализируете его, но, опять же, есть некоторые статичные вещи, которые вы можете заметить о ходах. Ход в углу доски, конечно, не так хорош, как в центре, и т. Д.

Некоторые варианты поиска сначала выполняют поиск на 1 глубину и используют результат для сортировки ходов по результату оценки. Затем выполняется поиск по 2 глубинам, и снова ходы сортируются по этому (более точному) результату... и т. Д., Пока не будет достигнута конечная глубина. Это может показаться большой работой, но сокращение альфа-бета даст наибольшую выгоду, когда движения будут упорядочены оптимально, и это будет более определяющим фактором для общей эффективности.