Piece lists

See Mediocre v0.3

I have been putting off the guides for some time. The main reason is we are entering territory that can be very implementation specific. Things that might work perfectly for one engine might be totally wrong for another. However I will make an attempt at explaining the five major new additions to Mediocre. Namely:

Piece lists
New way of generating moves gradually
Static exchange evaluation (SEE)
Late move reductions (LMR)
The new evaluation with Ed Schröder's scheme for piece attacks

In this post I will discuss the piece tables and why they are important.

The benefits Piece Tables

In earlier versions of Mediocre there was no easy way of determining where a piece was placed on the board. All we had was a 128 slot array with all the pieces and empty squares.

To find a particular piece we had to loop over all the squares. It is possible to speed this up quite a bit, by for example making sure we do as few loops over the array as possible, gathering all the nescessary information in one pass.

However it is still a slow process and even worse it makes for some very complicated code when trying to limit the number of loops. The old evaluation was an example of this with two huge loops trying to gather all the information at once.

A far better approach is letting the Board-object keep track of all the pieces and place them in separate lists as they move around. There are some things to consider while doing this, capturing a piece for example is no longer as simple as overwriting it in the boardArray. We now also have to remove it from its corresponding piece list.

Also promotions gets more complicated, we have to add a queen to one list and remove the pawn from another list. And similar when unmaking the promotion, the queen has to be removed and the pawn replaced.

There is also the matter of recognizing what particular piece is moving (not just its type). When moving a pawn from a2-a4 we have to know which of the pawns was moving so we know what index in the pawn list to change. We could of course loop over all the pawns to see what slot had the particular index and change it, but this would be quite slow.

Here is an attempt at an explanation of how I did it in Mediocre.

A possible implementation

I started with creating an internal class in the Board-class called PieceList which looks something like this:

public class PieceList
{
public int[] pieces; // Indexes on the board
public int count; // Total number the piece type

public PieceList()
{
this.pieces = new int[10];
this.count = 0;
}

// Various methods explained below
}

Since the Board-object is only initialized once at the startup of the program we do not have to worry about extra time for initializing these piece lists.

There can only be a total of 10 pieces of a certain type (two original and eight promotions), so that is how big the arrays have to be. Of course for pawns and king we can only have eight and one, but that is of minor importance.

We can now give the Board-class a list for every type of piece on the board.

public PieceList w_pawns;
public PieceList b_pawns;
public PieceList w_knights;
public PieceList b_knights;
public PieceList w_bishops;
public PieceList b_bishops;
public PieceList w_rooks;
public PieceList b_rooks;
public PieceList w_queens;
public PieceList b_queens;
public PieceList w_king;
public PieceList b_king;

Keeping the pieces unique

Many engines uses objects for keeping track of the pieces of the board, so one object is pawn(1) which keeps tracks of that pawn's index. When moving a pawn we automatically know which of the eight pawns it is and can update the object accordingly.

I went for a slightly different approach however.

I added another 128 slot array to the Board-class called boardArrayUnique, that instead of keeping track of what type of piece is on the particular index (square), keeps track of what index the piece on the square has in its corresponding piece list array.

In the position to the left there would be two 128 slot arrays, boardArray containing the piece types of the each square and boardArrayUnique containing information of what index the pieces can be found on in the piece list arrays.

The two arrays would look something like this (I left out the 'dummy' board for simplicity, there are however 8 extra zeros and -1:s to the right of each row, also the board is actually flipped, but this is just for illustration):

boardArray
0 0 0 0 0 0 0 -1
0 0 0 0 0 0 0 0
0 -6 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 6 0 0 0 0 0 0
6 0 0 0 0 0 0 0
0 0 0 0 0 0 0 1

boardArrayUnique
-1 -1 -1 -1 -1 -1 -1 0
-1 -1 -1 -1 -1 -1 -1 -1
-1 0 -1 -1 -1 -1 -1 -1
-1 -1 -1 -1 -1 -1 -1 -1
-1 -1 -1 -1 -1 -1 -1 -1
-1 1 -1 -1 -1 -1 -1 -1
0 -1 -1 -1 -1 -1 -1 -1
-1 -1 -1 -1 -1 -1 -1 0

As explained a long time ago the boardArray keeps the piece types where -6 is black pawn, -1 black king and so on. Now the boardArrayUnique keeps the indexes in the corresponding lists (-1 being no piece on the square, hence no valid index, this actually helps catching faulty indexes since it would attempt to reach the -1:st slot which produces an error).

The lists would now look like this:

w_pawns
pieces: {16,33,0,0,0,0,0,0,0,0}
count: 2

w_king
pieces: {7,0,0,0,0,0,0,0,0,0}
count: 1

b_king
pieces: {119,0,0,0,0,0,0,0,0,0}
count: 1

b_pawns
pieces: {81,0,0,0,0,0,0,0,0,0}
count: 1

// The rest of the lists (w_knights, b_queens etc.)
// have count 0 and empty arrays

So if we wanted to move the white pawn on B3 we would check in the boardArrayUnique where that pawn was located in the w_pawns array and get index '1'.

Every time a piece moves we update both the boardArray with the piece type, the boardArrayUnique with the list index, and the piece list with the new square.

Maintaining the lists

There are three places where we have to worry about updating the piece lists:

makeMove()
unmakeMove()
inputFEN()

Things like generating moves and evaluating piece positions etc. merely uses the lists, they do not have to worry about updating them.

There are three methods that will be used at different times when setting up the board, and making and unmaking moves.

removePiece(boardIndex) - Removes a piece from the piece list and updates the boardArrayUnique accordingly. If we remove a piece from index 0 we move the piece on the last index to this place so we do not get any holes in the array.
addPiece(boardIndex) - Adds a new piece to the end of the array and updates the boardArrayUnique. This is done both when setting up the board but also for promotions and unmaking captures.
updateIndex(from,to) - Updates the boardArrayUnique so the correct index points to the correct list. It also catches captures and removes the captured piece from the right list.

There is actually not much to it. We just have to remember updating the lists in a correct way whenever something changes on the board. Promoting a pawn would include something like this:

w_pawns.updateIndex(fromIndex,toIndex);
w_pawns.removePiece(toIndex);
w_queens.addPiece(toIndex);

Along with the usual changes to the boardArray, history and zobrist keys of course.

Using the lists

Now we can reap the benefits of this very convenient (and time-saving) feature.

For example in the new evaluation there is a method that evaluates the positions of the white pawns. To get the positions of the pawns all we have to do is loop like this:

for(int i = 0; i < board.w_pawns.count; i++)
{
index = board.w_pawns.pieces[i];
// etc.
}

Compare this to the old way:

for(int i = 0; i < 120; i++)
{
if(board.boardArray[i] == W_PAWN)
index = board.boardArray[i];
// etc.
}

It should be quite obvious there is some serious time to gain, as well as less complexity in the code.

The kings

As you might have noticed the Board-class creates a 'list' of the white and black kings. This is of course quite silly since there will never be more than one of each so we could just as well just have an integer with the index. However to keep the make and unmake methods a bit less complex I decided to do it this way, there is no noticeable speed loss by doing this.

In conclusion

I have no definite number of how much this speeded up Mediocre since I did the change parallell to some other things, but I have a feeling it was with quite a bit. And even with zero gain in speed it would still be very much worth it since the evaluation code has become a ton simpler to write.

On to the guide for the new move generation code.