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.
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.
 | |
| 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.
Comments
Post a Comment