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

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

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

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

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

[Other] Evaluating new features

I ran a couple tournaments to test the new features LMR, SEE and an attempt at a more dynamic time management.

Trying LMR

The first tournament is a 200 game match between Mediocre v0.241b and a version with LMR that decides what to reduce based on the move being a capture or not, the current depth, and if the position before the move had one of the kings in check. It does this after searching four moves to regular depth (usually hash move, killer moves and one more).

Obviously this is a quite loose way of handling the reductions, so plenty of moves are going to get reduced. This made me unsure how sound the LMR was going to be, so the result came as a bit of a surprise:

   Engine           Score
1: Mediocre LMR     132,0/200
2: Mediocre v0.241b 68,0/200

The LMR really pays off it seems, and that is with hardly any limits as to what gets reduced after the first four moves.

This was the base of the assumption I made in my last post about the upcoming Mediocre v0.25b having a rating of about 2050 (about 100 points higher than v0.241b).

The 'previous position in check' seems quite useless as a condition when deciding what to reduce, I simply put it in there because we have the information free from the check extension heuristic. Better obviously, is checking if the move up for reduction is a checking move, and if it is, not reduce it. If we do not have that condition the check extension is effectively cancelled out.

So in the next test tournament I changed that and also added a couple of different setups with SEE.

Trying LMR and different setups of SEE

There are numerous ways to use the static exchange evaluation in the search (as well as in the positional evaluation, but I have not gotten to that yet).

It can be used for better sorting of both the quiescent search moves and ordinary search moves. Also in the quiescent search we can prune out losing captures since they should not come up with anything interesting (good sacrifices are handled by the ordinary search) as mentioned by Ed Schröder.

So we have a few possible combinations. In this tournament I decided LMR with 'current' in-check condition is better than 'previous' in-check (based on a few mini tests they surprisingly enough seems quite equal), so I went with that for all the SEE-versions. Every other condition for LMR is the same (4 moves to full depth, do not reduce 3 plies from the horizon, and do not reduce captures).

clmr -> LMR does not reduce checking moves
plmr -> LMR does not reduce previous positions in check
ss   -> SEE sorting in ordinary search
qs   -> SEE sorting for quiescent moves
qsp  -> Same as qs but prunes losing captures
nt   -> New time mangement (didn't work out too great)

If not mentioned, it is the same as in v0.241b (quiescent search being ordered with the ordinary MVV/LVA setup for example).

The tournament had a total of 375 games (25 games between all engines) and these were the results:

   Engine                     Score 
1: v0.25b (clmr,ss,qsp)    79,5/125
2: v0.25b (clmr,ss)        71,0/125
3: v0.25b (clmr,ss,qs)     66,5/125
4: v0.25b (clmr,ss,qsp,nt) 66,5/125
5: v0.25b (plmr)           57,0/125
6: v0.241b                 34,5/125

The version with quiescent pruning seems to be the best, but worse with my new clumsy time management.

As usual we have too few games to make any real conclusions, but I will go for quiescent search pruning, it seems to make a difference for the better, and SEE ordering in ordinary search is clearly beneficial.

Splitting up the table for statistics of version vs. version is rather useless with such few games, but here is a table for the v0.241b against the others:

-----------------Mediocre v0.241b------------------
v0.241b-v0.25b (clmr,ss)        : 6,5/25 4-16-5 26%
v0.241b-v0.25b (clmr,ss,qs)     : 8,5/25 7-15-3 34%
v0.241b-v0.25b (clmr,ss,qsp)    : 6,0/25 4-17-4 24%
v0.241b-v0.25b (clmr,ss,qsp,nt) : 5,5/25 4-18-3 22%
v0.241b-v0.25b (plmr)           : 8,0/25 5-14-6 32%

In conclusion v0.241b got horribly beaten by all the new versions. :)

Elostat

The last analysis of this tournament is done by Elostat, a utility by Frank Schubert for determining rating differences between the engines from PGN files. I set the starting rating to 2090 to get v0.241b to about a rating of 1953 as suggested by Le fou numérique.

These were the results:

  Program                   Elo   +   -   Score
