Sat-navs, 2048, and what does operational research have to do with them?

Last year I wrote a blog about 2048, the addictive game which came online then, which has spawned apps for Android and iOS, and has led to discussion about using artificial intelligence (AI) to play online games.  As that blog has had numerous hits, I felt that it was worth returning to the topic.

First, a paragraph about operational research (O.R. or operations research or management science). O.R. is the science of decision making, the science of making management better, the science of asking "What's best?" and answering it, or the science of asking "What happens if a change is made?".  Some people say that O.R. is the hidden science, because nobody has heard of it - but it is used by almost every company on every stock exchange in the world, by public utilities, by governments and charities.  O.R. is the science that ensures that there is a mast in the right place and with the right frequencies for your mobile phone.  It is the science that determines the price for your next train or plane ticket.  It is the science that routes your eBay purchase from vendor to you.  It is the science that stocks up your supermarket with ice-cream before a hot weekend.  And much else.  (Yes, I am an enthusiast - but I have seen how O.R. helps managers and workers, customers and passengers.)

The ideas which give simple rules for playing the game 2048 well are rather like the rules which are programmed into your sat-nav or route-finder on your tablet or computer.  The most important underlying principle for playing the game well is to choose a corner and aim to get the cell with the largest value on the grid "stuck" in that corner.  Then the cell with the next largest value should be adjacent, along one edge, the next largest adjacent to that and when an edge is filled up, those cells form an edge for the rest of the game.  I choose the lower right-hand corner, and that means that I use the "down" and "right" buttons for as long as I can.  Those two are my preferred moves.  When I can't use one of these, then I am forced to use "up" or "left" - because I stack my cells on the right hand edge, I do not use "left" unless I really, really have to.  (And almost invariably, this means that my game is in trouble.)

So, what are the parallels between playing the game and the sat-nav?

Both have an objective;
2048: to get a cell with value 2048 (or higher)
sat-nav: to get to the destination on the best route possible.

Both break achieving that objective into a series of manageable steps;
2048: each movement of squares is a step in the game; you make a decision about what to do after each movement;
sat-nav: the route is broken into steps at each road junction; (in theory) the program makes a decision about which route to take at each one.

Both work with extremely simple rules:
2048: keep the cell with the largest value in a corner (and the rest in an ordered pattern)
sat-nav: choose the best route to the destination from each road junction.  (This is a rule which is sometimes known as Bellman's Principle, after an American scientist - who I would have liked to have met - Richard Bellman.  He put into mathematics an idea which is simple and should be obvious.  If the best route from A to C goes through B, then the best route from A to C is made up of the best route from A to B followed by the best route from B to C.  This is useful, because it saves the sat-nav computer calculating routes over and over and over again.)

Both need to deal with the situation when things go wrong:
2048: it may be bad luck, or you may have made a mistake (which is why some versions of 2048 now include the facility to "undo" moves)
sat-nav: the driver may miss a turning, or there may be a blockage

So, when things go wrong, the objective may be changed temporarily:
2048: try and put it right, while keeping the structure of the cells as "tidy" as possible (and "Tidiness" will depend on what went wrong.)
sat-nav: either recalculate the whole route - so the objective becomes the best route from wherever you have got to, or make the objective that of getting back on the right route as soon as possible

Both look several steps ahead:
2048: although the game has a random element, it is still possible to look a few steps ahead and make choices of your preferred moves accordingly
sat-nav: looking ahead means that the direction is not always pointing towards the destination - it may be better to choose a faster road than to head in the compass direction.  (I sometimes explained to students that the motorway system in the UK meant that some sat-nav optimal routes would take the driver along three sides of a square, seen on a map, simply because there was no good direct road.)

And what is this to do with O.R.?  Simple; rules for sat-navs have been developed by people with expertise in one branch of O.R..  It's the hidden science in the electronics, or in the app on your tablet or phone.  So when you are playing 2048, you are actually doing O.R.!  And if you want to know more, contact one of the many O.R. societies in the world - such as the UK Operational Research Society, or the American INFORMS

Comments

Popular Posts