Secret Research Project 4: N Queens Problem with GA

Over the last couple of days I had an idea and nothing to do, so I implemented a genetic algorithm search for the N Queens problem. The N Queens problem is a toy problem in chess, where you are given N queens and a N x N chessboard, and where you are supposed to place the queens such that they do not attack each other.

The idea behind the GA search is simple; each individual in the population represents one configuration of the board. Better solutions can breed, thus (hopefully) conserving better positions. The details of the GA I used are as in the standard literature, employing uniform crossover and mutation with no elitism. The fitness function employed is the number of non-mutually-attacking queen pairs.

I tested the performance of the GA search algorithm on the N queen problem for N=4,6,8,10,12. Each problem was run 20 times, resulting in the following results:

N	4	6	8	10	12
Average Generations	2.0	184.5	195.4	838.0	396.2
Median Generations	1	19	38.5	320.5	295.5
Average* Generations	1.6	95.2	75.2	521.9	349.4
Solution Density	128	11664	1.8E6	1.4E7	6.3E8
Efficiency	0.82	1.22	24.3	264	17968

*Average after discarding the 2 highest and lowest extremes.
Solution Density is the number of board configurations divided by number of distinct solutions; hence representing the number of random searches before a solution is found.
Efficiency is the solution density divided by average number of GA searches.

The results of the GA search are not too bad, though I was expecting better performance. However, the scaling seems a bit haphazard; I am unable to explain why N = 12 runs better than N = 10. Another point which is unreflected in this report is that for N = 15 and beyond, this GA search will require considerable time to run. More improvements are necessary.

Lastly, here are some of the solutions found by the GA search. A solution each for the N = 8 and N = 12 cases are shown.

N = 8 Solution

N = 12 Solution

True Hair Loss Products

In the future, there will be true hair loss products. No, not products that treat hair loss, but products that cause hair loss.

It seems stupid, true. Who would want to buy true hair loss products? It doesn't seem to make sense. Well, many things don't make sense either; why people smoke, or drive dangerously, or buy expensive but useless luxury goods.

It's the handicap principle, really. Agents, whether humans or animals, may adopt useless handicaps to signal their superior fitness. Whether it is the fancy tail of a peacock or the stotting of a gazelle, the message is basically "Hey, I have this really dumb thing and yet I'll still alive and kicking. If I'm not great then I would have been long dead!".

So, in the future there will be true hair loss products. People who use them are more macho than people who do not. They are in turn more macho than those who use hair gain products.

Unless of course you are balding. Then you have adopted a handicap and failed miserably.

Children and Daughters

Here are two interesting problems for you.

Problem 1:

I have 100 children. The oldest 99 are girls. What is the chance that I have 100 daughters?

Show Answer

The answer is 1/2. Quite obvious, really.

Simple, no? Now for the next problem.

Problem 2:

I have 100 children. At least 99 of them are girls. What is the chance that I have 100 daughters?

Show Hint 1

No, the answer is not 1/2. Try again.

Show Hint 2

Use conditional probability to solve the problem.

Show Answer

The answer is 1/101. Compute this by finding P(A|B), where event A is having 100 daughters, and event B is having at least 99 daughters.

A fun problem, though I didn't really get it right instantly too.

Shibahama

I’m not really old, but I think that as you age, your memories of people fade. Once-friends become familiar-strangers illuminated by the sole few events that still cling precariously to your memory. In way, it might be regrettable, but somehow time has this effect on almost everything.

Not too long ago, while I was out shopping for a few business shirts for some job interviews, someone walked up to me and said hello. Jerked out from of my own lines of consciousness, I staggered for a moment before finally recalling that that someone was an old classmate from my secondary school. For a half-second, I kicked myself for being too caught up in my thoughts and not noticing him when he was right in front of me. This kind of thing happens often, you know, and I’ll guess that it has something to do with how much the person is in your consciousness as well. In this case, I haven’t seen him for many years now. I greeted him as well, and we exchanged some how-are-you-doings and well-that’s-good-to-hears before running out of things to say. I couldn’t remember any common memory that could be used to further the conversation, and neither could he, and so we stood there for an awkward spilt second before he excused himself with a hey-I’ve-something-on-see-you-some-other-time.

