java - 在基于时间的解决方案中，消除国际象棋中无趣/丢失线的最佳方法？

Question

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

在使用 alpha-beta 剪枝 实现 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，因为深度优先搜索时间甚至在计算另一条线之前就用完了。

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

以下是我教过的一些解决方案。

1. 实现一个isInteresting() 函数。它采用所有先前的分数并检查当前行是否有趣/获胜，如果是，然后才计算下一个子节点。

例如

• [0,0,0,0,0,0] 可以解释为一条画线。
• [-2,-3,-5,-2,-1] 可以解释为丢失线。

---

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.
    }

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

有更好的方法吗？

Answer 1

每个国际象棋引擎使用的这个问题的解决方案是iterative deepening .

您不是搜索到固定深度(在您的示例中为 MAX_DEPTH)，而是从搜索深度一开始，然后当搜索完成后，您再次从深度二开始，并继续像这样增加深度，直到您没时间了。当您超时时，您可以下最后一次完成搜索的着法。

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

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

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