Skip navigation

Happy 2015! If you are reading this it means I actually got to finish writing this blog post and it did not go to that Graveyard of Unpublished Posts in my server.

I started 2015 (the first few hours of January 1st) finishing off a phase of a personal project I’ve been working on for a few months now. World, meet Chess Templar.

So well, I guess its time for some public documentation. That’s what this post is exactly.

So what is this project all about?

Around August of 2014 (August 18, 2014, to be precise), I got fascinated with Chess. I’ve had bouts of fascination with Chess before this but I did not push it that much. I remember spending a chunk of my after-school Grade 6 time playing Chessmaster 5500. During my third year in college, I had the idea that if I play a game of chess everyday, by the end of a month, I would’ve played 30 games, and I’m 30 games more experienced than I was a month ago; I played against the Chess program in Windows Vista and against GNU Chess. I had the same idea in 2013, only that time I played against Chess Free in Android.

The thing with those bouts is that they did not last because, I guess, I was ill-equipped to study Chess. Reading reviews of Chessmaster 5500, I keep running across the remark that it has an excellent tutorial mode. I have vague recollections of using that mode but I think I just did not see the reason behind the moves the AI was coaching. Besides, will you ever trust an AI that it will coach you to defeat itself?

Sure now there are lots of software out there for studying Chess, some even free. But then, I don’t find that they have the features I’d like to have while I study Chess.

What features?

For one, I’d really like an engine that will help me practice a particular opening. Or annotate games. And I’d like to be able to tinker with the algorithms (not just the parameters) of my engine.

Hey, I found this Chess software that does exactly that and it’s free and open-source!

Oh. I forgot to say that this is also my rather-lengthy exercise on artificial intelligence. There’s a reason I wrote it in Java (not my usual Python project).

To note: Had I only wanted a Chess engine to play with, I would’ve forked PyChess.

What do you have now? What’s coming up next?

The biggest chunk of Chess Templar right now is the GameArbiter, which enforces the rules of Chess. I have tried to be as meticulous as possible in encoding creating the arbiter. To mind it can take account of:

  • En passant captures
  • Subtleties of castling: you cannot castle out of, through, or into a check.
  • Rules on dealing with checks.

Notably, it cannot yet account for:

  • Draws. Man, draws must be among Chess’ most complicated rules.
  • Pawn promotions. Actually, I have not yet decided where in my code should I handle Pawn promotions.

That said, at 317 commits at press time, GameArbiter would still handle endgames poorly.

Also, coming up next is adding rudimentary AIs. I’m still studying Chess-playing algorithms. Chess is a well-known example of combinatorial explosion so it automatically rules out basic minimax, unless maybe if I limit the depth (but how much good will that be?).

To count, there are 20 possible first moves:

  • each of the eight pawns can either advance one or two squares -> 16 moves
  • the two knights have two squares each to move to -> 4 moves.

Black, in reply, have the same 20 choices.

Any metrics you are using to evaluate your output?

In the long run, if I make it good enough, I want to pit whatever engine I come up with in the Thoresen Chess Engine Competition. For now I’m settling with getting good unit-test coverage.

(Note: This is a fault of the Maven coveralls plug-in I am using but the badge at the repo’s README is misleading in terms of my current code coverage. Check the last link to see that I am at 91.86% coverage at press time).

Any algorithms/tricks/hacks you would like to note?

To check on the King’s safety, I modeled the relationship of pieces and squares in the board as a directed graph. For every square in the board, an edge is incident to it if any piece can move to it on a side’s next turn. Only squares with pieces occupying them can have an edge incident from them. (So, if an occupied square has an edge incident to it, it means that that particular piece is in danger of being captured.)

With this representation, I want to check on “hotspots” in the board: squares with the most pressure, pieces under the most pressure. Just a gut feel that I could make an engine take advantage of this.

So there, everything of note in my project so far. Happy new year and, if you’re interested, fork me on GitHub!


