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 :)