Important Pic

Was chatting with Neeraj the other day and he sent me this pic (Neeraj in bodega bay)

(For those who dont know - Neeraj is the "bald one" in the pic).

I am putting the following as per By Neeraj's "special request" :

Quote
Hi ladies , if you want to get in touch with me - my Y! id is : "neeraj_yeswant"
END Quote

Hope this is enough Neeraj ? ;)

Ok , "comments" are welcome now !

Multiplayer Gaming

An addiction that has such a huge hold on you that you dont even want to get rid of it !
Be it quake , doom , duke3d , aoe , etc - love them all !
(Hmm maybe I will add bomberman and paddlegame to this ? ;) )
But why is it that multiplayer gaming is so much more popular , more fun than the single player versions ?

Is it that you try to pit your wits against some other human - who "might be" better than you ?
Is it that the bots in the game become repetitive and easy to beat ?
Is it another oppurtunity to meet other people ? (Ya right - I am talking about geeks like me who spend upwards of 12 hours in front of the comp :-) )

Dont know the answers - maybe it is combination of all these and more reasons - but they are indeed great fun !
Speaking of which , not all games are fun in multiplayer mode.
Perfect example of a game that sucks in multiplayer mode as compared to their great single player versions are :
1) Heroes series.
2) Civ 3 PTW (earlier versions dont support multiplayer afaik).

Common thing thing about these are that they are turn based - and so basically you sit and rot while the other dudes battle it out in their turn.
This very soon becomes quiet boring - especially if the game becomes long and involved.
In Civ 3 , the developers have tried and made a creditable effort in minimising these effects - but this cannot be eliminated and so these effects do rear up its ugly head quiet soon.

Compare these with no-brainer trigger happy games like Q3 , unreal ,etc - ah perfect bliss !
These games are almost as though "designed" for multiplayer !

Ok , enough typing time to get back to Quake - err work.

Why I program my chess engine.

Without going into technical details , I will try to list a few of them due to which I still continue this hobby even after nearly 2 years. This is , I think the single longest computer related hobby that I have ever had.
Most other projects would have been either completed or abandoned by now :)



1) Human opposition.

It is extremely satisfying to see your creation battle it out against an IM or GM and win against them.
When there are almost no tactical blunders from either side , the joy is infintely more - since basically , your program has outplayed the human !
Now if it is say tic-tac-toe or some game like that, where you can get till the leaves of the game , or there is not much ambiguity involved in evaluation - it would have been passe : luckily chess is unlike this !
The chess tree is way too huge to be completely traversed in the near future.

The way humans play chess is way too different from how computers play.
Lot of good chess players find it quiet difficult to grasp how computers manage to play good chess inspite of its approach !

I will try to present a basic idea here -

Given a position , how a human typically thinks is :

Find out the sub-set of "good moves" that he can make , then switch sides , find the good responses , keep minimaxing this way.
Now , in most middle games , the number of possible legal moves would be in the order of 40 - 80 moves per position.
It is trivial to see that without such an approach a human will not think deep !
The number of possible position even for a ply depth 2 will be 40 * 40 - and it keeps going exponentially for every additional ply depth you want to search !

Out of these 40 - 60 moves , just based on his "feel" and experience, a good human player is able to eliminate most of the bad or "uninteresting" moves and get a small subset of good moves to look furthur into.
This way , a human (more commonly a serious chess player) player can search relevent variation trees of quiet impressive depths.
The better the human is at playing chess , the better would be the sub-set that he chooses and so , better would be his play.

Another factor is evaluation of a position.
In lot of post-game analysis with IM's and GM's , I get something like this.
They follow a variation and then in the resulting position say "This looks better for white" or "White has more possibilities" or "Advantageous for Black" , etc.
This sort of "feel" for a position is not always based on standard positional and tactical heurestics.

Such a feel for a position - where some side has better possibilities or attacking chances is impressive most of the time -
and very tough , if ever possible , to implement in a program while still making it play competitive chess (that is , reach
sufficient depth so that it does not get killed by tactics).

Now let us come into how a program thinks :
A very basic idea is -
i) find all legal moves at current position
ii) For every legal move , find all possible responses.
iii) Continue the above process until you have reached the required depth.
iv) Evaluate the resulting position ,
v) Use minimax/alphabeta/other variants of these to arrive at the best score , best move and best variation for this depth.
vi) If you have more time , increment depth and repeat process.

