Parallel search in chess

(This is something I wrote down about 3 weeks back and forgot to post ... so here goes nothing !)

If you know alphabeta , you will know that it is 'essentially' a serial algorithm : there is a pretty high dependency among the nodes in the tree. (I mention only alphabeta here , though all variations of it have same problems).

This has resulted in two directions of research for parallel search , two approaches so as to speak of :
* Trying to come up with alternate algorithms which try to 'eliminate' (or reduce) this dependency between nodes : lower the dependency , the more 'parallel' the algo becomes.
* Variations of alphabeta itself so that you can parallelize it better.

Most of my experiments with anything other than pvs (variant of alphabeta) has not been very fruitful : they suffer from a variety of problems (MTD(f) , ABDADA , etc) ... and yet some people do seem to be using them quite well !
So it is a case of YMMV I guess.

Among the various algorithms in the second category , I have always found nothing much in the literature which is really good - so I hacked up a algo which is reminiscent of DTS.
I have an iterative search , with YBW (for deciding on split points) and no concrete subtree ownerships (so the tree 'owner' can move between processes) - (skipping the gory details here ;-) - bug me if you want to know more :-P )

Note , I usually run on an SMP box - never have worked on an MPI box and very rarely on a NUMA box : so I have not considered the implications of a MPI or NUMA problems in my design too much. (Yes yes , I try to make sure that localization of mem is highest , etc - but there could be other 'issues').

The above should be boring stuff for most I guess ? :-)

Anyway , the reason why I am blogging about parallel chess algorithm is :
* I have a dual core proc box at home - was eating into me that I am not using it efficiently enough.
* I was bored out of my wits and needed a new challenge - fixing bugs after the major release is done can be a bit boring after a while :-D

and so ....
* I just completed testing my new parallel search which exhibits very good average speedup of around 1.88+ for 2 procs , with a scaling of 1.98+ ! :-D
The worst case behavior is still around 1.4 or so , also the scaling ramp up is not as fast I would like it to be (takes a few secs to get to 1.9x).

Ofcourse other than the parallel search , rest of this new engine is 'borrowed' from my previous engine - so the gameplay is not really much better (I was testing some wacky eval and moveordering ideas earlier using incremental attacktables) : but damn it gives me a kick to see it fly like this :-)

The way I have designed the search , I am not sure till how many processors it will scale , how NUMA will affect its performance , etc.
I expect it to impact it atleast a bit : no I am not even thinking of clusters or other MPI boxes - all that is in the realm of testing and tuning (I suck at tuning :-( ) , but I would expect it to do quite well indeed upto quite a high number of processors.

So tonight , I relax and enjoy the numbers flashing through my screen - tomorrow I port it to solaris and then ... let us see if I can get a 'relatively free' box at office ;-)

GPL 3

Came across this : http://blogs.sun.com/roller/page/webmink?entry=gpl_v3_released
Interesting read !


By the way, whole license at : http://gplv3.fsf.org/draft

Pure Pwnage

Sascha pointed this to be yesterday - http://www.purepwnage.com/
Absolutely hilarious ... I am currently downloading episodes 8 and 9 , but the ones till now have been way too entertaining !!

Enjoy !

XML Languages

Tim Bray , one of the inventor's of XML , has written two really nice articles on XML Language design : here and here.
The relevence of most of the arguments and points though are not limited to just XML - really interesting read !

Definition of sexy !

Alok just pointed this to me.

Press release here.

Check out the specs people :
41 Giga pixels/sec
96 pixel pipes !
2 Gig graphics RAM !!

What you will need is a quad cpu dual core opteron with this as the grahics card - ah , that will be the life !!
If only I had a house to sell to buy this baby :-(

Gajjar ka halwa

First things first : A very happy and prosperous New year to all !

Now ....

I suck at cooking , and yet I like to eat tasty food :-D
(Note : The definition is hacked such that whatever I cook is tasty ;-) )

Me , Aparup and Shireen were at Koshy's for dinner on 1st Janand Shireen had this craving for 'Gajjar ka halwa'.

Unfortunately , they did not have it.
So we dropped desert plans from there and went 'Gajjar ka halwa' hunting in the restaurants nearby.
The pretty heavy dinner that we just had made us (me and Aparup ?) give up the search pretty fast.

In most normal circumstances (read lazy me) , the matter would end there .... and I did promptly forget all about it as soon as I got home.

But ....

Next night , Aparup IM's me to go over to his place ... and when I get there , voila !

Pity that I was full , else I could have had more :-) (Is dessert served at the end of a meal on purpose ? So that we dont have lots of it ?!)


Shireen did try to give me a technical rundown about how easy/hard it was to make it , but /me content to just gorge on the delicious sweatmeat :-D


Moral of the story :
* Never give up your desires.
And more importantly ,
* Stay close to people who dont give up their's and are willing to share :-)


By the way people , Mr. Noufal Ibrahim is back to blogging :-) Yet another destination for me to spam at !!