I am currently reshaping the evaluation a bit and while doing that I noticed a very subtle bug. Instead of using the piece table for black bishops I used the table for black knights. This resulted in black thinking fiancetto was a bad thing since the knights get a penalty for standing on the G7/B7 squares, and also a smaller penalty for the D7/E7 squares (which are quite natural for the bishops).
I had been thinking about adding even more incentive for developing the bishops since it looked like they were rarely developed properly. This bug was probably the problem though.
Apr 5, 2007
[Other] New archive site address
Thanks to Wang Zhen the Mediocre archives now have a new ad-free home!
The new address is http://mediocrechess.varten.org/.
The new address is http://mediocrechess.varten.org/.
Apr 4, 2007
[Other] Finally futility
After hours of despair and a bunch of helpful tips that I could not get to work, I decided to post one of my implementations of futility on the Talkchess.com forum. And finally I got the mystery solved. :)
I had overlooked the possibility of all moves in a node fitting the requirements for futility pruning. In some of my implementations this caused a very faulty value being recorded for the node, and in other the mate detection thought no legal moves existed and returned the stalemate score (0).
After having sorted this out, the new implementation of fuility pruning in Mediocre is working like a charm.
I started a little tournament to test it out and the results so far looks quite promising:
I had overlooked the possibility of all moves in a node fitting the requirements for futility pruning. In some of my implementations this caused a very faulty value being recorded for the node, and in other the mate detection thought no legal moves existed and returned the stalemate score (0).
After having sorted this out, the new implementation of fuility pruning in Mediocre is working like a charm.
I started a little tournament to test it out and the results so far looks quite promising:
Engine Score MeAnd this is with futility pruning for only non-captures, so there is still some in there up for grabs.
1: Mediocre dev 0.31 20,5/30 ..............................
2: Mediocre 0.3 9,5/30 00=0=010101=110=0=00=0000=0001
Apr 2, 2007
[Other] Struggling with futility pruning
About two months ago I tried implementing futility pruning. I failed miserably and decided to blame it on the general structure of Mediocre at the time. :)
Once again I am trying to get it to work and obviously I am doing something terribly wrong. I have tried three different setups and run 100 games matches against version 0.3, all three setups resulted in weaker play.
The theory is so simple that I must be missing something.
Well I will keep trying this time.
Once again I am trying to get it to work and obviously I am doing something terribly wrong. I have tried three different setups and run 100 games matches against version 0.3, all three setups resulted in weaker play.
The theory is so simple that I must be missing something.
Well I will keep trying this time.
Apr 1, 2007
[Other] Mediocre website is up
I uploaded the website. For now you can find it at http://hem.passagen.se/maragor/, sorry for the horrible ad covering half the page, it was the easiest solution. When a get a tad better cash flow I will probably get a better location for it.
It is very simple and only intented as a bit more structured way of reading the guides and downloading older versions of Mediocre, atleast for now.
As I said earlier I will be adding content to the site from the blog now and then.
One nice thing is the links to old Jim Ablett executables of Mediocre which I have not had up anywhere before.
Well enjoy. :)
It is very simple and only intented as a bit more structured way of reading the guides and downloading older versions of Mediocre, atleast for now.
As I said earlier I will be adding content to the site from the blog now and then.
One nice thing is the links to old Jim Ablett executables of Mediocre which I have not had up anywhere before.
Well enjoy. :)
Mar 31, 2007
[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:
Le Fou Numérique only uses UCI engines and this is how the division Mediocre will be playing in looks like:
Engine RatingTournaments within the divisions are run regurarly so I am quite happy about this. 'Official' results from a third party are always nice to have.
Adam 2125
Mediocre 2116
Matheus 2106
Monarch 2098
Lime 2097
Firefly 2053
BigLion 2052
DelphiMAX 2035
Mar 30, 2007
[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. :)
Mar 26, 2007
[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:
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. :)
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 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:
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. :)
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 &&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.
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
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
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:
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:
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:
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
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];The piece_values array simply contains the piece values (with an offset of 7 since black pieces have negative indexes).
attacked_piece_value = piece_values[(Move.pieceMoving(move))+7];
sideToMove = board.toMove*-1;
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] =After every capture we attempt to add a hidden attacker.
attacked_piece_value - scores[scoresIndex - 1];
scoresIndex++;
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)In our example the scores-array would look like this {1,8}.
{
scoresIndex--;
if(scores[scoresIndex-1] > -scores[scoresIndex])
{
scores[scoresIndex-1] = -scores[scoresIndex];
}
}
return scores[0]*100;
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
Subscribe to:
Posts (Atom)