This looks terribly inefficient and downright idiotic and wasteful for most humans.
Question like "Why move queen in opening when it is such a "bad" move ? Always develop minors first ?" , etc get asked.
The simple answer to all that is - any move can be good or bad depending on the position.
In all positions queen moves in opening need not be bad - even when minors are not developed - trivial example would be fool's mate !
Hence , without a search , a program cannot decide whether a move is good , bad or neutral ...

There were indeed expiriments based on how humans think , where the program tries only 3 or 4 best moves from given position after static evaluation on the "goodness" of each move and try those out... But they failed pretty badly.
The kind of pattern matching , associations and logical "jumps" that humans can do, are tough if not impossible to codify so that a program can make use of this (hmm , as usual strong ai folks can bash me on this ;) ).

Here I must point out that there have been plus points in this field by studying how humans think :
One example is "reductions" / "pruning" and "extensions"

Reductions and pruning work on principle that if the move is not good enough , or threatening enough and if it cant help the side that is to move to equalise or gain an advantage against the opponent side , then reduce the search depth for this subtree.

As can be expected , this is a very dangerous - though IF done right , potentially very lucrative area of research as it can bring down the size of the serch tree.
Some basic ideas have evolved , but I do not rely on any of these - my expiriments have concluded that they destroy the "sanctity" of my search tree too much for me incorporate them in my search.
I keep looking out , thinking and researching more on this field for potentially good ideas - but till now , have not found anything very convincing (other than NULL move based pruning - this I will discuss this some other time , or you can follow this up in some chess programming site).

Extensions are the reverse idea - IF the current move is threatening , then extend the search subtree so that you will try to find out if the opponent has any refutation for this , or if something in the search horizon is hiding anything from us ...
Typical examples for this type of threatening moves which most programs extend are checks , recaptures , passed pawn pushes to seventh rank , etc.
This has the potential to blow up your search tree and ruin your branching factor.
Hence you have to be careful while using these , but most amateurs use this with without much care ....
In earlier version of my program , I had done "selective extensions" where I extend only actually threatening moves , and not moves that may appear as threatening - but are not.
Examples : Most checks can be stupid - so extending these are a very bad idea - like sacing your bishop to give a check , etc.

I keep interacting with strong human players, try to find out how they think , why they think something is good/bad/neutral and try to incorporate that into the program.
Some of the ideas that come out of these interactions are very very interesting and revealing !



2) Incompleteness

There is nothing like "perfect search" , "perfect evaluation" , "perfect moveordering" , etc
Hence , there is always an incompleteness in any approach - due to which , there is _always_ scope for improvement !

Due to the way the tree searches like alpha beta work , the minimal tree is searched when you always search the best move first.
BUT , If you know the best move for a given position - then why search !
So what we try is , various move ordering heurestics (the more number of heurestics or more complex heurestics - the more is the associated speed penality) , so that the most likely best move gets searched first.

This is a very dodgy field , but if you get it right , the gains are exponential !
There is a delicate trade off between linear time that you "waste" in trying to "order" the moves and exponential time game that you get by a reduced tree to traverse.
A very interesting field - where I have been thinking and researching a lot !

Evaluation is another vast field - how do you make the perfect assesment of a position (well near-perfect :) ).
Since there are various factors involved - positional and tactical , and each of which interacts with the other in subtle and not so subtle ways depending on the uniqueness of a position , we can only come up with a set of heurestics based on your expiriments.
Which are the set of herestics that we pick , what weightage do we give for each , what patterns to have in the evaluation , what are the interactions between various heurestics and patterns , etc , etc - a very involved field with lots of traps , pitfalls and possible brilliancies !

One of the best evals I have seen are in Diep and HIARCS - very good programs with some pretty awesome evaluations.


3) Fellow programmers

Barring a few , most of the fellow amateur and professional chess programmers I have met are very open to new ideas and are always willing to discuss their ideas (unless it is going to directly give out what they consider vital secrets :) ).
This open atmosphere helps a newbie quickly understand and assimilate the basic concepts and rise to try out the more advanced approaches.
Without these great guys , (NOTE : I have not met/heard of any serious female chess programmer and so this is not an MCP statement ;) ) , it would not have been half as fun !

