java有没有一种方法可以加速国际象棋中的“检测检查”方法？

Question

我正在开发一个JavaFX国际象棋应用程序，我正在尝试实现一种方法来检测黑白国王是否受到控制。它可以工作，但即使每次用户移动一个部件时我只调用它，它仍然大大滞后于应用程序。它的工作原理是检测所有可能的对色移动，然后检查这些移动是否处于国王的位置。有什么办法能使方法更有效吗

private boolean getCheck(String colour) {
    ArrayList<int[]> totalMoves = new ArrayList<int[]>();
    ArrayList<int[]> pieceMoves = new ArrayList<int[]>();

    int kingRow = 0;
    int kingColumn = 0;

    if (colour.equals("BLACK")) {
        for (int i = 0; i < chessPieces.size(); i++) {
            if (chessPieces.get(i).getPiece().equals("BLACKKING")) {
                kingRow = chessPieces.get(i).getRow();
                kingColumn = chessPieces.get(i).getColumn();
            }
        }

        for (int i = 0; i < chessPieces.size(); i++) {
            if (chessPieces.get(i).getPiece().contains("WHITE")) {
                pieceMoves = showPossibleMoves(new int[]{
                        chessPieces.get(i).getColumn(),
                        chessPieces.get(i).getRow()
                    }, chessPieces);

                for (int j = 0; j < pieceMoves.size(); j++) {
                    if (pieceMoves.get(j)[1] == kingRow && pieceMoves.get(j)[0] == kingColumn) {
                        return true;
                    }
                }
            }
        }
    } else if (colour.equals("WHITE")) {
        for (int i = 0; i < chessPieces.size(); i++) {
            if (chessPieces.get(i).getPiece().equals("WHITEKING")) {
                kingRow = chessPieces.get(i).getRow();
                kingColumn = chessPieces.get(i).getColumn();
            }
        }

        for (int i = 0; i < chessPieces.size(); i++) {
            if (chessPieces.get(i).getPiece().contains("BLACK")) {
                pieceMoves = showPossibleMoves(new int[]{
                        chessPieces.get(i).getColumn(),
                        chessPieces.get(i).getRow()
                    }, chessPieces);

                for (int j = 0; j < pieceMoves.size(); j++) {
                    if (pieceMoves.get(j)[1] == kingRow && pieceMoves.get(j)[0] == kingColumn) {
                        return true;
                    }
                }
            }
        }
    }

    return false;
}

Answer 1

我在这里看到了几个潜在的瓶颈

每个for循环都会经过每次迭代。在你找到国王后，也在你找到攻击它的棋子后，你就可以破发了

还有，你是如何计算移动的？这也可能会影响性能。如果你每回合计算一次可能的移动+工件位置列表，并在某个地方保留一个参考，你可以避免大量昂贵的重新计算

还有其他潜在的运行瓶颈，但如果不了解有关移动计算算法的更多细节，甚至是设计国际象棋程序的方式，就不可能知道

为了进一步的参考，the Chess Programming wiki有很多关于国际象棋编程的精彩文章。你可能会发现checks上的页面也很有用，因为有多种检查检测方法。我个人更喜欢（也曾使用过）用attack and defend maps即时计算支票，因为它的直观性，我相信Chess.js也会做类似的事情

Answer 2

你可以从每个国王的位置开始，扫描骑士的动作，垂直、水平和对角线，寻找合适的对手棋子，以检查国王。这将导致比所有可能的移动更小的扫描

Answer 3

这并不是你问题的答案，但在这里加一个休息会防止你在这个阶段检查不必要的部分。我猜最耗时的部分是在每件作品上打电话展示可能的动作

          for (int i = 0; i < chessPieces.size(); i++) {
                if (chessPieces.get(i).getPiece().equals("BLACKKING")) {
                    kingRow = chessPieces.get(i).getRow();
                    kingColumn = chessPieces.get(i).getColumn();
                    break;
                }
           }

Answer 4

我很确定已经有了一个（最佳）算法。尽管我会建议，如果有必要的话，我会如何处理这个问题。如果你想尽快检测支票，我认为明智的做法是预先计算并将工作划分为电路板的单元。你可能想知道“我怎样才能做到？”，那么，每当一件物品移动时，它都会标记出一块区域，构成威胁吗

假设这是我们的细胞类：

public class Cell{
    private ArrayList<Piece> whiteThreats = new ArrayList<>(); 
    private ArrayList<Piece> blackThreats = new ArrayList<>();
    ...
}

上面的类将有2个ArrayList用来存放威胁细胞的碎片。多个碎片可以威胁一个细胞，也可以威胁两侧（白色和黑色）。现在，每次工件移动时，应执行两个动作：

1. 找到受到当前片段威胁的细胞，并从其列表中删除引用

2. 找到并标记新的单元格，这些单元格现在会显示威胁，并在列表中添加一个引用

通过这样做，每一块都应该立即知道电池是否安全，这可以通过检查ArrayList（适用于适当颜色）是否为空来轻松验证。如果对手队的ArrayList内至少有一个物体（这意味着大小大于零），则表示对手队威胁该单元。因此，国王现在可以检测签入时间