Mar 26, 2007

[Guide] Generating moves gradually

To start off I can say that this is one way of doing this, I am sure there are plenty of other ways that might be better (or worse). All I know is this made Mediocre a whole lot faster and if you do not have something similar it might well be worth implementing it.

Older versions of Mediocre had one big move move generation method called generatePseudoMoves(). This method generated all possible moves on the board and these were then 'filtered' with the method filterMoves(). The filterMoves method filtered out the moves that left the own king in check which resulted in all the legal moves.

For quiescent search moves the same was done except only captures were verified for legality (and the rest discarded).

A quicker apporach

To save time it makes sense to only generate the kind of move we want, capture or non-capture.

This is done by separating the generatePseudoMoves() into two methods, gen_caps() and gen_noncaps(). We simply do not store any move that is not a capture in the gen_caps, and do not store captures in the gen_noncaps.

Already by doing this we are saving some time in the quiescent search, but the ordinary search needs to use both the methods to get all the legal moves obviously.

However this is only part of what we can do with this.

Gradually finding all moves

In Mediocre v0.241b I introduced a way to avoid generating moves before we searched the hash move. If the hash move caused a cut-off we saved the time it would cost to generate the moves.

However if the hash move did not cause a cutoff all moves were generated, ordered and searched in one go.

Elaborating on this approach we can split up all the move generation in a similar fashion. In pseudo code it looks something like this (see the source code for Mediocre 0.3 for the full code):
while(generationState < GEN_END)
{
switch(generationState)
{
case GEN_HASH:
selectHashMove();
break;
case GEN_CAPS:
gen_caps();
sortCapsWithSee();
selectNonLosingCaps();
break;
case GEN_KILLERS: // See below
case GEN_NONCAPS:
gen_noncaps();
sortWithHistoryHeuristicAndKiller();
selectSortedNonCaps();
break;
case GEN_LOSINGCAPS:
selectLosingCapsFromCaps();
break;

for(int i = startIndex; i < endIndex; i++)
{
pickMoveFromList();
verifyTheMoveForLegality();
searchMove();
}
generationState++;
}
As you can see we start with selecting the hash move (if it exists, which it should after the internal iterative deepening), and searching it.

After we have searched the hash move and it did not cause a cut-off we move on to generating captures and ordering them with SEE (explained later), making sure we do not research the hash move (this goes for all the proceeding steps, if we run into the hash move again we simply discard it since it has already been searched).

When the captures are ordered we will have two parts, one with good/equal captures, and one with losing captures (captures that seem to lose material). We start with searching the good/equal captures one by one, leaving the losing captures for later.

Here is the next big time saver, instead of verifying all moves up front, that is checking wether it leaves the king in check, we save that check for when we actually search the move. If we get a cut-off somewhere we saved all the time verifying the rest of the moves.

So we take the first move in the good/equal captures list, verify it for legality and then play it on the board and search it.

Next comes the killer moves, for now they are handled in the non-captures part (more below).

So we generate the non-captures, sort the killers first and then by their history heuristic values. Verify each move and search it.

And last we get to the losing captures which rarely are any good (queen capturing a protected pawn for example) and do the same with them. We can not simply discard the losing captures here since they might lead to a winning combination that the SEE does not spot (however in the quiescent search the losing captures are indeed discarded, more about that later).

Extending the idea; killer moves

The killer moves are always sorted first in the non-capture phase as I explained above. However we already have the killer moves available without generating anything at all.

The problem is the killer moves are moves that are generally good at the certain ply, but we can not know if the move actually exist in the position we are at.

For example capturing a rook with a bishop might usually be good at a certain depth, but if we moved that bishop earlier in the search that move probably does not exist at this particular position.

To solve this we could write a verifying method that takes the killer move and checks if it actually exists on the board, if it does we could just play it without generating all the non-captures first.

I have not done this for Mediocre yet but it seems like a good idea since the killer moves often cause cut-offs, saving the time it would take to generate the non-captures.

Extending the idea; check evasions

When the own king is in check there is a very limited amount of moves that can be made to avoid the check. So instead of generating all possible moves with gen_caps and gen_noncaps we could make a third method called gen_evasions that only generates moves that takes us out of check. With the given condition that we know our king is in check this could be done quite fast by searching for the checking piece and generating moves that intervenes it.

This way we would save some time by not generating a bunch of moves that would be instantly be discarded by the inCheck lookup anyway.

I have not done this yet for Mediocre, but probably will quite soon.

In conclusion

This saved a whole bunch of time for Mediocre, mainly because the old move-sorting scheme was very crude and did a whole lot of unnescessary work.

Saving work until it actually has to be done is generally a good idea.

Moving on to SEE.

[Guide] Piece lists

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.

[Other] Improvement

Mediocre 0.3 got a preliminary rating of 2165 on Le fou Numérique, with a draw against Spike 1.2 Turin and a win against Delfi 5.1 as notable accomplishments.

The new rating is 245(!) points higher than v0.241.

Even though Le fou numérique only bases its ratings on blitz games, and only 128 games played against various opponents gives a fairly big error margin, this is atleast a good indication that Mediocre took quite a leap in strength.

Mar 25, 2007

[New Version] v0.3 - New evaluation, SEE and LMR

Changes:
  • Mediocre is now stable enough to leave the beta, this is the first 'sharp' version
  • Complete redesign of the evaluation
  • In line input mode the command 'eval' now prints a list of the results of the different evaluation segments
  • New piece lists that store every type of piece in its own list, no more looping over the pawns to check for promoted pieces
  • Simple late move reduction added, every move after the first four are reduced with one ply if they were not a capture or a check
  • Static exchange evaluation added, used for sorting of both ordinary and quiescent moves
  • Losing quiescent captures (captures that lose material) are now pruned
  • New move generation methods gen_caps and gen_noncaps replaces the old generatePseudoMoves
  • Sorting moves is now handled inside the alpha-beta method, it is done step by step so we do not have to generate all moves up front, but rather one portion at a time
  • Move legality (not leaving king in check) is now verified when the pseudo-legal move is being played in the alpha-beta method instead of verifying all moves up front
  • With the new move sorting all non-losing captures are searched before the killer moves, the killer moves can only be non-captures now
  • The UCI protcol would crash the engine if an illegal move was sent in the position string, while this really should not happen Mediocre now recognizes illegal moves and sends an error message instead of crashing
Note: Thanks to Daniel Shawul and Tord Romstad for having such great open source engines (Scorpio and Glaurung), and also Ed Schröder and his website.

mediocre_v0.3

[Other] Version 0.3 nearly done

I have finished with the new evaluation. It took a while since it is nearly 2000 lines of code and both better and faster than the old.

At times it is almost confusing watching the engine play with the new evaluation, it does not play like it used to and some moves just seem weird, but then in the end it comes out ahead usually.

I have high hopes for this new version and it will be very interesting to see how it performs on Le Fou Numérique etc.

Things I will leave for the next version (0.31 or so) are
  • Bishop/knight outposts
  • King tropism. Awarding pieces near the opponent king even if they do not directly attack the squares around it
  • Only rewarding rook on seventh rank if there are still pawns there or opponent king is on the 8th rank
  • Implement x-ray attacks in the general attack table, a queen behind a bishop that attacks the king should be taken account of
  • Win chance evaluation. If near the 50 move rule the score should get closer to 0, and opposite color bishops ending etc.
  • Some more endgame knowledge to avoid going into a losing endgame
  • Pawn and evaluation hashtables to not repeat evaluations of already evaluated positions
I am going to let it play over night now to catch any bugs (hopefully none) and then release version 0.3 tomorrow.

Mar 22, 2007

[Other] Working with evaluation

I am planning to implement Ed Schröder's setup with piece attacks to get a solid foundation to build the evaluation on.

Since I am recreating the evaluation from the ground up it is easy to see what causes slowdowns and one thing I found was the arrays needed to store the attack information.

We need two 128 slot arrays (one for each color) and these need to be reset at the start of the evaluation. Unfortunately Java does not have a good (fast) way of resetting an array (i.e. filling it with zeros).

The choices are using a loop to set every slot to zero, use the Java method Arrays.fill(), or simply create a new array (which always starts with zeros in all slots).

As it turns out all these are fairly equal in speed, and hence rather slow. I lost about 5-10% of the total evaluation speed by just setting up the attack arrays.

At first I wanted the arrays to consist of type 'int' (32-bit numbers), since I find Ed's implementation a bit restricting, but creating a 128 slot array with integers is about 3 times slower than creating an array with type 'byte' (8-bits). I guess byte will have to do.

Mar 21, 2007

[Other] New piece lists done

Mediocre now has piece lists in the Board class like this:
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;
The piece lists for the kings were a bit of a workaround to make it all work together, obviously there will never be a 'list' of kings.

As I mentioned before my previous piece list was a simple 32 slot array where index 0-15 held the black pieces and 16-31 the white.

The problem with them was the promotions. If a pawn got promoted one of the pawn slots (0-7 for black, 16-23 for white) started representing the promoted piece instead of a pawn.

This caused a lot of unnescessary looping since it was never possible to know beforehand if there was a promoted pawn, so both the ordinary slots for the piece type and the 8 pawn slots had to be checked.

The new setup has arrays for every type of piece which are updated in the makeMove and unmakeMove methods. The array comes with a count keeping track of how many pieces there are in the array.

I also added a boardArrayUnique array that keeps track of which index a certain piece is on in its corresponding piece list. So a 2 on 'd7' in boardArrayUnique and a -6 on 'd7' in boardArray means the black pawn on 'd7' can be found on index 2 in the corresponding piece list.

Perhaps this could be done in an easier way, but I am quite satisfied with the result. It was a needed change.

Moving on

The move generation time was essentially cut in half with this and the other changes I have made since last version. It was quite complicated but worth it.

On to revamping the evaluation, and then Mediocre 0.3 is ready (time to let the beta go, I think Mediocre is stable enough now).

[Plan] Better piece lists and another look at evaluation

I am now done with the new sorting. It resulted in quite a noticeable speedup overall.

There are now two things I want to do before releasing the next version.

New piece lists

My old piece lists had a problem with promotions. Instead of looping over the positions for a certain piece you had to loop over the piece type plus all the pawn indexes since one of the pawns could have been promoted.

I considered setting a flag if a pawn was promoted to a certain piece to know if looping the pawn indexes was nescessary. But this is a rather crude workaround.

Instead I am going to create a real list for every piece type. If a pawn gets promoted it is removed from the pawns list and added to the corresponding list.

This way we always have all pieces of a certain type available with a minimum of looping.

Evaluation again

While the old evaluation works quite ok, I do not really like the structure of it. I am sure it could be done better and faster.

Also the old evaluation is missing penalty for backwards pawns, does not calculate mobility, lacks a good 'pawn race' evaluation and does not consider 'hanging' pieces. It is also still quite common that Mediocre fails to castle, especially in queen pawn openings.

So while implementing those features I am going to take a look at the overall strucutre as well.

Mar 20, 2007

[Other] Another chess engine creation blog

Jaco van Niekerk has just started a new chess engine creation blog at http://vicki-chess.blogspot.com/. He is programming in C and uses another board representation (12x12 instead of 0x88 like me).

So far he is working with the move generation. I look forward to seeing how it develops.

Mar 19, 2007

[Plan] Mediocre in WBEC and some planning

The 15th edition of the WBEC (http://wbec-ridderkerk.nl/) starts at the beginning of April and Mediocre is going to play in the 5th (last) division.

I am very much looking forward to it and I hope to have Mediocre v0.25 ready by then.

After getting SEE and LMR working I am now attempting a sorely needed reconstruction of the sort prodecures.

So far I have separated the generatePseudoMoves() method into gen_caps and gen_noncaps. Where the first generates only pseudo legal captures, and the other only pseudo legal non-captures.

Not only does this save some time when generating quiescent moves (ordinary moves does not benefit from this since it has to use both gen_caps and gen_nocaps anyway), but it also makes it possible to generate moves 'as we go along'.

In Mediocre v0.241 I introduced a way to pick the hash move before generating any moves at all, my plan is to elaborate on this. The prodecdure will look something like this:
  1. See if we have a hash move and search it
  2. Generate the captures and search all that are not losing material (checked by SEE) one by one
  3. Get the two killer moves and do a quick verification if they can be played on the board, if they can, search them. We need the verification since the killer moves are based on depth and not position, so a killer move may not be possible to play in some positions
  4. Generate all non captures and search the one by one
  5. And finally only the losing captures are left so search them one by one
The assigning of ordering values and sorting is integrated in each step. So if we get an early cutoff not only do we save the work of generating moves we have no use for, we also save the time of needless assigning of ordering values and sorting.

Also, since gen_caps and gen_noncaps generates pseudo legal moves, we need to verify if the move is legal (not leaving the king in check) before it is searched. This saves time as well since we only have to verify moves we are actually going to use, and not a whole list of moves that might get pruned by the alpha-beta.

Since we have to wedge this part right into the alpha-beta method there are a lot of things to keep track of. And it will probably take some time before it is all finished.

Hopefully I will get it all together before WBEC 15 though.