Refactoing & revisiting

There are few things as annoying as a dormant blog - and here I am doing the exact same thing. I've recently revisit Vicki and I am in the process of refactoring the engine. I have found some bugs with the repetition detection and I am spending some time to get the engine stable. Once this is complete, I'll start working in getting the engine up to scratch.

One element that has been missing from Vicki is decent testing. For the time being I've identified 28 engines, ranging from weak to rather strong. The idea is to put Vicki in a gantlet against them and work with the final score as an indication of strength (2 rounds, from the starting position). Later on I'll try the test suites again.

Let see how it goes...

New Vicki almost ready...

I've been promising a new release for some time now... Fortunately, my thesis was accepted with little change and I can now focus that attention on my chess engine too. Vicki has been a bit a of a disappointment and I am working hard on getting her ready for WBEC Ridderkerk's 15th edition. Hopefully we'll see an engine around 2100 in stength :-)

Time-off...

Hi all

I need to take some time off from Vicki for a few weeks or so. My thesis has just arrived back from the moderators and I have some minor changes to make before I hand it in on the 24th of August... then there is also a research paper that needs to be submitted before the end of this month. Then apart from that, I also have to work to pay for everything...

So, Vicki will have to wait a while...

Sorry guys :-(

Null moves

I finally got null moves to work in Vicki. I had some trouble with the capturing of the king (which caused Vicki to hang), but I eventually got it fixed. I am utterly amazed at the effect of null moves in the engine. With null moves Vicki searches (on average) 1-2 plies deeper and even more later in the game. In late-middle games, depths of 12 plies are reached! That is without any other form of pruning or transposition tables. The new version of Vicki is already playing on FICS and I am conducting tests against the older version to evaluate the improvement.

Why didn't I have this ready for the WRCC?

Test cases and transposition tables!

The test cases was a great idea and it paid off! I detected a problem with the Zobrist keys in that en-passant was not correctly added/removed. I also detected a nasty (and embarrassing) castling bug. I omitted the break-statement after each case-statement when verifying that the castling was valid. This means that if white wants to castle king-side, queen side castling must not move through check and white must not prevent black to castling either side, either! A very silly bug! I only detected it after adding a large series of perft checks to my test cases. By squashing this bug, my engine plays much better chess already!

Transposition tables is turning out to be very annoying! I keep on getting them "working" only to find that in a duel (100 games, 3 minutes per side, different starting positions) with the previous version that is does badly... or at best, just as good. Shouldn't transposition tables increase the ELO with 200+ points? As a result I've put this on ice for awhile.

In the WRCC tournament, my engine lost a particular game by means of a long capturing sequence that ended in a check. As checks are not part of the quiescence search, my engine never saw the pending disaster. I am thinking of ways to incorporate checks into the quiescence search without slowing things down too much. But how?

I'm also going to attempt to incorporate null moves into the engine. After reading up on the concept a few months ago I was most intrigued with the concept and it would be interesting to see what effect it will have on my engine.

Vicki playing online

I've just checked on Vicki playing online at FICS. The engine is doing pretty well...actually too well. Vicki has a rating of over 2000 for standard and lightning play and 1897 for blitz (see my website for more exact figures - or better yet - log onto FICS and pay Vicki a visit. She plays under the "myvicki" handle).

I've shifted my approach when working on the code. Instead of hacking away and trying to squeeze a few ELO points in between work, family and social life (actually work and family only - sadly this blog is pretty much the limits of my social life :-(), I want to set definite milestones for the engine. The first important change is test cases. I've devoted an entire c-source file for test cases, which I'll run periodically to ensure that I did not break something while adding some nifty new feature. My "hacking"-approach is what cost me to play without a transposition table in last weekend's tournament. This needs to end...

Vicki tasted blood!

It is with great pride that I announce that Vicki is now playing on the Free Internet Chess Server (FICS) under the handle of "myvicki". Please pay her a visit! After all the fun of the WCRCC I am very motivated in getting Vicki to play decent chess!

Vicki is also competing in ChessWars XI under the promotion section. So far Vicki is not doing that bad, having drawn the first game. It would be interesting to see how she does later on.

Final standings...

The tournament was very exciting and Vicki actually won one game and drew another. For an engine that's missing serious components, I am quite surprised. However, I can't wait for the next tournament to start so that I can amaze a few people... grrr... :-)

