A New year’s post!

Kumbakarna

Kumbakarna

Happy new year all 🙂 Belated wishes and wishes still even if somebody moved your new year to a different date 😛 On Vishu day, (apparently) it is tradition to pick a random chapter in the Ramayana early in the morning, and whatever is read is said to have some impact on the reader’s life in the coming year. I tried it yesterday and the chapter I picked was about Vibheeshana’s confrontation with Ravana. It was quite serendipitous as the event has constantly been a source of confusion to me. To elaborate …..,

Vibheeshana

Vibheeshana

Two of Ravana’s brother are source of particular interest – Kumbakarna and Vibheeshana. Both, at some point advise Ravana against a war with Rama. However Vibheeshana is shouted at for this advise and  leaves Lanka to join forces with Rama and betrays many of Lanka’s secrets to Rama. He is later anointed King of Lanka after Ravana’s death. Kumbakarna makes the same advice but follows it up by comforting Ravana speaking of an assured victory despite knowing fully well what was in store for him. Kumbakarna is eventually killed in battle.

Kumbakarna’s actions are all too familiar. Actions like his are replicated in the Mahabharatha and is generally seen as the nobler of the two courses. Vibheeshana is often criticized for betraying his King and is commonly seen as an usurper and traitor. So then what is the confusion? Vibheeshana is (at the end of the epic) ordered by Lord Vishnu in the original form to guide people towards Dharma. He also becomes an immortal joining the ranks of Hanuman, Parasurama and Mahabali. What the _?

For those of us who are used to seeing the epics in black and white (no, not literally) – and thanks to Ramanand Sagar for this – this situation is confusing. What is correct here? Too often in life we are faced with similar situations. When and why is it ever right to be a snitch!! And the epics seem to be of no help here – both courses are shown as good and not against Dharma. All along, Valmiki continually praises the qualities of Vibheeshana – he is at no point portrayed as greedy or selfish. Instead, the descriptions are

“Vibheeshana spoke to powerful Ravana the words convinced of reason and which were very much beneficial. He, who could discriminate between good and evil things in the world, having sought the favour from his eldest (half-) brother by means of soothing words arranged in an order, spoke in consonance with place, time and purpose.”

I am not still fully clear why this action is considered correct. I am not at that level yet. But the original author clearly seems to think so. Feel free to read the original text and make sense of it. If you come by interesting commentaries, I would love to be notified.

The intention that drives your action is perhaps more important than the action itself. From a different perspective, this episode reinforces the idea that there is no distinct line between black and white in such situations.

I want to make a special note of this because it is very easy to get lost in the strongly polar natures of the main characters in the epics. The epics would seem to be of no practical use as situations or characters as seen in them would never happen in real life. In fact however, there is a large trove of such useful tips and indicators buried within them. Many answers are here. So take a closer look.

References and Further reading:

Note: Nope, this is no longer going to be an exclusively tech blog. There is enough boring content on the net already. Time for some arbit content. Sure there’s enough of that too, but the world could always use more 😛
Advertisements

On Tigers, diffusion and chaos

Tiger

RT @sanchan89 Always good to know that my mojo is still intact after 4 years 🙂 Take a look http://bit.ly/bGv5su

So, after quite a while, I tried sketching again. And it came out pretty neat, I suppose. But then, I want this to be a tech blog, right?

We humans, have a somewhat dull skin[1]. It is completely bereft of any fur[2] and any pattern to be had on are to be painfully tattooed. Look, on the other hand , at the pervasive presence of spacial patterns on animal coats and flora. Most commonly seen in plants are the rosette patterns, and self replicating branching systems. Mammals and fishes are so much richer – their fur coats come with stripes, spots, rosettes, bands, blocks, combination of these  and in the case of some sea shells – Serpenski triangle! Even in animal behavior, there is so much elegance – if you have not seen the movements of large schools of fish or birds in flight, you have a serious problem and you should consult a psychotherapist. Even the inanimate desert sands are beautifully patterned with near parallel curves.

Spatial patterns collage

Spacial patterns collage

It makes us think, doesn’t it? How are these patterns formed?

