java - MiniMax 实现

Question

我正在尝试用 Java 编写一个小型 AI 算法来实现 miniMax 算法。

此游戏所基于的游戏是双人游戏，两名玩家每回合各走一步，每个棋盘位置都会导致每位玩家得分。玩家 X 位置的“质量”是通过从玩家 X 在该位置的得分中减去对手的得分来评估的。每一步都由一个整数表示(即输入 1 移动一，输入 2 移动二等)

我知道 miniMax 应该使用递归来实现。目前我有:

evaluate() 方法，它以表示棋盘状态的对象(即“BoardState”对象和一个名为“max”的 boolean 值(签名为evaluate(BoardState myBoard， boolean 最大值))。

轮到玩家 X 时，max 为真。给定棋盘位置，它将评估所有可能的移动并返回对玩家 X 最有利的移动。如果轮到对手，max 将为假并且该方法将返回对玩家 X 最不利的移动(即:对玩家 y 最有利)

但是，我在编写实际的 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. 您对评估的定义似乎与大多数人不同。通常评估函数会返回游戏状态的预测值。你对求值函数的定义和极小极大函数的定义不一样吗？
3. miniMax 和 MiniMax 有什么不同吗？因为如果你的意思是递归那么你需要在调用下一个 miniMax 时传递 depth-1

minimax 的思想是深度优先搜索。并且仅评估叶节点(具有最大深度的节点或获胜或平局的节点)，如果当前玩家是最大化者，则选择最大值，如果当前玩家是最小化，则选择最小值一。

我是这样实现的:

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

注意:

• return v，best_move_index表示返回v和best_move_index的两个值(以上代码在lua中，lua可以返回多个值)

• evaluate 函数为两个玩家返回相同的分数(即游戏状态 A 在观点 P1 中得分为 23，在观点 P2 中也得分为 23)

• 此算法仅在两个玩家交替运行时才有效(没有玩家可以连续运行两个 Action )，您可以通过给对手一个 Action 来绕过此限制，即移动 PASS(跳过他/她的回合)如果其他玩家需要移动两次。

• 这个 minimax 可以进一步优化(从最简单的开始排序):

  1. alpha-beta修剪
  2. 迭代深化
  3. 移动订单