Latest improvements (EOY 2013)

In the last few months of 2013, I managed to carve out some time to work on Nakshatra after a pretty long gap. I tried out several things, and among them two particular additions helped in significantly boosting Nakshatra's suicide chess playing strength:

Proof Number Search:

I had known for a long time that nilatac (another suicide chess engine) uses PN search. However,  I had very little idea how the algorithm actually worked and why it is so useful particularly in suicide chess. Digging a bit further, I came across Victor Allis' original PhD thesis (I think) which explains PN search remarkably well. It got me hooked. It was only a matter of time before I came across several variants of this algorithm, including the PN^2 search algorithm which helps somewhat with the memory constraints resulting from the best-first nature of PNS. Follow this link for an excellent explanation of PN^2 search.

I implemented PN and PN^2. For quick searches (such as during a game), PN search is fast enough to produce excellent results, so that's the one Nakshatra is currently running. PN^2 however is going to be useful in researching solutions for certain tough lines or parts of opening book (though I haven't spent much time doing this).

With PNS, Nakshatra can avoid making a lot of really bad blunderous moves in suicide chess (called forced losses), and more importantly find many very deep forced wins (where the opponent made a losing move) extremely quickly! Most of these moves are not usually found by nega-scout owing to the enormous search depth involved, while it is not a problem for PNS because of it's best-first search characteristics.

Late Move Reduction:

This is an enhancement to alpha-beta (negascout) search. I believe I was inspired by this article (which has an excellent illustration of how the algorithm works). The trick is simply to trust more in move ordering than we already do, and reduce the depth of search for later moves (which are likely fail-low nodes), thereby saving time to allow stronger moves to be searched deeper. After a lot of trial and error, I seem to have got the parameters just about right for the engine to be able to search a couple of plies deeper on average, and come up with better moves than it did before (most of the times). Although it is likely that in many positions, it makes somewhat worse moves compared to non-LMR version (owing to losing depth on some good moves that came later), it definitely has increased the overall strength, and that's all that matters to me.

Closing remarks:

I think PNS and LMR together have improved Nakshatra's suicide chess playing strength by about 150-200 points (with PNS responsible for the bigger chunk). I also added a 2 piece EGTB that has been quite helpful in many end games, but it is unlikely to have increased playing strength in any serious way. On FICS, Nakshatra is now up from 2400-2450 range to 2600-2650 range. The other strong active player on FICS, namely stayalive, is still better than Nakshatra but Nakshatra is able to beat stayalive in more matches than it could ever before. My local engine matches where I played Nakshatra against Sjeng and Nilatac (both quite strong players), did show Nakshatra to be a better player, which is pretty cool!

Having a comprehensive opening book like that of Nilatac or Nettogrof's suicidechess.ca could enormously increase Nakshatra's rating. But, unfortunately, I am unlikely to spend any time working on it in the near future.