Moving Blog

This will be my last post here, I am moving my blog to http://mpatric.com.

My new blog is a custom-built Rails app, hosted on Heroku, using Gravatar for avatars, Akismet for anti-spam and Amazon S3 for storing assets.

Is reversi too difficult?

Much time went into making the AI of reversi strong enough on its higher levels to challenge human players. The highest three levels (of the seven available) are challenging for most human players. On the lower levels, the intention was for it to play as a novice human would play. On the lowest level (beginner) in particular it plays for short-term gains, without considering longer term strategy at all. On each turn, the beginner level plays the move that flips as many of the opponent's pieces, taking a corner if one is available and avoiding squares that would give the opponent a corner on the very next move. This reflects the basic manner in which most novices would tend to play reversi.

Playing each of the other levels 100 times against beginner results in beginner level being whipped 100-0 by every other level. So, it's significantly weaker than all the levels above it, including the one directly above it (intermediate).

All of this makes some of the comments in reviews for Reversi on the App Store all the more surprising:

"Othello is an awesome game I really enjoy playing it but this game is way to difficult even on the easiest setting I cannot beat this game even once I think you should change that" - BjMiller20, Jan 2010

"..it's too difficult to win even on the easy setting. After playing it just a few times, I've given up on it. It's no fun if you don't feel like you even have the slightest hope of beating the computer and on the easy setting, you should have at least a 50/50 chance." - Mitchipoo, Jan 2010

"..frak me, the AI is ridiculous! I've played this game for years but I can't beat the game on Beginner! I'm not Einstein, but I should be able to win at that level.." - Nuclear Moose, Oct 2009

Is beginner level really too difficult? I have played against it dozens of times and beaten it without really thinking about where to play, but I'm probably not the best yardstick as I've played thousands of games of reversi.

I thought a good, objective test of the difficulty of the beginner level would be to see how it does against a player that makes completely random moves on every turn. Surely if the player making random moves manages to win a few games, then the AI of the opponent player is weak. With this in mind, I pitted beginner level against a bot playing random (valid) moves on every turn; 100 games with beginner playing black and the random bot playing white, followed by 100 games with colours switched. The results of the 200 games were as follows:

164 games won by beginner (80 as black, 84 as white)
29 games won by random (11 as black, 18 as white)
7 games drawn

Beginner level managed to win 82% of the games against the random bot, suggesting that it is fairly weak.

Most people that have played reversi know that corner squares are important and often determine who wins the game. Adding two very simple rules to the random bot, which are to play a corner if one is available and to avoid playing squares that give away a corner to the opponent on the very next move (otherwise, just to play randomly as before) changes the results to:

85 games won by beginner (40 as black, 45 as white)
111 games won by random (53 as black, 58 as white)
4 games drawn

From this we may conclude that beginner level is pretty weak. It is beaten often by this simple bot. It would only be weaker if it intentionally played moves that were advantageous to the opponent - in other words, if it played to lose. It would appear that amazingly enough some human players play in this way, perhaps thinking they're playing good moves. To those complaining that the beginner level on reversi is too difficult, it really isn't. Learn some basic strategy and you'll find you will be able to beat beginner level quite easily.

UPDATE: The difficulty levels have been spread out a bit, so beginner is now even easier.

Unethical practises on the App Store

Every iPhone app developer goes through great pains to get their apps noticed and hopefully to break into the charts, which will result in increased sales. Rather than building great apps to entice buyers, the approach some devs take is to release crapware and then to dishonestly fill the App Store with five star reviews that rave about the brilliance of their apps, enticing many gullible users into buying them in the process. Whilst I understand the difficulty that all devs have in promoting their applications, Apple should draw the line at this sort of unethical behaviour.

"Hold on!" I hear you cry. "How is this even possible? You need an iTunes account to place a review and creation of an iTunes account requires the entering of personal details and credit card information!"

Yes, you do need an iTunes account to place a review; however an iTunes account can be created quite easily using a promo code which EVERY developer on the App Store that has published applications can generate for their own applications. Personal details are not verified, so anything can really be entered. New email addresses are easy to generate. It wouldn't take more than a few minutes to generate each new iTunes account. This technique can currently only be applied to the US App Store.

