实现极小极化

Question

有人可以帮助我吗？我正在尝试为我的Tic-Tac-Toe游戏编写一个AI，所有相关的搜索都将我带入了最小最大化算法。从我阅读和观看的所有内容中，我对该算法背后的理论有了基本的了解。我遇到麻烦的是它在我的游戏中的实际应用。我知道这个算法本质上应该是完成每一步，并根据棋盘的状态返回得分。我如何让它每次都有不同的组合？我如何确保每一个组合都能得到？在找到胜利的状态之后，我该如何回复正确的举动？我应该将每个状态存储在一个数组中吗？对不起，我只是想巩固我的理解力，并确保我能够实践我正在阅读的东西。我正在为游戏提供我的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函数）。请注意0​​的目标是最大限度地提高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)返回的最大比分的MIN玩家可以强迫你来实现的，即它保证无论你的对手发挥着什么样的策略可以随时实现至少minMax(c, MAX)得分。

1. 我该如何让它每次播放不同的组合？

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

1. 我该如何确定每一个组合？

你必须正确地实现移动生成算法。

1. 找到胜利后，我该如何返回正确的移动？

如果您score功能获胜状态恢复+inf，你总是选择由getBestMove返回的举动，那么你将永远在获胜状态结束了（前提是您的opponend不具有反战略它和搜索的深度是无限的）。

1. 我应该将每个状态存储在数组中吗？

您可以生成所有动作并随时修改电路板。