Course:CPSC312-2017-2048

2048

Authors: Michael Yau, Jack Ding

What is the problem?

2048 is a popular single-player mobile sliding puzzle game. The objective is to slide numbered tiles around the board which combine to form larger numbers, eventually to create a tile with the number 2048.

A brief description of the game mechanics can be found on the Wikipedia page:
https://en.wikipedia.org/wiki/2048_(video_game)

The Android version of the game can be found on the Google Play Store:
https://play.google.com/store/apps/details?id=com.androbaby.game2048&hl=en

We will implement 2048 using SWI-Prolog, playable via command line. Gameplay is extremely simple, with only 4 moves available at any given time (a swipe up, down, left, or right).

What is the something extra?

We will have two in-depth components. First, we will attempt to translate the command-line version of the game into a GUI application using the XPCE native GUI library. Second, we will perform some research on designing optimal algorithms for solving 2048, and then create a simple AI with the goal of achieving as high a score as possible.

What did we learn from doing this?

General Comments

2048 is a fairly simple game with only a few rules. Every component that needs to be implemented can be summarized as follows:

Storing the game board as an NxN matrix (N is typically 4) of integers, where empty tiles have a value of 0
Sliding the game board in one of the four directions - this amounts to recursively 'sinking' all the elements in each row or column in the direction of the move (Blob ListOfBlob from CPSC 110, anyone?)
Adding up the score from any combined elements and making sure the sum of scores propagates to the highest level in the game state
Generating a random tile (with a value of 2 or 4, which have probabilities 0.9 and 0.1 according to the original implementation) at a random empty location on the game board
Displaying the game board in the console output in a generic way, regardless of how large the board is
Creating a game loop that continuously reads user input, performs an action, displays the game state, and then starts over again - although this is really just infinite recursion since we're using Prolog
Ending the game when no further moves are possible
Any additional 'helper functions' (relations) needed to manipulate lists or matrices and grab information from them (largest element, position of largest element, number of empty tiles, etc.)

In the end, implementing 2048 in Prolog was fairly straightforward. Recursion on lists (which comprise a majority of the program) can be done very intuitively because of their cons-style construction. Also, any 'action' which appears difficult to implement but has a simpler logical equivalent can be rewritten very easily. For example, the game board is represented as a length N list of lists, each of length N. This means that rows can be traversed easily, but columns require a bit more thinking. Fortunately, we do not need to think at all, as we can simply transpose the matrix, traverse the rows, then transpose it back. With well-defined relations, this is only a few lines of code!

User Interface

We did not end up using XPCE due to it adding a bit too much to the project scope and being somewhat irrelevant to the concepts we have been covering in class. Instead, we focused our efforts on improving gameplay and building the 'AI'. However, the game board is still very nicely printed to the console. See for yourself!

AI

A quick google search reveals a StackOverflow thread with several reportedly very good algorithms for solving 2048:
https://stackoverflow.com/questions/22342854/
...some of which have 100% win rate (obtaining at least the 2048 tile, although the most popular algorithm goes as high as 32768 on 36% of attempts). Implementing most of these algorithms in Prolog is out of the question (for this project), as they can get fairly complex after considering many optimizations and heuristics.

We chose one of the simpler approaches, where we use a multi-depth exhaustive search algorithm that favours empty squares, performing the move which maximizes the maximum number of empty squares at any step after performing D moves (for search depth D). A comment on runtime complexity: since there are 4 possible moves per step, and at each step we need to count over N^2 tiles for a NxN board, the cost per move is O(4^D * N^2).

Averaged over 10 trials each, this is the performance (score obtained) of our algorithm:

1157 (randomly chosen moves)
2757 (depth-1 search)
5932 (depth-2 search)
4409 (depth-3 search)
2705 (depth-4 search)

A score of 5000-6000 is roughly equivalent to 512 being the highest tile on the game board.

It seems that this algorithm actually does not work very well (compared to some of the proven better algorithms, no, but compared to me playing the game, it's pretty good). One hypothesis is that because this version of the game (which is the official version) is not deterministic, the algorithm makes an assumption about the position and size of new tiles (without considering weighted probabilities, etc.), but the position of new tiles will likely be different when the predicted moves are actually performed. This is one of the main drawbacks of this approach, and possibly a reason why increasing the search depth (surprisingly) does not improve performance (worsens it, actually). We can infer that the impact or cost of making these guesses increases as we increase the depth of the search.

Conclusion

Overall, we are satisfied with these results. Prolog is an excellent candidate for succinctly coding many different kinds of search algorithms, which is perfect for tasks such as implementing a solver for 2048. Given more experience working and getting familiar with the language, it will be possible to write much better solvers than the one we have here.