實現極小極化

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. 我應該將每個狀態存儲在數組中嗎？

您可以生成所有動作並隨時修改電路板。