If you want to get in touch with them , follow the links on the side to CCC or the Winboard forum , where most of them hangout and post.



4) Parallel Search

This is the most recent interest in this field for me.
Making an essentially serial algorithm like alpha beta (and its variants) parallel.
The amount difficulties involved are non-trivial , which is possibly one of the reasons why there are so few of them around !
I have been quiet sucessful in this (well , my last program folded up in the end due to impossibility in maintaining a 3 + MB source tree :( ) thanks to help , suggestions and testing help from a lot of people.
But this field , still has lot of scope for improvement and is one high performance computing field which will always attract me and possibly other likeminded people time and again !
Efficient and time critical usage of multi processor systems with minimum resource contention to maximise the search efficiency is indeed a challenge !


5) Tournaments , testers and users

It would not be fair to not mention this part !

Tournaments , especially author's only tournaments , where we get to meet and interact with other fellow programmers is a veritable treat !
The amount of ideas discussed , the amount of fun that is had , has to be expierenced to be believed !

I dont think there is a such a big body of testers , amateur testers and enthusiasts who do free testing of various chess programs for the sole purpose of helping the programmer improve his creation in any other field !
These guys are great , and even though I have not yet released my program till now , the feedback that I keep reading about their analysis , comments , etc about other programs is one of the main reasons why I want to make my program available to them.
Their interest and dedication to this field is truely amazing and is , I think, one of the main reasons why this field has progressed so much.

Users , are the reason why there is so much commercial interest in this field ;)
They give valuable feedback and are constant source of motivation for the commercials to improve theor program ($$$ :) )
But jokes apart , even for amateurs chess program authors , the user comments are very valuable "non-geeky" source of ideas and inspirations.
Hope this interest continues for a much longer period - I have had lots of fun , met some wonderful people and learned a lot and I hope more people will join this challenging and interesting field.

Good night ...

Site is better !

Finally got the comments, some links , etc up and running.
Thanks much to Guru for these !
http://www.haloscan.com is providing the required links and support for comments section ... will work on the rest of the site later.

Weekend at Benniganahalli

While chatting with Noufal , decided on a spur to visit and stay over at their place for the weekend.
Got some time to introspect , chat and catch up with old college memories , rag eachother senseless and have a ball of a time !
Some pretty important decisions were taken during the course of this weekend and it was quiet a "learning"expierence :



1) Make my chess program freely available as fast as possible - even the (S)MP version.

I had already decided on making the single proc version freely available : only binary.
It would be a winboard/xboard compatible engine - later will add UCI support also ...


No , the source wont be available - reasons are many and varied , most important ones being :

a) Way too may clones available - look at the number of crafty clones that keep springing up !
b) Ideas - yes , I will expose - absolutely no need to make the source available.

(Note : the below "justification" is primarily for my friends who keep pestering me to open up the code ;) )

* If someone cant implement the ideas in their own way - they are are not fit to be looking at chess engine sources :-)
There are lot of GOOD opensource training programs available - though this was not an option for me when I started two years back due to lack of knowledge of their existance :(

* I do this as a hobby and as a means of relaxation - dont want some idiot making a clone out of it and then people asking to figure out if some XYZ is a clone of my program - if you think this does not happen , sorry - it happens a bit way too much for my comfort : ask Dr. Bob Hyatt of Alabama University, and many others in this field - many many stories abound of clones.
Yes - I have learned a lot from the community - and yes , I will give back to the community in my own way - as ideas.

* I dont want to hear bull about giving back to community , etc , etc , etc arguments for opening up the code.
Have heard it all , and dont find it very convincing ... If this is a one of a kind project (part of it maybe) , and it is critical to open it up , their would have been sufficient justification - but right now , lot of open source programs exist already.

* Anyway I doubt anyone will be interested in the engine code _other_ than for the (S)MP search part :)
Previous version had a pretty awesome scaling of 1.96 for duals , and 3.9 for a quad ! (Comparison - crafty gets 1 + 0.7 *(n - 1) where n is number of proc - this is according to Prof. Bob Hyatt at CCC ).
And this , I dont want to open up - for reasons including that this is a very good YBW full dynamic tree splitting implementation that I know of (note : I am not being arrogant here) expect for a very few that I personally know of (like Diep by Vincent Diepeveen for instance).