If every skin cell were to take on either black or white color with a uniformly random probability, then a zebra would look like white noise. Try imagining one with a coat like that. No probabilistic distribution is ever going to generate patterns as fantastic as those on every tiger. Does every cell, then, have a global spacial view of itself? Is it possible that a single cell knows that it is a part of the stripe across the head of the tiger, and therefore, it should take on a black pigmentation? That seems like something phenomenally complex for a single living cell to know.

Related problems in developmental biology are cell differentiation, and Morphogenesis. Every cell in an embryo is the same. Embryos are homogenous; and yet without a single central controller, cells in different areas of the embryo develop into different parts of the body. Some develop into the the heart and lungs and others into brain and legs.

The first explanation for this phenomenon was provided by the British Mathematician, code breaker, logician, computer scientist ( and during the later days of his life, a chemist )  Alan Turing in his paper titled ‘The Chemical basis of Morphogenesis” in 1951.  ( This paper has its own wiki page ) The paper described mechanisms; borrowing heavily from concepts of self-organisation, well known in physics; by which non-uniformity may arise from uniform homogeneous states, and outlined the reaction-diffusion theory of morphogenesis. Reaction–diffusion systems are mathematical models that describe how the concentration of one or more substances distributed in space changes under the influence of two processes: local chemical reactions in which the substances are converted into each other, and diffusion which causes the substances to spread out in space.

Independently, around the same time a Russian biophysicist Boris Belousov discovered a reaction-diffusion system, now called the Belousov-Zhabotinsky reaction. Where Turing had proposed mathematical models, here was already a demonstration of the self-organizing tendencies of the non linear systems which he had proposed. Here’s a video of a BZ cocktail evolving

From a uniformly homogeneous solution – spirals, spots and expanding rings are formed. And no two instances of the same experiment will get you the exact same results. The equations that govern these reactions are so expressive that you can actually come up with results that show stripes and hexagons! Try it out yourself in this applet.

These two works are considered by some as the founding work on chaos theory. In a nutshell, Chaos theory deals with highly nonlinear and usually self looped systems that despite being fully deterministic, are subject to abrupt and seemingly random change. It is clear in this case –  In spite of explicitly and deterministically defined rules, the reaction-diffusion yields a uniquely different result every time. The source of all this chaos is, well…, in the source itself. The non-linearity of the system greatly magnifies even immeasurably small changes in the initial state. So, the next time you round up a value from 0.506127 to 0.506, be warned! As a sidenote, the phrase “Does the Flap of a Butterfly’s Wings in Brazil Set Off a Tornado in Texas?“, is not a misunderstanding of chaos theory. It is in fact the title of the talk presented by Edward Lorenz at AAAS, 1972 on chaos theory. The title was the result of inferences from a run of the simulation he had built, when he changed one of the values of atmospheric conditions as stated above.

If you are interested in learning more about Chaos theory, there is a fantastic one hour program on BBC. No, it does not have equations ( well, maybe just one )

  1. Well, thats not entirely true! We have fingerprints. And they are beautiful and unique, but not colorful or macro. Guess that still qualifies as dull.
  2. This is interesting because, man is the only mammal; excluding those that are aquatic, that has no fur, check out the February 2010 edition of Scientific American

Further reading

  • Stumble this here. Follow me on twitter @sanchan89.
  • If you find my posts interesting, you can follow me via RSS here.
  • Some of my shared items are here, in case you find it interesting.

Genetic Algorithms.., A Primer

It is Charles Darwin’s 200th birthday. So I guess there must be loads of posts on GA, strewn across the Internet. Genetic Algorithms are special to me because they are the prime reason why I am doing whatever it is that I am doing.

This post is a light intro to Genetic Algorithms, sans its terms. Genetic Algorithms are delightfully simple. GA is an approximation algorithm, that is, they are used in situations where either the optimal solution is unnecessary or the complexity of the problem does not permit it. Sometimes, the Genetic Algorithm may produce the most optimal result also. Since examples are the best way to learn an algorithm, here’s the example problem we are to solve.

Balancing moments

Balancing moments

