[Plan] Some planning

Here is a list of what I will be doing next. In order.

1. Make an opening class of my own (right now I am using Yves' opening class just to avoid repeated games). This is a rather small project and there is not much to it. I will go through how to implement it and what you should keep in mind while writing it.


2. Iterative Deepening and time management.
   
   What iterative deepening does is start to search the position with 1 ply depth, return the best move and evaluation, then search it to 2 ply, and so on until the allocated time is up.
   
   This way we always have a searched move to return when we need to move. We will need to keep track of the times used and make some intelligent calculation on how to spend the time, perhaps use a little more in complex middle games for example.


3. Some improvement to move ordering.
   
   Iterative deepening might seem costly since we do a bunch of repeated searches. A 5-ply search will include all the moves searched in 4, 3, 2, and 1 ply searches as well.
   
   But as I will show later, it is not that much of an extra cost and since it will help improve our move ordering greatly we will actually gain speed by using it.
   
   As I have stated before the move ordering is very important in alpha-beta search. As it is now Mediocre can barely get to a 5 ply search without using too much time to make it annoying. This is mainly because I have no move ordering at all. In fact the move ordering is probably about as bad as it can be since the moves are now sorted starting in the corners where we rarely see the best move.
   
   With iterative deepening in place we can simply input the previous best line and search it first. Since this line will be the best in a majority of the positions, we should see a huge improvement in search speed once this is done.
   
   There are a number of more ways to improve move ordering. I will save that until later since I believe Mediocre will be fast 'enough' for now with this technique.


4. Start tweaking the evaluation so Mediocre plays more interesting (and better). I am planning to put a lot of effort into this before moving on.
   
   The evaluation portion is where we can do the most to shape our engine, and it is the part where every chess engine gets its personality. The search and any search optimization (transposition tables, null-moves etc.) you might have will be pretty much the same in most engines, but the evaluation is unique.
   
   Here are a few things I am planning to implement in the evaluation:
   
   
   • Piece placement evaluations. We want the engine to put his pieces on the best squares. This includes putting rooks on open/semi-open rows. Bishops on the long diagonals where they are not hindered too much by pawns. Knights on good central squares. And anything else I might come up with.
   
   
   • Development. We need the engine to understand what to do in the opening, our opening database only helps until the opponent deviates. This will be done by giving various bonuses; like awarding moving the central pawns, penalizing pieces left on the first rank, greatly awarding castling and so on.
   
   
   • Pawns. We want to make sure the engine understands doubled and trippled pawns are bad (but not always, so we should make a controlled open line more important than avoiding doubled pawns). Award passed pawns and penalize isolated pawns.
   
   
   • The kings. We want our engine to try attack the enemy's king if possible, so award pieces that are in the vicinity of the opponent's king. Also we need to keep our own king safe with a similar scheme.
     
     Here we should also try calculating what protection the king gets from own pawns. An intact wall of pawns in front of the king is a good thing for example.
   
   
   • Endings. We need the engine to realize when the game is turned into an ending. Since in the ending the kings should be brought out and pawns advanced.
   
   These are a few things. More will be implemented as we go along.


5. Transposition table. This is a hash table that keeps track of previous positions in the search, so when we reach a repeated position we already know how to score it. Especially useful in endings where positions are repeated all the time.


6. A full three-fold repetition detection. Once we have the transposition table in place, we will also have Zobrist keys which we can use to efficiently keep track of passed positions in the search tree.


7. Looking even further ahead; Killer moves, null-moves, search extensions, MTD(f) search, better move ordering and more.

There are a lot of things to implement, so lets get started. :)

[Bug] Another little bug in castling rights

The code in makeMove() in the Board-class was written so that if one side could castle one way and a rook was missing from the other side, the castling rights for castling both ways were removed.

Very silly bug, and the second one in a very simple piece of code. I must have been tired that day. :)

This will be fixed in the next download.

[Plan] A crude repetition detection

Not being able to detect draw by repetition is a huge problem. The most obvious reason is of course the fact that even in the most obvious winning situations it can start repeating moves and the opponent gladly accepts the draw.

But the reason I am picking this up (before implementing transposition tables as I said I should) is because trying to play the engine against itself simply does not work with no repetition detection. In 90% of the matches somewhere in the middle game the engine started repeating and the game was drawn. So I could never see the games played to the end.

What I will do is a very crude repetition detection that probably slows down the engine a tad (not enough to make a difference though).

I will keep a history consisting of FEN-strings (instead of Zobrist keys which will be used in the transposition and history later) and in the alpha-beta search I will go through the history and compare the moves just made and see if a three-fold repetition occurs. If it does the engine will evaluate it to draw.

This takes care of the most pressing repetition detection.

What it will not handle is repetitions that occur in the search tree. So it will miss forced repetitions while searching. This is a minor problem though since they are not too common.

This solution will do for now.

[Other] A note on repeated games

I am currently working on making Mediocre a tad more intelligent by upgrading the evaluation function with piece positioning scores. A knight in the center will be more worth than a knight in the corner.

But this will not change the fact that it will give the exact same evaluation if the position is the same. This means that if you play the same move sequence, Mediocre will always answer with the same moves.

There is no random selection of the moves. What the engine consider is the best move will always be played.

Luckily enough this will be solved by itself once we get openings implemented. In the openings there will be an element of randomness since any opening move in the book is considered good, so if we have many to choose from we can pick one at random.

If you by chance encounter the same opening, the engine will still play the same moves after it. But with a large opening book this should be a very rare occurence.

I received a mail from a guy named Yves Catineau where he showed me a bit of his work, and he also included his opening book which is very nice (thanks Yves) and I will be using that. I will take a peek at the way he solved the opening selection as well and see if I can get some ideas.

[Download] #8 - WinBoard compatible and quiescent search

I really should have made this in two separate files, but here you go.

Playing in an interface

The engine is now capable of playing using the winboard protocol. Mediocre only handles the most basic winboard-calls.

• "new" - Resets the board to the original position and starts a new game. This is done by a simple FEN-string input.


• "quit" - Exits the program. I did this with System.exit(-1).


• "setboard" - Sends a FEN-string with a position to setup. Mediocre simply inputs the submitted FEN-string without checking for validity, so be careful.


• "go" - Tells the engine to move from the current position. Mediocre will find the best move and play it.


• "usermove" - If the command starts with 'usermove' it will be followed by the move. Mediocre takes the move, plays it on the board and then replies with best move it can find.

WinBoard

You can download the WinBoard client here.

To play with the engine you need to edit the following line so it looks something like this in the winboard.ini:

/firstChessProgramNames={GNUChess.exe
"java Mediocre x" /fd="path to mediocre"
}

WinBoard comes with GNUChess so that will already be there, you can remove it if you want or keep it. New engines are added by making a new line between the curly bracers {}.

The "java Mediocre x" is the command used to start the engine, and /fd is the directory the files are in.

There is also a /secondChessProgramNames, this is used if you want to play engines against each other. You can add Mediocre there as well and let it play against itself.

Arena

I have also added a .bat file in the download, this can be used by WinBoard as well but mainly we need it for use with the Arena software. To install the engine in Arena you go to the 'Engines' menu and select 'New engine', then choose 'winboard' and find the .bat file and you are done.

Any other graphical interface you might use will work in similar ways. The .bat file should be the easiest way to install Mediocre.

Quiescent search

I have added the quiescent search and it is working as intended, I think. :) The quisSort()-method is used for sorting the moves according to MVA/LVV, it is a bit messy but should be quite fast.

Mediocre is now playing some seriously decent chess. The lack of any sort of piece placement evaluation and opening book makes it play very weird though.

I will be tweaking that next.



Edits:
2006-12-29 - Submitted the compiled .class-files as well.

[Bug] Mate score

The mate score returned by mateCheck() needs to be negated and should not depend on what side is moving.

This is because the mateCheck() is a static evaluation, meaning if we call it there are no more moves to calculate and we know we will either get a mate score or a draw score (mate or stalemate).