I’ve heard a half-dubious theory on human memory which stated that even if you couldn’t recall something immediately, the subconscious mind continues to work on the task. Regardless of the veracity of the theory, I did manage to remember more about my classmates a few days after the encounter. I was reading the newspaper while eating some instant noodles, two activities which were absolutely unrelated and unconducive to the task of recalling, but the next moment everything was clear and obvious.

He was only in the school for about a year; his father had been posted to an important (and probably long-term) position overseas, and he had to move overseas after the first year. I think he had known about the posting since his entry to the school, and hence was more or less reluctant to spend too much effort at socializing and making friends. It might be for this reason that I did not recall very much more about him. In fact, I could only recall two particular events that sort of crystallized my memory of him.

Though we did not take the same way in getting to school, there was some overlap in our routes. Now, our routes intersected at a narrow one-way road that we had to cross to get to school; the road was only used by vehicles going to the school, and hence was rarely used. There was a diminutive traffic light and painted crossing halfway along the road, but in all seriousness nobody really followed the traffic light. Everyone, student or staff, just checked the road and crossed. The traffic light was quite pointless, really, since there was no danger of getting into an accident; it was impossible to not notice any rare vehicles that come down the road.

Hence, I found it amusing when I observed that he, for some reason obscure to me, consistently used the traffic crossing, even in the heat of the midday sun, even when it was drizzling, even when it everyone just passed him and crossed the road. It was something I could not fathom. I wanted to ask him for the reason, but I never got the chance to raise the question before he left the school.

The second incident I recalled was the storytelling contest sometime in the middle of the first school year. Some teacher had come up with this bad, facepalm worthy idea, and everyone was clearly disinterested, but every class had to come up with at least one participant. Though he had kept a low profile in the class, the “honor” of participating in the contest, determined by a cycle of nominees nominating the next person, somehow fell to him. He did not reject the nomination when it fell to him, so it was somewhat surprising.

When the contest came about, there were only ten participants (rightly corresponding to the nine classes of the level and one enthusiastic participant, though there must have been one class with two enthusiasts, since no sane person would participate when there was already one willing volunteer). In any case, I could only remember the story he told, which was a Japanese story, Shibahama. I had no idea he chose the story, but the oddness was perhaps the reason for recalling it so well.

The story was about a lazy fishmonger who drank all day and neglected his work. One day, the fishmonger picked up a purse with a huge sum of money. To celebrate his find, he immediately bought some wine, and drank himself to sleep. Upon waking the next morning, he discovered that the purse was gone! He asked his wife whether she had seen the purse, but she admonished him for drinking everyday and dreaming of nonsense. After searching the house and indeed finding no trace of there ever having been a purse, the fishmonger believed that his wife was telling the truth, and was so ashamed of his poor conduct that he resolved to change his behavior and to give up drinking.

Three years later, a clerk from the government came to the fishmonger’s now well-thriving shop, and informed him that the purse had been unclaimed during the entire period and hence now belonged to him, the finder. The fishmonger’s wife revealed that three years ago, she had lied and reported the lost purse to the government office. Now that everything turned out well, and that the fishmonger had changed his ways, perhaps it would be good to celebrate over some wine, she said. To her surprise, the fishmonger declined, saying that drinking caused him to wake up empty-handed from a beautiful dream three years ago; he would hate for things to lose the beautiful dream now.

Now, his story didn’t win the storytelling contest, but it appeared to be well-received. However, I was not especially fond of the story; it seemed to more of a moralizing tale rather than a believable or realistic story. In particular, I thought that the fishmonger’s redeeming change was too sudden, and motivated by too little, to be credible. That was what I thought then, anyway.

A few days ago, I suddenly recalled the story of Shibahama. I had finished writing the final few sentences on what was to be the final paper of my undergraduate days, and was idling flipping through the pages of the examination booklet. In other situations, I might have checked some of my answers, or expanded the answers to some questions, but somehow, I had no desire to do all these now. Instead, my mind wandered to random things, until the bell rang.

When the examination was over, I walked home slowly. As I walked home, the inevitable truth which I had known all along was no longer deniable. An illusory dream had ended, now replaced by the reality of the working world.

Birthday Story

I sometimes think that the best stories are those left to the readers' imaginations. Consider one of my favorite short stories, written by Ernest Hemingway :

