An Update

Nakshatra codebase is now made public on github - http://github.com/goutham/nakshatra.

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.

Nakshatra is now Multi-variant

For more than a year, Nakshatra has been more or less actively playing rated suicide chess on FICS and it has constantly improved in strength through versions 0.0 to 0.5. This is the rating chart for the year 2010.

It was quite a remarkable journey through the first half of 2010 - when the rating improvement was really big. However, it plateaued out towards the end of the year and the trend has continued into 2011 as well as you can see from the graph below:

Sometimes, its quite disappointing to see that there hasn't really been much rating improvement over the last one year or so... My goal was to get it into 2700+ league but I have not even crossed 2400 yet. Some milestones such as an improved opening book, mobility factor experiments and an integrated EGTB have not been accomplished though I have been blabbering about it since forever... Unfortunately, it looks like I will not be able to spend much time on it in the forseeable future :-( (may be its time to open source and attract some developers). And of course, "the law of diminishing returns" has started biting in (a lot more effort is now required for small improvements).

However, one really awesome thing that happened today - and the reason I actually started writing this post - is that Nakshatra has finally gone multi-variant! Ok... it has had the standard chess code for a while but I never dared to enable it on FICS for the fear of being bashed up black and blue (what will it do to Nakshatra's confidence? ;-) ). But after finally ironing out some nasty little bugs yesterday night, I finally got around to getting it play some unrated blitz matches of 5 minutes+. Astonishingly enough, it won a lot of these matches and I was pleasantly surprised. With curiosity surging, I had to then enable rated blitz matches and it went on to win 2 out of 4 matches it played! (one win against a 1500+ rated human player made my day!).

Now the real deal is that Nakshatra's standard chess capability is quite dismal - which is why I was quite surprised by the wins. Hardly any work has been done to improve the strength of standard play (its more like pre-0.0 suicide code). There is hardly any opening book. Having a rather large opening book is quite important in normal chess in my opinion. And the evaluation logic is so crappy that I am ashamed of it. But it still plays legal chess and at times, when you are not looking, it gets you by the balls...!

New things to do

Been a long time since I worked on Nakshatra, thanks to the Masters program I enrolled in which kept me busy for a few months now.

Now that it is holidays, I plan to do a few things:

1. Tune evaluation parameters.
2. Enable EGTB in the engine.

Before I left, several months ago, I was experimenting with mobility factor changes and left it inconclusively. Time to go ahead and finish it off. EGTB creation code is ready for a long time now. Time to write code to integrate it with the engine.

An update on current status

Nakshatra has been doing well on FICS. The current version is v0.4. It has few bug fixes and minor improvements over v0.3, though no measurable improvement in playing strength. v0.4 has been on and off playing on FICS for the past 3-4 months and its rating is hovering around 2300.

Nakshatra's finger:

	rating	RD	win	loss	draw	total	best
Suicide	2307	31.7	2992	912	117	4021	2376 (24-May-2010)

Noticeably, nakshatra has crossed 4000 games with nearly 75% wins!

v0.3 crosses 2300!

Nakshatra achieved yet another milestone by crossing 2300 rating points on FICS today! v0.3 had some major improvements over v0.2, the most important ones being the replacement of AlphaBeta with NegaScout algorithm for search, revamp of transposition table for better utilization of available space and some nasty tree pruning bug fixes. Cumulatively, these improvements led to an average of 100+ rating points improvement. The best part is that Nak managed to defeat two of the best active suicide engines on FICS - stayalive (2500+) and Plnik (2400+) in at least a couple of matches!

My goal now is to make Nakshatra the strongest suicide engine on FICS. Currently it is at #3 among the active suicide engines and probably much lower ranked if we take into consideration the inactive ones. Going further, Nakshatra will definitely require a bigger opening book (as I found that despite Nak's strength, it does play some losing opening lines occasionally!) and possibly an EGTB. Even the evaluation heuristics are in dire need of my attention as the one in v0.3 is almost the same as the one in v0.0! But testing changes in evaluation is rather tedious! I have also been experimenting with some new algorithms like forced line search; and though I am excited about this, I am not yet convinced that it could lead to a measurable improvement in the strength of the engine.

Nakshatra crosses 2200 briefly

Yesterday, v0.2 crossed 2200 briefly. It achieved a best of 2216 before it started plummeting down, thanks to many humans who managed to drag it into end games where it is known to perform poorly. At the moment, it is at 2120.