The mate value is then returned immediately and since the score returned will be negated in the alpha-beta loop by the line:

int eval = -alphaBeta(board, ply-1, -beta, -alpha, localpv);

we need the number to be negative to start with.

If we were to return a positive score the engine would think it was losing if it mated the opponent.

Also if we were to return a negative/positive score depending on who did the mating, only one side would try to mate. This is what was happening in Mediocre before I fixed this.

[Bug] The pains of programming

Last night I implemented the quiescent search, leaving the bug I know was lurking in the old code. I figured it would show itself eventually. When I started testing the search the engine started making non-sensical moves from time to time.

It left a rook unprotected and did not even calculate for it being captured. After the rook move he also claimed being ahead 500 points (equal to a rook) while in fact he was going to lose it.

I sat for for 5(!) hours yesterday and 5 hours today trying to figure out what had happened.

At first I thought the quiescent search was the problem, since I could not reproduce the error without it. But after playing a number of games with a 2-ply non quiescent search, the bug appeared in a game again.

After putting in a few trace fen-outputs I noticed the engine was searching positions like the one to the left. With both kings and rooks appearing from nowhere.

I tried cutting off games every time more than two rooks appeared on the board, in unmakeMove(), makeMove(), quiescentSearch(), alphaBeta(), and main(). But every time the game found more than two rooks the problem was nowhere to be found, they had just appeared out of nowhere, and I could not trace it back to the source.

When I reached the position in the diagram I decided to replay the game by hand (writing the moves manually instead of playing them in winboard). It was then I realized the engine did not update the castling rights correctly.

The solution? Change the line:

if(white_castle != CASTLE_NONE && black_castle != CASTLE_NONE)

to this:

if(white_castle != CASTLE_NONE || black_castle != CASTLE_NONE)

In the makeMove()-method in the Board-class.

That line is supposed to determine if a castling rights check is nescessary. If noone can castle, we do not need to check for castling right changes. But in the old line we only check for castling right changes if both sides can castle. Obviously we need to check for changes even if only one side can castle.

If we do not update the castling rights, the engine thinks he can castle and calculates the moves, but since the makeMove()-method simply puts a new king and rook on the board, without any further checks, it is imperative that the castling is correctly updated. Or else kings and rooks will be popping up out of nowhere.

Afterwards it feels like I should have realized this much earlier since there were rooks and kings appearing from nowhere, but no other pieces.

Anyway it is fixed now and it will be changed in the next download.

[Guide] Quiescent search and the horizon effect

While there might still be a bug or two in the code so far I will go ahead and implement the Quiescent search.

The horizon effect

I have mentioned the horizon effect in previous posts and it is a problem for every chess engine. I will try to illustrate it with an example.

Consider the position. Now we want the engine to determine if white can capture the pawn on a2. It is obvious to us the move is not ok. We would get:

1. Rxa2 Rxa2
2. Rxa2 Rxa2

And white is down a rook.

Now we are going to look at the engine thinking with different depths. In the following lines the '|' character symbolizes the 'horizon' for what the engine can see.

1 ply depth
Rxa2 | Rxa2 Rxa2 Rxa2

The engine would evaluate the position as equal since all he sees is the pawn capture. And he would make the move.

2 ply depth
Rxa2 Rxa2 | Rxa2 Rxa2

The engine would evaluate the position as being down a rook. And not make the move.

3 ply depth
Rxa2 Rxa2 Rxa2 | Rxa2

The evaluation would be equal again, and he would think he gained a pawn. So he would make the move.

4 ply depth
Rxa2 Rxa2 Rxa2 Rxa2 |

He sees the whole capture sequence and realizes he will be down a rook after capturing the pawn. He would not make the move.

This example is an obvious kind of horizon playing a big role in what moves the engine makes. There are trickier examples though, like the next one.

It is black to move and he is going to lose a piece, so he has to make the best out of the sitation. Here are the lines he will choose at depth 3 and 4.

3 ply depth

1. ... Bxh2
2. Kxh2 Nc5

He sees that he is going to lose a piece no matter what he does, so by taking the pawn he thinks he atleast gained some material. Since he can not see passed the horizon he does not realize that he still will lose one of the knights.

4 ply depth

1. ... Nbc5
2. cxd7 Nxd7
3. h4

With the extra ply depth he sees that capturing the pawn on h2 still loses one of the knights and he ops for a more sound line.

Note that depending on move ordering he might go for the knight move in the three ply search as well, since that also gains a pawn. But the fact that it even considers taking on h2 (Mediocre currently takes on h2) illustrates what a big problem the horizon effect is.

There are countless more examples, like the engine being about to lose his queen and sacrifices piece after piece to keep the queen loss out of his horizon. I think you got the point now though. :)

The 'quiet' solution

The more depth you add to the search, the less of a problem the horizon effect is. If you make a 20 ply search it does not matter too much if the engine thinks he will gain a pawn at the end of the line, since he has plenty of time to change his plan when it comes within his horizon. An error 20 plies away is rarely forced by the first move in the line.

But a 20 ply search takes ages to calclulate even for the best engines out there, so we need a different approach to solve the problem.

The solution is called Quiescent search.

The idea is to search every position until it is 'quiet'. By quiet we mean no captures can be made, so nothing game breaking should be happening in the near future. Some quiescence searches consider checks as well, but I will only consider captures.

We do this by doing an ordinary search to a certain ply, but instead of evaluating the position when we reached the depth, we continue calculating every move that is a capture.

We can do this without it costing too much extra calculation since the way quiescent search works (more about this below) we get a search tree that looks something like the image. This is a bit simplified since I only used a branching factor of about 5 (branching factor is the number of possible moves in each position) for the ordinary moves, a real position has a branching factor of about 30-35.

The bottom line is compared to the ordinary search, quiescent search takes a minor part of the calculation time into consideration, but improves the playing strength immensely.

With a working quiescent search even an engine playing with only 1-ply ordinary depth can play quite descent chess, or atleast not lose pieces too easily.

The implementation

It works almost like alpha-beta and goes something like (pseudo code this time):

quis(board, alpha, beta)

eval = evaluatePosition();
if(value >= beta)
   return beta;

if(value > alpha)
   alpha = value;

generateCaptures();
forEveryCapture
{
   makeMove(nextCapture);
   eval = -quis(tempBoard, -beta,-alpha);
   unmakeMove();
      
   if(eval >= beta)
      return beta;

   if(value > alpha)
      alpha = eval;
}

return alpha;

We start with evaluating the position as it is. If we get a cutoff we end the search here, this happen quit a bit, meaning we never even enter the actual quiescence search. If we get a better move than our last best move, we remember the value and continue the search.

For every capture we keep searching until all captures are made or we get a cutoff. If we find a capture that improves our last best move, we remember it.

This is basically how it works. Now on to a possible problem.

The importance of move order

I have mentioned before that move ordering is important for the alpha-beta search, since searching the best moves first will enable the engine to cutoff many bad lines without looking at them.

When it comes to quiescent search this is even more important.

Since quiescent search does not have a set depth it searches to, a bad ordering of the moves may result in extremely deep lines that completely ruins any kind of efficiency. This is called a quiescent search explosion.

But if we search the best capture first, we can cut off the other captures fast, just like in alpha-beta.

It is hard to know which capture will be the best in every position so we have to make our best guess.

The sorting scheme I will be using is called MVV/LVA (Most Valuable Victim/Least Valuable Attacker). It does what the name implies, sorts the moves to get the low value pieces capture high value pieces first. So PxQ is the first capture that will be checked, next comes NxQ, BxQ and so on down to QxP which will be the last capture we evaluate.

By sorting like this we make sure we are not calculating obvious losses early in the search.

Of course we can not know if the captured pieces are protected. A queen capturing an unprotected pawn is often a good move, but a majority of the time the pieces will be protected.

A limitation

The quiescent search I am going to use will not be able to detect mates. This is not a problem though since the ordinary search will be able to take care of that.

It is possible to tweak the quiescent search to call alpha-beta again if the king is in check (or any other suspicion of a mate being near), but as I said I will not do this.

