MiniMax的實現

Question

我想在Java中寫一個小AI算法來實現miniMax算法。

這個遊戲基於雙人遊戲，其中每個玩家每回合移動一個棋子，每個棋盤位置導致每個玩家都有一個得分。玩家X的位置的「品質」通過從玩家X的該位置的得分中減去對手的得分來評估。每一步都用一個整數表示（即，通過輸入1來移動一個，通過輸入2等來移動兩個）

我知道miniMax應該使用遞歸來實現。目前我有：

一個evaluate()方法，它需要參數代表板狀態的對象（即「BoardState」對象和布爾值稱爲「最大」（簽名將是評估（BoardState myBoard，布爾值max ））

當玩家X回合時，最大值爲true。給定一個棋盤位置，它將評估所有可能的移動並返回對玩家X最有利的移動。如果是對手的回合，max將爲假，並且該方法將返回對於玩家X最有利的移動（即：對玩家y最有利）

然而，我是havi編寫實際的miniMax方法存在困難。我的一般結構是這樣的：

public int miniMax(GameState myGameState, int depth) 

由此我提交了最初的gameState和我希望它查看的「深度」。

然後，我會是具有類似：

int finalMove = 0; 
while(currentDepth < depth) { 
    GameState tmp = myGameState.copy(); 
    int finalMove = evaluate(tmp, true or false); 
    iniMax(tmp.makeMove(finalMove)); 

} 
return finalMove; 

請問這聽起來像一個似是而非的實施？有什麼建議麼？ :)

謝謝！

Answer 1

不會工作。

細節：

1. 會引起無限循環。 currentdepth永遠不會遞增
2. 您對評估的定義似乎與大多數不同。通常評估函數將返回遊戲狀態的預測值。您的評估函數的定義是否與minimax函數的作用相同？
3. 是miniMax和MiniMax的不同嗎？因爲如果你的意思是遞歸，那麼你需要在調用下一個miniMax時通過depth-1

minimax的想法是深度優先搜索。和只有評估葉節點（具有最大深度的節點或節點是勝利或領帶）並選擇一個如果當前玩家是最大化玩家爲max，並且如果當前玩家是最小化玩家選擇最小值。

這是我是如何實現它：

function miniMax(node, depth) 
    if(depth == 0) then --leaf node  
     local ret = evaluate(node.state) 
     return ret 
    else -- winning node 
     local winner = whoWin(node.state)  
     if(winner == 1) then -- P1  
      return math.huge 
     elseif(winner == -1) then -- P2   
      return math.huge*-1 
     end 
    end 

    local num_of_moves = getNumberOfMoves(node.state) 
    local v_t = nil 
    local best_move_index = nil 
    if(getTurn(node.state) == 1) then -- maximizing player  
    local v = -math.huge 
     for i=0, num_of_moves-1 do      
      local child_node = simulate(node.state, i)) -- simulate move number i 
      v_t = miniMax(child_node, depth-1) 
      if(v_t > v) then 
       v = v_t 
       best_move_index = i    
      end 
     end    
     if(best_move_index == nil) then best_move_index = random(0, num_of_moves-1) end 
     return v, best_move_index 
    else -- minimizing player 
    local v = math.huge 
     for i=0, num_of_moves-1 do   
      local child_node = simulate(node.state, i) 
      v_t = miniMax(child_node, depth-1) 
      if(v_t < v) then     
       v = v_t    
       best_move_index = i    
      end 
     end 
     if(best_move_index == nil) then best_move_index = random(0, num_of_moves-1) end 
     return v, best_move_index        
    end 
end 

注：

• 返回V，best_move_index意味着返回v和best_move_index（上面的代碼是在LUA和LUA能的兩個值返回多個值）

• 評估函數返回兩個玩家相同的分數（即遊戲狀態A in觀點P1得分23，並且在觀點P2也得分23）

• 這個算法只在兩個玩家交替運行（沒有玩家可以連續運行兩個動作）時才能工作，你可以欺騙這個限制通過給予對手一個動作，即如果另一個玩家需要移動兩次，則移動PASS（跳過他/她的回合）。

• 這極大極小可以進一步優化（從最簡單的一個排序）：

  1. α-β修剪
  2. 迭代深化
  3. 移動訂購

Answer 2

我發在盧阿執行minimax。我希望它能幫助您瞭解如何從Java視角處理算法，代碼應該與您非常相似。它是專爲一場井字遊戲而設計的。

--caller is the player who is using the minimax function 
--initial state is the board from which the player must make a move 
local function minimax(caller,inital_state) 
    local bestState = {}; --we use this to store the game state the the player will create 
     --this recurse function is really the 'minimax' algorithim 
    local function recurse(state,depth) 
     --childPlayer is the person who will have their turn in the current state's children 
     local ChildPlayer = getTurn(state) 
     --parentPlayer is the person who is looking at their children 
     local ParentPlayer = getPreviousTurn(state) 
     --this represents the worst case scenario for a player 
     local alpha = - (ChildPlayer == caller and 1 or -1); 
     --we check for terminal conditions (leaf nodes) and return the appropriate objective value 
     if win(state) then 
      --return +,- inf depending on who called the 'minimax' 
      return ParentPlayer == caller and 1 or -1; 
     elseif tie(state) then 
      --if it's a tie then the value is 0 (neither win or loss) 
      return 0; 
     else 
      --this will return a list of child states FROM the current state 
      children = getChildrenStates(state,ChildPlayer) 
      --enumerate over each child 
      for _,child in ipairs(children) do 
       --find out the child's objective value 
       beta = recurse(child,depth+1); 
       if ChildPlayer == caller then 
        --We want to maximize 
        if beta >= alpha then 
         alpha = beta 
         --if the depth is 0 then we can add the child state as the bestState (this will because the caller of minimax will always want to choose the GREATEST value on the root node) 
         if depth == 0 then 
          bestState = child; 
         end 
        end 
       --we want to MINIMIZE 
       elseif beta <= alpha then 
        alpha = beta; 
       end 
      end 
     end 
     --return a non-terminal nodes value (propagates values up the tree) 
     return alpha;   
    end 
    --start the 'minimax' function by calling recurse on the initial state 
    recurse(inital_state,0); 
    --return the best move 
    return bestState; 
end