5

I'm developing a JavaFX chess application and I'm trying to implement a method that detects whether or not the black and white kings are in check or not. It works, but even when I only call it every time the user moves a piece, it still lags the application immensely. It works by detecting all the possible moves of the opposing colour, then checks if any of those moves are in the position of the king. Is there any way to make a more efficient method?

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;
}
1
  • Please let me know if any more information is needed, such as the showPossibleMoves() method. Dec 25, 2018 at 18:34

4 Answers 4

5

You could start with the position of each king, scan for knight moves, vertically, horizontally, and diagonally for the appropriate opponent pieces that are putting the king in check.This should result in a smaller scan than all possible moves.

1
  • 1
    Brilliant! I just implemented it, and it works wonderfully. Thanks! :D Dec 25, 2018 at 21:08
3

Couple of potential bottlenecks I'm seeing here.

Every for loop goes through every iteration. Break after you find the king and also after you find the piece attacking it.

Also, how are you calculating moves? That could affect the performance as well. If you calculate the list of possibles moves + piece locations once per turn and simply keep a reference to that somewhere, you could avoid a lot of expensive recalculation.

There's other potential runtime bottlenecks, but it's not possible to know without seeing more details about your move calculation algorithm or even the way you've designed the chess program.

For further reference, the Chess Programming wiki has a lot of wonderful articles about, well, chess programming. You might find the page on checks useful as well, as there's multiple ways of check detection. I personally prefer (and have used) calculating checks on the fly with attack and defend maps because of its intuitiveness, and I believe Chess.js does something similar.

1

I am pretty sure there is already an (optimal) algorithm for this. Although I am going to suggest the way I would approach this problem if I had to. If you want to detect check as fast as possible, I believe the smart move would be to pre-calculate and divide the work into the cells of the board. You might be wondering "how can I achieve that?", what about everytime a piece is moving it marks the territory the piece threat?.

Let's assume this is our Cell class :

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

The class above will have 2 ArrayList which will hold the pieces which threat the cell. Multiple pieces can threat one cell and for both sides (white and black). Now every time a piece moves should perform two actions:

  1. Find the cells which were threatened by the current Piece and remove the reference from their lists.

  2. Find and mark the new cells which now the piece threat and add a reference to their lists.

By doing so, each piece should immediately know if the cell is safe for it or no, which can easily be verified by checking if the ArrayList (for the appropriate color) is empty or not. If the ArrayList of the opponent team has at least one object inside ( which means the size is greater than zero) that mean the opponent team threatens this cell. So the King can now detect check in O(1) time.

0

Not the answer to your problems but adding a break here will prevent you from checking unnecessary pieces at this stage. I'm guessing the most time consuming part is calling to showPossibleMoves on every piece.

          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;
                }
           }
1
  • Yeah, that's the main problem, because it's also how I get the possible moves for each of the individual game pieces. It works quickly for one piece, but not for 16 iterations through. Although I didn't realize that's what break did in Java. That's very helpful, thanks. Dec 25, 2018 at 19:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.