Mediocre (blog here) did particularly well - the name really does not suit it well. It is far from being Mediocre and to think it is all written in Java! Well done to Jonatan Peterson. He's a real inspiration!

Just for fun, here is the game that Vicki won (my little engine was playing black). I hope to have many of these soon!!

Official tournament!

Hi all...

I haver entered Vicki into the "The 2007 Second Annual ACCA President's Tournament & 2007 World Computer Rapid Chess Championships". So far, 40 engines have entered and I fear them all! Although this will be a good exposure for Vicki.

I am having difficulties with the transposition table and it seems that Vicki may be the only engine participating without a transposition table at all. At least the improved move ordering is allowing fairly deep tree searches. Also the evaluation function has been improved somewhat and bug fixes have been made. I'll add this version of Vicki to the website soon.

I know Vicki will be obliterated in this tournament - but if I can only get one draw, I'll be very happy :-)

Hold thumbs!

Hello? Someone there?

Not a single post in June does not mean that I have not been busy! I have the new version of Vicki almost ready. Only a few more tweaks before release. My focus has been on the static evaluation code which was rather poor up till now. I separated the evaluation function into 3 sets, depending on opening, middle or endgame.

The transposition table is working... but I did expect a bit more... at least it is working. A few nasty bugs are still lurking in the code during draws which I still need to resolve.

I am also implementing better time control and rewriting the winboard section so that Vicki claims draws and end the game after losing/winning.

I'm also running tournaments to measure the development of the engine. This can be viewed at http://www.vicki.co.za/test.html and is updated real-time.

If only I had more time!

Transposition tables and tidying up.

I realised this morning that it has been quite a while since my last posting. I am currently working on a number of things in Vicki and my guess is that release 0.04a would be significantly stronger than the previous versions. I am somewhat reluctant to drop the alpha qualifier, but perhaps I will in the next release (version 0.05beta).

I currently have a structure called CHESSENGINE that I pass around (or the pointer to it) between functions. I realised that this parameter-passing may actually degrade performance, cause problems because of its size (I’m not completely sure, but isn’t there a limit of 64k on a "struct"s – even on modern operating systems?) and waste quite a few clock cycles to find the data element within this structure. Regardless, all I gain from this is the ability to have multiple engines in the same process as its state is completely described by this one chunk of data. I’m moving away from this and dumping everything as global variables and structures in a header file. Who wants multiple engines (of the same kind and strength) in the same process anyway?

I am also implementing an elementary transposition table and cleaning up the code as I go. At the moment I am having problems getting it to work, but I’m sure it is just a case of a silly bug lurking somewhere. Once this are done, Vicki will not be such a pushover anymore! ;-)

I’ll keep you all posted...

Testing 1, 2, 3,..., 99282111917764

I am currently experimenting with killer-moves, splitting of the evaluation function (opening, middle and end-game), aspiration windows and all kinds of small tricks. For now, I'm leaving transposition tables for later. The idea is to optimise this part of the engine so that the impact of transposition tables will be maximum.

I'm running tournaments on my computer and I wrote a little Java application to upload the file to my FTP account every now and again. The current tourney is between 9 engines, 15 minutes a side and 2 rounds. For up-to-date, semi-real time updates, visit the test page.

Re-engineering...

OK, I realised that this early exit strategy (in SEE) of mine is actually pretty dumb. I replaced it with a very elementary minimax search to evaluate the entire capture sequence for both sides. The results were rather good. I search on average a ply deeper with only SEE in quiescence search (no ordering in the alpha-beta). By adding the improved move ordering in alpha-beta as well I get another ply deeper with longer time controls.

Although Vicki is no push-over any more, a significant amount of work still lies ahead. In order of implementation this is:

1. A long, hard look at the evaluation function of end-games. Vicki struggles with KQ vs. K (never mind KR vs. K).
2. Move ordering within alpha-beta can still be improved.
3. Killer-moves, history heuristics and null moves (I may implement transposition tables before null moves though).
4. Transposition tables.
5. Hash tables (evaluation, pawns, etc.).
6. Opening books (adaptive?) and perhaps even end-game databases.
   
7. Pondering.
   
8. Learning.
9. Factor X.