Obviously, it's hard to prove which developers are doing this, however when it's done blatantly it's obvious. Take this developer for example, who has several applications on the App Store that all have suspiciously good reviews and ratings on the US App Store. Clicking through on each of the 'reviewers' reveals that each one has reviewed all of the developer's applications, giving five stars in each case and glowing reviews. The offending applications include My Othello and Reversi Extended (which look to be identical games).

Or course, I'm not saying these reviews were submitted using this trick; however the evidence is quite strong. Furthermore, these implementations of reversi are easily (IMHO of course) the worst on the App Store, yet have the best ratings (4 stars and 5 stars respectively on the US App Store, with 29 suspicious reviews each). The reviews are not true reflection of these implementations.

Hopefully Apple addresses this loophole, or the reviews in the App Store will become worthless. Thankfully, at this point it's only the US App Store that is affected; however, for most developers the US App Store is the most lucrative, so it might become difficult to compete with apps whose rating has been boosted using this technique. Apple, please close this loophole.

The trouble with timers

On the iPhone it seems to have become commonplace to use a NSTimer to trigger redraws on OpenGL ES applications when displaying a changing or animated scene. To run smoothly, a frame rate of 30fps or higher is generally aimed for (60fps being the maximum, limited by the iPhone hardware refresh).

Relying on a timer to fire the code that renders the frame has its pros and its cons. The pros are simplicity and having everything in the same thread of execution (or runloop) means not having to worry about concurrency issues. The cons are what I'm more interested in..

The NSTimer class reference states: A timer is not a real-time mechanism; it fires only when one of the run loop modes to which the timer has been added is running and able to check if the timer’s firing time has passed. Because of the various input sources a typical run loop manages, the effective resolution of the time interval for a timer is limited to on the order of 50-100 milliseconds. If a timer’s firing time occurs while the run loop is in a mode that is not monitoring the timer or during a long callout, the timer does not fire until the next time the run loop checks the timer." Therefore, the actual time at which the timer fires potentially can be a significant period of time after the scheduled firing time.

The low resolution and the fact that a timer can misfire (skip frames) are the most worrying for me.

A frame rate of 60fps means a timer period of 1/60 = 0.016667 seconds (or 16.667ms). What this means is that the frame needs to be rendered well within 16.667ms or the timer will misfire. Flipping buffers when rendering an OpenGL frame can block, depending on the hardware refresh sync, making the likelihood of an overrun (and subsequent misfire) even higher.

What typically happens is the timer fires every 16.667 ms or so (depending on what else the run loop is up to), but for frames whose drawing code has not completed by the next time the timer is meant to fire, the subsequent frame is effectively skipped.


A misfire results in the time between two ticks suddenly being twice the expected period (or possibly a higher multiple of the period if the overrun in the rendering is even higher). Depending on the way in which the animation is implemented in the application, this will usually cause a visible blip or stutter. Regular misfires would make the animation appear jittery and unpleasant.

As most developers simply add the timer to the main runloop, it means that the events need to fire in between whatever other code the main runloop is executing (in particular, user events). This can add inconsistency to the timer period.

Things that can be done to improve this situation (many of which can be done together) are:

1. Optimise the drawing code so that it comfortably completes within the timer period (16.667ms for 60fps). If it's far under this threshold, then the other things happening in the runloop shouldn't regularly push it over the threshold.
2. Change the animation code so that it does not expect a regular period and animates the scene based on how much time has passed since the last animation. This is not always feasible - see this time-based animation tutorial.
3. Set the timer on a seperate thread (not the main thread).
   
4. Use a thread with its own custom loop rather than a timer. This in itself is not a solution if the rendering regularly exceeds the desired frame rate period, however can improve the smoothness of the animation when combined with some of the other things in this list; it also gives you greater control over when to draw the next frame when the previous frame has overrun, instead of being forced into multiples of the timer.
5. Increase the timer period and only render the scene when an appropriate amount of time has passed (oversampling).
6. Decrease the frame rate; however it can only be decreased so far before it starts to look bad.
7. Decouple the drawing from code that is not directly related to rendering (such as physics simulation or animation logic) - see this blog on fixing the animation timestep for a good overview of this approach.
8. Synch to the hardware refresh. This is typically what console games do and would be the best approach in many situations. Unfortunately this not currently possible on the iPhone as no hook or callback is provided by the underlying APIs.
   

My preferred approach is a combination of 1, 2 and 4. If option 8 was available I would go for a combination of 1, 2 and 8.