Looking ahead

When quiescent search is implemented I expect the engine to vastly increase its playing strength. I might go ahead and add a few guidelines in the evaluation just to make it play less 'weird', and then start putting it to the test with a number of games to try to finding some hidden bugs.

[Other] The way a stupid engine thinks

In a 2 ply depth game Mediocre made a weird move I could not figure out. I thought there were something wrong with the search until I realized a 2 ply depth search is not very smart. :)

I will give two examples, in the first the engine plays as it should, moving randomly but protecting its pieces.

e2e4 a7a5 Line: a5 Nc3 0
d2d4 a5a4 Line: a4 Nd2 0
g1f3 b7b6 Line: b6 Nd2 0

As you can see I made a log file of the engine's thoughts. All is well with these lines. Changing one move though (Bc4 instead of Nf3) and the engine does something silly:

e2e4 a7a5 Line: a5 Nc3 0
d2d4 a5a4 Line: a4 Nd2 0
f1c4 a4a3 Line: a3 Nxa3 -100

This line boggled me for quite a bit. Why would the engine consider sacrificing a pawn, evaluate to being behind and still make the move?

At first I thought there was a problem with the evaluation, being black he could consider -100 as being ahead, but then he should not expect the opponent to capture.

The answer lies in the shallow depth. After the move Bc4 from white, the engine thinks any move he makes will lose a pawn since white can capture the f7 pawn in the next move no matter what. So he takes the first move in the vector and accepts being behind a pawn.

I found this rather amusing. :)

When quiescent search is implemented these kinds of problems will disappear since the engine will keep searching until there are no more captures and he would realize that white can not capture on f7 afterall.

[Other] New screenshots

Up until now I have been copy pasting screenshots of the board. While it is not that much work it can get a bit tedious. I will now use the Arena software which allows easy export of the board to clipboard. The new screenshots will look like this:

[Other] Playing around

I got Mediocre working together with WinBoard and played a few games. A few observations so far:

Speed:
1-3 plies; Instant moves.
4 plies; 2-3 seconds.
5 plies; 20-25 seconds.

Since we have no move ordering what so ever and no optimizations like transposition table etc. we can not expect the engine to be much faster. I think this is quite acceptable at this point.

Playing strength: It plays some ridiculous moves. Moving pieces back and forth, having no plan at all. But as soon as a combination of some kind comes within its search depth it finds it without problem.

One severe problem is the horizon effect. If the line ends with its queen capturing a pawn, the engine can play for it without realizing the queen can be captured the next move, since that is out of his 'horizon'.

This will be solved effectively with quiescent search which I will add as soon as I get a few bugs worked out.

Bugs: I have run into one bug so far when playing, the engine tried to move his king into an attacked square. I will check into what the problem was. The more games played the more bugs will be revealed and hopefully I can work them all out.

What now: I will make sure everything works smoothly, and get the engine vs. engine working. After that it is time for quiescent search.

[Other] So how smart is it?

Here are a few tests I made. All searches are made at 5 ply search depth.

Expected line:
Ra1
Qxa1
Rxa1
Kb7
Rb1
Evaluation: 500 (equal to rook up)
Time: 1391 ms
Fen: k7/8/8/8/q7/8/8/1R3R1K w - - 0 1


Expected line:
Nh6
Kh8
Qg8
Rxg8
Nf7
Evaluation: 100000 (mate)
Time: 2422 ms
Fen: 5rk1/5Npp/8/3Q4/8/8/8/7K w - - 0 1


Expected line:
a3
Kd2
a2
Ke1
a1=Q
Evaluation: 900 (equal to queen up)
Time: 32 ms
Fen: 2k5/8/8/8/p7/8/8/4K3 b - - 0 1


Expected line:
0-0-0
Kg1
Ra1
Kh1
0-0-0
Evaluation: 100004 (mate)
Time: 156 ms
Fen: 8/8/8/8/8/8/R7/R3K2k w Q - 0 1


Expected line:
Ke3
Qxa4
Kf2
Qb3
Kg1
Evaluation: -900 (equal to queen down)
Time: 250 ms
Fen: 7k/8/8/8/R2K3q/8/8/8 w - - 0 1


All in all the engine is doing well. It picked the best move for all five positions. As you can see the evaluation is positive even if it is black that is ahead in the third example. This is because black is the side calculating and the numbers are therefore switched so black sees positive numbers as a good evaluation.

In the fifth example white is calculating and realizes he will be down a queen, therefore the number is negative.

In the fourth example you can see traces of the problem I had with the principal variation extraction. The first move is correct (long castle) which mates the black king, but since it was told to search to ply 5 it does so and you get traces of the search in the principal variation. This will be fixed one way or another (probably by stopping the calculation when a mate is found, this method is called killer moves).

Positions with a queen let loose on an open board takes longer to calculate, while a position with only a pawn the calculation is extremely fast. This is of course because of all the possibilites the queen has to choose from. We can shorten the time with better move ordering (among other things). Had we for example calculated checks first in the second position, the time would have been much shorter. Since the first move checked would have been a knight move, and we would have quickly found the mate. And then all the unnessescary queen moves would have been cutoff.

[Bug] Pawn move generation

While testing the search I ran into a few bugs concerning pawn move generation. Namely:

• When generating captures for pawns on the edge of the board no check was made if the piece tried to capture outside the board. I missed this since the only time it generated an error was when a black pawn was standing on 'a2' and tried capture diagonally to the left which results in an out of bounds exception, since that square would get index -1 which does not exist in the array.


• Black pawns were given rank 2 as homerank instead of rank 7, resulting in the pawns happily moving two squares and jumping off the board as they passed rank 1.


• The last bug was rather amusing. The default value for no existing en passant is -1. And the check consisted of trying to match the pawn's diagonal movement to the en passant 'square'. Since a black pawn standing on 'a2' has left diagonal movement index -1 (outside the board), it matched the no existing en passant number and a very weird en passant move was generated.

These changes are made in mediocre(dl7).

[Programming] Extracting the principal variation

This is a somewhat complicated matter. I try to explain it the best I can. Have my code ready, since it is spread through the entire Engine-class and trying to show examples of it would be futile.

When alphaBeta() is first called we submit a pointer to a global vector. This is where the principal variation will be stored when the search is done.

Inside the method a vector called localpv is created. Every time the alphaBeta() is called recursively we submit the localpv.

If we get a move between alpha and beta we have found a new best move, so we want to add this to the principal variation.

Now, since there will most likely be a number of lines that look good at first but then is discovered to not be the best line afterall, we can not just save the line. That is why we have a localpv passed around.

When calculating down in the trees, we are using the localpv of the last instance that called alphaBeta and add the move to it, along with the rest of moves in the current localpv.

So let's say we have returned to ply 3 in a 6 ply search and find the evaluation is between alpha and beta, we add the move that resulted in the line (a move on ply 3) to ply 2's localpv. And then add the rest of ply 3's moves to it.

When we reach the root we are once again working with the actual global pv, and if the evaluation is still between alpha and beta we add the move and the rest of the line to it.

Basically we are working with hundreds of localpv, created at each new call to alphaBeta(). This takes quite some memory but does not slow the engine down, and compared to the number of moves generated it is not much.

This is one tricky bit of code to comprehend. Just remember that even though the code says we are adding moves to pv it is not the global pv unless we are at the root, down in the search trees we are adding it to the last instance' localpv.

[Download] Search done

I have now finished the Alpha-Beta search.

It uses a simple evaluation of piece values, and keeps track of mate, stalemate, 50 move draw, and lack of material draw. As I said I will wait with implementing the three-fold repetition draw.

The depth we want to search is for now stored in the Engine-class, called PLY_DEPTH. If we want to search at different depths we need to recompile the Engine-class with a new value for PLY_DEPTH. I will probably change this in the future, but for now it will do.

The Engine-class also uses a small class called LineEval which holds the expected line and an evaluation. With this download I also submitted the Test-class which I have used to try out the search. In it you can see how a call is made to the search after setting up the board with a FEN-string.