For Sale: Baby shoes, never worn

And that's it. That's the entire (written) story. For such a short piece, the number of questions it brings into mind, and the number of possible interpretations, are astounding. A comedic understanding would be that the clumsy father bought shoes of the wrong size, and realized it too late for returns to be made. But, as a person with more of a taste for the tragic, I would read it as being some terrible tragedy- perhaps a fatal accident before the full term, for instance.

The story I'm going to tell next is also one which lends itself to interpretation. I won't claim that what I'm telling is what exactly transpired, since I never really got to know the complete details, but as things go, my interpretation incorporates all the facts I know. So, from my point of view, it's pretty valid, but if you have any alternative readings, be sure to share.

This happened about six months after I moved into my new home, which was sited close to the university at which I was lecturing. After getting to know the neighborhood, which had the cozy university town feel to it, I started frequenting, on weekday evenings, a small cafe near my home. The cafe was owned and run by Karen, a charming and witty lady just pushing into her mid-thirties. She would often tell amusing anecdotes about her previous customers, and that, along with the delicious chocolate cakes which were never too sweet nor horrendously bitter, convinced me to become a regular at that cafe.

My schedule usually involved getting a slice of cake along with some warm peppermint tea, and then slowing consuming the two items over the dailies or a book. If my eyes happened to be strained due to overuse at work, I would probably strike a conversation with Karen or some of the other regulars at the cafe. There was almost always an interesting story to pass around.

It was one of those eyestrained days when this story happened. I was halfway through the newspaper when I decided that the sharp pain around my temples was too much for me to bear any more reading for the day. Cake and tea weren't the best foods for a eyestrain induced headache, so I was prepared to leave, if it weren't for the heavy downpour. Resigned, I slumped back into the chair, and rested my eyes.

It was in that moment of bored contemplation that I was suddenly aware of the somber quietness. To be sure, the cafe never had the rowdy atmosphere of bars or pubs, but the background would always be filled with some level of chatter and conversation coming from the cafe regulars and their life stories. But now, there was only a soft silence amidst the sound of rainfall outside the cafe. Queer, but welcome nonetheless, for noise did nothing to sooth headaches. I did start feeling better shortly after.

Though my headache had dissipated somewhat, the rain had not stopped. Feeling that this might take a while, and with nothing else to occupy my time, I did a lazy scan of the cafe. It was then that I noticed something strange.

There was a young man sitting alone in the corner of the cafe. That in itself was queer, for the corner seats were usually occupied by privacy seeking college couples from the nearby university. But the man did not appear to be a student- judging from his appearance, he should be in his late twenties, and ought to have graduated some years back.

My interest somewhat stroked, I continued to study this odd person. Perhaps I had caught the wrong idea at the wrong instant, and perhaps he was just a random passerby who was unaware of the connotations of the corner seats. Maybe he was an out-of-towner that happened to be caught in the rain, and sought some refuge here, taking dinner at the same time. Maybe, there- hmm, no, the last theory didn't make sense, I realized.

The man was not having dinner, not unless you would consider a cake dinner. It was no normal cake either, but a birthday cake as indicated by the candles topping the cake. And, if I was not mistaken, one made in this cafe, which was pretty rare, since you would need a special request before Karen would make one.

If my eyesight did not fail me, there were three candles on the cake, 2 large, 1 small. Queer.

And there were two small plates on the table, each with a slice of the cake. One from which the man was eating from, and one with its own spoon, totally untouched.

Perhaps there was another person due, perhaps delayed by the sudden and heavy rain. This would help explain the other slice of cake, and also possibly, if I were forced to make a judgment, the aura of moodiness from the man.

Some time passed, and the rain stopped. The candles on the cake melted. The man got up, made his payment, and left the cafe, the single slice of cake virgin, untouched.

There was nothing left to do, and with the rain gone, it seemed a good time for me to leave too. I got up and slowly made my way over to the counter. Karen was just cleaning up after the cake-man, bringing the uneaten cake, save for two slices, back to the kitchen area for disposal. When Karen passed by me on the way to the kitchen, I managed to catch a glimpse of the cake.

"Sweet 21, Selene"

