Dec 25, 2006

[Guide] Attacked squares

Now that we have our pseudo-legal move generation ready, we need to be able to sort out the illegal moves. As mentioned below they are:
  • Leaving king in check.
  • Castling while king in check.
  • Castling over an attacked square.
All these require us to be able to determine if a square is attacked by the opponent.

There are different ways to do this.

One obvious way would be to make the move on the board and then generate all the moves the opponent can make and see if any of them captures the king, if any does we know the move made is illegal. We would also have to figure out ways to make sure castling was legal.

This way is sure possible, but very costly in terms of speed. We would have to generate moves for all the opponents pieces for every move we want to check.

Attack array: To make sure we do not have to generate moves for pieces that have no possible way to get to the square, I have constructed this attack-array:

public static final int ATTACK_NONE = 0;
public static final int ATTACK_KQR = 1;
public static final int ATTACK_QR = 2;
public static final int ATTACK_KQBwP = 3;
public static final int ATTACK_KQBbP = 4;
public static final int ATTACK_QB = 5;
public static final int ATTACK_N = 6;

public static final int[] ATTACK_ARRAY =
{0,0,0,0,0,0,0,0,0,5,0,0,0,0,0,0,2,0,0,0, //0-19
0,0,0,5,0,0,5,0,0,0,0,0,2,0,0,0,0,0,5,0, //20-39
0,0,0,5,0,0,0,0,2,0,0,0,0,5,0,0,0,0,0,0, //40-59
5,0,0,0,2,0,0,0,5,0,0,0,0,0,0,0,0,5,0,0, //60-79
2,0,0,5,0,0,0,0,0,0,0,0,0,0,5,6,2,6,5,0, //80-99
0,0,0,0,0,0,0,0,0,0,6,4,1,4,6,0,0,0,0,0, //100-119
0,2,2,2,2,2,2,1,0,1,2,2,2,2,2,2,0,0,0,0, //120-139
0,0,6,3,1,3,6,0,0,0,0,0,0,0,0,0,0,0,5,6, //140-159
2,6,5,0,0,0,0,0,0,0,0,0,0,5,0,0,2,0,0,5, //160-179
0,0,0,0,0,0,0,0,5,0,0,0,2,0,0,0,5,0,0,0, //180-199
0,0,0,5,0,0,0,0,2,0,0,0,0,5,0,0,0,0,5,0, //200-219
0,0,0,0,2,0,0,0,0,0,5,0,0,5,0,0,0,0,0,0, //220-239
2,0,0,0,0,0,0,5,0,0,0,0,0,0,0,0,0 }; //240-256
This might look like hard work to put together, and it was. :) If you want it go ahead and use it, and perhaps put a link to my page or so next to it.

Ok, great. So how does it work?

Firstly the constants are groupings of pieces that move the same way in a certain pattern. E.g. ATTACK_KQR is king, queen and rook, since they can all move one square up, down, left and right. ATTACK_QB is queen and bishop since they both can move diagonally more than one square. ATTACK_KQBwP is king, queen, bishop, and white pawn, since they can move one square up diagonally. And so on.

The attack-array is filled with these constants, and we can easily look up what a square can be attacked by from another square, using this formula:
attacked_square_index - attacking_square_index + 128
So let's take a couple examples (using indexes from the 0x88 board of course):
Can a piece on g1 be attacked by a bishop on c5?

6 - 66 + 128 = 68

ATTACK_ARRAY[68] = 5 = ATTACK_QB (yes it can)

Can a piece on b1 be attacked by a rook on g2?

1 - 22 + 128 = 107

ATTACK_ARRAY[107] = 0 = ATTACK_NONE (no it can't)
This is a very fast way to determine if it is possible for a piece to attack a certain square. After we know that we can go ahead and check for pieces standing in the way.

Delta array: I have also constructed a delta-array (I will not post it here, but you can find it in the code in my next upload) which works the same as the attack-array, but instead of being filled with the constants, it is filled with the delta needed to get to a square.

In the first example above the delta-array would return '-15', which stands for diagonally down to the right (which is one of the bishop's deltas).

The delta-array is a fast way to find the direction we want to check for intervening pieces. Now we can check each square from the attacking square to the attacked, by using the delta, and if we run into a piece on the way (either color) we know the attacking square can not reach the attacked.

Puttng it together: So now that we have our arrays we can construct a method that takes a square on the board and checks if it can be attacked by the color to move. It will follow this pattern:
  1. Loop through all squares.
  2. When a piece of the right color is found, use the attack-array to see if it can attack the checked square.
  3. If it can, get the delta needed in the delta-array.
  4. Use the delta to check every square on the way, if we run into any piece it is not possible to attack the checked square.
  5. If we reach the checked square, the square can be attacked by the piece.
So now we have a fast way of seeing if a square can be attacked, and can use it to determine if a move is leaving the king in check by making the move on the board and calling the attack-method with the king's index.

No comments: