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!