Merelles iPhone game released (finally)

I've been working on Merelles for the last 4 months and I'm pleased to say, I've finally finished it. It's available on the Apple App Store for a small amount.

Merelles is an abstract strategy game. It is also know as Mills, x Men's Morris (4, 6, 9 and 12 men variations) and by many other names.

Seeing as this is my technical blog (and the Apple NDA has been lifted), I feel compelled to provide some technical details. The app itself is written in Objective-C (of course) using TDD (of course!) driven by OCUnit.

The computer AI uses a negascout tree search to examine the game tree. The use of the negascout algorithm means that some pruning will occur on the game tree so that not every node needs to be examined, as long as the moves are ordered so that better moves are examined first!

Iterative deepening is applied on top of this, starting by searching one move ahead, then two, and so on. The moves that look to be good after a search are considered first when searching deeper. In addition, as the same board position can occur several times during a single tree search, moves that result in a really promising board position are classified as killer moves and examined before other moves if they occur again during the search. All this helps in obtaining an amazing prune rate of more than 90%

A question that is often asked is how do you determine if a board position is better than another board position? Unfortunately, it's a fuzzy answer. A set of heuristics is applied, which take into account things like how many pieces each player has in play, how mobile each player is (how many valid moves they have), how easily they can form a row of three pieces, and so on. The strength of the AI is determined largely by these heuristics.

There are 3 difficulty levels. For each level, the heuristics are mostly the same, with varying depths for the tree search and the maximum number of board positions that are considered. For the most complex game (the 12 men game):

• On easy, the AI only looks 2 moves ahead.
• On medium, the AI looks 2 to 4 moves ahead examining up to 3000 board positions.
• On difficult, the AI looks as many moves ahead as it can in examining up to 15000 board positions - in practice this is between 4 and 8 moves ahead, depending on the state of the game.

The resulting game play feels quite natural to me, with the AI coming up with some clever strategies, which in themselves have not been programmed into it, but rather are the result of the tree search and the heuristics. I've been astounded a few times at the way it has trapped me!

The primary challenge in writing this game was to balance the heuristics to set up board positions that would yield good results later in the game rather than just constantly pursue the capture of opponent pieces, which would result in rather one dimensional game play. On top of this, it was necessary to keep the calculations light and to optimise the code as much as possible so that the tree search would not take too long, remembering that it's running on a device with limited computational power. On difficult, the deepest tree searches take up to just over 4 seconds on the iPhone.

Unit testing iPhone applications

The OCUnit framework is bundled with a standard xcode installation, which is handy for getting up and running with unit tests and test-driven development (TDD). Somewhat annoyingly though it does not play nicely with the Cocoa Touch framework. So, how does one go about building iPhone applications using TDD? I'm sure there are several ways of achieving this, but I wanted to stick with OCUnit. After a bit of messing about this is how I do it.

Image from Bhavna Bahri's photostream.

The Cocoa Touch framework encourages the use of the model-view-controller (MVC) pattern. It's only the 'V' and 'C' bits however that need to extend Cocoa Touch objects (UIView and UIViewController); you're completely free to implement the 'M' bit as you see fit. So, the basic approach I take is to write the model classes against OCUnit tests compiled against the (Cocoa) Foundation library only, and to then use these same classes in my iPhone application, which is compiled against the Cocoa Touch framework. The Foundation library exists in both the Cocoa and Cocoa Touch frameworks and is (almost) identical, although the unit tests only run against the Cocoa version.