Factor X is basically that element in Vicki that makes it unique. I don't think I'll be happy with "just-another-chess-engine.". What is factor X? I don't have any idea...(yet!)

Version 0.031alpha an now be downloaded at Vicki's home.

Move ordering

If there is one thing in chess programming that cannot be overstressed then it is coffee. Without coffee all is lost... No really, the difference move ordering can have to an engine cannot be overstated. After resolving a few nasty bugs, Vicki now boasts the following move ordering:

1. The previous PV of iterative deepening is feed back into the search. This is been implemented for a while, but I fixed a bug here which caused the engine to hang. A slight difference is that the entire PV line is used, even if a better line is found the previous line is still investigated first. I was quite amazed by the speedup gained from this.
2. Quiescence search now uses a Static Exchange Evaluation (SEE), which turned out far easier than I thought and to my surprise, caused a fair amount of speedup. The SEE I use also uses an early exit technique. Say for example, I have a pawn and queen attacking a bishop, while my opponent has two pawns protecting the bishop. The full SEE evaluation will result in a negative value: 3-1+1-9+1=-5 (I gain a bishop and a pawn for a queen and a pawn). With early exit I only realize that I can stop after capturing the knight, resulting in +2. A great move!

Vicki is playing a good game of chess already and I find it difficult to beat the engine with tight time controls (3 mins/less), but still beat the engine 80% of the time if I allow myself ample wetware processing time! ;)

I am now concentrating my efforts on the ordering of normals moves as part of alpha-beta (in conjunction with the PV-value). So far the results are very promising, but it still needs some work before being released.

Vicki is crawling now...

Vicki is now out there, but I am not very happy with her performance. It plays terrible chess and the positional play is especially weak. Fortunately, there is still a great deal that I can do. I have started adding to the chess knowledge by tweaking and improving the static evaluation function to get a base to work from. The following is now considered:

• Pieces on the board, P=100cp; R=495cp; N=280; B=290cp; Q=895cp (a bit less than the accepted values to encourage positional play).
• The pawns positions on the board, giving a small bonus to pawns that have advanced further up the board.
• Bonus for passed pawns; penalty for doubled & isolated pawns.
• Knight position bonus (controlling central squares).
• Mobility bonus (1 centipawn for each move), excluding the king.
• Bonus for castling capability (retains bonus once castled).

I estimate Vicki at about 1100, having played against rated engines (she even won a few!). Some serious things are still missing and are next on my todo list:

• Vicki does no move ordering whatsoever. I have a few ideas that I would like to implement, including SEE, sorting by the principal variation returned by the iterative deepening search (yes, all previous iterations are wasted!) and finally, a variation of killer moves.
• Transposition table (Zobrist keys are working).

On a positive note, Vicki had an interesting game against Mediocre, where it was way behind in material and tried to sacrifice a rook (by attacking Mediocre's rook) to force a stale-mate. I was rather impressed by the strategy (which I first thought was a bug!) However, Mediocre is no pushover engine and didn’t fall for that trick and simply moved its rook away! Vicki was mated a few moves later, but at least the draw-detection is working well.

First release

I finally have the first release of Vicki available. It is less than a skeleton of a chess engine and I am rather reluctant to release it, but decided to do so anyway. From the few games I've played against Vicki, I estimate an ELO of around 900, if that much.

I have removed the move ordering as it is not contributing to the engine (slow implementation) and will re-engineer this at a later stage.

Vicki also has a permanent home now, where I'll add the downloads and progress. Let me know what you think. Oh, yes, Vicki's home is www.vicki.co.za.

Basic engine...

I wish I were still a student... my time is so limited! Vicki is making good progress under the current time constraints. So what do I have:

• I have a decent move generator that can generate moves pretty fast using the 12x12 representation technique. I can also generate captures only.
• Alpha-beta search.
• Quiescence search, with MVV/LVA move ordering. Currently, I'm not pruning any of the moves and merely orders them by the MVV/LVA scheme.
• Horrible evaluation function.
• Separate input thread that takes minimum amount of processor time.
• A minimal WinBoard interface (but without any time management).

This is a good start. I must say the the quiescence search makes a huge difference to the engine and I do not think an engine can be successful without it. Despite the fact that Vicki is very limited in knowledge, it doesn't play as bad as I thought. I estimate the ELO to be around 800. which is a bit better than a human that has just learned how to play chess!

Before releasing the first version of Vicki (version 0.1 beta), I need to implement the following first:

• Do away with MVV/LVA and implement SEE. I have an idea which I would like to try out before reading to much on how other people do it. I basically "count" attackers and defenders on a square AS PART of the move generation. Once I have the idea well defined and tried on paper, I may divulge some information on it... :)
• Implement some move ordering in the alpha-beta search using table lookups.
• Implement the standard iterative deepening and re-use its results in the move ordering.
• Add some time management!