To extract the principal variation (the line the engine expects both players will be following) is not a simple matter, and it can be hard to follow how it is done. I will make a post trying to explain it. There are some minor errors in it for now, like showing expected moves after a mate (which is not possible of course). The main thing is the first move is correct though, so the engine knows what to play.

Since the engine is ready to play some mediocre(!) chess now I will implement compability with WinBoard next. By doing this I can easily check if additions to the engine are improvements or not but letting the engine play itself.

Once that is done we can start adding things like iterative deepening, quiescent search and transposition tables. And looking further ahead openings, time management, three-fold repetition and a more advanced evaluation algorithm.

mediocre(dl7)

Edits:
2006-12-27 - Added information about where to change the search depth

[Guide] Alpha-Beta Search

Now it is time to build the brain of our chess engine; the search algorithm.

The basics: We start with the basics. The min-max.

If we think a bit about what the engine should do, the answer should be something like; play through the the possible moves and answers as deep as we want to go and then evaluate the position.

This is quite true actually. Take a look at the image to the left. White makes a move, black answers, white makes another move and evaluates the position.

The best evaluation is the line abd, scoring 14. So white might decide to play the inital move a. But we can not forget we have an opponent as well, and he tries to minimize the evaluation.

So black will pick the moves that will result in the lowest score, while white picks the moves that results in the highest score. We can call them min and max instead, and there you have the name for the algorithm.

I illustrate this in the image to the left. We look at it from the bottom up (since there is where the evaluation starts). As you can see, in the left tree white (max) chooses the moves a and d in response to black's (min) a and b moves, since they give the highest evaluations.

Now black chooses his move a, since this gives the lowest evalation. We now have the final evaluation 3 of the left tree that starts with white's move a.

We now do the same thing in the right tree, and as you can see the evalation of white's move b is 4.

So white will play b, since that gives him (at worst) 4 in evaluation.

The engine will always assume the opponent making the best moves. Even if white had the chance of getting an evaluation of 14 by starting with the move a, if black accidently answered with b, we assume black will always play the correct move.

The problem with mini-max is we are not cutting off any lines at any point. We simply look at all the lines, make sure each side picks the right moves and finally we get an evaluation. And as stated in an earlier post, there are MANY lines to go through.

I will not give a code example here since I will not use this algorithm, or rather, I will not use it in this simple form, but an optimized version called Alpha-Beta.

An improvement: While min-max searches all possible lines that can arise from a certain move, Alpha-Beta uses a more intelligent approach that cuts off as much as 80% of the lines, without losing any accuracy at all.

To explain how alpha-beta search works I will use an example (slightly tweaked) from Bruce Moreland's page (link on the right).

This is how it goes; You (your name is Max, what else) and your friend (Min) has a number of bags filled with dollar bills. You will get to pick a bag and then Min will pick one bill from the bag and give it to you. Knowing Min is a greedy bastard you know he will give you the least valuable bill in the bag.

If you only knew about the min-max algorithm you would check every bill in all the bags, and pick the bag which had the most valuable lowest bill.

Now try the alpha-beta way instead.

You start with looking through the first bag. There you find a 100-dollar bill and a 20-dollar bill. Knowing Min will give you the 20-dollar bill if you pick this bag, that is what this bag is worth.

You now start looking in the second bag. First you find a 100-dollar bill, and since it is better than the 20-dollar bill in the first bag, the second bag is now the best so far. You then find a 50-dollar bill, it is worse than the 100-dollar bill, but still better then the 20-dollar bill from the first, so you still want to pick the second bag which is now worth 50 dollars.

So far it works exactly like min-max. Now you move on to the third bag, and you pick up the first bill which is a 10-dollar bill. Since this bill is worse than the 50-dollar bill from the second bag, you can discard the rest of the contents of the bag without looking at it. No matter what more you find in it, it will not matter since you will get the 10-dollar bill. There could be a 1000-dollar bill in there but you will not get it since Min will give you the 10. There could also be a 1-dollar bill in there, but that does not matter either since you have already discarded the bag as worse than the second bag.

So your final choice will be the second bag, and you saved the hassle of looking at all the bills in the third bag.

Putting it into practice: When writing the code we will have two numbers passed around, called Alpha and Beta (there is the name of the algorithm).

If you are Max and the alpha >= beta, you know that Min can force a position that is worse than the best you had so far.

The same applies if you are Min with the alpha < beta.

If any of these occur you can stop looking at the current move and move on to the next. This is like finding the 10-dollar bill in the third bag.

I will now show a bit of code that is used for alphaBeta search. This whole thing could be made by using two methods, one called max and one called min, and then passing numbers between them, having the checks between alpha and beta being like above.

But to get code that is easier to maintain I am going to make one method that will be called recursively and have a tweaked recursive call to simulate max and min switching side:

 1 private int alphaBeta(int ply, int alpha, int beta)
 2 {
 3    if(ply == 0)
 4       return positionEvaluation;
 5
 6    Vector legalMoves = generateMoves();
 7    for(int i = 0; i < legalMoves.size(); i++)
 8    {
 9       makeMove(legalMoves.get(i));
10       eval = -alphaBeta(ply-1, -beta, -alpha);
11       unmakeMove(legalMoves.get(i));
12
13       if(eval >= beta)
14          return beta;
15
16       if(eval > alpha)
17          alpha = eval;
18    }
19    return alpha;
20 }

On line 1 we start with calling the alphaBeta-method with a certain depth we want to use, a very low number for alpha, and a very high number for beta. The numbers for alpha and beta should be lower and higher than the mate value, to make sure we get new values for them when searching.

On line 3 we check if we reached the depth we wanted. If we did we evaluate the position and return the number.

On line 6 and 7, if we did not reach the depth yet, we generate all legal moves in the position and go through them one by one.

On line 9 we make the move on the board.

On line 10 we call the method recursively. As you can see the call is tweaked a bit, this is done to simulate switching from Max to Min. By putting -beta for alpha, and -alpha for beta and then negating the answer we get the right cutoffs from the checks below it.

On line 11 we unmake the move on the board to reset it.

On line 13 we have the beta cutoff. The evaluation of the move is 'too good' so we know that the opponent will never go this way and we can stop looking at the moves in this line. Of course this can both be Max and Min doing the cutoff, depending on where in the recursive call we are.

On line 16 we check if the move is better than our previous best move. If it is update the alpha.

On line 20 we are done with the evaluation and the resulting evaluation is returned. Since we assume Max was the one calling the method, we return the alpha.

I hope that was clear enough. There are not that many lines of code, but being a recursive function it can be very confusing.

Something about move order: If we ordered the moves so in every line we always look at the worst moves first, we would never exceed the beta and get a cutoff. If this happened the algorithm would work the same as Min-max since we would not be able to cutoff any lines.

If on the other hand we ordered the moves so we always looked at the best move first we would be able to cutoff pretty much all lines.

Since we can not know beforehand what moves will be the best we will have to make our best guess. One thing is to always evaluate captures first, they tend to be better than random moves.

Once we start with iterative deepening (more about this later) we can use passed results to order the moves as well.

What we will get: Once we have our alpha-beta search done, the engine can start playing. And even if we only use the most basic of evaluations (piece values) it should play fairly well, or atleast not get mated too easily.

So on to writing the alpha-beta search.

[Plan] Draws, mate and stalemate

Before starting with the Alpha-Beta search I need to make things clear regarding to draws, mates and stalemates.

There are a number of ways a chess game can end and how they are handled by the engine:

• Mate - A side has no legal moves while his king is in check.
  
  This is easily checked in the search. If we run into a position where a side has no legal moves, we check if its king is in check. If it is, the position is mate. This is awarded a very high value so the engine always tries to get it (or avoid it).


• Stalemate - A side has no legal moves while his king is not in check.
  
  This will be the result if the check for mate does not find the king in check. It will be rewarded a zero value.


• Lack of material draw - If neither side has enough material to mate.
  
  This will be handled by the position evaluation. Check the board for pieces, if not enough on the board (only at most knight or bishop on both sides). Awarded a zero value.


