非递归修剪算法

Question

我将在硬件(fpga)上执行游戏应用程序，但由于可识别的硬件难度，我无法实现函数递归。我刚刚搜索了极大极小树的非递归修剪算法。不幸的是没有找到合适的。任何使用堆栈或其他数据结构解决递归问题的算法或实现都将受到赞赏。

Answer 1

看着我的alpha-beta maximin代码，我有一个建议:

在我的算法中只有一个递归方法，它是这样的:

/** 
  * Returns maximin value of node with alpha-beta pruning for a certain level of forecasting.
     */
double getMaxAlphaBeta(Node currentState, Player player, int level, double alpha, double beta) {
// [ . . . ]
if(player == MAX){
for(State s : currentState.nextStates){
   utility = getMaxAlphaBeta( s, MIN, level - 1, alpha, beta);
   if (utility > alpha)
      alpha = utility;
   if (alpha >= beta)
      break;
}
}
else{ // [. . .] MIN is playing, do the same things with oppisite sign }
return newBeta;
}

这个方法被另一个方法调用，像这样:

public Action getMinimaxStrategy(Node currentState, Player player, int level) {
    double max = this.getMaxAlphaBeta(currentState, player, level, -inf, +inf);
// [ . . . ]

我要做的是像这样改变第二个方法:

public Action getMinimaxStrategy(Node currentState, Player player, int level) {
    DATA max = new DATA(currentState);
    for(!max.isOptimal){
    Array<Node> nextNodes = max.currentState.getNextNodes();
    for(Node max.s : nextNodes){
        max = this.getMaxAlphaBeta(currentState, player, level, currentAlpha, currentBeta);
        // [ . . .]
    }
    }
    // [ . . . ]

其中DATA是一个数据结构，包含所有你将作为递归参数传递的内容(当前状态，玩家，关卡，alpha, beta)以及最优性(这是你将从递归返回的条件)。
然后，您可以使用相同的逻辑来修改第一个方法。这个解决方案可以优化，我没有尝试过。

如果你喜欢试试，告诉我好不好。