But now I'm so-o late for work :)

Threading in C

The mere thought of multi-threading in C was scary enough... the realization that it will be the best approach for implementing the Winboard interface was very depressing. After some careful reading from various sites, I was pleasantly surprised. It it not hard after all (actually I find it as easy as Java's multi-threading!). Refer to the excellent tutorial by Adrian Worley.

It basically boils down to passing a function (Java eat your heart out!) to another function, which will then execute the function as a thread. Other elements such as critical sections, waiting for threads and juggling information between threads are straight forward and provided by the Windows API. The only drawback of this approach is the fact that my current implementation will not be platform independent (i.e. between Unix and Windows) as the Java implementation is (...here C will eat its heart out :)).

I have implemented crude move ordering, but I am not yet satisfied with speed increase I gained. I also got Arena to work for testing, once my WinBoard protocol (UCI later) is up and running.

Quiescent search

I have been away fro a few days to the Kwazulu Natal's north coast (in South Africa), taking a break from all the nonsense of city life. It was wonderful! I did take my laptop along and worked on Vicki when I was not walking along the beach or reading the book inspired by Edge called "What is your dangerous idea?" (an interesting read - even though they had my blood boiling a couple of times).

I've implemented a 3-fold repetition check that works quite well. I use a hash table of 256 entries (it must be a multiple of two, since I simply do a bitwise and which is much cheaper than a mod-operation) After each makeMove() I probe the hashtable to see if the position exists (using the Zobrist key), handling collisions using linear probing. If it exists, I increment a counter associated with the entry, else I add the entry the table with a value of 1. When a "permanent" move is made (i.e. not part of a search) I clear the table if the move involved a pawn push or a capture, leaving the hashtable nearly empty and keeping collisions to an absolute minimum. This technique hardly made any difference to the overall speed, even though I found it a bit complicated.

Quiescent search is now also successfully implemented. It works - but not very well - since I use the normal move generator and check for non-captures within the quiescent search function itself. Using a function that will generate captures only will definitely speed up the function a bit as well. However, the main culprit is move-ordering as I do absolutely no ordering whatsoever.
The time to decide on a move increases drastically when captures on the board become apparent.

My idea for move ordering is as follows. Each move takes up 27 bits of a 32-bit integer, leaving 5 bits free at the end. My idea is to use these 5 bits to represent the potential strength of the move (32 possible strengths) and to populate this field either as part of the move generation or as a separate function. I suspect that a separate function would be better as static move ordering will not always be necessary (consider iterative deepening for example). Combining this with a quicksort() function will give me the starting blocks for a move-ordering routine.

Once this is complete, I will finish the Winboard interface and start measuring Vicki's strength. I'm making progress, slowly, but steadily!

Zobrist keys

I am having trouble with Vicki and three-fold repetitions. So before anything else, I need to implement Zobrist keys. I might as well, since this would also need to be used with the transposition tables later on. I've heard that C's rand() function is not always random enough, so maybe in Vicki version 29.3 I'll get some random numbers here. :-)

So what do I need?