I just got locked out of my Linux machine (details here) for reasons I am still trying to determine (see the link). I tried to recover my password but, unfortunately, all my most recent Live CDs I’ve left at work. All I have with me is an old Karmic installer, incidentally, the first Ubuntu I ever tried to install (and failed miserably more due to hubris and absence of mind—but that’s another story).

So from the Live CD, I was able to mount my Linux partition fine. Note that, I guess due to EFI and/or the tutorial I was following is just outdated, a mere sudo fdisk -l did not show me all my partitions; I had to use gparted (thankfully available with Karmic). But when I try to chroot, into my mounted partition, I get an exec format error which is apparently because my Karmic LiveCD is just 32-bit while the installation I am trying to salvage is 64-bit.

Thankfully, tinkering around with how Linux stores passwords, I got to reset my main account to have no password.

  1. Edit /etc/passwd. Look for your username in the first of the colon-delimited fields. A typical line in the this file looks like bin:x:2:2:bin:/bin:/bin/sh. The ‘x’ in the second field means that the password for this account is encrypted. Remove the x so the line corresponding to your user becomes similar to bin::2:2:bin:/bin:/bin/sh.
  2. Your actual password is stored in the /etc/shadow file. Open this file and, again, edit the line corresponding to your user to just have four colons after it like so: user::::.
  3. Reboot. You should now be able to log-in passwordless. Remember to reset your password at once.

Note that to get my system to boot from LiveCD I had to tweak my BIOS yet again. I had to set my boot mode to Legacy and, after doing the steps outlined above, had to switch back to UEFI and disable Secure Boot. Man is BIOS dealing becoming traditional for me!

I’ve always wanted to discuss algorithm problems here but a quick look over at my posts (even just the tags) reveals that I haven’t really done much of that. Over at Github, I have a repository dedicated to solving Programming Praxis problems1 and I’ve thought of discussing my answers here but I haven’t had the time. My interview with Google is, I think, a good chance to dish out something similar to my intentions.

(Author’s note: Of course, I won’t discuss the specific problems I encountered during my interview. For reasons that will become clear if you think about it for a moment, Google clearly prohibits that.)

There are three stages I encountered during Google’s interview process. The first is a short initial (phone) chat with a recruiting coordinator. Next I had a phone technical interview which, aside from taking a longer amount of time, had me coding on a Google Doc. The third part is where they flew me to Mountain View, an interview which Google terms as “panel interview” but I will forever stubbornly refer to as a “circuit interview”.

My interviews, in general, looked at my problem solving skills. For a company like Google, I expected that they will be more interested in my engineering competence, i.e., questions like “How do you get things done?”, “What frameworks have you used?”, “Why would assembly trump everything?”, “Concurrency, Cloud Computing, Parallelization, Multi-core issues, Efficient Caching Mechanism, High-Throughput Responsive MVC Framework Layer MOAAARRRRR!!!”2 .

Watch this short video featuring Laszlo Block on the type of people Google is after. It may be hard to believe, as it was for me, but based on my experience, this is so true.

Overall, I’d say that my Google interview was 85% algorithms/problem solving and 15% engineering.

I found the second phone interview a bit bumpy that afterwards I did not really expect much. I was just happy that I got a Googler asking me technical questions. My interviewer’s voice wasn’t very clear through the phone (as opposed to the first one). It did not help that I was having coughs that day which later developed into a slight fever.

And, as you may know, Google Docs isn’t really made for coding. I wish Google used a platform more suitable for writing code than a word-processing document. My interviewer wasn’t meticulous about syntax but it was still awkward indenting my lines.