When Karen returned, I popped the question, "Who's Selene?" Seemingly taken aback by my question, it took a long moment for her to weigh an answer. Finally, she merely pointed to one of the photographs plastered on the wall behind the counter. This was the kind of picture wall where everyone puts a happy picture, and promptly forgets about and ignores. I myself had not paid much notice to the wall of pictures before.

There was a particular photograph on the wall, a bunch of people celebrating a birthday at the cafe. The man from earlier on was there too- or should I say, a younger and possibly less unhappy version of the man, five or six years removed. There were some other girls in the photograph, but I would guess that Selene was the one in the center- the birthday girl. Bright eyes, an incandescent smile, a sweet-seeming girl. Perfectly happy and innocent.

The time stamp on the photograph was today's date, five years ago.

I felt an uneasy tingle in my gut. Hesitantly, I asked, "Did something happen? Perhaps like five years ago?"

Karen only gave a slight nod, before retreating to some other part of the cafe.

It was a terrible story, one so terrible that I had hoped that someone would jump right up and shout, "AHA, fooled you didn't I?" But there was no such declaration, it was real.

Was there some tragedy? I don't know for sure. And I asked myself, would fate be so cruel as to allow some sort of tragic event to occur on one's 21st birthday? There was no reason, I would have thought. But then, what if cause and effect were reversed, and that one's 21st birthday was the cause? An intense celebration, a few loose drinks... Not so difficult to believe, then. But it makes the entire affair take on an entirely regrettable feel, even moreso than before.

And that is my version of the most terrible birthday story I know.

Solipsist Reincarnation

I found a girl and exhorted her money. She seemed half-confused, half-scared, but she gave up her money nonetheless. Then, as I was walking way, a bespectacled kid saw me. The kid, shouting in a raised voice, said, "Stop ! I am you, and you are me !"

There was no sense to his statement, which irritated me to no end. Pissed, I beat up this insane kid. Immediately after the beating, the boy seemed to realize something, and ran way. Then, a winged angel appeared out of nowhere, and bellowed, "Thou shall feel the force of karma !"

When I next awoke, I found myself in an unfamiliar body, seeing everything from a much-displaced height. My next sight shocked me - someone resembling myself was approaching menancingly! I then realised that I was the girl I had previously exhorted! The shock and confusion left me stunned, and my money was effortless taken away by myself.

Another whiteout happened, and when I reawakened, I found myself in yet another vessel. I was now wearing spectacles... which would mean I was the bespectacled kid! The same one I beat up! Then I saw myself. Seeing myself approach, and knowing that I would soon be beaten by myself, I tried to stop this, by shouting "Stop! I am you, and you are me!"

It was useless, and I was beaten up. It was then that I realized the truth- that Karma works, but in a queer way. I was not being punished for earlier crimes. Rather, I was both the the victim and the perpetrator, that I was punished the instant I sinned against myself.

Upon realizing the absurd nature of the world, I repented, and became an angel.

Critical Reactions and Chain Mails (And Facebook)

Recently, I received a sort of chain mail on Facebook, which required me to list 25 random things about myself, and to then forward this to 25 people. Of course, I didn't reply because I didn't have 25 friends, but that's another matter altogether. In order to excuse my faux pas, I tried to create an elaborate explanation, which I detail here.

It struck me that chain mails, of which this was an odd example of, have great similarities to nuclear reactions. Each person, if affected, liberates a fixed number of mails, which may then also cause a similar event. If certain conditions are met, then a chain reaction has occurred.

I did study a bit on the subject of nuclear reactions, and the very obvious condition for a chain reaction was if number of reactions caused by a liberated neutron was greater than 1. Applied to chain mails, if each recipient of a chain mail manages to get 1 other idiot to pass on the mail, then eventually everyone will be spammed and/or the mail will outlast you.

The analysis is a bit simplistic, though. One ought to consider the nature of social networks, since in-groups tend to be interconnected, and asocial bastards that tend to be inhibitors also tend to not be very popular or influential in receiving or sending chain mails. Of course, what I was really trying to say with the last statement was that people with lots of friends tend to be ones that spam chain mails, for some queer reason. My personal take is that intelligent people are lonely, though this could be an example of self-serving bias.

Some academic ought to analyze the issue with more rigorous mathematics. It would make for a good paper, and an Ignobel prize.