2

我将在硬件（fpga）上实现一个游戏应用程序，由于可识别的硬件困难，我无法实现函数递归。我刚刚在 minimax 树上搜索了非递归 alpha-beta 修剪算法。不幸的是，没有找到合适的。任何使用堆栈或其他数据结构解决递归问题的算法或实现都将受到赞赏。

4

1 回答 1

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）以及最优性（这是您将从递归返回的条件）。
然后你可以使用相同的逻辑来修改第一种方法。这个方案可以优化，我没试过。

喜欢就试试看，好不好告诉我。

于 2014-08-03T15:10:29.543 回答