That said, here are some tips:

  1. For this part, do not use Python (or any similar whitespace-based language). I was intending to use Python even though I’ve already expected indentation to be difficult. Thankfully, my interviewer stated at the beginning that he’d prefer me to use Java. With Java, you can skip indentation for small blocks of code. Convenient when your line is getting long or the nesting goes deep3.
  2. Indent using two spaces. This is the indentation style of my first company. Tab is too wide and your lines might easily bleed off the edge, especially if you follow my first tip (new BufferedReader is already 18 characters!).

    Why indent at all? Well, no one’s forcing you but I find it easier to debug if I have indentations. Moreover, code is easier to read.

  3. Don’t hesitate to use the Google Doc for things other than code (like clarifications). Remember I said that my interviewer’s voice through the phone wasn’t very clear? Well, this is exactly what saved me.

As for the onsite, Google will be kind enough to fly its candidates in two days before the actual interview so you can settle down. Due to PyCon Philippines, I was unable to take full advantage of this. Nonetheless, I felt little to no jetlag that I even had time to explore a bit on my first night.

Here’s a little tip though: when coordinating with Google’s recruitment team, be clear and patient when it comes to your travel requirements. Based on my experience, Google’s recruitment team is very accommodating and helpful but that is not to say that they are 100% knowledgeable on the arrangements their applicants have to make for travel. (Cut them some slack as I’m sure they handle applicants from more countries than what you can name off the top of your head.)

In my case, I raised the point of needing a Visa for USA travel early on but it was ignored in the email thread so I assumed it’s okay. Thankfully, the issue came up when I coordinated with their preferred travel agency. This delayed me by almost a month. I should’ve been persistent because I’ve been raised since childhood knowing that Filipinos entering the USA need a USA Visa.

Google would really want you to focus on your interview so there is very little that you need to mind during your stay. They’d have your basics covered (accommodation, reimbursable food allowance, reimbursable transportation allowance) so just keep your receipts.

Here’s the interesting part. The onsite interview itself will last for five hours, lunch included (for comparison, the longest job interview I’ve had lasted for, I think, three hours, and it was more a personality interview; HR was talking to me). The reason why I will forever term it as “circuit interview” is because you will have five sets of interviewers, each of them in turn, as opposed to having all your interviewers in one panel.

As I’ve said, my interview was more algorithmic than engineering. One of my biggest anxieties was if they’d give questions the kind they give at ACM ICPC. I’m pretty sure I’d be tongue-tied had that happened. But fear not. The problems I encountered were less obscure and they won’t require you to provide full implementations for the more complicated ones.

Well, I did not make it so you may want to take the following with some grains of salt. But, hey, some tips:

  1. Use Python, finally. Or, bring your own whiteboard markers, as Steve Yegge advises. I’ve read Steve Yegge’s post prior to my interview but I missed the point on his tip about the whiteboard markers. I thought he was advising it just for the “preparedness” factor but notice that he advises it for the sake of whiteboard space. And yes, whiteboard space can be a real blessing. I want to note that, when I was there, Google’s Mountain View office had those flat-tip markers in stock, the kind like highlighters. In my opinion, that’s worse for an interview than the “fat ones” Yegge refers to in his post.

    Nonetheless, with Python, I was able to squeeze in three functions plus lots of scratch and some illustrations in a whiteboard of standard office size. I cannot imagine how that’d look like with Java (or worse, C/C++), nor can I overstate how good a thing is this.

    For the record, I brought my own whiteboard marker but I did not use it, did not even show or mention it, because I got anxious as to coming across as “too eager”.

  2. Use Python, again. This might vary from programmer to programmer but Python gave the advantage that I can focus on high level stuff. Given the nature of Google’s interview process, I believe this worked to my advantage. It’s really like doing runnable pseudocode.
  3. Use Python, not. I think I know where the weak points of my interview was and I believe I was weakest during the last interview. You see, the interviewer started with “I heard you use Python so just keep using that.” So I did. But then he gave me a problem that would require some low-level manipulation and, as I was using Python, I took time clarifying what am I allowed to do and what am I allowed to assume.
  4. Just keep talking. Remember my anxiety above that I might get tongue-tied? Well, here’s the tip: just keep talking, as long as you’re making relative sense. I’ve been told in a pre-interview email that they want to learn how I think so think out loud. Obviously, I’m not sure if this worked to my advantage or what but at least I managed to avoid that Great Wall of Social Awkwardness Produced by Silence. It might even help you; there was a part in my interview when I was like “Let me try some combinatorics here…so 2 will give this…3 will give that…but 4, oh wait—this is easier to to solve programmatically!”. No kidding.
  5. Relax, this isn’t the ACM ICPC. This comparison might deserve a post on its own but for now, the most obvious difference is the time constraint. I realized that the people interviewing me would like to get a picture of me in just around 45 minutes. So, in contrast to the ACM, they’d give you problems that are solvable in 45 minutes or less. Moreover, your code won’t be ran so (at least I think, and this I did), you are allowed a certain extent of handwaving and just say this function does this and that. At times, high-level descriptions of algorithms will also suffice (read: implementation, with all the debugging that might entail, is not needed).

