实现极小极大

Question

有人可以帮我解决这个问题吗？我正在尝试为我的 Tic-Tac-Toe 游戏编写 AI，所有相关搜索都将我带到了 minimax 算法。从我阅读和观看的所有内容中，我对算法背后的理论有了基本的了解。我遇到的问题是它在我的游戏中的实际应用。我知道这个算法基本上应该根据棋盘的状态来计算每一步棋和 return 的分数。我如何让它每次都播放不同的组合？我如何确保我得到每一个组合？在找到获胜状态后，我如何 return 从那里开始正确的移动？我应该将每个状态存储在一个数组中吗？对于所有问题，我深表歉意，我只是想巩固我的理解，并确保我能真正将我正在阅读的内容付诸实践。我正在提供游戏的 javascript 代码，希望有人能在这里为我指明正确的方向。谢谢。

$(document).ready(function() {

    var x = 'X';
    var o = 'O';
    var newgame = function() {
        turn = x;
        sqrData = '';
        xMoves = [false,false,false,false,false,false,false,false,false,false,false,false];
        oMoves = [false,false,false,false,false,false,false,false,false,false,false,false];
        squareFree = [false,true,true,true,true,true,true,true,true,true];
        moveCount = 0;
        compPlayer = false;
        playboard = [false,[false,true,true,true],[false,true,true,true],[false,true,true,true]]
        $('div').html('');
        $('#reset').html('Reset Game');

     };
    newgame();

    $('#fir').click(function() {
       turnchange(1,1,1,$(this));
    });
    $('#sec').click(function() {
        turnchange(2,1,2,$(this));
    });
    $('#thir').click(function() {
       turnchange(3,1,3,$(this));
    });
    $('#four').click(function() {
        turnchange(4,2,1,$(this));
    });
    $('#fiv').click(function() {
       turnchange(5,2,2,$(this));
    });
    $('#six').click(function() {
        turnchange(6,2,3,$(this));
    });
    $('#sev').click(function() {
        turnchange(7,3,1,$(this));
    });
    $('#eight').click(function() {
      turnchange(8,3,2,$(this));
    });
    $('#nine').click(function() {
       turnchange(9,3,3,$(this));
    });
    var turnchange = function(playerSquare,playRow,playCol,sqrData) {
        playboard[playRow][playCol] = turn;
        console.log(playboard);
        if (squareFree[playerSquare] == true) {
            $(sqrData).html(turn);
            if (turn == x) {
                xMoves[playerSquare] = true;
                turn = o;
            }
            else if (turn == o) {
                oMoves[playerSquare] = true;
                turn = x;
            }

            squareFree[playerSquare] = false;
            moveCount++;
            checkwin($(this));
        }
    };

    var checkwin = function() {
          if ((xMoves[1] && xMoves[2] && xMoves[3]) || (xMoves[1] && xMoves[4] && xMoves[7]) ||
            (xMoves[1] && xMoves[5] && xMoves[9]) || (xMoves[2] && xMoves[5] && xMoves[8]) ||
            (xMoves[3] && xMoves[6] && xMoves[9]) || (xMoves[4] && xMoves[5] && xMoves[6]) || (xMoves[7] && xMoves[8] && xMoves[9]) ||
            (xMoves[3] && xMoves[5] && xMoves[7])) {
            $('#game').html('Game Over - X Wins');
            deactivateSquares();
        }
        else if ((oMoves[1] && oMoves[2] && oMoves[3]) || (oMoves[1] && oMoves[4] && oMoves[7]) ||
            (oMoves[1] && oMoves[5] && oMoves[9]) || (oMoves[2] && oMoves[5] && oMoves[8]) ||
            (oMoves[3] && oMoves[6] && oMoves[9]) || (oMoves[4] && oMoves[5] && oMoves[6]) || (oMoves[7] && oMoves[8] && oMoves[9]) ||
            (oMoves[3] && oMoves[5] && oMoves[7])) {
            $('#game').html('Game Over - O Wins');
            deactivateSquares();
        }
        else if (moveCount == 9) {
            $('#game').html('Its a Draw');
        }

    };
    var deactivateSquares = function() {
        for (var e in squareFree) {
            squareFree[e]= false;
        }

    };


    $('#reset').click(function(){
        newgame();
        });

});

Answer 1

首先你需要一个score :: Configuration -> N函数。配置是电路板的当前状态。

我们可以画出所有可能配置的树。叶子包含棋盘的分数。 MAX是你，MIN是你的对手：

Configuration      Player
        A           MAX
    /       \
   B         C      MIN
 /   \     /   \
D,1  E,3  F,2  G,1  MAX

minmax是遍历这棵树的递归算法。它计算给定配置和播放器的最佳选择（基于您的 score 函数）。请注意，MAX 的目标是最大化 score，而 MIN 的目标是最小化它。

minMax(c, player)
  if c is leaf:
    return score(c)

  if player == MAX:
    bestScore = -inf
    moves = generateAllMoves(c)
    for each move m in moves:
      c = makeMove(c, m)
      currScore = minMax(c, MIN)
      if currScore > bestScore
        bestScore = currScore
      c = undoMove(c, m)
    return bestScore

  if player == MIN:
    bestScore = +inf
    moves = generateAllMoves(c)
    for each move m in moves:
      c = makeMove(c, m)
      bestScore = minMax(c, MAX)
      if currScore < bestScore
        score = currScore
      c = undoMove(c, m)
    return bestScore

getBestMove(c):
  bestScore = -inf
  bestMove = null
  for each move m in c:
    c = makeMove(c, m)
    currScore = minMax(c, MIN)
    if currScore > bestScore
      bestScore = currScore
      bestMove = m
    c = undoMove(c, m)
  return bestMove

minMax(c, MAX) returns MIN 玩家可以迫使你达到的最高分数，即它保证无论你的对手使用什么策略，你总能至少达到 minMax(c, MAX)得分。

How do I make it play a different combination every time?

您的评分函数可以是随机的。例如：score(c) = deterministic_score(c) + rand() * 0.0001.

How do I make sure I get every combo?

您必须正确实施移动生成算法。

After it finds a winning state how do I return the correct move from that?

如果您的 score 函数 returns +inf 用于获胜状态，并且您总是选择 getBestMove 返回的移动，那么您将始终处于获胜状态（假设你的对手没有针对它的反击策略并且搜索的深度是无限的）。

Am I supposed to store each state in an array?

您可以生成所有的动作并即时修改棋盘。

实现极小极大

Implementing the minimax

javascript

algorithm

tic-tac-toe

minimax