[Other] Mediocre entered Division Poussin

Le Fou Numérique updated their divisions and Mediocre was entered in the lowest (just above the reserves).

Le Fou Numérique only uses UCI engines and this is how the division Mediocre will be playing in looks like:

Engine    Rating
Adam      2125
Mediocre  2116
Matheus   2106
Monarch   2098
Lime      2097
Firefly   2053
BigLion   2052
DelphiMAX 2035

Tournaments within the divisions are run regurarly so I am quite happy about this. 'Official' results from a third party are always nice to have.

[Other] Working on a website

The last couple of days I have been working on gathering all the important parts of the blog into a simple website. As the blog has grown it has become harder to find the good stuff and it is probably about time I do something about that. In the picture you can see a glimpse of the basic layout.

The website will be static in nature, meaning I will not update it like I do with the blog, but every now and then add new content from the blog to it.

As for the address I will probably use the same space as I do for storing the versions of Mediocre, to start with.

I will inform you when it is ready. :)

[Programming] Faster SEE

For some reason I had the following lines inside the see() method. Meaning they were initialized every time the SEE was called:

int[] piece_values = {0,1,3,3,5,9,99,0,99,9,5,3,3,1};
int[] w_attackers = new int[16];
int[] b_attackers = new int[16];
int[] scores = new int[32];

Since we actually do not have to clear any of these at the start of every SEE-check (we keep track of the index and never use what existed there before) I simply moved them out of the method, making them static variables that are not cleared at each call.

This speeded up the SEE-check with about 30-40%. Imagine that. :)

Now SEE is not called that insanely often so in total this small change probably only accounts for a 5-10% speedup overall. But it is a reminder that you have to be careful with your initializations in Java. :)

[Guide] Late move reduction (LMR)

A late move (as opposed to an early move :) is a move that gets sorted late in the list of moves we are about to search.

These moves should rarely produce any good results. For example the latest moves of them all, the losing captures, need very specific features of the position to be successful. Things like a sacrifice exposing the enemy king. But in the general case these moves will just be bad.

The idea of the late move reductions is since we predict these moves will not produce any good results we might as well reduce the time we spend on them.

One neat feature with LMR is that it considers the moves that are likely to fail low, i.e. moves that are not good enough, as opposed to null-moves that tries to find moves that fail high. Since these two techniques operates in different ends of the spectrum they are not likely to overlap, which many other reducing techniques are prone to do.

How it works

Here are the lines of code I added to Mediocre, just before the search is about to go into the PVS search.

if(movesSearched >= 4             &&
   ply >= 3                       &&
   Move.capture(moves[i]) == 0    &&
   !isInCheck(board))
{
  eval=-alphaBeta(board,ply-2,-alpha-1,-alpha,true,depth+1);
}
else eval = alpha +1;

if(eval > alpha) // Continue with PVS search

We start with a few conditions for when we are allowed to reduce moves, more about this below. Then we do a search with a minimal window (since we are only interested if the move fails low or not) using a reduced depth. We reduce the depth with 1 extra ply (a usual search is ply-1). If the eval comes back lower than alpha we are satisfied with this result and can be quite confident that the move was indeed a poor one.

If the search however comes back higher than alpha, something is fishy and we have to continue with the ordinary search at regular depth.

When to reduce

The main idea comes with the first condition; movesSearched >= 4. Basically we start with searching all the likely contenders for best move to full depth, these being the hash move (by far the most common best move), good/equal captures (if there are any), the killer moves and possibly one or two of the best non-captures.

In general 3-4 moves is a good amount of moves searched to full depth before starting to reduce.

Now we need some guidelines as to what we should reduce among the 'late' moves. Here are some type of moves that we probably should avoid reducing:

• Checks - and any other moves that the engine extends, if we reduce an extended move, the extension effect is cancelled
• Captures - unless they are losing, and maybe not even then
• Promotions - atleast if they are queen promotions

These are the obvious ones, there are several other techniques for determining if a move is safe to reduce. Moves that historically failed high might not be good to reduce, neither might moves that raises the static evaluation above alpha or moves that can be determined to cause some sort of threat. These techniques are however a bit more tricky to implement.

This is a rather new technique and there are endless possibilites how to handle the reductions. You could for example try to reduce more than one ply or skip the research when a move comes back above alpha.

For further reading take a look at http://www.glaurungchess.com/lmr.html.

Does it work in Mediocre?

Indeed. And extremely well. Even though I have only tested with a few different setups so far, each and every one of them has given fantastic results. Even the simplest reduction conditions (only captures not being reduced for example) seems to work like a charm.

I will have to do some more testing to see what works best.

I think it is time to call it quits here for tonight. I am not sure if I should go through the evaluation since it is rather huge so it is probably better if you read it off the source code.

Hope you enjoyed my little guide-suite. :)

[Guide] Static exchange evaluation (SEE)

Static exchange evaluation is a very powerful tool for evaluating a capture without actually playing out the moves.

It is mainly used for sorting quiescent (and ordinary) moves which produces far better results than the MVV/LVA scheme.