Given to you is a configuration of balances as shown in the figure. The problem is to balance the configuration by adding weights on either side. You are provided with 10 weights measuring 1,2,3……10 kg each. Each weight is to be used exactly once. Thanks to GreatBG for this puzzle. His puzzles are always most entertaining. This can roughly be equated to the traveling salesperson problem. In the problem, the salesperson is to visit all cities (and comeback ), in such a sequence so as to minimize the total distance covered. The most naive solution is to try all possible sequences and see which one gives the minimum cost. For a map of n cities, that comes to n! combinations. A similar approach would work in our case also, but then, when the map or the number of weights is larger, the technique, takes so much more time. A more professional approach would be ruffle up your knowledge of elementary physics and reduce the problem to a set of linear equations and then solve them. Naaa.

Genetic Algorithms

My code, in C++, is here. Here’s the pseudo-code, sourced from wikipedia

  1. Choose initial population
  2. Evaluate the fitness of each individual in the population
  3. Repeat until termination: (time limit or sufficient fitness achieved)
    1. Select best-ranking individuals to reproduce
    2. Breed new generation through crossover and/or mutation (genetic operations) and give birth to offspring
    3. Evaluate the individual fitnesses of the offspring
    4. Replace worst ranked part of population with offspring

Initializing the Population

The algorithm maintains a set of solutions. Not optimal solutions, just solutions. For example, in the case of the TSP, it may be a set of random ordering of the cities. In our problem, a set of random configuration of weights. In the program, I maintain the configuration as a string, where the weight alloted to each slot is represented by a character, with ‘A’ being 1, ‘B’ being 2 and so on. The weights are added bottom to top and left to right. One point to be noted here is that all solutions in the set must stick to the constraints of the problem. No city must be re-visited, no weight can be added twice.

Evaluating the Population

This is the key part of the algorithm. Once a way is found to evaluate each member of the ‘population’, the problem is half complete already. In our case, the “fitness” will be based on the resultant moment in the system. Therefore, best solution will have 0 fitness, the resultant moment in the system would be zero.

Until the required precision is obtained, or a maximum limit on the number of iterations is reached, we continue by doing the following opertions.

Crossover

This is where we actually begin to understand why it is called Genetic Algorithms in the first place. According to Darwin’s thery of Natural Selection, the best members of the population mate to produce better offsprings. Similarly, in our algorithms, the best solutions found so far mate with each other to (hopefully) produce a better solution. In code, this translates as the merging of substrings from different members, chosen from among the best solutions found so far. Point to be noted is that if done improperly, this could result in an offspring, that is not even a valid member of the population. It might violate the problems’ constraints. In TSP, and in this case, the same city/weight might get listed again, which cannot be allowed. So we use a special crossover method called, Partially Matched Crossover(PMX in code) which is beyond the scope of a primer.

Mutation

Some members of the population are randomly chosen to be mutated. Mutation is a process by which the offsprings get a trait that is inherited neither from the father nor the mother.While translating into code, this simply means swapping two characters within the string. You can choose more complex mutation techniques if desired. Again, the problem constraints must be satisfied. Mutation is required mainly to increase the variety of solutions in the population. Variety is very important.

Natural Selection and Elitism

Once these operations are done on the parents, a new generation of solutions are born. To make sure that the best solution in this generation is atleast as good as the best one in the previous generation, we introduce “elitism”. Normally, all the individuals in the previous generation are replaced by the members from the newer generation. But by having a non zero elitism value, a small portion of the best solutions from the previous generation survive on in the next generation.

Going by the paradigm of survival of the fittest, we now select the best solutions from the both the generations and these form the actual next generation. (My code is slightly varied. It does not use natural selection, the members of the younger generation simply replace all but the elite members of the elder population)

Local Maxima

Genetic Algorithms suffer from the problem that it might converge to a non-optimal solution. Consider that we are looking for the solution that is at the top of a mountain. It is possible that the population end up on an elevated hill, far away form the mountain. This is possible if the various values are not tuned properly. The algorithm will not get out of this situation by itself. the best way to go in this kind of a scenario is to simply start again.

People, Blogs, Conferences and Applications

Game AI Development Event at Kurukshetra 09

College of Engineering, Guindy is organizing a game AI development event this time at  Kurukshetra, the annual International Techno-Management festival.

Kurukshetra 09

Kurukshetra 09

