4
$\begingroup$

I am new here. I have no idea is it appropriate to ask the complexity related question of a algorithm of a fun game at cs theory? So I'd like to find out whether or not it is appropriate first.

My question:

2048 is a very hot game on the Internet(http://gabrielecirulli.github.io/2048/).

We randomly select the side(up,down,left,and right). Stop the algorithm when 2048 is reached. What's the complexity of such algorithm?

$\endgroup$
3
  • $\begingroup$ there is some serious academic study of complexity of video games, board games, etc. ... you can also try Computer Science which has a more liberal policy $\endgroup$
    – vzn
    Mar 31, 2014 at 15:17
  • $\begingroup$ just wrote this up, it is a collection of computer scientific papers on video games, several tcs.se questions on the subj, etc... idea, think it would be great to have a tag for it on the site but "the mgt" might not go for that... re 2048 game, afaik it has finite size & therefore might have "no complexity" unless there is some way to generalize expanding the board. that is a key aspect of studying game complexity glossed over by many... $\endgroup$
    – vzn
    Mar 31, 2014 at 22:53
  • $\begingroup$ looking over the bkg/rules for the game (wikipedia). it has a significant random component on what tiles are dropped down & without more info one would have to make assumptions about probability distributions of tile values to analyze it. its also similar to the 15-puzzle in the square movements & grid size (there is one question on that on the site). yes tcs-related generalizations could be studied (as with other games), the most natural is to study an n x n board. similar cs.se Q/A on dominosa $\endgroup$
    – vzn
    Apr 1, 2014 at 5:25

2 Answers 2

Reset to default
1
$\begingroup$

heres a paper at ECCC on the subject of complexity of 2048 game & variants. complexity of (popular) games is subject to some TCS research in general, there are a few papers & questions on the site on the subj, eg some tracked here. there is also some academic study of video games etc.

2048 is (PSPACE) Hard, but Sometimes Easy / Mehta

We prove that a variant of 2048, a popular online puzzle game, is PSPACE-Complete. Our hardness result holds for a version of the problem where the player has oracle access to the computer player's moves. Specifically, we show that for an nn game board G, computing a sequence of moves to reach a particular configuration C from an initial configuration C0 is PSPACE-Complete. Our reduction is from Nondeterministic Constraint Logic (NCL).

We also show that determining whether or not there exists a fixed sequence of moves of length k that results in a winning configuration for an nn game board is fixed-parameter tractable (FPT). We describe an algorithm to solve this problem in O(4kn2) time.

$\endgroup$
2
  • 2
    $\begingroup$ I'm actually the author of this paper -- thanks for providing the reference! This isn't exactly the game that's online, but a close variant that we chose to examine for technical reasons relating to our proof. $\endgroup$
    – rahulmehta95
    Sep 16, 2014 at 2:59
  • $\begingroup$ :) @rahul welcome/ my pleasure, yes understand papers in this area often generalize the games for TCS angle/ purposes. the citation deserves to be on the main site instead of mere meta. & great to see you here, & creatively advancing the frontiers/ boundaries of TCS that as one can see, can be controversial at times... ps would be interested to hear more in Theoretical Computer Science Chat $\endgroup$
    – vzn
    Sep 16, 2014 at 3:46
2
$\begingroup$

As phrased in your question, it is unlikely to be on-topic here. However, that doesn't mean questions about games are off-topic, with the famous counter-example being the one on the Super Mario Galaxy problem. Asking a question about 2048 would take some subtlety.

I would recommend asking non-research level questions on CS.SE, but I would still suggest making sure first that you clarify all the words you use. The best questions are ones you tried solving yourself.

Finally, keep in mind that the above are my opinions based on a feeling of what the community prefers and a guess at how you would ask a question based on the evidence I have. I could very well be wrong and the community might love your question, I know that a number of cstheory-folks enjoyed playing 2048.

$\endgroup$
3
  • 3
    $\begingroup$ Suitably phrased it's probably fine. In fact, Michael Mitzenmacher already asked this question on his blog (see bottom of post): mybiasedcoin.blogspot.com/2014/03/… $\endgroup$
    – Huck Bennett
    Mar 30, 2014 at 21:37
  • $\begingroup$ @HuckBennett Thanks! Your information is very useful for me. $\endgroup$
    – Jill Clover
    Mar 31, 2014 at 8:52
  • $\begingroup$ Thanks. I got your point. is it fine to cite Michael Mitzenmacher'words to ask such question? "has anyone figured out the complexity of the 2048 game yet? Assuming that the game uses some stochastic model at each step, I wonder what you can say about the probability of getting to 2048 under some model of play. That's a stochastic model in need of analysis." $\endgroup$
    – Jill Clover
    Mar 31, 2014 at 8:54

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .