Minimax算法JS實現

Question

我有一些JavaScript代碼，而試圖編碼一個井字遊戲遊戲。
所以AI（人工智能）播放「X」，分別爲「人」播放器爲「O」;
對於測試我把板作爲
[ 'E'， 'E'， '0'，
'X'，  'O'， 'E'，
'E'，  'e' 的，'e']
這是AI轉動。所以很明顯的AI（人工智能）的最佳舉措是
[ 'E'， 'E'， 'O'，
'X'，  'O'， 'E'，
'X'，  'e'，'e']。
但它返回我
[ 'X'， 'E'， 'O'，
'X'，  'O'， 'E'，
'E'，  'E'，' e'] 變體。
我將不勝感激，爲好的提示，這將重新導向我以正確的方式。
是的，我讀了一個星期關於Minimax的文章一堆。我個人用作本教程的原型http://blog.circuitsofimagination.com/2014/06/29/MiniMax-and-Tic-Tac-Toe.html。
所以，請看看我的代碼：

var board = ['e', 'e', 'o', 'x', 'o', 'e', 'e', 'e', 'e']; 
var signPlayer = 'o'; 
var signAI = (signPlayer === 'x') ? 'o' : 'x'; 

//Circuits Of Imagination 

game = { 
    over: function(board) { 
     for (var i = 0; i < board.length; i += 3) { 
      if (board[i] === board[i + 1] && board[i + 1] === board[i + 2]) { 
       return board[i] !== 'e' ? board[i] : false; 
      } 
     } 
     for (var j = 0; j < board.length; j++) { 
      if (board[j] === board[j + 3] && board[j + 3] === board[j + 6]) { 
       return board[j] !== 'e' ? board[j] : false; 
      } 
     } 
     if ((board[4] === board[0] && board[4] === board[8]) || 
     (board[4] === board[2] && board[4] === board[6])) { 
      return board[4] !== 'e' ? board[4] : false; 
     } 
     var element; 
     if (board.every(function(element) { 
      return element !== 'e'; 
     })) { 
      return true; 
     } 
    }, 
    winner: function(board) { 
     return game.over(board); 
    }, 
    possible_moves: function(board, sign) { 
     var testBoard = [], 
     nextBoard; 
     for (var i = 0; i < board.length; i++) { 
      nextBoard = board.slice(); 
      if (nextBoard[i] === 'e') { 
       nextBoard[i] = sign; 
       testBoard.push(nextBoard); 
      } 
     } 
     return testBoard; 
    } 
} 

function score(board) { 
    if (game.winner(board) === signPlayer) { 
     return -10; 
    } else if (game.winner(board) === signAI) { 
     return +10; 
    } else { 
     return 0; 
     //Game is a draw 
    } 
} 

function max(board) { 

    if (game.over(board)) { 
     return score(board); 
    } 
    var newGame = []; 
    var best_score = -10; 
    var movesArray = game.possible_moves(board, signAI); 

    for (var i = 0; i < movesArray.length; i++) { 
     newGame = movesArray[i].slice(); 
     score = min(newGame); 
     if (score > best_score) { 
      best_score = score; 
     } 
     console.log('maxnewGame', newGame); 
     return best_score; 
    } 
} 

function min(board) { 

    if (game.over(board)) { 
     return score(board); 
    } 
    var newGame = []; 
    var worst_score = 10; 
    var movesArray = game.possible_moves(board, signPlayer); 

    for (var i = 0; i < movesArray.length; i++) { 
     newGame = movesArray[i].slice(); 
     score = max(newGame); 
     if (score < worst_score) { 
      worst_score = score; 
     } 
     console.log('minnewGame', newGame); 
     return worst_score; 
    } 
} 
max(board); 

Answer 1

有代碼中的一些錯誤：

1. 您的循環，提前終止搜索了return best/worst_score內。把它帶出循環。
2. score在循環中被重新定義爲一個數字，當它應該是一個函數。將它重命名爲moveScore。
3. max/minnewGame設置不正確。
4. best/worse_score被啓動到+/- 10，這意味着有時沒有找到最大值。