We wanted the event to reflect the current trends in the Game AI development industry. It is left to the participants to be the judge of to what extent the main goal is accomplished. The trends seem to be

  • Player specific content
  • A move away from hard-coded-rules based opponents.

We chose Lunar Lander to be the test game for both problem statements. Why? Lunar Lander was one of the earliest games to use Vector Graphics. But that’s not the reason why. Lunar Lander is simple, to code and to play. And.., it seemed to offer scope for hacking both problem statements. And now to the problem statements.

The First problem statement is a challenge to create a player that plays the Lunar Lander. You could try a rule based approach and try coding it. And you may succeed too. But I’ll bet the easier way out is to make your player learn how to handle the Lander. There are many situations where a rule based approach would fail. Consider the case of a car racing game, a rule based approach may satisfy the initial requirements of the game. Your racer may successfully out-race the human player, but it wouldn’t do well on tracks you, as its programmer would not have seen.  Because your AI doesn’t know how to ‘drive’. Well, that’s the motivation for this problem statement.

The second problem statement is with regards to content creation. Simple games such as Lunar Lander, I think deserve to engage the player for longer than 3 levels. The content of the game is very simple. It involves very little graphics. Is it possible to use modern / not-so-modern techniques to generate an infinite set of levels?? Theoretically, yes. Further, would these levels, ‘engage’ the player as much as hand-crafted levels would? It is definitely worth a try.

Well, if you are a Game AI developer PRO, and all this seems, well, ‘childish’ to you,  or in case you disagree with what we have identified as the current trend in the industry, try the third problem statement. If you have any innovative ideas on game AI, an implementation of your concept is most welcome. Although, we are not intending to accept any text-book based search algorithms. Even slightly modified but better versions are accepted.

This is the link to the event’s page. Please go through the problem statements again. This is the first time we are attempting such an event. Your comments and suggestions are welcomed. They would be most invaluable to making this a more successful event in the next editions of Kurukshetra. Have fun, Merry Christmas and Happy New Year!!!

A new kind of a Game

It doesn’t look visually enticing, but I am pretty sure its darn good. No, I have not played the game yet.

NERO

Now, I wasn’t expecting to write a post on a game, any time soon. Not even on DotA. But this is just too good a game for me to resist. I have been quite intrigued by the concept of Evolutionary Computation. One lazy Sunday, I started looking for more stuff on Evolutionary Computation. I found a lot. Particularly, a post-doctoral researcher’s blog. Julian Togelius. He’s published a paper on solving Sudoku using Genetic Algorithms. Serious stuff that! One of his other papers have been judged as one of the top ten AI game innovations of the year. This dude was one of the organisers of a Simulated Car Racing Championship atWCCI 2008. It seems there are not a lot of games available that actually use the latest Learning Techniques.

It was very funny in the beginning when I looked at the games’ graphics( WCCI ). Not a ‘Need for Speed’ then. On further reading, I found more on the rules of the game. From a programmer’s stand point, I thought, not very easy to program a controller. All the various cases. How could it adapt?? Perhaps learn?? Neural Networks then?? Neural Networks are to put it very very simple terms, like a brain. ( Please note that this is a gross over-estimation, it resembles the brain only in that it can learn new stuff. It is not even close to the functioning of a brain ). Perhaps neural networks would have been the answer if the same question had been put forth a few years ago. Today, ANNs alone will not suffice!!

Genetic Algorithms are now used to train Neural Networks. OK. Imagine you are given the job of teaching something to someone. If you couple GA with ANN, it’d something like, you just have to tell the person, how well he has learnt the subject, and he’ll keep improving all by himself. ( Of course, this is another gross over-estimation. If this is very non-technical please refer to one of the links given in the side )

It just got more interesting after that. I learnt that one of the Car controllers was evolved using rtNEAT( real time NeuroEvolving Augmenting Technologies ) developed by Kenneth O Stanley at University of Texas at Austin. NEAT not only evolves the best neural network of a given structure, it also evolves the best structure for the purpose. Fantastic stuff. As I kept reading, link after link. I get here. The page gives a detail overview of how NERO is played and how it is being developed. Please do read it. Its an interesting read. You’ll start wondering what kind of games will be the next big trend.

