minimax 函数始终返回 0

Question

一旦我返回值，问题就开始了，我无法解决它，因为每次我改变极小极大时都会发生奇怪的无限循环。所以我认为算法没问题，问题是检查游戏是否结束的函数，提前感谢。

第一个函数返回获胜者，如果没有获胜者则返回 null

const squares = [
  "x", "", "",
  "", "", "",
  "", "", "",
]

function isGameOver(board, currentMarker) {
  const winingConbinations = [
      [0, 1, 2],
      [3, 4, 5],
      [6, 7, 8],
      [0, 3, 6],
      [1, 4, 7],
      [2, 5, 8],
      [0, 4, 8],
      [2, 4, 6]
  ]

  let winner

  const tie = board.every(e => e !== "") //checks if its a tie
  
  const winResult = winingConbinations.some(combination => {//returns every array insede winingConbinations
      return combination.every(i => squares[i] === currentMarker)//all filled squares equal the index
  })

  if (tie) {
    return "tie"
  }

  if (winResult) {
    winner = currentMarker
    return winner
  }

  return null
}

function minimax(squares, depth, isMax){
  const player = isMax ? "o" : "x"
  const gameResult = isGameOver(squares, player) 
  if (depth === 0 || gameResult) { //checks if the game is over
    if (gameResult === "x") return -1

    if(gameResult === "o") return 1  

    if (gameResult === "tie") return 0
  }

  if (isMax) {//checks if the player is o
    let maxVal = -Infinity
    for (let i = 0; i < squares.length; i++) {
      if (squares[i] === "") {
        squares[i] = "o"
        let score = minimax(squares, depth -1, false)
        squares[i] = ""
        maxVal = Math.max(maxVal, score);
      }
    }
    return maxVal
  } else { //else is x
    let minVal = Infinity
    for (let i = 0; i < squares.length; i++) {
      if (squares[i] === "") {
        squares[i] = "x"
        let score = minimax(squares, depth -1, true)
        squares[i] = ""
        minVal = Math.min(minVal, score);
      }
    }
    return minVal
  }
}

console.log(minimax(squares, 3, true))

Answer 1

问题：

• null

  已返回但未处理，因此

  depth

  可能会变为负值
• 无论哪位玩家获胜，如果棋盘已满则返回

  'tie'

• isMax

  同时意味着两件事：
  • 哪位玩家最后出场
  • 现在哪个玩家在玩

• depth=3

  不足以找到获胜配置

修复：

如果从
• 0 返回

  null

  ，则

  返回 

  isGameOver
• 先查看中奖者，没有，返回

  'tie'

• 将

  isMax ? "o" : "x"

  替换为

  isMax ? "x" : "o"

• 至少使用

  depth=4

稍微固定的版本：

const squares = [
  "x", "", "",
  "", "", "",
  "", "", "",
]

function isGameOver(board, currentMarker) {
  //console.log(board, currentMarker)
  const winingConbinations = [
    [0, 1, 2],
    [3, 4, 5],
    [6, 7, 8],
    [0, 3, 6],
    [1, 4, 7],
    [2, 5, 8],
    [0, 4, 8],
    [2, 4, 6]
  ]


  const winResult = winingConbinations.some(combination => { //returns every array insede winingConbinations
    const x = combination.every(i => {
      const y = squares[i] === currentMarker
      return y
    })
    return x //all filled squares equal the index
  })

  if (winResult) {
    return currentMarker
  }

  const tie = board.every(e => e !== "")

  if (tie) {
    return "tie"
  }

  return null
}

function minimax(squares, depth, isMax) {
  const player = isMax ? "x" : "o"
  const gameResult = isGameOver(squares, player)
  if (depth <= 0 || gameResult) { //checks if the game is over
    if (gameResult === "x") return -1

    if (gameResult === "o") return 1

    if (gameResult === "tie") return 0

    return 0
  }

  if (isMax) { //checks if the player is o
    let maxVal = -Infinity
    for (let i = 0; i < squares.length; i++) {
      if (squares[i] === "") {
        squares[i] = "o"
        let score = minimax(squares, depth - 1, false)
        squares[i] = ""
        maxVal = Math.max(maxVal, score);
      }
    }
    return maxVal
  } else { //else is x
    let minVal = Infinity
    for (let i = 0; i < squares.length; i++) {
      if (squares[i] === "") {
        squares[i] = "x"
        let score = minimax(squares, depth - 1, true)
        squares[i] = ""
        minVal = Math.min(minVal, score);
      }
    }
    return minVal
  }
}

console.log(minimax(squares, 4, false))