固定代碼如下。 但是請注意，X仍然沒有選擇「明顯」的舉動。這實際上是爲您的minimax算法而設計的。這是由於該算法假定對手正在玩最佳狀態。在你給定的棋盤狀態下，最優的對手會使得不可能贏得X.因此，算法「放棄」並選擇第一個可能的棋步。

這是minmax算法的最大特性之一：該算法只能做出與其對手一樣好的決定。如果對手是最佳模擬的，算法不會考慮錯誤和放棄的可能性。爲了使算法可以選擇你認爲什麼，明顯的舉動，你必須讓算法也考慮到轉，直到損失，所以它會嘗試在遊戲中儘可能晚地失敗（這可以是通過給予失敗移動來完成-10+turns，其中turn是它失去的轉數）。另一種方法是根據各州可能的比賽來製作比分，並贊成以X獲勝的更可能的狀態進行比賽。

var board = ['e', 'e', 'o', 'x', 'o', 'e', 'e', 'e', 'e']; 
 
var signPlayer = 'o'; 
 
var signAI = (signPlayer === 'x') ? 'o' : 'x'; 
 

 
//Circuits Of Imagination 
 

 
game = { 
 
    over: function(board) { 
 
    for (var i = 0; i < board.length; i += 3) { 
 
     if (board[i] === board[i + 1] && board[i + 1] === board[i + 2]) { 
 
     return board[i] !== 'e' ? board[i] : false; 
 
     } 
 
    } 
 
    for (var j = 0; j < board.length; j++) { 
 
     if (board[j] === board[j + 3] && board[j + 3] === board[j + 6]) { 
 
     return board[j] !== 'e' ? board[j] : false; 
 
     } 
 
    } 
 
    if ((board[4] === board[0] && board[4] === board[8]) || 
 
     (board[4] === board[2] && board[4] === board[6])) { 
 
     return board[4] !== 'e' ? board[4] : false; 
 
    } 
 
    var element; 
 
    if (board.every(function(element) { 
 
     return element !== 'e'; 
 
    })) { 
 
     return true; 
 
    } 
 
    }, 
 
    winner: function(board) { 
 
    return game.over(board); 
 
    }, 
 
    possible_moves: function(board, sign) { 
 
    var testBoard = [], 
 
     nextBoard; 
 
    for (var i = 0; i < board.length; i++) { 
 
     nextBoard = board.slice(); 
 
     if (nextBoard[i] === 'e') { 
 
     nextBoard[i] = sign; 
 
     testBoard.push(nextBoard); 
 
     } 
 
    } 
 
    return testBoard; 
 
    } 
 
} 
 

 
function score(board) { 
 
    if (game.winner(board) === signPlayer) { 
 
    return -10; 
 
    } else if (game.winner(board) === signAI) { 
 
    return +10; 
 
    } else { 
 
    return 0; 
 
    //Game is a draw 
 
    } 
 
} 
 

 
function max(board) { 
 

 
    if (game.over(board)) { 
 
    return score(board); 
 
    } 
 
    var newGame = []; 
 
    var moveScore, maxnewGame; 
 
    var best_score = -Infinity; 
 
    var movesArray = game.possible_moves(board, signAI); 
 

 
    for (var i = 0; i < movesArray.length; i++) { 
 
    newGame = movesArray[i].slice(); 
 
    moveScore = min(newGame); 
 
    if (moveScore > best_score) { 
 
     best_score = moveScore; 
 
     maxnewGame = newGame; 
 
    } 
 
    } 
 
    console.log('maxnewGame', maxnewGame); 
 
    return best_score; 
 
} 
 

 
function min(board) { 
 

 
    if (game.over(board)) { 
 
    return score(board); 
 
    } 
 
    var newGame = []; 
 
    var moveScore, minnewGame; 
 
    var worst_score = Infinity; 
 
    var movesArray = game.possible_moves(board, signPlayer); 
 

 
    for (var i = 0; i < movesArray.length; i++) { 
 
    newGame = movesArray[i].slice(); 
 
    moveScore = max(newGame); 
 
    if (moveScore < worst_score) { 
 
     worst_score = moveScore; 
 
     minnewGame = newGame; 
 
    } 
 
    } 
 
    console.log('minnewGame', minnewGame); 
 
    return worst_score; 
 
} 
 
console.log(max(board));