I have added on my links lists some of the more interesting blogs I have found during my research. Anyone interested in AI, please do have a look at these pages. I definitely plan on writing more posts on my own discoveries on the Web about AI, more particularly, Evolutionary Computing. And next time, I hope I try to convey more technically what I actually wish to convey. Cheers.

Social Bookmarking

My faith in Humanity

Or maybe, the loss of my faith in Humanity

All these days, I have been positive, that the Human Race is simply not capable of destroying itself. Perhaps now, its about time I changed my views. I had forever hoped this day would never come. Alas, it has.

My days in Japan had rejuvenated my beliefs a little. Japan was clean and green and its people well aware of their duties to the environment. And then, I land at Coimbatore, a completely balded city. Dusty and in a ruin-like state. All in the name of development. I return back to Chennai, and as always there is Coovum ever ready to show off as the most violated, polluted river on the face of the Earth. My heart cringes in despair, EVERY time I take a ride on the local trains. I can’t bear the sight of the river. The sludge. That smell. And still there are those who pass over it everyday, not giving a damn as they pass by.

It is only once in a long time that I watch TV. And call it misfortune, to add to my despair, ‘An Inconvenient Truth’ was on on HBO. The hope the man has should really be commended. The ignorance of the American people, intrigues me. Why is it that everything is treated as hoax. Why? Armstrong never landed on the Moon. The 9/11 was perpetrated by the Government. And Global Warming is a lie.

Are they frigging out of their minds?

Why? Money. Isn’t that what everything is all about.

In the US, its about increasing the profits. The fuel efficiency law in force in the country is similar to the one in India, I think. And when a talk arises of putting a more stringent rule into effect, American car makers are the first to start swearing. Ford and GM are suffering heavy losses. If such laws are forced, where would they sell their cars? On the other side of the world, Toyota and Honda are flying high. And their market has the strictest fuel efficiency and emission laws. Japan. What an irony. Won’t their markets expand if GM and Ford actually embrace a strong emission rule?

In India, its about minimising expenses / trouble. Why bother to treat the sewage? Its not my problem. Why bother to properly dispose the waste? Its not my problem? Why even bother to look for a proper place to spit? Why not spit here? Why look for a dust bin to dispose the chocolate cover?

No one cares. Why should I?

There was no ice in the North Pole this Summer. I can imagine the response of anyone who I bother to tell it to. “O < like I care >”. Global warming is not a hoax damn it. Its here. And if you don’t do something about it, F*&^, you are not going to do anything anyway. And the TATAs hailed for bring the Industrial Revolution to India, yada yada etcetra etcetra yawn…, aren’t doing pretty things to the environment either. Being an e-member of Greenpeace isn’t every satisfying.

Global Warming. Thats not the only thing thats made me completely lose my faith in Humanity. Terrorism.

Unity in Diversity

What a fantastic concept, eh! The volatility pervading this Unity makes me sick. Of what use is such a unity. The only use of this is that one can swear at the other, at the other’s society and still not be called a racist. Sometimes I think we’d be better off as twenty different countries. And I pray to God I don’t start about politicians in the Country. Gandhi would be greatly ashamed.

I came home this weekend. Saturday, serial blasts in Bangaluru, and Sunday in Ahmedabad. Local news channels in each state crying out that it is their cities to be targeted next. Aaaahhh! What are they trying to be prove??? What the hell do they want? What do they gain by killing loads of innocent civilians? Frankly, I refuse to be intimidated by a bunch of demented fools. Jihad, indeed. If only someone told them what it truly means. Are they going to kill everyone who is not a fundamentalist Muslim? And a pathetic note challenging the police five minutes before the blasts. Sniggering, they must have been as they wrote the note. What a bunch of cowardly ignorants. Just look at this all from a higher plane… What an uncivilised act.

And we are humans!

So many cellular automatons, so many simulations. No simulation could possibly predict that any civilized population would eventually destroy itself. I was convinced that the analogy drawn between the human race and any virus. And perhaps then an automaton could properly predict the ultimate fate of such a race. But such a destiny!!!!

