Алгоритм MinMax работает не так, как ожидалось

Я строю игру с tic tac toe (проект на Free Code Camp) и реализовал алгоритм minmax, чтобы решить, какой квадрат должен выбрать компьютерный игрок.Алгоритм MinMax работает не так, как ожидалось

Он работает, как ожидается, во всех случаях я испытал, за исключением следующих случаев:

var userIs = 'o' 
var computerIs = 'x' 

function countInArray(array, what) { 
    var count = 0; 
    for (var i = 0; i < array.length; i++) { 
     if (array[i] === what) { 
      count++; 
     } 
    } 
    return count; 
} 

function nextMove(board, player) { 
    var nextPlayer; 
    if (computerIs !== player) { 
    nextPlayer = userIs; 
    } else { 
    nextPlayer = computerIs; 
    } 
    if (isGameOver(board)) { 
    if (player === userIs) { 
     return { 
     "willWin": -1, 
     "nextMove": -1 
     }; 
    } else { 
     return { 
     "willWin": 1, 
     "nextMove": -1 
     }; 
    } 
    } 

    var listOfResults = []; 

    if (countInArray(board, '-') === 0) { 
    return { 
     "willWin": 0, 
     "nextMove": -1, 
     }; 
    } 

    var _list = [];//keeping track of avalible moves 
    for (var i=0; i < board.length; i++) { 
    if (board[i] === '-') { 
     _list.push(i); 
    } 
    } 
    for (var j = 0; j < _list.length; j++) { 
    board[_list[j]] = player; 
    var nextTry = nextMove(board, nextPlayer); 
    listOfResults.push(nextTry.willWin); 
    board[_list[j]] = '-'; 
    } 
    if (player === computerIs) { 
    var maxele = Math.max.apply(Math, listOfResults); 
    return { 
     "willWin": maxele, 
     "nextMove": _list[listOfResults.indexOf(maxele)] 
    }; 
    } else { 
    var minele = Math.min.apply(Math, listOfResults); 
    return { 
     "willWin": minele, 
     "nextMove": _list[listOfResults.indexOf(minele)] 
    }; 
    } 
} 

function isGameOver(board) { 
    //horizontal wins 
    var gameOver = false; 
    var rowOffset = [0,3,6]; 
    rowOffset.forEach(function(row){ 
    if (board[row] === board[row + 1] && board[row + 1] === board[row + 2] && board[row] !== "-") { 
     gameOver = true; 
    } 
    }); 
    //vertical wins 
    var colOffset = [0,1,2]; 
    colOffset.forEach(function(col){ 
    if (board[col] === board[col + 3] && board[col + 3] === board[col + 6] && board[col] !== "-"){ 
     gameOver = true; 
    } 
    }); 

    ///diag wins 
    if (board[0] === board[4] && board[4] === board[8] && board[8] !== "-") { 
    gameOver = true; 
    } 
    if (board[2] === board[4] && board[4] === board[6] && board[6] !== "-") { 
    gameOver = true; 
    } 
return gameOver; 
} 

nextMove(["x", "x", "o", "o", "x", "-", "-", "-", "o"], computerIs)

, где она возвращается: {willWin: 1, nextMove: 5}, когда я ожидал бы {willWin: 1, nextMove: 7}

Я отработкой пример реализации в Python: https://gist.github.com/SudhagarS/3942029, который возвращает ожидаемый результат.

Вы видите что-то, что может вызвать такое поведение?

источник

2015-12-14 Geoff Wright

Хотя фактический результат отличается от вашего ожидания, действительно ли это _wrong_? Каково содержимое 'listOfResults' перед неожиданным выходом? – Codor

@ Кодор по ошибке, я подразумевал субоптимальное решение. Компьютер сможет выиграть, если они выбрали '7', но только рисуют, если выбрали' 5'. –

Похоже, что список результатов включает все «1», что также неожиданно, потому что не все выборы приводят к победе. Взгляни на это сейчас. –

Я добавил несколько протоколов и обнаружил, что я неправильно переключался между игроками.

Коммутация:

if (computerIs !== player) { 
    nextPlayer = userIs; 
    } else { 
    nextPlayer = computerIs; 
    }

к:

if (computerIs === player) { 
    nextPlayer = userIs; 
    } else { 
    nextPlayer = computerIs; 
    }

и реверсирования оценки (-1 к 1 и 1 к -1) возвращается победителю, когда игра закончена, кажется, сделал трюк ,

источник

2015-12-14 15:44:08

Алгоритм MinMax работает не так, как ожидалось

ответ

Смежные вопросы