Monday, 24 March 2014

Artificial Intelligence, Operational Research and 2048

Over the past month, the online puzzle game "2048" has gone viral; it has a very simple structure, a 4 by 4 grid, filled with powers of 2 and blank spaces.  Initially there are two occupied cells, values 2 or 4.  (I think that having a cell with value 2 is much more proabable than having a cell with value 4 at the start.)  Thereafter, the game uses the arrow keys to move tiles left, right, up, and down (L,R,U,D). If two tiles of the same number collide while moving, they will merge into a tile with the total value of the two tiles that collided. If the tiles would not move when this happens, nothing happens.  Every successful turn, a new tile will randomly appear in an empty spot on the board with a value of either 2 or 4.  The aim is to merge cells until you get one cell of value 2048.

A winning positions, from Wikipedia (c) 

 There have been several derivative games, using similar rules.

One of the tools of O.R. is game theory, and that lends itself to thinking about 2048.   You, the player, are playing against an opponent.  You can either assume that the opponent plays randomly, which makes it a single player game with incomplete information; or you can assume that the opponent plays optimally in order to try to defeat you.  Whichever assumption you make, there will be a game tree of positions that will be reached ahead of your successive moves (that is "if I move L/R/U/D, then certain cells will merge, and then the computer will select an empty cell and place 2 or 4 in it" for positions ahead of the next turn, and this can be repeated for two turns, three turns).  The game tree rapidly gets quite large!  In many positions, you will not have all four possible moves - in some cases there will only be one possible move. Another approach would be to think about it as an instance of dynamic programming.

One interesting aspect of the game is that as you get cells with successive high values (16, 32, 64, etc) the game becomes tougher, reflecting arcade games where success at one level leads to a more difficult level.  This is part of the attractiveness of 2048.  If you have achieved the modest success of a cell with value 128 with 16 cells to use, then the next cell with value 128 must be achieved with 15 cells to use, and the obstacle of the first cell value 128 that moves around the box with your successive turns.  And then comes 256 and to get to 512 you must manoeuvre around a cell with value 256 and another with value 128.

So what does game theory tell us about 2048?  First, that it is unlikely that anyone can completely analyse the game; this is true of most games with an element of randomness in the response to a move.  Therefore, one must approach the game with one or more heuristic rules, aimed at trying to win, by selecting a move which is "good" on some measure. 

This is where the programmers and artificial intelligence fraternity come alongside operational research people; what are good rules?  How can they be codified?  So there has been a great deal of discussion and challenge to devise programs that play against the (open source) code of 2048.  Rules such as "merge whenever possible" and "maximise the number of empty cells" have been proposed.  More subtle are those that look at the "shape" of the cells - for example it is not a good idea to have a box of high values around a cell with a low value.  So the value which we place on these rules lead to surrogate measures of the strength of the board.  Sometimes the rules may be in conflict - what do we do then?

Now, this is the "fun" side of O.R. - we have tools which can look at a game like this, recognise that it has features in common with other games and situations we have come across, and start to analyse it.  But the analysis has similarities to practical O.R. - we often have to measure surrogates rather than the objective of interest.  And when we do, it is important to keep an open mind and be prepared to look for better ones as we gain experience. 

Now, go away and play the game 2048 for yourself.  See what rules you will apply to try and get a high score.

And if you teach O.R., and your institution is tolerant of such excursions into "fun", spend a little time with a class working on this or a similar game as an instance of O.R.

Friday, 14 March 2014

What shall we do with a railway line like Dawlish?

Over the past two months, there have been numerous articles, speeches and discussions about the railway line at Dawlish, on the Devon coast, just a short way from Exeter.

There has been so much discussion on the internet that Google's auto-complete feature suggests "Dawlish railway" as soon as you enter "Dawlish".  In the first week in February, during a series of severe storms, the sea wall at Dawlish was destroyed and the railway track left suspended over a void.
(c) Getty images
Needless to say, no trains could run along the track.  And as a result, no through trains could run from Plymouth, Torquay and Cornwall to London - or anywhere else in mainland Britain.  The line through Dawlish is the only railway link between western Devon (and Cornwall) and the British railway network.

It wasn't always like this.  In the great days of railway travel, there were other routes that linked  the western end of the peninsula with the rest of the UK, but in the cutbacks of the 1960s, only the one line was left.

Dawlish has always been a problem for the railway line.  In winter storms, waves frequently wash over trains on the line, and services may be interrupted.  But the damage last month is far more serious than ever before.  It will be April 4th when the first trains can run again, after intense engineering work on the line, the sea wall and sea defences.  With eight weeks without a rail link, businesses all over Devon are counting the cost, with estimates of £5million lost per day. 

Proposals for alternative routes have been put forward.  The BBC report gives a very good summary of the five alternatives, of which three are essentially variations of the same concept.  Emotions are running high for some action, and several commentators draw a parallel between the investment in the infrastructure of Devon and the money that is planned to be spent for the high speed rail link between London and the north of England.  Why not invest in links to the west of England as well (or instead)?

So where can O.R. help?  Let's call the three alternatives A, B and C.  A is a line from Exeter to Plymouth, via the towns of Okehampton and Tavistock.  That would follow a former route, closed in the 1960s.  It would be the "easiest" to build.  However, it would link Exeter and Plymouth but bypass Torquay and south Devon.  It would be inconvenient to use as trains would have to be reversed in Exeter and Plymouth because of the track layouts.  B uses an old line from Newton Abbot to Exeter, which has been closed for fifty years, and whose tunnels would need to be reopened, possibly rebored.  C would be close to B, following one of three routes to bypass Dawlish by going through new tunnels. 

Engineers and economists can produce costs for each of these.  O.R. can produce models of demand for train services along the lines, and can help bring some rationality to the emotive atmosphere about possible decisions.  Here are some considerations

(1) Should the line at Dawlish be closed completely in favour of a new route?  That is not on anyone's agenda; the route through Dawlish is (a) picturesque and popular with holiday visitors (b) fast (c) a good link for the urban areas of south and south-west Devon

(2) If any of the options is chosen, will there be regular services all year round on that line, or will it simply be kept as a "Spare part" in case the line at Dawlish is broken?

(3) How much will it cost to keep a line in reserve "just in case"?

(4) If a line is used regularly, how often should trains run, and should they be through trains to other parts of the UK?  What would the demand be for such services?

(5) ... and more difficult ... what is the expected time before the line at Dawlish is broken again?

(6) What would cost-benefit show for each of A/B/C in the absence of emotion about "being cut off"?  Can one justify any of A, B or C on the basis of regular use?

Currently, the main line between Exeter and Plymouth/Torquay is well-used.  It is not used to full capacity - more trains could be run along it if there were sufficient demand.  So one cannot justify having two lines to Plymouth on the basis of demand for train services.  Potential demand from communities that would be served by A/B/C is small and thus there is only a slight economic case for those lines in the absence of the problem of Dawlish. 

I fear that the rational discussion may be drowned (pun intended) by hysteria about "remember Dawlish in 2014". 

Meanwhile, a "2014 Railways of Dawlish" calendar is still on sale here