在基于时间的解决方案中删除国际象棋中 uninteresting/losing 行的最佳方法？

Question

我正在 Java 中创建一个国际象棋引擎作为练习，我知道由于速度问题不推荐这样做，但我这样做只是为了练习。

在用 alpha-beta pruning 实现 minimax 之后，我想到了实现一个时间限制来查找给定移动的分数。

这是代码

    private int minimax(MoveNode node, MoveNodeType nodeType, int alpha, int beta, Side side, int depth) throws Exception {

//        isInterestingLine(prevscores, node, side);


        if (depth <= 0) {
            count++;
            return node.evaluateBoard(side);
        }
//         Generate Child nodes if we haven't.
        if (node.childNodes == null || node.childNodes.size() == 0) {
            node.createSingleChild();
        }

        if (nodeType == MoveNodeType.MAX) {
            int bestValue = -1000;
            for (int i = 0; i < node.childNodes.size(); i++) {
                if (node.childNodes.get(i) == null) continue;
                int value = minimax(node.childNodes.get(i), MoveNodeType.MIN, alpha, beta, side, depth - 1);
                bestValue = Math.max(bestValue, value);
                alpha = Math.max(alpha, bestValue);
                if (beta <= alpha) {
                    break;
                }
                node.createSingleChild();
            }
//            reCalculateScore();
            return bestValue;
        } else {
            int bestValue = 1000;
            for (int i = 0; i < node.childNodes.size(); i++) {
                if (node.childNodes.get(i) == null) continue;


                int value = minimax(node.childNodes.get(i), MoveNodeType.MAX, alpha, beta, side, depth - 1);
                bestValue = Math.min(bestValue, value);
                beta = Math.min(beta, bestValue);
                if (beta <= alpha) {
                    break;
                }
                node.createSingleChild();
            }
//            reCalculateScore();
            return bestValue;
        }
    }

和驱动代码。

void evaluateMove(Move mv, Board brd) throws Exception {
    System.out.println("Started Comparing! " + this.tree.getRootNode().getMove().toString());
    minmaxThread = new Thread(new Runnable() {
        @Override
        public void run() {
            try {
                bestMoveScore = minimax(tree.getRootNode(), MoveNodeType.MIN, -1000, 1000, side, MAX_DEPTH);
            } catch (Exception e) {
                e.printStackTrace();
            }
        }
    });
    minmaxThread.start();
}

我就是这样实现时间限制的。

long time = System.currentTimeMillis();
moveEvaluator.evaluateMove(move, board.clone()); 
while((System.currentTimeMillis() - time) < secToCalculate*1000 && !moveEvaluator.minmaxThread.isAlive()) {
}
System.out.println("Time completed! score = " + moveEvaluator.bestMoveScore + " move  = " + move + " depth = " + moveEvaluator.searchDepth) ;
callback.callback(move, moveEvaluator.bestMoveScore);

现在，问题

你看，它只计算了Bb7，因为深度优先搜索时间在计算另一条线之前就已经用完了。

所以我想要一种计算方法，就像在基于时间限制的解决方案中一样。

以下是我教过的几个解决方法。

正在实施 isInteresting() 功能。它获取所有先前的分数并检查当前行是否为 interesting/winning 如果是则然后才计算下一个子节点。

例如

[0,0,0,0,0,0] 可以解释为画线。
[-2,-3,-5,-2,-1]可以理解为输线

首先搜索小深度，然后消除所有丢失的线。

    for (int i = min_depth; i <= max_depth; i ++) {
        scores = [];
        for(Node childnode : NodesToCalculate) {
            scores.push(minimax(childnode, type, alpha, beta, side, i));
        }
        // decide which child node to calculate for next iterations.
    }

但是，none 的解决方案是完美和高效的，在第一个中，我们只是在猜测，在第二个中，我们不止一次地计算一个节点。

有更好的方法吗？

Answer 1

每个国际象棋引擎使用的解决此问题的方法是iterative deepening。

不是搜索到固定深度（在您的示例中为 MAX_DEPTH），而是先搜索到深度 1，然后在搜索完成后，您再次从深度 2 开始，然后继续像这样增加深度，直到你没时间了。超时的时候可以下最后一次搜索完成的棋子。

看起来很多时间将花费在较低深度的迭代上，这些迭代后来被更深的搜索所取代，并且这样做的时间完全浪费了，但实际上并非如此。由于搜索深度 N 比搜索深度 N-1 长得多，因此在较低深度搜索上花费的时间总是比在最后（更深）搜索上花费的时间少得多。

如果您的引擎使用转置 table，则前一次迭代的转置 table 中的数据将有助于以后的迭代。 alpha-beta 算法的性能对搜索的移动顺序非常敏感。当首先搜索最佳移动时，alpha-beta 相对于 minimax 节省的时间是最优的。如果您在搜索深度 N 之前搜索了深度 N-1，则换位 table 可能包含对大多数位置的最佳移动的良好猜测，然后可以首先搜索。

实际上，在使用转置 table 并根据先前迭代在根部排序移动的引擎中，使用迭代加深比不使用它更快。我的意思是，例如，进行深度 1 搜索，然后进行深度 2 搜索，然后进行深度 3 搜索，直到进行深度 10 搜索比立即进行深度 10 搜索要快。另外，您可以选择随时停止搜索，并且仍然可以下棋，=.

在基于时间的解决方案中删除国际象棋中 uninteresting/losing 行的最佳方法？

Best way to remove uninteresting/losing lines in chess, in time-based solution?

java

chess

minimax