• 50 moves draw - If 50 moves are made without a pawn move or a capture.
  
  Every board object holds a value for this as mentioned in earlier posts, so all we have to do is extract it at evaluation time. Awards a zero value.


• Draw by repetition - If the same position arises three times with the same player at the move.
  
  This is one nasty thing to implement. Not only do we need to keep track of positions that already occured on the board, we also need to handle it in the search trees. I honestly have no idea where to start. Though it can be handled with the transposition table I am implementing later on. I will put off this until then.

So we got most cases covered. The three-fold repetition will just have to wait. Unfortunately I know by experience the engine can behave very annoying when it does not recognize that type of draw, but we will have to live with that for now.

[Plan] The Engine

What I will do is use an Alpha-Beta algorithm with Quiescent search.

Sounds nice right? :)

Alpha-Beta is the basic search, I will go through that in my next post.

Quiescent is a kind of extension to the basic search which looks at captures only. More about this later.

Since Alpha-Beta search relies heavily on move ordering (as we will see), I will have to implement a good sorting algorithm as well.

Also we need to be able to evaluate positions. To start with I will only use piece values to put scores on positions. Once we get the search up and running efficiently we can improve and tweak the evaluation as much as we want, this is the fun part. :)

All this together will make for a good solid engine. We can extend it with all kinds of things further on.

[Download] Move generation done!

As I said this was the biggest piece of the project so far. Move generation has to be very effective and even a small bug may crash the program.

Now that this is done Mediocre has a solid foundation to stand on when it is time to start writing the actual engine.

We can now make and unmake moves on the board and generate all possible moves available to each side.

The next step will be writing the search algorithm.

mediocre(dl6)

[Guide] Attacked squares

Now that we have our pseudo-legal move generation ready, we need to be able to sort out the illegal moves. As mentioned below they are:

• Leaving king in check.
• Castling while king in check.
• Castling over an attacked square.

All these require us to be able to determine if a square is attacked by the opponent.

There are different ways to do this.

One obvious way would be to make the move on the board and then generate all the moves the opponent can make and see if any of them captures the king, if any does we know the move made is illegal. We would also have to figure out ways to make sure castling was legal.

This way is sure possible, but very costly in terms of speed. We would have to generate moves for all the opponents pieces for every move we want to check.

Attack array: To make sure we do not have to generate moves for pieces that have no possible way to get to the square, I have constructed this attack-array:

  public static final int ATTACK_NONE = 0;
  public static final int ATTACK_KQR = 1;
  public static final int ATTACK_QR = 2;
  public static final int ATTACK_KQBwP = 3;
  public static final int ATTACK_KQBbP = 4;
  public static final int ATTACK_QB = 5;
  public static final int ATTACK_N = 6;
 
  public static final int[] ATTACK_ARRAY =
  {0,0,0,0,0,0,0,0,0,5,0,0,0,0,0,0,2,0,0,0,     //0-19
   0,0,0,5,0,0,5,0,0,0,0,0,2,0,0,0,0,0,5,0,     //20-39
   0,0,0,5,0,0,0,0,2,0,0,0,0,5,0,0,0,0,0,0,     //40-59
   5,0,0,0,2,0,0,0,5,0,0,0,0,0,0,0,0,5,0,0,     //60-79
   2,0,0,5,0,0,0,0,0,0,0,0,0,0,5,6,2,6,5,0,     //80-99
   0,0,0,0,0,0,0,0,0,0,6,4,1,4,6,0,0,0,0,0,     //100-119
   0,2,2,2,2,2,2,1,0,1,2,2,2,2,2,2,0,0,0,0,     //120-139
   0,0,6,3,1,3,6,0,0,0,0,0,0,0,0,0,0,0,5,6,     //140-159
   2,6,5,0,0,0,0,0,0,0,0,0,0,5,0,0,2,0,0,5,     //160-179
   0,0,0,0,0,0,0,0,5,0,0,0,2,0,0,0,5,0,0,0,     //180-199
   0,0,0,5,0,0,0,0,2,0,0,0,0,5,0,0,0,0,5,0,     //200-219
   0,0,0,0,2,0,0,0,0,0,5,0,0,5,0,0,0,0,0,0,     //220-239
   2,0,0,0,0,0,0,5,0,0,0,0,0,0,0,0,0         }; //240-256

This might look like hard work to put together, and it was. :) If you want it go ahead and use it, and perhaps put a link to my page or so next to it.

Ok, great. So how does it work?

Firstly the constants are groupings of pieces that move the same way in a certain pattern. E.g. ATTACK_KQR is king, queen and rook, since they can all move one square up, down, left and right. ATTACK_QB is queen and bishop since they both can move diagonally more than one square. ATTACK_KQBwP is king, queen, bishop, and white pawn, since they can move one square up diagonally. And so on.

The attack-array is filled with these constants, and we can easily look up what a square can be attacked by from another square, using this formula:

attacked_square_index - attacking_square_index + 128

So let's take a couple examples (using indexes from the 0x88 board of course):

Can a piece on g1 be attacked by a bishop on c5?

6 - 66 + 128 = 68

ATTACK_ARRAY[68] = 5 = ATTACK_QB (yes it can)

Can a piece on b1 be attacked by a rook on g2?

1 - 22 + 128 = 107

ATTACK_ARRAY[107] = 0 = ATTACK_NONE (no it can't)

This is a very fast way to determine if it is possible for a piece to attack a certain square. After we know that we can go ahead and check for pieces standing in the way.

Delta array: I have also constructed a delta-array (I will not post it here, but you can find it in the code in my next upload) which works the same as the attack-array, but instead of being filled with the constants, it is filled with the delta needed to get to a square.

In the first example above the delta-array would return '-15', which stands for diagonally down to the right (which is one of the bishop's deltas).

The delta-array is a fast way to find the direction we want to check for intervening pieces. Now we can check each square from the attacking square to the attacked, by using the delta, and if we run into a piece on the way (either color) we know the attacking square can not reach the attacked.

Puttng it together: So now that we have our arrays we can construct a method that takes a square on the board and checks if it can be attacked by the color to move. It will follow this pattern:

1. Loop through all squares.
2. When a piece of the right color is found, use the attack-array to see if it can attack the checked square.
3. If it can, get the delta needed in the delta-array.
4. Use the delta to check every square on the way, if we run into any piece it is not possible to attack the checked square.
5. If we reach the checked square, the square can be attacked by the piece.

So now we have a fast way of seeing if a square can be attacked, and can use it to determine if a move is leaving the king in check by making the move on the board and calling the attack-method with the king's index.

[Other] Merry christmas!

I will spend my christmas day finishing up the move generation. Sounds like fun ey? :)

But had a wonderful christmas eve at my parent's.

[Other] Those sneeky bugs

If you are trying my code and find any suspicious behaviour, please send me a note. Either a solution to the problem, or just the problem itself will help a bunch.

I always found bug-finding the most boring part of programming, and sometimes I get lazy with it. :) I'm sure there's a couple hiding in the current code, let's flush'em out!

[Download] Pseudo-legal moves

I am now done with the pseudo-legal part of the move generation.

The generateMoves()-method in the Board-class now returns a vector with Moves that are possible in the position.

I am not completely satisfied with the castling and pawn move generation, but they work and are fast enough. I might go back and make the code a bit clearer in the future.

As posted below I have also changed the unmakeMove()-method to make it much faster.

Download the new files and take a look. As usual I added tons of comments for easy reading.

The next step will be adding a check for attacked squares that will be used to get a filter for legal moves.

mediocre(dl5)

[Plan] Move notation

Before going into beta-testing with the move generation I need a way to easily see if all moves get generated correctly. So I am going to add a move-notation method to the Move-class.

Here are examples of all move types it needs to be able to generate:

Qe5       (ordinary move)
Rxc6      (capture)
e4        (pawn move)
cxb4      (pawn capture)
exd6 e.p. (en passant capture)
e8=Q      (promotion to queen)
cxd1=R    (capture and promotion to rook)
Red4      (rook on e to d4, two rooks on same row)
N4c5      (knight on 4 to d4, two knights on same rank)
0-0       (short castle)
0-0-0     (long castle)

The notation follows simple rules and is quite easy to extract in all areas but one; the check for two pieces being able to reach the same square. We can not extract this from the move-object alone.

I will not implement a check for the two pieces case right now. Mainly because I want to keep it simple and it is not really nescessary since we will be able to see the moves get generated correctly anyhow.

The reason I am going to use short notation here is because it is the easiest kind to read (atleast for me). If we were to use long notation we would not have to worry about the two pieces case since it holds the square the piece is moving from. But as said, this is done for easily getting an overview of the moves generated.

Later on when we are inputting moves into WinBoard (which I am going to use to let Mediocre play online) we will be using another notation, namely:

e4h8   (whatever piece is on e4, moves to h8
e1g1   (if king on e1 it turns into a castle)
c7c8=Q (promotion to queen)

In this notation we do not need to worry about captures or en passant or castling. WinBoard keeps track of what pieces are where, so when we enter this notation it makes the right move.

Edits:
2006-12-23 - Added a line about why using short notation instead of long.

[Plan] Pawns and castling

Finished up the unmake-move algorithm and it is working great. A whole bunch faster than the previous setup.

Also the generation of the pseudo-legal moves is coming along nicely. I got the generation for common moves up and running. I.e. king, queen, rook, bishop and knight moves are working.

Now we have the special moves.

• Castling - Here we need a special check to see if the squares between the king and rook are empty. Also it does not follow any delta and moves two pieces (the only move that does that), so we can not use the same generation as ordinary moves.
  
  So what I will do is; when a king is found both the ordinary generation method is called (for ordinary king moves), as well as a special castling generation method. We have to make sure the castling generation is cut off quickly if no castling is available so we do not slow down the end game with slow checks for castling at every move.


• Pawn moves - The pawns do follow a delta, but there are many differences compared to ordinary pieces. The differences we have to look out for are:
  
  
  • Captures diagonally and can not capture forwards. This is a major difference since the generation method for other pieces check the arrival square and turn the move into a capture if it holds an opposite side piece.
  • On the original square a pawn has the option of moving one or two squares. So we need an extra check to catch that.
  • If the pawn reaches the last rank, it gets promoted. Basically for one pawn move we then have four options (queen, rook, bishop, knight), resulting in four moves generated.
  
  It is hard to catch all these differences in the ordinary move generation method.

So I will be to making separate methods for each of these two (castling and pawn moves). It takes quite some extra code compared to tweaking the ordinary move generation to accept castling and pawn moves. But it will speed up the move generation a bit since we will not have to do extra checks for the ordinary moves (which there are much more of).

[Plan] Fixing the unmake move

After timing the move generation method, I concluded the takeback in my planned setup (as posted below) was by far too time consuming.

For every created move the method had to generate a FEN-string to put into the Move-object to remember its takeback-position. While one FEN-string generation takes a fraction of a millisecond to calculate you have to count with the engine generating millions of moves.

Below is an overview of the number of times we need to call the generate move method at each ply (a ply is one move made by one side). The average position has about 30 available moves for each side.

Ply  Possible lines     Total generation calls
1                30             1
2    30*30  =   900            31
3    900*30 = 27000         27931
4    .       810000        837931
5    .     24300000      25137931
6    .    729000000     754137931
     etc.

As you can see the numbers grow extremely fast. At ply 6 one extra millisecond in the move generation algorithm would result in 8.7 days(!) extra calculation time.

Now even in the worst possible scenarios we would not get near 8.7 days calculation time. Firstly one millisecond is a very high number and you would have to really mess it up to get it (one full move generation currently takes about 0.04 milliseconds on my hardware). Secondly our search algorithm will narrow the number of positions down to a fraction.

But you get the idea what one ineffective part of the chain can cause if we are not careful. At higher plies I would estimite my move generation with FEN-strings could cause minutes of extra calculation time.

I had hoped the easy unmake-method would help evening out the extra time, but after some thinking I realized it was slower than alternative methods as well. Since it requires a call to the inputFEN()-method which is quite slow.

So instead of a FEN-string in the Move-object we need to hold a few parameters that needs to be remembered about the previous position, these are:

• Captured piece - To know what piece to put back on the board. The boardArray holds no information about passed pieces.


• En passant square - Since the en passant square in the previous position arose one move further back, there is no way to calculate what it might have been, unless the move we are taking back is an en passant move.


• White/black castling rights - Even though we could calculate what changes the move caused to castling rights, we know nothing about passed castling rights. Just because the move we take back puts the white king back on its original square, it does not mean we could give white full castling rights again since it might have changed earlier in the game.


• Half-moves (for 50 moves rule) - In most cases it would be possible to calculate this while unmaking the move. But if the half-moves count was 0 before the takeback, we would have no idea what the count might have been before.

Captured piece is already implemented in the Move-class so we do not need to worry about that.

So we need to create a way to remember the other three parameters.

Total full moves can be calculated at the time we unmake the move.

[Plan] Trouble in paradise

As expected my unmake-move setup is a huge speed drain. I might have to do something about it right away. I'll finish up the move generation for now, but this will have to be fixed asap.

[Other] On the way to the GMs!

This blog is meant to be a source of learning, but also a place where I gather my thoughts about certain subjects, and a way of sketching up plans for the program.

Sometimes even I think my explanations get a bit lengthy and less then perfectly strucutred. :) Though I am already using it myself when writing the code, since it is basically a mix of a number of good sources on the net, combined with my divine wisdom (or not).

I hope you are enjoying it so far as well. I am looking forward to getting the basics done so I can get on with tweaking the evaluation and start beating GMs on ICC. :)

Input and feedback is most welcomed. Don't be shy.

[Guide] Move generation

All the parts of Mediocre up until now have been pretty basic and obvious. Now comes our first big challenge. The move generation algorithm.

This is a huge part of the program and plays a deciding role in the overall speed.

There are a couple of techniques which can be used;

One is only generating a few moves that 'look' good and skip the rest. This is how the human brain works, we look at a position and pick a few good moves to calculate. The problem is it is nearly impossible to make the engine pick the best moves every time, and even if we succeed in the majority of the positions, even a single missed move may lose the game.

Another technique is generating a few moves at a time, calculate them and hope they're so good you don't need to generate the rest. This requires mixing it with the search-algorithm and can get quite messy.

I will go for the third, and easiest approach; generate all moves up front for every reached position.

Pseudo-legal moves: We can divide the moves in a position into pseudo-legal and legal moves.

Pseudo-legal moves are all moves that follows the basic move rules. I.e. the move does not take the piece off the board, or captures own pieces. But it might leave the own king in check, castle while in check or castle over a checked square.

Legal moves are the pseudo-legal moves where the illegal moves have been filtered out.

The reason we make this distinction is because checking if the own king is in check can not be made up front. It takes two steps:

1. Make the move on the board.


2. Check if the square the king is standing on is attacked.

Since we have to actually make the move on the board to see if it's legal, we simply have to generate the pseudo-legal moves first, otherwise we have no moves to check.

We have a choice of leaving the generation at pseudo-legal moves, and then handle the illegal moves in the search by discarding moves if the king gets captured.

Since in-check routines are quite costly, this might save some time, but I find the whole idea a tad silly, capturing the king should not happen, even in the search in my opinion.

So I will generate all pseudo-legal moves and then filter them to get the legal moves to work with.

Deltas: I will be using something called piece deltas to generate the moves for the pieces.

Let's start with an example, the queen delta looks like this:

queen_delta = {-15, -17, 15, 17, -1, -16, 1, 16};

I explained a similar property of the makeMove-method in an earlier post. Here we see the full extent of it.

As illustrated in the diagram to the left the queen's delta is every square next to it, since it can move in all directions. If you take a closer look you will notice that the first position in the queen_delta array represents 'down diagonally to the right'. So add -15 to the original index 52+(-15) and we get the new index 37, as seen in the diagram.