Finally and most importantly, Prepare with a capital ‘P’. Read the Steve Yegge blog post I linked above and follow his advice on having long-term and short-term preparations. I just said above that Google interview isn’t ACM ICPC but I think ACM ICPC is good standard practice material and not just for Google interviews.

What do you prepare for? In my case, knowledge of data structures like some obscure variants of balanced binary trees and even-rarer forms of trees and forests helped as it gave me some talking points. A good knowledge of textbook algorithms will also help. In one case, repurposing a textbook algorithm allowed me to reduce a naive O(n2) algorithm to just O(n).

That said, even if you’re not planning to take a Google interview anywhere in the foreseeable future, I still find preparations of this kind useful for everyday. So just keep reading up and honing your problem solving knack!

  1. I have a similar private repository for the other algorithm problems I’m solving—ACM ICPC practice, to be specific. As a matter of principle, I’m willing to show my code solution to algorithm problems provided that the problem setters are expressly showing solutions, as with Programming Praxis. []
  2. Okay I’m trying to be funny here. But you get my idea of engineering vs. algorithmic skill. []
  3. Generally, I’d be cautious against getting too deep a nesting. When I encounter this in my code, it’s a sure sign that I’m getting lost and that maybe I need to refactor or re-read the problem []

The end of February was remarkable for a couple of things. First was PyCon Philippines 2014. I’ve already mentioned here a bit of my involvement with Python Philippines. I’ve noted my presence in Python Philippines’ monthly meet-ups. It is no secret that we’ve been working towards another PyCon Philippines.

PyCon Philippines 2014

I must say, organizing a conference is really a taxing job. Kudos to the volunteer team who worked really hard behind the scenes. And while yours truly was listed everywhere as a volunteer, it would be terribly unfair to compare the effort I spent compared to the effort of some others.

For day two, I was a speaker in behalf of Chikka. Chikka sent in a delegation of 26 corporate attendees. However, I was not able to finish day two because I had a flight to America scheduled. You see, I was in for an interview with the Google.

Yes! It has always been my dream to work on the type of problems which Google is tackling. I never thought that, as early as now, I’d be able to score an interview with them, at the Mountain View campus, no less. I did not get in but I’m no less grateful that I’ve had this opportunity.

While this whole adventure deserves a whole post on its own, let me end with the update I had at my Facebook profile after the closing phone call came.

When Google came calling

TL;DR: Nope, not yet. Still, thanks to everyone who wished me luck. This experience was definitely fun. Maraming salamat! (–,)

It started one Saturday morning in October last year. I received an email from an “” email address. He claimed to be a recruiter from Google who got impressed with my GitHub resume.

Now, prior to this I’ve already received a number of recruiting calls due to my GitHub and my PythonPH involvement. But, hey, Google? The Google? Just. Wow.

So…okay, I just sent in a copy of my proper resume as the recruiter wanted. Weeks passed without hearing anything from the recruiter. Until December.