This setup involves creating two projects: a Foundation Tool project and a Cocoa Touch project, and to reference the model code (which lives in the Foundation Tool project) directly from the Cocoa Touch project. Rather than duplicating the files that comprise the model, they are just referenced from the Cocoa Touch project (which is achieved by dragging them from the finder into the Cocoa Touch project, making sure the 'Copy items into destination group's folder' option is not checked).

The files that comprise the model objects should import Foundation/Foundation.h whereas the files in the Cocoa Touch project should generally import UIKit/UIKit.h (which is a higher-level header file that ultimately includes Foundation/Foundation.h).

What this means is that unit tests only cover the model, not the controllers or the views - so domain logic should be in the model, with the controllers simply acting as conduits for responses from this logic. In other words, there should be as little domain logic as possible in the controllers (and obviously the views, but there should not be any logic in the views anyway!)

App Store Trials and Tribulations

I got my first iPhone application submitted and accepted onto the App Store for its launch. Here are my impressions of the process so far.

As a developer, once you've built an application and tested it on the device, and digitally signed it with an Apple-issued distribution certificate, the application is submitted to the App Store via iTunes Connect, which is a simple web application. All the meta-data for the App Store is entered at this point. I have a few small gripes about it and was hampered by a bug that didn't let me change details on a subsequent upload, but otherwise it's simple and does the job.

The application only appears on the App Store once it has been reviewed and approved by Apple. The first time around this took two days, but the rate at which they are approving releases seems to have slowed to a crawl now. I submitted an update more than a week ago, which has yet to be approved. In fact, I now have another update ready (which should be my last). My concern around the slowness of the approval process is that if there is a pressing update you need to roll out, it will take as long as Apple decide it will take and as a developer you have no control over this.

Once the application is on the App Store, you are at the mercy of the iTunes community. I am not convinced that the reviewing mechanism used for music is appropriate to applications. I've had several low ratings (zero or one star) simply because there is a free version of something similar and mine costs £1.19. Being as objective as I can, I can honestly say that the free version is free for a reason - it's not very good. Allowing people that haven't even downloaded the application to give it a rating is opening the door to this sort of abuse. It can be really gutting to see your rating drop, especially when the reviewers haven't been fair, or even downloaded the application in the first place. This of course has the knock-on effect that fewer people download it because of the low ratings. Given the months of hard work that went into producing my application, I can't understand why someone that hasn't downloaded it is able to review it and thus directly impact how many people are likely to download it. Apple, you need to change this!

My last gripe is that Apple don't provide any download statistics to the developer. A monthly report is produced, but in the fast moving world of online sales surely daily stats wouldn't be too much to expect?

Update: old news now, but Apple are providing daily and weekly stats.

New domain name shortage

I was recently looking to register a new domain for a project I've been working on. I underestimated the amount of time it would take to find an available domain. What's incredibly annoying is that many domains have been registered purely in an attempt to make money by selling them on (especially .com domains). Let's face it, everyone wants a .com domain.

Here's an experiment to try. Think of an obscure word or combination of words that surely nobody would have thought to register, and do a whois check on it. You'd be suprised at the domains people have registered (I was).

Let's try some... How about eatbananas.com or flybot.com. Nope, both taken.

Ok, how about purpletree.com, happycow.com and satisfiedmonkey.com? Taken, taken and taken. Yes, satisfiedmonkey is taken.

Maybe the trick is to find something that's not really a word. Something cool like digg or boingboing. How about kerplunk.com, sproing.com, flugle.com or cartoo.com? Ah, no, all taken.

Maybe the trick is to leave out letters like flickr? How about shattr.com or shtterbug.com? No.

Should it really take a day of hitting whois with odd words until amazingly you manage to find one that is available and not completely ridiculous? Shouldn't domains have a use-it-or-lose-it rule? Should there be a limit to the number of domains one can register? Until then I guess we're doomed to having lots of startups with absurd names because that was the best .com domain name they could find.

South Africa and Open Source

Last year, the South African government announced their intention to roll out open source implementations across all government departments. A move that surprised, but delighted me and many others.

So, when statements are made like the one made recently by Microsoft's director of corporate standards that South Africans were unlikely to benefit from OSS, or do any 'deep' development work on Linux (hello, heard of Ubuntu?), I have to ask myself, where is this coming from? What is a statement like that aimed at achieving? Furthermore, saying that students in South Africa are 'still grappling with coding skills' smacks of complete ignorance.

While I don't agree with all the government's policies, they should be applauded for the move to OSS and for setting a precedent that other developing countries in Africa may follow. Well done!

Raising the bar on bug priorities

Inevitably during the course of writing an application, bugs creep in. And like all good software teams we diligently capture them, along with some priority level. Let's say for the purposes of discussion the priority levels are: trivial, minor, major and critical. Fine. So far, so good. But, as time goes by and bugs get raised and some get fixed, the way in which priorities are determined seems to change. If the entire bug queue does not get cleared out regularly, what was minor before starts to become major because the people raising the bugs know that it will be fixed sooner. The result is that most of the bugs tend to land up in the next-from-top priority level (major) and before long the lower ones (trivial and minor) become little more than an afterthought. The highest priority level (critical) is usually spared as it is those bugs that really are showstoppers that still fill this priority level. It's not uncommon for a new priority level to suddenly be introduced to start separating the major bugs out into the more major and the less major bugs. This sets a dangerous precedent - what's next: Even more major? Almost critical? Aargh..

This seems to be a fairly common problem, seen in many organisations, on teams of varying sizes. As I see it, some of the root causes are:

• Letting the bug queue grow too big
• Not defining exactly what is meant by each priority level
• Having too many stakeholders. Whose priority is more important?
• Complexity or difficulty in fixing a bug are not interchangeable with priority - just because a bug has a priority level of 'trivial' it doesn't mean it will be quick to fix; and vice-versa.

Getting into iPhone development

So, I have an iPhone, I have a Mac and I have some ideas. It seemed only right that I combine them and build an iPhone application. Only problem... I hadn't done C or C++ in years and Objective-C looked a bit daunting. But, what the hell, I took the plunge.

I am happy to report that it's not too bad. Working in xcode however is nowhere near as rewarding as IntelliJ or Eclipse. Just setting up my project to use ocunit (see update for more on this) so that I could start with some tests and step through my tests with the debugger required a few hours of searching the interwebs and some messing about (thanks Chris Hanson for this good short guide) . You'd think they would make creating a new project would add unit testing to it by default. It still comes as a surprise to me that people don't automatically write unit tests. Can software really be built effectively any other way??

All in all, the experience has been good. I'm just getting to the point now that I'm starting to put the GUI together. More to come on this.

Update: now that I'm building the GUI, I've switched to the Cocoa Touch sdk and it seems that ocunit does not work with it yet, which makes TDD (with ocunit) difficult. For now, I'm testing my classes with ocunit compiled against cocoa, then moving them to my cocoa touch application, but that's not a very good, or sustainable approach. The other options at this point are: write a simple testing framework; wait for apple to make ocunit compatible with Cocoa touch.