我试图写一个小的人工智能算法Java实现MiniMax算法。
这是基于一个双人游戏，两个玩家每回合移动一步，每个棋盘位置导致每个玩家都有一个分数。玩家X的位置的“质量”是通过从玩家X的位置得分中减去对手的得分来评估的。每个移动都由一个整数表示（即。移动1是通过输入1，移动2是通过输入2等）
我知道miniMax应该使用递归实现。目前我有：
方法，它将一个表示板状态的对象（即BoardState对象和一个名为max的布尔值（签名将被评估（BoardState myBoard，布尔值max））作为参数。
当轮到玩家X时，max为真。给定一个棋盘位置，它将评估所有可能的移动，并返回对玩家X最有利的移动。如果轮到对手，max将为false，该方法将返回对玩家X最不利的移动（即：对玩家y最有利）
但是，我在编写实际的MiniMax方法时遇到了困难。我的总体结构大概是这样的：
public int miniMax(GameState myGameState, int depth)
因此，我提交了初始游戏状态和我希望它调查的“深度”。
然后我会有这样的东西：
int finalMove = 0;
while(currentDepth < depth) {
GameState tmp = myGameState.copy();
int finalMove = evaluate(tmp, true or false);
iniMax(tmp.makeMove(finalMove));
}
return finalMove;
这听起来像是一个可信的实现吗？有什么建议吗？：）
谢谢
那是行不通的。
细节：
极大极小的思想是深度优先搜索。并且仅计算叶节点（具有最大深度的节点或是胜利或平局的节点），如果当前玩家是最大的，则选择最大的节点，如果当前玩家是最小的，则选择最小的节点。
我就是这样实现的：
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
注：
>
evaluate函数为两个玩家返回相同的分数（即从P1的角度来看，游戏状态A的分数为23，从P2的角度来看，游戏状态A的分数也为23）
此算法仅在两名玩家交替跑动时有效（没有玩家可以连续跑动两次），如果另一名玩家需要移动两次，您可以通过给对手一个移动来欺骗此限制，即移动传球（跳过回合）。
这个极小值可以进一步优化（从最简单的一个排序）：
我在lua中实现了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