The other positions in the array represents every direction the queen can move (left, right, up, down, diagonally up to the right etc.).

Now let's say we want the queen to move to 'a8'.

The queen follows the line in the diagram, now we need to get the indexes for the squares it passes. So we add the 'up diagonally to the left'-delta (third position in the array, i.e. 15) for each new square.

We get:

'd5' - 52+15 = 67
'c6' - 67+15 = 82
'b7' - 82+15 = 97
'a8' - 97+15 = 112

As you can see we now have a very easy way of generating the squares a queen can move to from a certain position. Just do the same thing with all the deltas until we reach the end of the board with each of them (which will of course be caught by an i & 0x88 check).

The rook delta looks like this:

rook_delta = {-1, -16, 1, 16, 0, 0, 0, 0};

Notice how the last four positions are zeros, that's because the rook can only move in four directions.

And similar for the other pieces.

Sliding and non-sliding pieces: There are two types of pieces, sliding and non-sliding.

Queens, rooks and bishops are sliding. Knights and kings are non-sliding.

The sliding pieces can move numerous squares in a direction, while non-sliding only have one square to move to. This is used to determine wether we should update the delta with the next square (for sliding), or stop after one move is found in a direction (for non-sliding).

Pawns and castling: We now have two trickier moves to handle. Pawn moves and castling.

Pawns are a bit special since they capture diagonally, but can not capture when moving forward. So either we write a separate method for pawns, or make sure we realize it is a pawn when generating the moves for it. We can still use deltas but it gets a bit more complicated.

Castling is a move of it's own and has to be handled separately.

When to stop: Of course not every piece can travel all the way to the edge of the board in every direction. You are bound to run in to a piece now and then.

For ordinary moves we just have to check what piece it runs into, if it is an opponent, the move turns into a capture, and then we have to stop moving in that direction (for sliding pieces). If it is a friendly piece we have to discard that square as moveable and stop generating moves that way.

For castling first we need to make sure castling rights are available for the moving side, but also make sure no pieces are in the way. For legal (as opposed to pseudo-legal) moves we also need to make sure the king is not in check or passes a checked square.

Attacked squares: To be able to check if the king is left in check we need a way to determine if a square is attacked. This can also be useful for other parts of the program and not only for move generation. Like space-evaluation, where the side that attacks the most squares has an advantage in space if material is even.

If this is done wrong it can be very costly, so be careful.

I will make an attack-array in which the program quickly can look up what pieces can attack a certain square from another square.

So let's say I wanted to see if the white king on 'g1' is in check. I would send the index (6) to an isAttacked-method, then go through all squares on the board, and when a piece is found I look in the attack-array to see if it can attack the square from its position.

Let's say we found a bishop on 'b4', the attack-array would quickly state that no piece can attack 'g1' from 'b4', and we know the bishop is not checking the king.

If we found a rook on 'g8' our attack-array would state that it is possible for a rook to attack 'g1' from 'g8', so now we have to check if any pieces are in the way. This is done by traversing the rook's delta towards the king, if we do not run into any pieces on the way, we will eventually end up on the same square as the king and we can conclude the king is in check.

On a sidenote this whole thing could be made another way; let's say we wanted to see if the white king was attacked. Then we could just generate all moves for black (pseudo-legal since it does not matter if black's king is under attack if he can capture the white king), and see if any of the moves is a capture of the white king.

This approach would for sure be easier to implement, but the speed would suffer. We would have to generate all moves (which is quite costly) instead of just doing an extremly fast checkup if the piece has any way of even getting to the square.

I will cover attack-array more thoroughly with examples in later posts.

Conclusion: There is a whole lot of work to be done with this. Let's see if I can put it all together.

Edits:
2006-12-19 - Added the reason for having an attack-array

[Download] #4 - Unmaking moves

I took the easy route for unmaking moves. What I did was simply adding a prevPos property to the move class which holds a FEN-string with the previous position.

In short if the move is e2-e4 in the starting position, the Move-object describing the move would hold a FEN-string with the starting position in prevPos.

Then when we want to unmake the move, we simply use the inputFEN()-method with the FEN located in the Move-object.

When using this way of taking back moves, we will have to be very careful to do the takebacks in the right order. If we try to unmake a move that was not just played on the board, we would jump to some arbitrary position when that move was made. Of course this will be the case even with another setup, since trying to take back a move that was not just played on the board could have unexpected effects.

I have a feeling this will have a considerable effect on the speed of the program later on, but atleast it gets the job done for now. Expect it to change when we start to tweak the performance.

mediocre(dl4)

Edits:
2006-12-18 - Added a few lines about importance of taking back moves in the right order

[Programming] The makeMove()-method

The makeMove-method takes a Move-object and makes the move on the board. There are a few things that happens when making a move.

• Updating the piece positions in the boardArray. This is basically updating the target square with the moving piece, and emptying the square it moved from


• When castling we also need to move the rook.


• When capturing en passant we need to remember to clear the square above/below the piece (depending on what side is capturing).


• Make sure we update the castling rights.


• If a pawn moved two squares, we need to put in a new en passant square.


• If a pawn got promoted, we need to replace it with the chosen new piece.

There's alot of things to keep track of isn't it? :)

Castling rights: There are a number of ways to see if the castling rights changed after a move. I decided to do as follows.

After each move we check the corners and both sides' king square ('e1' and 'e8'), if any of these squares were to lack the right piece (e.g. a black rook on 'h8') we can update the castling rights.

A white king missing from 'e1' would result in all castling rights being removed for white, since the king has moved. A black rook missing from 'h8' would result in removing the short-castle rights for black, since he has moved the rook (or it has been captured).

We do not have to worry about previous castling rights. Take a look at the diagram to the left. At a first glance it might look like white has his castling rights intact, but the rook on 'h1' has been moved!

On the Rf1-h1 move, we would not catch any change in the castling rights, since all the castling pieces are placed at their correct square. But the castling rights were changed when the rook moved from 'h1' in the first place, resulting in an update of white's castling rights to only alow long castling.

Keep in mind we are not adding any rights just because the pieces are placed correctly, so earlier changes will always stay intact.

If the move is a castle, all we have to do is remove the rights for the side castling, since a castle can't interfere with the other side's castling rights. It can temporary stop a castle by having the rook positioned so the other side's king needs to pass a checked square, but it doesn't permanently change the rights. The temporary change will be handled by the move-generating algorithm.

Promotions: Since our Move-objects keep track of what piece has been chosen for the promotion, all we have to do is replace it's target square with the corresponding piece. I have done this using the following code:

switch(move.moveType)
{
   case PROMOTION_QUEEN:
      boardArray[move.toIndex] = W_QUEEN*(-toMove);
      break;
   case PROMOTION_ROOK:
      boardArray[move.toIndex] = W_ROOK*(-toMove);
      break;
   case PROMOTION_BISHOP:
      boardArray[move.toIndex] = W_BISHOP*(-toMove);
      break;
   case PROMOTION_KNIGHT:
      boardArray[move.toIndex] = W_KNIGHT*(-toMove);
      break;
}
boardArray[move.fromIndex] = EMPTY_SQUARE;

I am using the 'toMove' property to get the right colour of the new piece. The toMove variable is either 1 (white's move) or -1 (black's move), so by simply multiplying the piece by it we can change the colour. Now we already switched side to move in the beginning of the method so we have to use -toMove to get the right side.

So if it is black's move, the W_QUEEN (integer 2) will be transformed to B_QUEEN (integer -2) when multiplying with the side to move (-1).

Getting the moves: For now we do not have any easy way of creating a Move-object to make on the board. So we have to hard code it using something like:

Move move = new Move(B_KING, 116, 118, 0, SHORT_CASTLE);

This is obviously not that much fun when you want to try going through a whole game. But don't worry, the move generating algorithm will generate all moves available on the board, so soon we have easy access to every possible move in Move-object form.

Conclusion: We now have a way setting up a position, making a move, and extracting the position. Next step will be unmaking a move.