I cannot pen on anymore. I am either so full of spite or despair, or both. Please note that I have not intended to cause any harm, sentimental or otherwise, through this page. I am simply so full of despair and been this way for sometime now that I just had to pen this down. Pardon any inaccurate detail in the page, and please bring it to my notice. I’d be forever indebted.

Sanjeev

Japan Trip – Part 1

It’s been quite a few days now, I’ve been wanting to write about my truly mind-blowing experiences in Japan. Its great that I’m finally getting down to write it . So much has happened that I’ll probably forget most of it if I don’t put it down in words while its still fresh in my memory.
For a few months in my second year, I had been mad about WoW – DotA (World of Warcraft – Defence of the Ancients). I’d happily spend most of my saturdays blissfully enjoying game after game. It was on one such evenings —–

“Sanjeev …, room 10. Ram Kumar .., room …, please come down”

“Who wants to see me on a saturday evening???”

I couldn’t recognize the voice. You can imagine my confused reaction when I realized that it was the Dean who wanted to see me.
A visit from the Dean is seldom good. Generally it is a very organized procedure. The watchman calls out on the mic that the Dean was coming, and everyone scrambles to switch off and hide his cell-phone. There was no warning this time. I was in my shorts and bare-chested. Quite an awkward situation. I got my shirt on, and went to call Ram. He wasn’t in his room.
“I didn’t get into any trouble did I? Why does the Dean want to talk to me? I sure could use some one by side to share whatever I was into. ” By the time I had finished thinking of all the possible things I had done that could have landed me in trouble, I was already standing in front of the Dean.
“You are Sanjeev???”
“Yes.”
“Would you like to go to Japan?”

Err.,”, I thought. Either I’m dreaming or he’s crazy. I remember thinking, ‘You don’t jump in front of a black man in a buffet and ask him to hurry up.’ Chris Tucker in Rush Hour 2. No. It wouldn’t be apt to pull up that dialogue there. After a minute of stunned silence, I replied.., “Yes.., sure.” I would be contacted by a Professor from the Center for Crystal Growth. And Ram Kumar would accompany me on the trip. “Cool.”
And that is how it all began. Call me an antagonist, but I never thought that it would actually happen. I told Ram and we waited for a quite a few days until we got further information. I was once again playing DotA when the next visit came. This time it was not from the Dean. It was from a student of the professor, I had earlier been informed about. Ram was also available then. So we accompanied the dude back to the Professor’s room. Apparently he had spent some time in Japan, and was quite fluent in the tongue. God help us if we were ever to be tested for our knowledge of the language again. I had scored 75 on 450, and failed in the Level 4 exam. I suppose Ram had fared a little better. The professor wasn’t there when we got there. We waited in his room for awhile all the time dreading his arrival.
Many people entered and left the room. We just sat there not knowing who was who. The professor turned out to be a fairly built guy, with glasses and a moderately stately bearing. There wasn’t much talking. We just filled up a few forms. And then….,
“Nihingo wakarimaska??” Do you understand Japanese.
I didn’t know who it was directed at. “Hai, wakarimashita”, I replied. And I received a pat on the back for that. Wow!! Tests should be more like this. We were asked to submit the forms directly at the consulate in Teynampet, and they’d take care of all the VISA issues. Also, “ The last date for the submission of the applications is Feb 28. So you want to submit the applications as soon as possible. The consulate is closed for visitors after 5 O’ clock. ” It was 4 in the evening of the 28th of February.
Great news pro. Thanks for everything.
We did manage to get to the consulate on time. At 5. On the dot. Not without events though. We had stopped on the way to get my photo taken. The shop keeper went on a mad shouting spree when I opened the door to another room. Some guys were watching a cricket match inside. It couldn’t have been the black room. Frankly, I had other things on my mind then to even bother about his furious yapper.
Our contact at the consulate asked us to come back the next day. And he gave us new copies of the same form to be filled again. “You’re the boss man. Anything you say.” So the next morning, Viki and myself, went to submit the forms. Ram couldn’t make it. That ends the first episode. We did not receive any news whatsoever from anyone for about two months. My beliefs were getting stronger.
This is too good to believe. I mean come on we don’t even know how we were selected. Why are we going to Japan? Would there be anyone else with us? Ten days. Sponsored by the Japanese. Is it enough to know only this much??