Ti c -Ta c -Toe реализация MiniMax всегда возвращает первое свободное место - PullRequest
Новая
       39

Ti c -Ta c -Toe реализация MiniMax всегда возвращает первое свободное место

0 голосов
/ 14 января 2020

Я пытаюсь реализовать Minimax, чтобы найти лучший ход за каждый ход в c -ta c -тое в js.

Однако, он всегда возвращает первое свободное место: 0,0 и когда это место занято 0,1 и так далее. Оказывается, функция miniMax всегда возвращает 1. 

let board = [
    ['', '', ''],
    ['', '', ''],
    ['', '', '']
];

const scores = {
    'X': 1,
    'O': -1
}

function miniMax(board, isMaximizing, player, turns) {
    let winner = checkForWinner(board);
    if (winner != null)
        return scores[winner];
    if (turns > 9)
        return 0;

    let bestScore = isMaximizing ? -Infinity : Infinity;
    let score;

    for (let i = 0; i < 3; i++) {
        for (let j = 0; j < 3; j++) {
            if (board[i][j] == '') {
                board[i][j] = player;
                score = miniMax(board, !isMaximizing, isMaximizing ? p2 : p1, turns + 1)[1];
                board[i][j] = '';
                if (isMaximizing) {
                    if (score > bestScore) {
                        bestScore = score;
                        bestMove = [i, j];
                    }
                }
                else {
                    if (score < bestScore) {
                        bestScore = score;
                        bestMove = [i, j];
                    }
                }
            }
        }
    }

    return [bestMove, bestScore];
}

Я пытался посмотреть на реализацию Minimax других людей для Ti c -Ta c -Toe, но я не мог понять что делает мой сбой.

Что я сделал не так?

РЕДАКТИРОВАТЬ: Я обновил свой код, но теперь он возвращает 0,0, затем 1,0, затем 0 1, затем 2,0, затем 0,2.

1 Ответ

1 голос
/ 15 января 2020

Я вижу 2 проблемы с вашим минимаксным (negamax) кодом:

'1. В своей минимаксной функции вы проходите через каждый квадрат, находя наилучший ход. Однако вы только возвращаете счет, а не лучший ход. Если вы найдете выигрышный ход, напишите это: 

return None, 1

Затем в своем минимаксном рекурсивном вызове вы напишите: 

miniMax(board, !isMaximizing, isMaximizing ? p2 : p1, turns + 1)[1]

В нижней части вы напишите: 

return bestMove, bestScore

Если вы выбираете bestScore, вам также необходимо обновить bestMove, ТОЛЬКО ЕСЛИ меняется максимальный / минимальный балл. Аналогично тому, что вы делаете в функции bestMove.

'2. В вашей функции bestMove вы снова проходите все квадраты. Это то, что заставляет его возвращать один и тот же квадрат снова и снова. Так как ваш минимакс найдет лучший ход, вам нужно только сделать начальный колл: 

bestMove, bestScore = miniMax(board, !isMaximizing, isMaximizing ? p2 : p1, turns + 1)

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

Надеюсь, я что-то понимаю, Engli sh не является моим родным языком, и я привык только кодировать в Python:)

...