He had me scheduled for a 15-minute phone interview. I thought that Google will finally have developer operations in the Philippines. During this 15 minute interview, it became clear to me that I’m interviewing for a position at their Mountain View campus. The interview went fine which led to a 45-minute technical phone interview in January. Apparently, they got impressed with it as well because they eventually had me for an onsite interview.

After some bureaucratic fiascos with travel documents, I finally managed an onsite interview during the last week of February. Google had me for an all-expenses paid US trip. I was in California for around four days.

I’ve been to a number of interviews already and I must say, Google is really different. They call it a panel interview but I think a better term is “circuit interview”. And it was more like a mentorship session than anything. No pressure, just geek-to-geek chat.

I managed to answer all of the problems they gave me which is to say I performed better than I expected (haha!). I just got a call saying I did not make it but getting from that October email to that closing phone call is still quite a ride.

I’m 21, college-age in America’s educational system. I’ve less than two years industry experience, while most of Google’s job openings require at least three. I did not approach Google; Google approached me. I think I’ve earned the right to be very proud of this experience.

Yay! \(^_^)/

The longer Story, sometime soon!

Yay. I just defeated Miraak, making the Dragonborn DLC the first story arc I actually finished in Skyrim. I did not really intend to make it the first, it’s just that, Miraak’s theft of the souls of the dragons I slay has started to become a pain in the neck. So I decided to finally do him in.

However, I encountered a real show stopper of a bug along the way. I found a workaround to it myself, but one with which I’m not very pleased.

I haven’t found this bug described anywhere else so if anyone else encounters the bug, here goes…

Bug behavior: Upon dismounting Sahrotaar to face Miraak, the Dragonborn is instantly killed. Note that I dismount while Miraak is making his little welcome speech.

Dragonborn glows green and dies. No explanations whatsoever. What a way to finally face an arch-nemesis, keeling over to instant death.


  1. When the game prompts you to make a landing (e.g., in PC, the text “Press E to land” is displayed), do not land. Steer Sahrotaar to the Summit of Apocrypha and use the Bend Will shout once more. This will make Sahrotaar take ground without the Dragonborn dismounting.
  2. I’m not sure if you can order Sahrotaar to interrupt Miraak’s speech and just do battle but I sat through it.
  3. When the battle starts, you will have to battle while riding Sahrotaar. You can order him to attack Miraak, but not the other two dragons. Miraak behaves normally (i.e., keeps attacking you, the Dragonborn).
  4. Miraak still kills Sahrotaar last. When Sahrotaar is killed, the Dragonborn is automatically dismounted from him. Beware that, at this moment in the fight, the Dragonborn becomes very open for Miraak’s attack. Plan your actions well after this forced dismount. (This caught me by surprise but I was able to handle it with a well-timed consumption of a healing potion or two).
  5. Continue the battle. At this point, Miraak only needs to be weakened once more before Hermaeus Mora finally ends him.



  • My biggest annoyance with my workaround is in how it cut the battle with Miraak very short. Since, in the first three rounds, I’m ordering Sahrotaar to attack Miraak, Miraak was quickly weakened. I appreciate the leg-up but I really prepared to face Miraak: items, skills, tactic research, game plan preparation, the works. It sucks that I only get a single round out of four; Sahrotaar took the first three. And even the first three rounds did not last long as Sahrotaar was dealing damage way more than what my Dragonborn could’ve dealt.
  • As I noted in (3), the fight goes on even if you have not yet dismounted Sahrotaar. I’m not sure how Skyrim implements battles while dragon riding, but will it be possible for Sahrotaar to have died before his turn to heal Miraak? Judging by the wiki bugs list for this quest, in the event that Sahrotaar dies before healing Miraak, the quest may not complete.
  • Some experiments with my workaround would be interesting, but I haven’t got the proper save points to try it out. For one, would it be okay to dismount once the battle has started (and remedy my big annoyance described above)?

For the record, here’s the kind of battle I prepared for:

In contrast, I think my whole battle with Miraak did not even go beyond five minutes.

The First Dragonborn is dead. Long live the Last Dragonborn!