FEN Strings

I've made some progress yesterday.  I have an elementary bitboard representation working and I can set and get the chess board using a FEN string.  A FEN String essentially represents the current board setup in a convenient notation.  Here is an example after white's initial e4:

rnbqkbnr/pppppppp/8/8/4P3/8/PPPP1PPP/RNBQKBNR b KQkq e3 0 1

Each string in between the slashes represents a rank in the chessboard, starting from the 8th rank. Lower case is black, upper case is white. Numbers represents empty squares between pieces.  For example '4P3' represents four empty squares, followed by a pawn, followed by three more empty squares, totaling eight.  The '/8/' therefore means (you've guessed it!) a complete empty rank.

The remaining string 'b KQkq e3 0 1' represents the side to move, the castling rights (e.g. 'K' means white can caste king-side, 'q' that black can caste queen-side, etc.), en-passant square and the move counters.  The en-passant square is the square directly behind the pawn that made the two-square move.  In this case, white move e4, which means that e3 is the en-passant square.  Black can capture the pawn if he had a pawn on either d4 or f4.  Regardless, the en-passant square is always indicated, whether it can be taken or not.  The move counts are the half-moves since a last capture or pawn move (for the 50-move draw rule), followed by the number of full moves.

I found myself constantly checking the validity of the FEN string during the parsing stage, which started to look really ugly.  So I turned to one of my best friends... regular expressions!

Regular expressions can get tricky...quickly, but is incredibly powerful to recognise patterns in strings.  Here is a short extract from Vicki that shows how a FEN string can be checked:

 
The 'verifyRank()' method simply verifies that the a rank adds up to eight. Doing that in a regular expression may get very hairy (actually I don't think it can be done). The code also verifies that there are 2 kings at least.  Of course, that can easily be done by the regular expression, but the string will get rather long. 

Move generation

The first step is move generation.  I have committed myself to Java and bitboards for Vicki 2.0.  The advantage of Java is that it is much more platform independent than C... well, mostly.  Bitboards is also a good move, given that it is theoretically faster than the postbox method and besides, it is something interesting to learn.

So the list of tasks for the next few days is as follows:

1.	Set up data structures	Done
2.	Set and get board (FEN-based)	Done
3.	Simple textual display	Done
4.	Move generation for non-sliders (pawns, knights and kings)	In progress...
5.	Move generation for sliders (bishops, rooks and queens)	Pending
6.	Make move	Pending
7.	Unmake move	Pending
8.	Perft testing	Pending

For now, the representation simply contains positions for each of the pieces.  The derived pieces will be added later.

Something stirring in the shadows...

I have only fond memories of Vicki...  The website is still up, but Vicki has not used a clock cycle in years.  The current release is several years old... written in C.

I am currently (as in already busy) rewriting Vicki.  Vicki 2.0 is a complete rewrite of the engine, reusing nothing but the name.

I am not looking at any existing computer chess code and I am avoiding any heavy bias to single papers and single units of theory - trying my own. The research in computer chess is all but exhausted.  So all that is left is to redesign the wheel for the fun of it and looking at existing code will spoil it for me... Vicki is not meant to "extend" the envelope of computer chess.  It's my Everest and South Pole.  

Vicki 2.0 is being written in Java.  Java's speed is comparable to C and C++ (in some people's opinions!) Also, I want something which is easily transferable between Linux and Windows platforms.  C does not really cut it for me any more.

Board representation will the elusive bitboard (or bitmap) technique.  It cannot be that hard... (famous last words!) and I cannot ignore it's advantages any longer.

I hope to post regularly and have something on the main website up and running soon.

Ping...

I've not posted for over a year.  Although I have not had much time to work in Vicki, the engine is definitely not dead.

I will start with a rewrite in the foreseeable future.  I am not yet sure which direction I'd like to take with Vicki - but I am toying with the following:

1. Possibly rewriting the engine in Java.  The speed difference between Java and C is negligible, when the number of objects used are limited.  Java also has better testing frameworks (well, from what I could find) and is platform independent.  I can also throw in my own GUI, if I like.
2. General improvement on absolutely everything from move generation write through to opening/ending databases.
3. Multi-threaded searching for multi-core systems.  I have access to some serious hardware at work (i.e. 64Gb RAM with 8 quad core processors).  Would be interesting to use of of those for a tournament!
4. I would like to finally get learning right!
5. Full-time up server playing on servers.

Watch this space!

Delays

Seems like I'm going to need a few more days. I've manged to split the move generation so that I now incrementally generate moves and search them (as appose to generate all the moves at once). This seems to be paying off. However, I'm having some transposition table problems again!

I'm hoping for end January.

Resurrected? ...or just out of the coma?

I guess life happened while I was busy working on my chess engine. I few months ago, I dumped the entire engine and started fresh. Then after a month or so, I dumped that idea and went back to the original codebase. I started integrating the sections of code that I rewrote and improved. To be frank, large sections of code in current release of Vicki is a terrible mess and these needed to be rewritten. I'm almost done with that.

I have already rewritten the move generation, which resulted in a speed increase of around 10%. I’ve also changed the representation of the move (I use a 32 bit integer for this) so that a full 8 bits are available for move ordering (this use to be 6). This change will greatly enhance the move ordering capabilities of Vicki.

I am now working on the actual search function and the transposition table. Apart from fixing a nasty bug with the transposition table (it returns a mate score, but just chases the king around with trivial end game positions), I also need to rethink all the pruning and speed-up techniques individually. I threw all these together without giving any much thought. I paid the price.

I'm also planning pondering, opening book learning and better interface support.

The next release is scheduled for the 4th of January 2010.

Vicki is back... and smelling blood!

Frustration

Even though I haven't posted in a while - Vicki is not dead. I'm having huge issues with Vicki at the moment which is taking up a great deal of time. The biggest problem at the moment is the transposition tables that are not working as it should. Every time I implement it, the engine plays weaker...substantially weaker. This can only be as the result of a bug. I hope to have this sorted out in the next week or so...

The transposition table is a very important component and I want that working first, before spending any more time with move ordering and evaluation as these elements share some common ground