Is it possible to stuff a really challenging backgammon game into a mobile
phone? And still have fun with it? The authors asked themselves these questions when they started a project a few years ago that led to the creation of BGBlitz2go. BGBlitz2go is a backgammon game that runs on your mobile phone. Version 2.0 was recently published.
There were a lot of obstacles to overcome. First, there are thousands of devices on the market, having many varying specificationsdifferent screen sizes, different amounts of memory available, vastly different speeds, all kinds of keyboards and touch screens. Every mobile phone has it own quirks and capabilities.
Instead of megabytes or even gigabytes of memory, you have to
restrict yourself to kilobytes. The desktop version of BGBlitz uses more than 50 megabytes of RAM at runtime, whereas BGBlitz2go needs to fit in less than 500 kilobytes. That means a mobile phone has only 1% of the memory resources available that the desktop version needs!
The neural nets alone of BGBlitz desktop use more than 1 megabyte, so it was obvious that a smaller net was needed, and a compromise between playing strength on one side and memory usage and performance on the other side had to be found.
The first version of BGBlitz2go had 40 hidden neurons and 3 million games of supervised training using the desktop BGBlitz. Now two years have gone by, and mobile phones have more resources, so version 2.0 uses a self-trained net with more than 20 million practice games and 60 hidden neurons. And the old net had some quirks, especially in the endgame, that now seem to be resolved.
A lot of (older) phones have no floating point at all or slow
floating point capabilities, but neural nets need floating point
calculations. So we had to recode our nets to use fixed point math,
which was again a trade-off between speed and precision where we
had to learn some lessons until we got it right.
The effective CPU speed is several orders of magnitude smaller on a mobile phone. A Sony-Ericsson K750i (bought in late 2005) evaluates approximately 80 to 100 positions per seconds with the version 2.0 net. A current middle class phone like the Sony-Ericsson K770i evaluates about 250 positions per second. And my recently bought Nokia E63 evaluates 350 to 400 positions per second.
On a recent Core2 Duo, BGBlitz evaluates roughly 50 000 positions of
the much larger net on only one core! My Intel quadcore (Q6600) evaluates 170 000 positions per second. The higher
clock rate, extremely fast special function units (SSE, FPU, branch
predictions, etc.), a hierarchy of CPU caches, and much RAM that the
desktop version uses to cache positions adds up to a huge speedup.
We are talking about a speedup factor of 100-1000.
In version 1 of BGBlitz2go, we had to restrict the evaluation to 1-ply. Two-ply evaluation was added in the new 2.0 version. Depending on your patience, 2-ply evaluation will be usable with a phone that evaluates more than 150 positions per second. So a recent middle class
phone will probably work fine. Beyond 300 evaluations per second, the response times are similar to a human opponent.
We did some 3-point matches with 2-ply and fed the matches into Gnu Backgammon to analyse the playing strength. The results were
satisyfing: An error rate beyond 2 and a rating over 1970 is more than
we expected, given the restrictions we just demonstrated.
Can it be fun to play backgammon on a screen that is just a little larger than a stamp? With a limited keyboard? Good question! Because the screen is small, the information has to be very condensed. And, because the keyboard is small, every key press is cumbersome, so we had to strive to avoid any unnecccessary user interaction.
One of the authors has a collection of dedicated backgammon computers
from the 70's and 80's, all playing stupid and with vastly different user interfaces. Most user interfaces were simply bad. Just the Gakken and Saitek sensory board had some good details. And the Mephisto had a really good interface.
We blended the best ideas of those computers with what we already had and polished it for version 2.0. We think the user interface is at a point where BGBlitz2go really shines. In most situations you can make a move by simply pressing 3 times with the navigation button and maybe clicking one or two times with the navigation left, right, up and down. It is really intuitive. As a tester said, "After you get used to itit takes about a
minutethe usage is dead easy."
But there are a lot of features packed into this
small game. You have several themes to choose from, a tutor to help
improve your own game play, a pip counter. Most keys (e.g., 1, 3, 5, 7, *) are mapped to functions such as showing you "best moves", board evaluation, and a winning probability graph.
A recent addition, for all those that want to play other people, is a FIBS client which allows internet game play, with integrated
repbot and chat functionality. This gives you the ability to play on
FIBS anywhere, anytime.
the best moves
Strangely, one of the hardest things to deal with is that many users think
the game cheats. Humans very easily remember when the opponent is
lucky, but we are not so good at remembering our own luck, or when the
opponent is getting really bad dice.
We have tried our best to convince users that BgBlitz2go does not have to cheat. It is simply a very good AI. Users can preview the upcoming dice, replay the game with the same dice trying new techniques, and even reverse the dice allowing them to play the other side of a game. We hope this will convince users that we do not cheat with the dice.
With all these features, you might think that there is nothing else for us to do. On the contrary, we have quite a few ideas on how to improve
the game and add more stuff. So be sure to visit www.bgblitz2go.com to see the latest updates. And, if you haven't already, download the game and try it out.
Have fun and always good dice,
Frank and Markus