2) Never, never and I mean NEVER ask an unknown girl out on a date directly.

Well , this is not my direct expierence , another friends - but since I saw it all happen , better learn from it :)
Hmm , better keep this under wraps unless I want to piss him off ;) !



3) Started reading Penrose's "The Emperor's New Mind"

Yes , yes , I am loser not to have done much much earlier !
But since the book was lying around and I had time to kill , I decided to give it a read - and man did I screw up !
Took me 3 + hours to finish the preface - it was simply TOO Thought provoking !
(latest edition - with new preface , etc ...)

Took me some time to digest some of the stuff.
(I dont really agree with Turing's idea of how to identify intelligence , but that is another discussion.)

And then went on to first chapter - and got stuck there for a long time.
No no , there was nothing tough about it much - comp AI - a subject that I like a lot (though never read any theoretical before about it ) ... but it was Grey Walters's tortoise that did me in.

Interesting concept of trying to make a scale of pain-pleasure and decide on the response based on that.
If I had left it at that , it would have been ok - problem is this irritating brain of mine...
Got me thinking late into the night - and just could not sleep with all the ideas jumping around in my head.

Dunno whether this has been done / attempted before and possibly already rejected/finished studying about !

Basic I had was this :
Find out the population distribution and characterstics of a group of "entities" (I am modelling these entities around primitive humans here) : based on a variety of factors - not a simplistic view as taken by "Game of Life".
Model it around something similar to evolution - borrow some concepts from GA (rare mutations ,etc) and try to find out the resulting population characterstics after an arbitrary large number of "generations" have passed by.

Example :

Suppose , we have the following "environment variables"
E1) Food distribution (Like power source in the tortoise) - variety , etc could be added later ...
E2) Danger - which will directly effect say , survival rate and "toughness" of the entity.
E3) Desirability - climate , etc , etc.

Entity characterstics :
C1) Surrounding population influence - similar to the Game of Life ... only a bit more complex.
C2) Reproduction - age range when it is capable of it , how many progenies , sex of the entity (assuming bi-sexual) , etc.
C3) Survival abilities - toughness , strength , etc , etc.
C4) Temperment - lazy (flock around food sources and vegetate :) ) , active : as in interact with others , take danger , etc.
C5) Effects of age - strength , toughness ,etc reduction with age , etc.

Could come up with more , but restricting to these for now.
Now as you would have guessed - E* and C* are linked :
For example , E2 and C3 & C4 are linked - more toughness C3 , better chance of surviving danger D2 and more the entiry can survive danger - so does its toughness increase.
Similarly , as age increases C5 - entities ability to survive decreases , etc , etc , etc.

Have not yet completed all the interconnects in this idea - and not yet completely ironed out the idea.
For now , the simulation would be like game of life - turn based and a generation would be like 60 turns or so - typical age of an "entity" in this case.

What I want to see is , for various types of these characterstics , and starting for various types of entity distributions , with various distributions of entity characterstics , how the resulting population characterstics would develop out as.
A few simiplifying and maybe useful restriction and boundry conditions that could be applied would be based on our understanding of how the humans evolved from apes to manlike beings.
Start from that age , with that kind of environmental conditions and then try to find out how this system behaves.
When I initially thought about it , I assumed that it would reach steady state (without mutation from above for example) , but the more I analysed this - the more I was conviced that this would most probably be a very very dynamic system - dont ask me why/how - I can just feel it.
When I am done running a few rounds of this , I can explain better.
Put this idea to Noufal , and after a while , even he was hooked - now , both of us cannot be wrong together (I hope!) , so we are going to pursue this more .....



4) Why most good cooks are males.
Catching heading - but just to show my appreciation to an amazing dish of "Kadai Paneer" made by my friends - very very tasty and mouth waterng stuff - it was too good for their first try !(Hope they did not lie to me on this ;) )
Manoj , Ajay and Noufal - cooks of the future :-)

Ok , tired and sleepy now ....
Comments , brickbats now :)