MinMax algorithm not working as expected

I'm building a the tic tac toe game (a project on Free Code Camp), and have implemented a minmax algorithm to decide which square the computer player should choose next.

It is working as expected in all cases I have tested, except for the following:

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)

where it is returning: {willWin: 1, nextMove: 5} when I would expect {willWin: 1, nextMove: 7}

I was working off an example implementation in Python: https://gist.github.com/SudhagarS/3942029 that returns the expected result.

Can you see something that would cause this behavior?

---

I added some logging, and discovered that I wasn't flipping between players correctly.

Switching:

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

to:

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

and reversing the scores ( -1 to 1 and 1 to -1 ) returned for the winner when the game is over seems to have done the trick.

链接地址: http://www.djcxy.com/p/56384.html

上一篇: 关于alpha beta修剪的随机性和最小最大值算法

下一篇: MinMax算法不按预期工作