1 v0.25b (clmr,ss,qsp)    : 2172  56  55  63.6%
2 v0.25b (clmr,ss)        : 2131  55  55  56.8%
3 v0.25b (clmr,ss,qsp,nt) : 2110  55  54  53.2%
4 v0.25b (clmr,ss,qs)     : 2110  54  54  53.2%
5 v0.25b (plmr)           : 2066  54  54  45.6%
6 v0.241b                 : 1952  60  62  27.6%

I cut out a few statistics to make the table fit, the layout of this page is not very forgiving. :) The '+' and '-' is the error margin for the elo-ratings. Using the error margins it seems Mediocre is about to gain somewhere between 105 and 338 elo points.

Not too bad I guess. :)

[Other] Rating estimations

The french site Le fou numérique is regurarly estimating the rating of new versions of UCI chess engines.

I hunted down all the estimations Mediocre has gotten and tried to fill in some of the blanks. v0.22b never got an estimate on the site, and v0.12b got a very high estimate (1578) for some reason (this does not reflect the tourneys I have done with it).

Below is a list of the ratings for the different versions of Mediocre. The 'estimated' ratings is results from my own tourneys and the rest is from Le fou numérique.

The numbers should be taken with a grain of salt, for example the difference between v0.232 and v0.231 is almost 100 points, while there is no real difference between those versions (v0.232 got automatic protocol detection, perhaps that helped it play better with Le fou numérique's software, who knows).

However this is also true for the other engines, so take it for what it is, a crude estimate.

Mediocre 0.25b     : 2050 (estimated)
Mediocre 0.241b    : 1942
Mediocre 0.232b    : 1832
Mediocre 0.231b    : 1753
Mediocre 0.22b     : 1650 (estimated)
Mediocre 0.2b      : 1378
Mediocre 0.12b     : 1278 (estimated)

For some comparison here are a few other engines.

GreKo 5.1          : 2265
   Winner of WBEC 14, division 5
Gibbon 2.31d       : 2157
   Qualified for promotion phase of WBEC 14, division 5
Clueless 1.3.4     : 2004
   Qualified for second phase of WBEC 14, division 5
BiBiChess 0.5      : 1991
   Top half of first phase of WBEC 14, division 5
Roce 0.0350        : 1758
   Bottom half of first phase of WBEC 14, division 5

Obviously these numbers mean quite little. They are a very rough estimate of the individual strength of the different engines. In matchups they probably do not hold up too well.

But it is fun to play around with numbers like this without actually having played thousands and thousands of games for statistically accurate rankings.

[Plan] Static exchange evaluation, late move reduction and new time management

I am currently working on some rather powerful additions to Mediocre.

SEE

The static exchange evaluation is probably the most needed one. It is a way of determining if a capture is winning or losing material without actually playing out the sequence on the board. We simply count the number of pieces attacking the square for both sides, and order them so we always capture with the least valuable piece first.

This way we get a good idea if a capture is winning or losing with little time used.

This information can then be used for better sorting of quiescent search moves and also for the main sorting of moves. For the main sorting, winning captures is more likely to produce good results than even the killer moves, and equal captures should be sorted before losing captures obviously.

The problem is writing a good algorithm for this since it will be called very often. If it is too slow the gains will diminish fast. I have taken a good look at the Scorpio and Glaurung engines way of doing this and I think I got it to work very well.

The code is quite complex and I will write a thorough guide when the next version of Mediocre is ready.

LMR

As opposed to null moves that reduce moves which are likely to fail high (be too good), late move reductions reduce moves that are likely to fail low (not reach up to alpha).

The way it works is we start by searching the first 3-4 moves to full depth. In Mediocre these should be the hash move, the killer moves, and possible a move from the history heuristic or a capture sorted high with MVV/LVA (once SEE is implemented winning captures will be among these as well).

Then we reduce the depth of the rest of the moves with 1 and search with a minimal window. If the move by chance surprises us and returns a value bigger than the previous best move, we research the move with full depth.

It is very rare that one of the remaining moves produce better results so this technique saves quite some time. However we need to be careful to not reduce mindlessly. We do not want to reduce moves that we think leads to something interesting. For example we can not reduce checks, since that will cancel out the check extension. Also captures are risky to reduce.

There are several more ways to determine if we should allow reducing a move. For example if a move has failed high often in the passed it is not a good candidate for reducing, we can also check the static evaluation and see if reducing is a good idea (if static evaluation is currently below alpha we should probably not reduce any moves).

There are a few more considerations that can be done as well and I am currently experimenting with what works best for Mediocre. I will get back with a more thorough analysis.

Time management

Currently Mediocre uses a fixed percent of the time on every move (2.5% + increment/2). This is a very crude way of handling the time assignment.

I have been looking at a number of considerations to make the time management more dynamic. Things like different time usage for different kinds of positions, using more time if the evaluation drops drastically after an iteration and spending a bit extra time when getting out of the opening book.

Also using the best move from aborted searches (where we ran out of time and exited the search) is an option as pointed out to me by Greg Schmidt.

All in all there are a lot of things to consider when deciding how much time to use for a move, and the best part is we can have very advanced ways of determining this since it is only done once per search and will not have a big impact of the total time usage.

[Other] A little test tourney

I ran a small tourney (300 games) to test the internal iterative deepening added in the latest version. The results were:

   Engine  Score         1         2         3
1: v0.241b 122,0/200     *     52.0-48.0 70.0-30.0
2: v0.24b  114,5/200 48.0-52.0     *     66.5-33.5
3: v0.232b  63,5/200 30.0-70.0 33.5-66.5     *

As you can see the 0.24 version with its adjusted evaluation is plenty stronger than the 0.23 version. However there is not much difference between the version with iid and the one without (the result between them 52-48).

I will keep working on this and see if we can get it to do better.

[New Version] v0.241b - Internal iterative deepening and changed back eval output

Changes:

• Internal iterative deepening was added along with hash move search before generating moves
• The aspiration windows were reduced to 10 centipawns
• The evaluation output was changed back to show the eval from the engine's point of view

Note: The internal iterative deepening does a mini-search (half the remaining depth) if there is no hash move for the current position. This mini-search finds a plausible move that will be tried first.

Once we have a hash move it will be searched before generating any other moves, that way if we get a cutoff from it (which should be quite likely) we saved some time.

I have chosen to not check the hash move for validity as of now. This can be risky since it is possible for two different positions to have the same zobrist key (possible but highly unlikely). I will probably add some sort of verifier in upcoming versions.

mediocre_v0.241b

[Bug] Evaluation was right

In the last version I simply negated the evaluation output if Mediocre was playing black. This way a 'positive' score would be reported as negative, meaning black was ahead, instead of positive (engine is ahead).

While this seem more logical to me, unfortunately the protocols does not work this way. The evaluation should always be in terms of the engine, and not on what side is ahead.

Fortunately the thinking output does not affect the actual thinking of the engine, BUT some interfaces (like Arena) adjudicate games based on the evaluation of the engines. This can lead to Arena adjudicating a game since it thinks Mediocre considers its position very bad, while in fact it considers it very good.

I will change it back in the next version.

[New Version] v0.24b - Adjusted evaluation and bug fixes

Changes:

• The evaluation was readjusted, resulting in quite an improvement in overall strength
• Fixed an issue with the force mode in winboard, was not leaving force mode on the 'new' command
• Added searchRoot() that works a bit differently on root nodes than ordinary alpha-beta, this should take care of the rare occasions where Mediocre did not have a move to make
• The thinking output now shows white ahead as positive value and black ahead as negative value, the evaluation output no longer depends on what side the engine is playing
• Fixed the contempt factor again, hopefully it works now (slightly negative number for the draw if white is moving, and slightly positive if black)

Note: The changes in evaluation were all quite minor. Added bonus for bishop pair and readjusted a few of the piece tables to encourage development, also slightly increased bonus for rooks on open and semiopen files, and slightly decreased the bonus for king attacks with two and three pieces (the old evaluation would go bananas over even a slight chance of attack).

But all together it really increased the overall strength of Mediocre.

mediocre_v0.24b

[Bug] No move reported and winboard force mode (again)

The first bug has haunted me since transposition tables were implemented. Occassionally (every 20th game or so) Mediocre seemed to stop running and not report any move to be played. The engine did not crash and it did not misinterpret the interface output in any way.

After some research the only explanation I can give is this is due to the position where the search started was overwritten with some deeper searched position in the transposition table. Hence the position can not be found when we traverse the transposition table for the principal varation. And since the 'bestmove' sent to the interface is dependant on the first move in the principal variation, no move is sent.

I hoped the depth/new replacement scheme would take care of this, but in retrospect this hope was futile since the second entry (the 'new' entry) is replaced very often.

In the upcoming version of Mediocre I have added a searchRoot-method that only handles root nodes (that is the first set of moves the engine has to choose from and of which one will ultimately be played). This method is called from the iterative deepening loop, and from here it calls alphaBeta for every root move.

This way we will always know what move was chosen as the best, and we can base the principal variation output on this. Now the worst thing that can happen to the pv-output is we only get the best move and nothing more (instead of best move plus the rest of the expected line), this should happen very rarely (every 20th game or so as mentioned) so it is no big deal.

There are also other benefits to be gained from this approach, since the root is only iterated 30-35 times on average (the number of available moves) we have room for things like more advanced move ordering, reporting the currently searched move etc. Anything we do here will have little effect of the overall performance of the search.

Also we should not probe the transposition table at the root node to check for cutoffs. I have done this before, but all we are interested at the root node is what move to be played.

So all in all this change was needed, and hopefully the annoying bug is gone for good.

Winbord force mode

The winboard protocol clearly states that when the 'new' command is sent, the engine should exit force mode. I simply overlooked this and therefore Mediocre has not been able to play to games in a row if it is black in the second game. This was only noticeable under certain circumstances though since some interfaces handles this more loosely, and also restarts the engine after a game.

However, when a new game is about to start the winboard interface sends:

force

followed by

new

I am not entirely sure what the point of the force command there is, but probably it has something to do with preparing the engine for any possible starting moves that might come.

Anyway after this the interface sends 'go' if the engine is white, since it should move, but only 'usermove [move]' if the engine is black.

So it is imperative we exit the force mode on the 'new' command, or else the engine will only play the 'usermove' on the internal board, but not start thinking about an answer.

[Other] Slowing down a bit

The last three months I have been spending hours every day on Mediocre. For the next month or two I will be slowing down a bit and work on bug fixes and tweak the evaluation a tad. I do not plan to implement any big changes during this time.

I think this is important so I do not end up with a big unmanageable engine that I do not have any overview of.

I also have a few exams coming up that I need to spend time on, so this is a good time to do it after getting all the major parts of Mediocre done.

There are still plenty of things I want to implement and change, but that time will come.

I will report from any 'official' tournament Mediocre participates in. Recently for example it played in a test tournament on Le Fou numérique with quite a pleasing result.

1 Mediocre 0.232b  10,5/14  ·· 0= 01 11 01 11 11 11
2 Philemon C       10,0/14  1= ·· 1= =0 01 11 1= 11
3 Heracles 0.3.0    9,0/14  10 0= ·· 10 11 01 =1 11
4 Piranha 0.5       9,0/14  00 =1 01 ·· =0 11 11 11
5 ApilChess 1.05r1b 7,5/14  10 10 00 =1 ·· 10 01 11
6 T.rex 1.8.5       5,0/14  00 00 10 00 01 ·· 11 10
7 NSVChess 0.14     4,0/14  00 0= =0 00 10 00 ·· 11
8 Ace 0.1           1,0/14  00 00 00 00 00 01 00 ··

If there is anything you want me to clarify or write about post a comment or send me a note, I will also probably write a guide or two about the latest changes. So keep checking in. :)

[New Version] v0.232b - Automatic protocol detection

Changes:

• Mediocre now automatically detects what interface is being used, no parameter is needed

Note: This is another tiny fix in my continued quest to make Mediocre work in all interfaces. The jlaunch solution was hardly brilliant so I decided to drop it and let people use Jim Ablett's executables instead.

But then a new problem arrives, Shredder and Chessbase does not accept parameters on engine startup (like Arena) so Mediocre does not start correctly (or actually it starts to the line input mode which does not recognize anything).

With this new version Mediocre starts and waits for the first command from the interface, if it is "xboard" it switches to xboard, if it is "uci" it switches to uci, and for anything else it goes to line input. This means you will have to type in a 'dummy' command to enter the line input mode, but that is a minor nuiscance.

mediocre_v0.232b