1

我正在编写一个程序来玩跳棋，每一步都是定时的。我正在使用 alpha-beta 修剪来找到最佳移动。我只能深入决策树，因为：

  1. 决策树对于跳棋者来说是巨大的
  2. 有时间限制我必须决定搬家

有没有办法在我用完时间时立即从调用堆栈中逃脱，即使堆栈上有很多帧？我想过抛出一个异常，但这似乎是一个糟糕的决定。

这就是我现在正在做的，但它不够快

public Board play(Board board) {
    ArrayList<Board> actions = board.findPossibleMoves();

    if (actions.size() == 0) {
        return new Board();
    } 

    int depth = 3;
    // Each move has 1 second (1000ms)
    TimeLimit tl = new TimeLimit(1000);
    double alpha = Double.NEGATIVE_INFINITY;
    double beta = Double.POSITIVE_INFINITY;

    Board bestSoFar = actions.get(0);

    double v = Double.NEGATIVE_INFINITY;
    for (Board b : actions) {
        if (tl.isTimeUp())
          return bestSoFar;

        double result = minValue(b, depth, alpha, beta, tl);
        if (result >= v) {
            bestSoFar = b;
            v = result;
        }
        if (v >= beta) return b;
        alpha = Math.max(alpha, v);
    }
    return bestSoFar;
}

private double maxValue(Board board, int depth, double alpha, double beta, TimeLimit tl) {
    if (tl.isTimeUp())
        return score(board);
    ...
}

private double minValue(Board board, int depth, double alpha, double beta, TimeLimit tl) {
    if (tl.isTimeUp())
        return score(board);
    ...
}
4

1 回答 1

2

鉴于要在严格定时的环境中使用递归，可以考虑几个选项。下面列出了这些：

选项1：

    在整个方法体中添加更多 if 语句，尤其是在可能阻塞的代码段之前，以确保代码执行在时间到期后立即停止。必须实现一个特定的缓冲间隔，以便为返回语句向上传播堆栈留出时间。

优点：

  • 实施简单。
  • 比较简单有效。

缺点：

  • 降低代码的可读性。
  • 不保证执行会在指定的时间内完成。


选项 2：

    将执行代码移植到辅助线程，该辅助线程在执行时逐步写入对象。然后主线程可以在触发该线程时启动一个计时器。当计时器到期时，主线程只需要检索这个对象并通知工作线程死亡。

优点：

  • 极其准确（由于同步导致的延迟几乎即时检索到的结果）
  • 不需要缓冲间隔 - 递归函数可以深入到它想要的深度，而不会通过尝试在计时器内适应返回传播而被束缚。
  • 允许优雅地关闭执行代码，因为它不再受时间限制（获取结果并允许线程以自己的速度终止）。

缺点：

  • 多线程 - 由于此解决方案是多线程的，它可能不适用于所有场景。
  • 需要大量额外代码，并且可能需要更改一些现有代码才能实现。
于 2013-09-15T13:58:07.773 回答