1

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

在实施minimaxwith之后alpha-beta pruning，我想到实施一个时间限制来查找给定动作的分数。

这是代码

    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);

现在，问题来了 Nf3.jpg

你看，它只计算了 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.
    }

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

有一个更好的方法吗？

4

1 回答 1

3

每个国际象棋引擎使用的解决这个问题的方法是迭代深化。

不是搜索到固定深度（在您的示例中为 MAX_DEPTH），而是首先搜索深度为 1，然后当此搜索完成后，您再次以深度 2 开始，并继续像这样增加深度，直到您离开时间。当您没有时间时，您可以玩最后一次搜索完成的移动。

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

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

在实践中，在使用转置表和基于先前迭代的根部排序的引擎中，使用迭代深化比不使用它更快。例如，进行深度 1 搜索，然后进行深度 2 搜索，然后进行深度 3 搜索，直到深度 10 搜索比立即进行深度 10 搜索要快。此外，您还可以随时选择停止搜索并且仍然可以玩，=。

于 2019-12-08T13:15:33.240 回答