• A 64-bit random number generator which will populate 12 145-element arrays (for each piece of each colour).
• A total of 16 Zobrist keys for castling and turn combinations (I really only need 5, but using an array lookup like this will be cheap. All I need to do is to do a lookup, based on the board's status flag, which is a 4-bit value).
• A total of 16 Zobrist keys for e.p. squares.
  

I still need to think how this will impact on draw detection, where e.p. squares and castling rights are ignored. Maybe using two keys, where the one is derived from the other? But now I have to get to work - long gone are the student days of programming for fun all day... :'(

Vicki's first game

To my utter disbelief Vicki played its first game a few moments ago. Its a great feeling. All I used was a the basic alpha-beta search (with no move ordering) with crude mate detection. The evaluation function considers only material and gives a small bonus for controlling central squares (which makes for interesting games as well.) Vicki plays like a complete beginner - but it plays!

Next, I'll probably need to add some Winboard support.

It works!

I finally gave in and decided to write a divide() function to count the number of positions per move and comparing it with the results of Sharper. My other lazy attempts were fruitless. So after writing the divide method, downloading Sharper and seeing how simple it is to use I started debugging...

It seemed castling was the culprit yet again. Let's start with the basic rules of castling: A side may castle if the king has not moved; the rook has not moved; there are no blocking pieces and the king does not move through check or is not in check. Do you spot the bug? Aren't I missing something... Yes, you actually need to HAVE a rook in the first place!! I never canceled the castling bit if the opponents captured a player's rook. The result was a weird castling move without the rook. Funny right? I don't think so! :-)

Well, the move generation, making and taking back of moves now works beautifully. It is not a pure pseudo-legal move generator as it will not generate castling moves if the king moves through check or is in check currently. This does cause a slight drop in speed - but I hope that it will pay off later.

At last, I can start with the alpha-beta search.

Solved in part

I finally found a part of the bug. In turns out that the "bishop" on c8 was actually a phantom king, caused by a faulty take-back of long castling. Running perft() again for the FEN string, "r3k2r/p1ppqpb1/bn2pnp1/3PN3/1p2P3/2N2Q1p/PPPBBPPP/R3K2R w KQkq - 0 1", shows correct values up to perft(3). The values obtained were:

perft(1) 48 (correct)
perft(2) 2039 (correct)
perft(3) 97862 (correct)
perft(4) 4085659 (should be 4085603)
perft(5) 193696117 (should be 193690690)

Well at least the program is not hanging anymore. I don't know whether I should ignore this error for now or try and resolve it first. This little project turned out to be much harder than I thought!

Frustrantion, anger and despression!

Vicki kept on getting beaten over the knuckles by Windows (invalid operation) and after hours of debugging, I've detected a nasty error occurring with the piece lists. For some unknown reason, black pieces landed in the white lists and white pieces landed in the black lists. This caused a problem when the makeMove() method tried to remove a white piece from the white list and the white piece happened to be in the black list (something like a naughty boy being caught in the girl's dormitory!).

The can only happen is if a piece captures another piece of the same colour, but surely, that cannot happen. The move generation carefully checks such scenarios. Yet, after generating over 600,000 random games of 10 moves each from the following starting position,
"r3k2r/p1ppqpb1/bn2pnp1/3PN3/1p2P3/2N2Q1p/PPPBBPPP/R3K2R w KQkq - 0 1", the following happened:

  +---+---+---+---+---+---+---+---+
8 |   | r | B |   | k | . |   |   |
  +---+---+---+---+---+---+---+---+
7 | . | . | p | N | q | p | b |   |
  +---+---+---+---+---+---+---+---+
6 | . | . | . | . | p | n | p | . |
  +---+---+---+---+---+---+---+---+
5 | p | N | . | P | . | . | . | . |
  +---+---+---+---+---+---+---+---+
4 |   | p | n | . | P | . | P | r |
  +---+---+---+---+---+---+---+---+
3 | . | . | . | . | . | Q | . | p |
  +---+---+---+---+---+---+---+---+
2 | P | P | P | B | . | P | . | P |
  +---+---+---+---+---+---+---+---+
1 | R | . | . | . | K | . | . | R |
  +---+---+---+---+---+---+---+---+
    a   b   c   d   e   f   g   h  

