javascript - 尝试在我的井字棋中实现 Minimax AI (javascript)

Question

所以在阅读了一些关于 Minimax 的博客之后，例如 http://neverstopbuilding.com/minimax ，从概念上讲我理解，但使用我当前的代码，我很难执行它。

到目前为止，我有一个非常简单的计算机人工智能，它只是随机选择当前状态下的任何可用 Action 。

任何人都可以给我一个关于从哪里开始的提示/技巧吗？我假设创建类似新 State 对象的东西，但不确定..

$(document).ready(function(){
  var human;
  var computer;
  var board = new Board()
  var game;

  function Human(symbol){
    this.name = "Player",
    this.symbol = symbol;
  }
  function Computer(symbol){
    this.name = "Computer",
    this.symbol = symbol;
  }

  //Modal opens when page is rendered. User can choose symbol
  $("#myModal").modal()

  $("#xPlayer").on('click',function(){
    human = new Human("X");
    computer = new Computer("O");
    board.initalize();
    game = new Game(human)
    game.play();
  })
  $("#oPlayer").on('click',function(){
    human = new Human("O")
    computer = new Computer("X");
    board.initalize();
    game = new Game(computer)
    game.play();
  })

  //Board constuctor
  function Board(){
  this.board = []
  this.status = "";
  }

  //method calls for an empty board filled with "E"
  Board.prototype.initalize = function(){
    $("td p").empty()
    this.board = ["E","E","E","E","E","E","E","E","E"]
    this.status = "New Game";
  }
  //return true if there is a win. Otherwise, false
  Board.prototype.win = function(){
    var B = this.board;
    //check row
    for (var i = 0; i <= 6; i = i + 3){
      if (B[i] !== "E" && (B[i] === B[i+1]) && (B[i+1] === B[i+2])){
        board.status = "Winner is: " + game.currentPlayer.name
        return true
      }
    }
    //check column
    for (var i = 0; i <= 2 ; i++ ){
      if (B[i] !== "E" && (B[i] === B[i+3]) && (B[i+3] === B[i+6])){
        board.status = "Winner is: " + game.currentPlayer.name
        return true
      }
    }
    //check diagonal
    for(var i = 0, j = 4; i <= 2 ; i = i + 2, j = j - 2) {
      if(B[i] !== "E" && (B[i] == B[i + j])  && (B[i + j] === B[i + 2 * j]) ) {
        board.status = "Winner is: " + game.currentPlayer.name
        return true;
      }
    }
    return false
  }

  //checks if the current status is draw. If so, updates the status to "Draw"
  Board.prototype.draw = function(){
    //checks if the board itself is draw
    for(var i = 0; i < this.board.length ; i++){
      if (this.board[i] === "E"){
        return false;
      }
    }
    board.status = "Draw!"
    return true;
  }
  //method returns array of indexes that are not empty cells in the board
  Board.prototype.available = function(){
    var B = this.board;
    var indexes = [];
    for (var i = 0; i < B.length ; i ++){
      if (B[i] === "E"){
        indexes.push(i)
      }
    }
    return indexes;
  }

  //checks first if the User Input is valid or not
  Board.prototype.validMove = function(position){
  var availableCells =  this.available();
  return availableCells.includes(position);
  }

  //updates the board when using jQuery click
  Board.prototype.updateBoard = function(position,playerInput) {
    var availableCells =  this.available();
    if (availableCells.includes(position)){
      this.board[position] = playerInput
    }
  };

  function Game(firstPlayer){
    this.currentPlayer = firstPlayer;
    this.over = false;
    this.win = "";
  }

  Game.prototype.switchPlayer = function(){
    this.currentPlayer = (this.currentPlayer === human) ? computer : human
  }

  Game.prototype.restart = function(){
    board.initalize();
  }

  Game.prototype.gameover = function(){
    if (board.win() || board.draw()){
      alert(board.status)
      game.restart();
    }
  }

  Game.prototype.play = function(){
    board.status = "Game playing"
    if(game.currentPlayer === computer){
      computer.makeMove();
      game.switchPlayer();
    };
    // console.log(game.currentPlayer)
    $("td").click(function(){
      var position = $(this).attr("id");
      var positionNumber = parseInt(position.slice(4,5));
      // This here renders to the board and updates board.board

      if(board.validMove(positionNumber)){
      //Checks if the move is valid. If it is, append it.
      //Otherwise, alert the user that it is taken
        $(this).find("p").append(game.currentPlayer.symbol)
        board.updateBoard(positionNumber, game.currentPlayer.symbol)
        //Check if it the game is over or draw
        //If either is true, play new game
        game.gameover();
        game.switchPlayer();
        if (game.currentPlayer.name === "Computer" ){
          computer.makeMove();
          game.gameover();
          game.switchPlayer();
        }
      }else{
        alert("Try Again!")
      }
    })
  }

  Computer.prototype.makeMove = function(){
    var availableMoves = board.available()
    // random move without any AI implementation
    var computerPosition = availableMoves[Math.floor(Math.random() * availableMoves.length)];
    $("#cell" + computerPosition + " p").append(game.currentPlayer.symbol);
    board.updateBoard(computerPosition,game.currentPlayer.symbol)
  }

})

