Есть ли способ ускорить метод «обнаружения чека» в шахматах?

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

Я почти уверен, что для этого уже есть (оптимальный) алгоритм.Хотя я собираюсь предложить, как бы я подошел к этой проблеме, если бы мне пришлось.Если вы хотите обнаружить чек как можно быстрее, я считаю, что разумным шагом будет предварительный расчет и разделение работы на ячейки доски.Возможно, вы задаетесь вопросом: «Как я могу этого достичь?», А как насчет того, чтобы каждый раз, когда часть перемещается, она отмечала территорию, на которой находится часть угрозы?

Давайте предположим, что это наш класс Cell:

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

В этом классе будет 2 ArrayList, в котором будут храниться части, которые угрожают ячейке.Несколько частей могут угрожать одной ячейке и для обеих сторон (белых и черных).Теперь каждый раз, когда ход фигуры должен выполнять два действия:

1. Найти ячейки, которым угрожала текущая фигура, и удалить ссылку из их списков.

2. Найдите и отметьте новые ячейки, которые теперь являются частью угрозы, и добавьте ссылку на их списки.

При этом каждая фигура должна немедленно знать, безопасна ли ячейка для нее.или нет, что можно легко проверить, проверив, пустой ArrayList (для соответствующего цвета) или нет.Если ArrayList команды противника имеет по крайней мере один объект внутри (что означает, что размер больше нуля), это означает, что команда противника угрожает этой ячейке.Таким образом, король теперь может обнаружить чек за O (1) раз.

Answer 2

Вы можете начать с позиции каждого короля, сканировать ходы рыцарей по вертикали, горизонтали и диагонали на предмет соответствующих фигур противника, которые ставят короля под контроль. Это должно привести к меньшему сканированию, чем все возможные ходы.

Answer 3

Пара потенциальных узких мест, которые я вижу здесь.

Каждый цикл for проходит каждую итерацию.Перерыв после того, как вы найдете короля, а также после того, как вы найдете фигуру, атакующую его.

Кроме того, как вы рассчитываете ходы?Это также может повлиять на производительность.Если вы вычисляете список возможных ходов + места фигуры один раз за ход и просто сохраняете ссылку на это где-то, вы можете избежать дорогостоящего пересчета.

Существуют и другие потенциальные узкие места во время выполнения, но невозможно узнать, не увидев больше деталей об алгоритме расчета вашего хода или даже о том, как вы разработали шахматную программу.

Для дальнейшей справки, вики Chess Programming wiki содержит множество замечательных статей о, ну, в общем, шахматном программировании.Также вам может пригодиться страница check , так как существует несколько способов обнаружения чеков.Лично я предпочитаю (и использовал) вычисление чеков на лету с помощью атаки и защиты карт из-за его интуитивности, и я считаю, что Chess.js делает нечто подобное.

Answer 4

Не ответ на ваши проблемы, но добавление перерыва здесь не позволит вам проверить ненужные части на этом этапе.Я предполагаю, что самая трудоемкая часть - это вызов showPossibleMoves для каждого куска.

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