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!