In the above position, Vicki generated the move c8xd7 (capturing it's own knight) ??? I took the FEN-string from the above position and passed it through the move generator by itself. It did not generate the self-capture move, which means somewhere something is messing up the board.

What I really don't understand is that perft(7) gave a valid move count, without any crashes (from the standard opening position), which make me think that promotion may have something to do with it - yet, I did ran a test for promotions and it worked fine! What is going on?

Searching...

The search function (apart from the move generation) is perhaps the most critical piece of code in the entire engine. If the search function is solid, the rest is mere detail (I think I may regret that). OK, so here's the plan:

1. First I need some sort of interface! I've got a nice ASCII board already - but I still need some way to talk to my engine! I'll do WinBoard later.
   
2. A very basic alpha-beta pruning algorithm (once sorting is done, I'll give negascout a try - see point 5!).
3. Simple sorting together with iterative deepening.
   
4. Separating the move generator to generate captures, checks (not sure about this yet) and normal moves separately.
5. Some cleverer and more informed sorting functions.
6. All the other tricks, tips and tweaks.
   
7. International award winning and world-famous chess program.
   

For the rest of this week, I'll focus on 1 and 2. Points 3 is for the weekend, while points 4 and 5 are a for March-April. Point 6 will follow once everything else is done. I don't know how point 7 got there... someone else must have written it! ;)

Move generation fixed!

The move generation seems to be fine now. I discovered more bugs than I thought I would. These included en-passant (ep) status flags that were not set correctly (allowing any piece to capture ep, which is very humorous!), castling which never updated the piece positions (in the lists), creating invisible phantom rooks and kings and numerous other weird and bugs.

I've run two perft tests for now. In both instances the correct move counts were obtained. I guess I need to do a few more, but I am both reluctant, scared and lazy. :-) I want Vicki to start playing chess! Here is the benchmarks so far (which still includes all the asserts). I am happy with the results - although, I don't have any idea if this is slow or fast. It's probably just okay.

For FEN-string:
"rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR w KQkq - 0 1"

Up to perft(3), I got 0ms.
perft(4) 0.078s
perft(5) 1.687s
perft(6) 39.985s
perft(7) 17m 53.812s
perft(8) still running :-)

I also checked against the FEN-string
"n1n5/PPPk4/8/8/8/8/4Kppp/5N1N b - 0 1" to catch any promotion bugs. Fortunately, it checked out.

This should cover most move generation, make move and take back move scenarios. Next is a basic search function, to get Vicki to play its first valid chess game. I am still not sure what to actually release. The engine itself should be freeware and available to all, but I am not sure whether I want to release the source code - or is that sore code? ;-) I am open for suggestions, of course.

Uphill battle

I've just discovered another (much older & complete) blog that is doing exactly the same as I'm doing! Jonatan Pettersson's blog is worth a visit. Well done to him!

I have decided to implement Perft calculation to verify my move generator is correct before moving on. The technique simply counts the nodes of valid moves (that is, you have to avoid check, etc.) all the way down the tree. I found this link quite helpful.

My results are the same up to depth 4 (197281 positions), but then miserably falls apart. Not only are the numbers wrong, but the engine occasionally gets slapped over the knuckles by Windows (this is C after all). The moves that cannot occur prior to depth 5 are promotions, castling and en-passant. Logically, it must be one of these moves that is messing things up!

Well, at least the speed that I'm getting from the genMoves(), makeMove() and takeBack() functions are decent (more on that later). I hope I'm not going to spend the next few days trying to get rid of this pesky bug(s).

In the process I've also moved away from passing individual pointers and variables around and settled on a structure that defines the state of the game. The nice thing about a structure like this is that I can dump as much stuff in there without making the functions bloated in any way. Here it is:

typedef struct tag_CHESSENGINE
{
 CHESSPIECE* chessboard[144];
  int status;
 CHESSPIECE* whites;  
 CHESSPIECE* blacks;  
 CHESSPIECE* recycle; 
 CHESSPIECE* whiteking;
 CHESSPIECE* blackking;
} CHESSENGINE;

The pointers, whites, blacks and recycle are lists to ALL the pieces, while whiteking and blackking are pointers to the kings for quickly verifying illegal moves that leaves the king in check. The recycle list is useful to avoid any malloc() calls when taking back moves that resulted in captures. As the engine will only take back moves in a stack-like fashion, it is not even necessary to set the values of the piece structures as they are removed from the recycle list.

Well, back to coding.

What Makes A Good Chess Engine?

While writing the isUnderAttack() function I was wondering about what makes a good chess engine? I realised that it is not only by using the best algorithms and well-informed heuristic functions, but that all the small optimisations also adds up! For example, the method that I just mentioned checks to see if a particular square is under attack. As this function gets called during move generation (for castling) it needs to be pretty fast!

