java如何从MiniMax AlphaBeta的返回值在游戏板上移动?
我所说的游戏类似于Gomoku或“大型”简化版的Tic-Tac-Toe。基本上,您有一个8x8板,赢家是在一行或一列中链4(无对角线)的板
我已经用alpha-beta修剪设置了一个minimax,问题是我不确定返回值如何让您知道要执行哪一步。或者喜欢如何将值连接到移动
目前,我考虑返回GameStateNode。GameStateNode具有以下字段:char[][](电路板的当前状态)、evaluationVal(非终端节点时的当前状态值)
但是我仍然想不出一种方法来使用返回的节点来决定最佳移动
// Alpha-Beta Pruning Search
private static Node alphaBeta(Node initial, int depth) {
Node bestMove = max(initial, depth, NEGATIVE_INFINITY, POSITIVE_INFINITY);
return bestMove;
}
private static Node max(Node n, int depth, int alpha, int beta) {
int value = NEGATIVE_INFINITY;
Node currentBestMove = null;
Node temp = null;
// Terminal state
if(n.fourInALine() != 0) {
return n;
}
// Depth limit reached
if(depth == 0) {
return n;
}
ArrayList<Node> successors = n.generateSuccessors('X');
// Iterate through all the successors, starting with best evaluationValues
for(Node s : successors) {
temp = min(s, depth - 1, alpha, beta);
if(temp.evaluationVal > value) {
value = temp.evaluationVal;
currentBestMove = temp;
}
alpha = Math.max(alpha, value);
if(alpha >= beta) {
break;
}
}
return currentBestMove;
}
// I have similar min method just with the correct comparison
# 1 楼答案
您无法从返回的
bestMove
中获取移动信息,因为该节点表示depth
移动后板的位置。如果你区分bestMove
的位置和initial
的位置,你会发现多个不同,你将无法分辨出这些动作是按什么顺序进行的要使用搜索代码,请执行以下操作:
max()
添加一个boolean isRoot
参数,告诉该方法是否直接从alphaBeta()
调用,n
是搜索树的根节点李>max()
中,如果isRoot
为真,则不跟踪temp
(从min()
返回的节点)的currentBestMove
,而是跟踪最好的s
(从n.generateSuccessors()
返回的节点)李>alphaBeta()
中,获取bestMove
(从max()
返回的节点)并将其状态数组与initial
区分开来。找到bestMove
有'X'
和initial
没有的插槽的坐标代码:
请注意,这些都没有经过测试