javascript - 极小极大算法的实现错误在哪里？

Question

它在 Tic-Tac-Toe 游戏的实现中存在一个小问题。对于以下组合:

['x', 'o', 'e',  
 'o', ' e', 'e',  
 'e', ' e', 'e']  

最好的选择是

['x', 'o', 'e',  
 'o', ' x', 'e',  
 'e', ' e', 'e']  

但它返回的是我认为最接近的合适的:

['x', 'o', 'x',  
 'o', ' e', 'e',  
 'e', ' e', 'e']   

在这种情况下，人工智能输了。这是代码:

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

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 < 3; 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;
        }
        return ( board.every(function(element) {
            return element !== 'e';
        })) 
    },
    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 moveScore(board) {
    var result = game.winner(board);

    if (result === signPlayer) {
        return -100;
    }
    if (result === signAI) {
        return +100;
    }
    return 0;
    //Game is a draw
}

function max(board) {

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

    for (var i = 0; i < movesArray.length; i++) {
        newGame = movesArray[i].slice();
        score = moveScore(min(newGame));
        if (score > best_score) {
            best_score = score;
            bestMove = newGame;
        }
    }
    return bestMove;
}

function min(board) {

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

    for (var i = 0; i < movesArray.length; i++) {
        newGame = movesArray[i].slice();
        score = moveScore(max(newGame));
        if (score < worst_score) {
            worst_score = score;
            worstMove = newGame;
        }
    }
    return worstMove;
}

max(board);

Answer 1

存在以下问题:

• over 方法会为某些板提供错误的输出，例如此板:

  ['e', 'e', 'e', 'o', 'o', 'o', 'x', 'x', 'e']
  

  在前三个元素中找到三个 e 值并返回 false 后，它实际上会停止查找，即它在第二行中看不到胜利o。要修复此问题，请更改此行:

  return board[i] !== 'e' ? board[i] : false;
  

  至:

  if (board[i] !== 'e') return board[i];
  

  如果函数连续找到三个 e，这将使该函数继续进行其他检查。其他循环中也需要类似的修复(最后一个循环除外)。

• 尽管极小极大算法成功访问了搜索树中的节点，但它不会将找到的叶分数(0、-100 或 100)带回到搜索树中。相反，您只需查看静态板配置即可重新计算每个位置的分数，忽略从递归调用中可以获得的最佳/最差分数。要解决此问题，请让 min 和 max 函数不仅返回最佳移动，还返回与其关联的分数。所以替换这个:

  return bestMove;
  

  与:

  return [best_score, bestMove];
  

  然后你可以从递归调用中获取分数，如果你替换它:

  score = moveScore(min(newGame));
  

  与:

  score = min(newGame)[0];
  

  对于游戏结束的情况，您需要进行类似的更改。替换这个:

  if (game.over(board)) {
      return board;
  }
  

  与:

  if (game.over(board)) {
      return [moveScore(board), []];
  }
  

  请注意，这是调用 moveScore 的唯一正确时机。数组的第二个元素应该是最好的移动，但由于没有移动，所以最好只使用一个空数组。

• 这是一个小问题:您实际上并没有使用从对 max 的主调用中获得的最佳移动。通过上述更改，您可以在主调用中获得最佳 Action 及其得分:

  [score, nextBoard] = max(board);
  

这是更正后的代码，末尾有一些附加代码，允许通过单击 3x3 网格来玩游戏。为此，我将代码 e 更改为空格，因为它在打印板上看起来更好:

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

var 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] !== ' ' ? board[i] : false;
                if (board[i] !== ' ') return board[i];
            }
        }
        for (var j = 0; j < 3; j++) {
            if (board[j] === board[j + 3] && board[j + 3] === board[j + 6]) {
                //return board[j] !== ' ' ? board[j] : false;
                if (board[j] !== ' ') return board[j];
            }
        }
        if ((board[4] === board[0] && board[4] === board[8]) || 
                (board[4] === board[2] && board[4] === board[6])) {
            //return board[4] !== ' ' ? board[4] : false;
            if (board[4] !== ' ') return board[4];
        }
        return ( board.every(function(element) {
            return element !== ' ';
        })) 
    },
    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] === ' ') {
                nextBoard[i] = sign;
                testBoard.push(nextBoard);
            }
        }
        return testBoard;
    }
}

function moveScore(board) {
    var result = game.winner(board);

    if (result === signPlayer) {
        return -100;
    }
    if (result === signAI) {
        return +100;
    }
    return 0;
    //Game is a draw
}

function max(board) {
    //if (game.over(board)) {
    //    return board;
    //}
    if (game.over(board)) {
        return [moveScore(board), []];
    }
    var newGame = [];
    var bestMove = [];
    var score;
    var best_score = -Infinity;
    var movesArray = game.possible_moves(board, signAI);
    for (var i = 0; i < movesArray.length; i++) {
        newGame = movesArray[i].slice();
        //score = moveScore(min(newGame));
        score = min(newGame)[0];
        if (score > best_score) {
            best_score = score;
            bestMove = newGame;
        }
    }
    //return bestMove;
    return [best_score, bestMove];
}

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

    for (var i = 0; i < movesArray.length; i++) {
        newGame = movesArray[i].slice();
        //score = moveScore(max(newGame));
        score = max(newGame)[0];
        if (score < worst_score) {
            worst_score = score;
            worstMove = newGame;
        }
    }
    //return worstMove;
    return [worst_score, worstMove];
}

// Extra code for adding a simple GUI

var board = [' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' '];
var score = null;

var tds = Array.from(document.querySelectorAll('td'));
var table = document.querySelector('table');
var span = document.querySelector('span');

function display(board, score) {
    board.forEach( (v, i) => tds[i].textContent = v );
    span.textContent = score;
}
display(board);

table.onclick = function (e) {
    var i = tds.indexOf(e.target);
    if (i == -1 || board[i] !== ' ' || game.over(board)) return;
    board[i] = signPlayer;
    display(board);
    [score, board] = max(board, 1);
    display(board, score);
}

td { border: 1px solid; width: 20px; text-align: center; cursor: hand }
tr { height: 25px; v-align: middle }

<table>
<tr><td></td><td></td><td></td></tr>
<tr><td></td><td></td><td></td></tr>
<tr><td></td><td></td><td></td></tr>
</table>
<div>
Score: <span></span>
</div>

最后说明

我刚刚进行了更正以使其正常工作，但请注意有多种方法可以提高效率。您可以通过使用 alpha-beta 搜索、跟踪已评估棋盘的分数、同时通过平移(转动、镜像)映射类似棋盘以及变异棋盘(而不是每次下棋时创建新棋盘)来实现此目的。