The implementation is very code specific, meaning there are not many general rules that apply, we simply have to find a fast way of determining if a capture gains or loses material once all the moves in the sequence has been played out.

To fully understand how it is done in Mediocre you might want to take a look at the source code in See.java which is not very long but heavily commented, I will try to give the general idea here though.

General outline

The see() method takes a move we want to check. This move is done by the initial attacker. For example Qxb6 in the diagram. It then returns a value for what this move is worth. If B6 contains an undefended pawn the value would be +100. However if the pawn is defended one time and there are no more attackers (like here) the value would be -800 (-900 for the queen +100 for the pawn).

I will use this queen and pawn capture sequence as an example when explaining other things below.

What we want to do is simply find all attackers, let them capture alternately on the square starting with the lowest valued piece, keep track of what pieces capture and finally find the best possible results of the capture sequence.

I have divided it into a few steps.

Step 1: Finding the obvious attackers

We start with finding the 'obvious' attackers to the square. Meaning pieces that directly attack it. If there are two rooks on the same file for example only the first rook is directly attacking the square, the second is indirectly attacking it and this will be handled later.

The initial attacker is not added here but handled separately.

We do this in the fastest possible way, for example we do not loop over all the pawns for each side, we simply check squares where a possible pawn could attack from, and if it contains a pawn of the right color we add it.

This is the general approach throughout the code. Instead of taking a piece and see if it can attack the square, we take the square and see if a delta runs in to a piece of the right type.

In the diagram you can see how we check for attacking pieces in the different deltas, red for straight, green for diagonal and orange for knight. Since the queen is the initial attacker it will not be added but handled separately as already mentioned, however the black pawn will.

When this is done we have two arrays, w_attackers and b_attackers, filled with all the obvious attackers of the two sides.

Step 2: Simulate the inital capture

We now simulate the inital capture. This is done like this:

score = piece_values[Move.capture(move)+7];
attacked_piece_value = piece_values[(Move.pieceMoving(move))+7];
sideToMove = board.toMove*-1;

The piece_values array simply contains the piece values (with an offset of 7 since black pieces have negative indexes).

So what was done was setting 'score' to the piece that was initally standing on the square (a pawn in the example, so score would now be 1), setting attacked_piece_value to 9 (for the queen) and 'switching' the side to move.

Keep in mind that we do not actually carry out this on the board, we simply simulate it. 'sideToMove' is just an internal integer that keeps track of what side to simulate next.

The attacked_piece_value keeps track of what piece is currently 'standing' on the square. In this case it is 9 since the white queen 'moved' there by capturing.

Finally we update the first index in the scores-array (not same as the score integer) with the score. After the capture sequence this array will be filled with alternating white and black piece values.

Step 3: Adding hidden pieces

Now that the queen was 'moved', we need to check for any pieces that might have been 'hiding' behind it, and hence attacking the square indirectly.

We do this by using the delta the queen moved with (that is by rook delta), and starting from the square the queen stood at we move away from the attacked square.

If we run into to a rook or queen while moving in this direction (since those are the two that can use the delta) we can add it to the attackers. If we run into any other piece, or move off the board, no attackers were hiding behind the queen.

You can see how this is done in the diagram.

The same is done for the other pieces, except for kings and knights. No piece can be hiding behind a knight (think about it), and pieces hiding behind kings are futile since if it is a piece of opposite color it would just catch the king and win the game, and if it is a piece of the same color it will never be able to reach the square since that would mean some other piece captured the king first in the sequence.

Step 4: Playing out the sequence

Now we simulate captures on the square, alternating between white and black, always capturing with the least valuable piece first. And updating the scores-array as we go along like this:

scores[scoresIndex] =
    attacked_piece_value - scores[scoresIndex - 1];
scoresIndex++;

After every capture we attempt to add a hidden attacker.

Once we run out of attackers of either side the sequence is done and we stop.

So in our example we start out with the scores[0]=1 from the captured pawn, and on the next pass we add 8 (=9-1) to scores[1], and then we stop since white ran out of attackers.

Step 5: Evaluating the sequence

Now the scores-array is filled with piece values so we can extract the value of the sequence.

It is done like this:

while(scoresIndex > 1)
{
  scoresIndex--;
  if(scores[scoresIndex-1] > -scores[scoresIndex])
  {
    scores[scoresIndex-1] = -scores[scoresIndex];
  }  
}
return scores[0]*100;

In our example the scores-array would look like this {1,8}.

So scoresIndex would start at 2.

We decrement it to 1 and if scores[1-1] > -scores[1] (in our example 1>-8) we put the lower value in front.

Since we only had two captures in our example we are done here. And can return the centipawn value of -800. Since the queen captured a pawn and then was captured itself.

In conclusion

As you can see the example would sort under 'losing captures'. Winning captures would get a positive score and equal captures would get '0'.

It is hard to write a guide about something this code specific. But atleast I made an honest attempt. :) Hope it helped.

On to explaining LMR.

Edit: Added a few more images for better illustration

[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.

[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.