[Download] #3 - makeMove() added

I've implemented the makeMove feature. It takes a Move-object and does the nescessary changes on the Board.

For now we have no easy way of creating a Move-object, so we just have to hard code it in a test method to try it.

I'll go through some important passages in my next post.

I'm sure there could be a bug here and there in the code, feel free to report them if you find any.

mediocre(dl3)

[Other] Updating posts

The attentive reader might have noticed I'm updating many of the old posts as I go along. Mostly spelling errors, but occasionally there are some bigger things added.

For example I added a couple of lines about error handling in the FEN input/output post.

From now on I'll make a note at the bottom of the post when something more than trivial is added.

[Programming] FEN input/output methods

Peeking into the board class: To start off I created a bit of code which displays what the Board-class holds at the moment. This is a way of making sure we actually get the right numbers when using the FEN codes later on.

If you decided to skip writing any FEN code, you could use this piece of code forever. Trust me though, FEN-notation is a good thing. :)

It looks like this:

System.out.println(enPassant);
System.out.println(movesFifty);
System.out.println(movesFull);
System.out.println(white_castle);
System.out.println(black_castle);
  
int i = 112;

while(i >= 0)
{
   if((i & 0x88) == 0)
   {
      System.out.print(boardArray[i] + " ");
      i++;
   }
   else
   {
      i -= 24;
      System.out.print("\n");
   }
}

And the output from a board with the starting position would be:

-1
0
1
3
3

-3 -5 -4 -2 -1 -4 -5 -3
-6 -6 -6 -6 -6 -6 -6 -6
 0  0  0  0  0  0  0  0
 0  0  0  0  0  0  0  0
 0  0  0  0  0  0  0  0
 0  0  0  0  0  0  0  0
 6  6  6  6  6  6  6  6
 3  5  4  2  1  4  5  3

As you might've gathered from my Definitions file, negative numbers stand for black pieces, and king = 1, queen = 2, etc. And 0 for empty squares.

The reason I'm showing this is to illustrate one of the nifty features of the 0x88 setup. We want to view the board with the black pieces on top, so we start writing from the 'h8' square (index 112 in the array).

First we check if the square is on the board with i & 0x88, I went through this in an earlier post.

Now if the square is not on the board, we know we reached the edge, so we need to move to the next rank (the 7th rank since we're moving from the top). To get to the first square on the next rank all we have to do is subtract 24 from our current position. This works for any square that's one step off the board (120, 104, 88 etc.), and with this setup that's where we'll be when we want to change rank.

As a sidenote; adding 16 takes us one rank up, subtracting 17 takes us one square down diagonally to the left, and so on. This will be extremely useful when we start generating moves.

Ok, now we have a way of peeking at our board class.

FEN input/output: This is the first "programming" post I write, and even though I'd really like to bore you with the ins and outs of the code, it's really nothing special.

The output goes through all the properties of the class and creates a string accordingly.

The input goes through the inputted string character by character and inputs the information at the right place.

It's all quite basic, but there's one passage I'd like to show, the en passant passage in the inputFEN()-method. It looks like this:

case 3: // En passant
{
   if(currentChar.equals("-")) enPassant = -1;
   else
   {
      switch(currentChar.charAt(0)) // Find the row
      {
         case 'a': enPassant = 0; break;
         case 'b': enPassant = 1; break;
         case 'c': enPassant = 2; break;
         case 'd': enPassant = 3; break;
         case 'e': enPassant = 4; break;
         case 'f': enPassant = 5; break;
         case 'g': enPassant = 6; break;
         case 'h': enPassant = 7; break;
      }
      
      // Get the next character (the rank)
      i++;
      currentChar = trimmedFen.substring(i,i+1);

      // On rank 3 or else rank 6
      if(currentChar.equals("3")) enPassant += 32; // Add 2 ranks to index
      else enPassant += 80; // Add 5 ranks to index
   }
}

First if the character is '-' there's no en passant. Now we look at the first part of the square, the row (a,b,c,...), we translate this to the index of the first rank. Then we go on to checking the rank, if it's the 3rd rank, all we have to do is add 32 to the number and we've moved up two ranks and get the right index. Same with rank six (the only other option since en passants only occur on the 3rd and 6th rank), now we add 80 and we've moved up 5 ranks.

Easy ey? :) Of course it's very possible to just take the coordinates and transform them into an index (using a transformation table, or some method), but this is faster and easier. And fast is what we need for move generation later on! As I keep saying. :)

Error handling: For now I have done very little to handle errors that might occur. Later on a thorough check to see if the inputted FEN-string is valid should be implemented. As it stands a faulty FEN-string could result in a crash. But as long as we're the ones inputting the strings, we should be ok, and if a crash occurs we know where it came from, just make sure we have valid strings in the first place.

Conclusion: Now we have an easy way of inputting positions into the engine, and also looking at the positions that arise on our virtual board.

Since this part of the code was so basic I didn't feel the need to go any deeper. If you want to see what I've done, take a look at the code (mediocre(dl2)). I've made sure to add a bunch of comments just about everywhere, so it should be easy to follow.

In later programming posts I'll be more thorough if needed, atleast on the not so obvious parts.

Next up is making and (hopefully, if I get it figured out) unmaking moves on the board, and after that comes the huge move generating project.

[Download] #2 - FEN input/output added

A new download is available. I've added the getFEN() and inputFEN() to the Board-class, along with a couple of new properties for the class. I also made a few adjustments to the Definitions interface.

I'll go through the new methods in my next post.

mediocre(dl2)

[Guide] FEN Notation

FEN Notation basics: A FEN-notation is a single string that holds all the information about a position. That is piece placement, side to move, castling rights, en passant square, number of half-moves (moves by one side) since last capture or pawn move (to keep track of 50 move rule), and total number of full moves (moves by both sides). In that order.

The starting position is described with FEN-notation as:

rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR w KQkq - 0 1

And here's how to read it:

We start with the black pieces (8th rank, in lower-case for black), then '/' to move to the next rank (the 7th), there we have the black pawns, then next rank where we have no pieces so we put the number 8 (as in eight empty squares).

Then comes 3 more empty ranks, then the white pawns and pieces (in upper-case for white).

Next character 'w' determines it's white turn to move.

KQkq is for castling rights (K - white can castle kingside, Q - white can castle queenside, and same for black in lower-case). If noone can castle we put a dash '-'.

Then comes the en passant square, since there is no en passants available in the starting position we have '-' there. There can only be one en passant square in any given position (there's only one pawn move at a time that can result in the square).

Then comes the half-moves since last capture or pawn move, and finally the total of full-moves (starting at 1 and incremented every time black moves).

A few examples:

k7/8/8/4N3/8/8/8/3K4 b - - 13 56

Notice how neither side has castling rights. The black king is placed in the corner so we write 'k7' for black king and 7 empty squares, while the white knight is in the middle of the rank so we write '4N3' for four empty squares, white knight, and 3 empty squares.

rnbqkbnr/pp2pppp/8/2ppP3/8/8/PPPP1PPP/RNBQKBNR w KQkq d6 0 3

The black pawn has just moved two squares, so there is an en passant available on d6.










Don't mind the formatting, I'm sure it looks horrible on some web browsers. (I noticed the last characters on the second FEN example got cut off on mine)

Why do we want it, and why now?: We will need an easy way of seeing what our engine is doing. Sure we could write some ASCII presentation of the board, or even a graphical interface (I will not touch that subject here), but why spend the time when we can create a very easy and effective feature, that we for sure will be using later anyways.

At this stage we have no (easy) way of seeing how the application perceives the board. A FEN-output feature easily solves that.

For development purposes later on we will insert different positions using FEN, and then analyze them with the engine.

If we use a third-party program with its own graphical interface (any that can read/write FEN will do), we have an easy way of writing our own FENs and also a way of looking at how our program perceives the board at the moment.

This was a little bit about FEN Notation. Now let's try to implement it in our Board-class.

(screenshots are taken from Blitzin 2.5, available at Internet Chess Club)