body {
  background: skyblue; }

#tictactoe {
  max-width: 700px;
  min-height: 300px;
  margin: 68px auto;
  display: flex;
  width: 100%; }
  #tictactoe table {
    width: 100%;
    font-size: 65px;
    text-align: center;
    vertical-align: middle;
    table-layout: fixed; }

td {
  height: 115px;
  color: #101935;
  background: #F2FDFF;
  border: 5px solid #DBCBD8;
  border-radius: 12px;
  cursor: pointer;
  transition: background 0.5s ease-out, color 0.5s ease-out; }
  td:hover {
    background: #564787;
    color: #F2FDFF; }

.modal-dialog {
  text-align: center; }
  .modal-dialog .modal-footer {
    text-align: center; }

<html lang="en">
<head>
  <meta charset="UTF-8">
  <meta name="viewport" content="width=device-width, initial-scale=1">
  <title>TicTacToe FCC</title>
  <link rel="stylesheet" href="https://maxcdn.bootstrapcdn.com/bootstrap/3.3.6/css/bootstrap.min.css" integrity="sha384-1q8mTJOASx8j1Au+a5WDVnPi2lkFfwwEAa8hDDdjZlpLegxhjVME1fgjWPGmkzs7" crossorigin="anonymous">
  <link rel="stylesheet" href="css/styles.css">
  <script src="https://ajax.googleapis.com/ajax/libs/jquery/2.2.4/jquery.min.js"></script>
  <script src="https://maxcdn.bootstrapcdn.com/bootstrap/3.3.6/js/bootstrap.min.js"></script>
</head>
  <body>
    <div id="tictactoe">
      <table id="game-board">
        <tbody>
          <tr id="row1">
            <td id="cell0"><p></p></td>
            <td id="cell1"><p></p></td>
            <td id="cell2"><p></p></td>
          </tr>
          <tr id="row2">
            <td id="cell3"><p></p></td>
            <td id="cell4"><p></p></td>
            <td id="cell5"><p></p></td>
          </tr>
          <tr id="row3">
            <td id="cell6"><p></p></td>
            <td id="cell7"><p></p></td>
            <td id="cell8"><p></p></td>
          </tr>
        </tbody>
      </table>
    </div>
    <!--Modal Window -->
    <div id="myModal" class="modal fade" role="dialog">
        <div class="modal-dialog">
            <div class="modal-content">
                <div class="modal-header">
                    <h4 class="modal-title">Choose your character!</h4>
                </div>
                <div class="modal-body">
                    <p>Have fun!</p>
                </div>
                <div class="modal-footer">
                  <button type="button" id="xPlayer" class="btn btn-default" data-dismiss="modal">X</button>
                  <button type="button" id="oPlayer" class="btn btn-default" data-dismiss="modal">O</button>
                </div>
            </div>
        </div>
    </div>


  </body>
  <script src="js/javascript.js" type="text/javascript"></script>
</html>

Answer 1

这是基本思想，您必须填写 evaluate() 和 board.isTerminal() 的详细信息，并且可能还需要对其进行调试，因为我没有不检查它。可以使用称为 negamax 的算法来实现更简洁的实现，但请坚持使用它，直到您熟悉它以及它为什么/如何工作为止。

Computer.prototype.makeMove = function() {
    function evaluate(board) {
        // if win for current player, return 1, loss return -1, tie return 0
    }
    function max(board) {
        if (board.isTerminal()) return evaluate(board);
        var successors = board.available();
        var best = Number.NEGATIVE_INFINITY;
        for(var i = 0; i < successors.length; i++) {
            var moveScore = min(successors[i]);
            best = Math.max(best, moveScore);
        }
        return best;
    }
    function min(board) {
        if (board.isTerminal()) return evaluate(board);
        var successors= board.available();
        var best = Number.POSITIVE_INFINITY;
        for(var i = 0; i < successors.length; i++) {
            var moveScore = max(successors[i]);
            best = Math.min(best, moveScore);
        }
        return best;
    }
    function selectMove(board) {
        if (board.isTerminal()) throw "something went terribly wrong";
        var successors = board.available();
        var best = Number.NEGATIVE_INFINITY;
        var bestMove = null;
        for(var i = 0; i < successors.length; i++) {
            var moveScore = min(successors[i]);
            if (moveScore < best) {
                bestMove = successors[i];
                best = moveScore;
            }
        }
        return bestMove;
    }
    var computerPosition = selectMove(board);
    $("#cell" + computerPosition + " p").append(game.currentPlayer.symbol);
    board.updateBoard(computerPosition,game.currentPlayer.symbol)
}