I suspect that by simply changing the order in which pieces are checked as potential attackers for the square can make a difference. My current order is bishops/queens, rooks/queens, knights, pawns, king. The ordering is derived from the fact that the pieces that hinder castling is usually bishops, followed by rooks (I get queens for free!) . If a valid attacker is found, the function returns straight away, skipping all the others.

Once I get Vicki to play valid chess, I can start experimenting with these to determine the actual difference that such a seemingly insignificant change could bring.

Generating Moves & Playing Them

The move generator was relatively painless. I decided to represent a move as a 32-bit integer (the most logical choice) and use a structure to represent the pieces. The piece structure looks as follows:

typedef struct tag_CHESSPIECE {
 char type;
 int position;
 struct tag_CHESSPIECE* next;
 struct tag_CHESSPIECE* prev;
} CHESSPIECE;

The two pointers is used in a linked list to avoid iterating through the entire board array. It also saves me from recreating pieces when they are captured, since I simply push the captured piece onto a stack and pop it off with takeBack(). I designed both makeMove() and takeBack() to be tightly coupled, which is a great improvement on my previous attempt. Assumptions often causes problems, but it can sure boost the engine speed! There is simply no room for defensive programming in a chess engine.

The moves are represented by a 32-bit integer, specifically:
bits 00-07 stores the source square.
bits 08-15 stores the destination square.
bits 16-21 stores the captured piece, if any (0 if none is captured)
bits 22-27 stores the promoted to piece, if any (0 if none)
bit 28 is used to indicate whether the move models castling - this allows quick checking in the makeMove() and takeBack() methods.

After some tinkering, Vicki made the first valid chess move. I had some issues with pointer arithmetic, but is seems to be resolved. I cannot wait to get Vicki to play its first valid chess game!

Board Representation

The past two weeks (even before the start of this blog) I have been trying to decide which representation scheme to use. From a bit of research on the net, I found the following techniques:

8x8-element array (or 64-element array)
Straight forward and very intuitive. The main problem with this approach is legality checking. Every time a sliding piece (queen, bishop or rook) moves the program needs to check if a boundary has been crossed. That will be slow. I also had some experience with this in my very first chess engine.

12x12-element array (or 144-element array)
At first glance I wanted to throw out this idea, but after looking at it, I decided that after bit-boards (see below) this can be pretty quick. All I do is to surround the board with a constant INVALID pointer, which makes checking for legality quick and painless. This is the approach that I am going to use in Vicki.

0x88 approach
In this approach the first 4 bits stores the row, and the last 4 the column. Since the rows and columns ranges from 0-7, the 3rd and 7th (counting from 0) are not used. By using this technique it is relatively cheap to determine an invalid board position. Merely and with 0x88 (10001000 in binary) and if the value is non-zero, the position is invalid.

Bit-boards
This is a technique used by most high-end chess engines. It can be very fast, but is rather tricky to implement, especially the rotated bit-board variety. It is based on the idea of soring information in 64-bit integers. By applying various bitwise operations the boards are manipulated all at once. I am still not sure how to effectively retrieve the list of moves from the bit-board set and have decided to leave this for later.

Baby Steps

I have decided to develop a chess engine and keep a diary of the process from the very start and what better way than using a blog! I have written a chess engine before, but it is very weak and nothing to be proud of. It does beat me, but not consistently.

Every chess engine needs to have a name. I am going to call my engine Vicki. Why Vicki? Apart from being a girl's name and containing the letters 'c' and 'i', which could stand for the words 'chess' and 'intelligence' in an acronym, I have no particular reason. But, I do like it.

My expectations of Vicki in the following year are as follows:

• a strong chess engine that consistently beats me and most other human players.
  
• participating in computer chess tournaments and not finishing last.
• playing beautiful chess by preferring position over material and explicitly endeavoring to create pins, skewers, double/discovered attacks, etc.

I have decided to use C as the programming language. Few languages can keep up with C's speed as it is very close to the hardware (I do not buy the Java is faster than C arguments).

I am famous for always starting projects from the wrong ends. So here's the logo for a chess engine that's only consists of ideas at the moment!















The photo was taken by my talented wife who is a professional photographer. Please visit her website.

The text is my own creation. I like the simplicity of the logo. Rather silly to have a logo without a chess engine - so let me start coding!

[Edit: Removed the version information from the logo.]