9

One subfield of computer science that used to be quite popular is the computational complexity of playing particular games. At the end of the 1900s there was a slew of research on this, examine games ranging from the universally known such as Go and Chess to the more obscure such as Sim and Domineering. A look at the Wikipedia page shows that many papers along these lines were published not only in specialty venues, but top CS Theory venues as a whole such as SIAM Journal of Computing, J. Combin. Theory Ser. A, and STOC.

Over the past years, there have been a number of papers along these lines, primarily targeting computer games such as Bejeweled, many classical Nintendo games, and Pokémon. These later publications tend to be not published in peer-reviewed venues, or published in venues far less mainstream than the previous wave. Looking at some algorithmic game theory proceedings and journals, I’ve noticed few have papers on particular games. Instead, they tend to focus on AI playing games or more wholistic theoretical concerns not restricted to particular games.

My questions are:

  1. Is this assessment of history correct?
  2. Assuming the answer to #1 is yes, has something changed in the culture or interests of computer scientists that has lead to this?
  3. Are results along these lines no longer considered publishable?

Some context: I’m a young computer science researcher who hasn’t ever paid much attention to this field, but who has recently started dabbling in examining the complexity of games with my gaming buddies. I decided to do a preliminary literature review and was surprised by this pattern I’ve noticed.

closed as off-topic by user9646, scaaahu, Buzz, Massimo Ortolano, Scientist Jul 15 '18 at 12:51

This question appears to be off-topic. The users who voted to close gave these specific reasons:

If this question can be reworded to fit the rules in the help center, please edit the question.

  • 4
    A substance-related question like this might be a better fit for CS.stackexchange, perhaps. – henning Jul 14 '18 at 17:37
  • @henning I was back and forth on it, but I feel like this is ultimately more of a question about cultural attitudes than about any particular technical points, which is why I decided to post it here. It is certainly true that answering this is probably outside the experience of anyone who isn’t a computer scientist (maybe a mathematician or economist?), but it’s fundamentally not a question whose answer is statements about computers, but rather a question whose answer is statements about computer scientists and their behavior. – Stella Biderman Jul 14 '18 at 17:39
  • 3
    This might be a good question for cstheory.stackexchange.com I think your assessment is correct, although I’ve never looked into it. I think the issue is that the first few examples of NP-complete games are interesting, but there is not so much interest in example number 83. – Thomas Jul 14 '18 at 17:57
  • 1
    @Thomas That is a good point, and raises the question of what is “interesting enough.” Someone tried to prove that Magic: the Gathering (a physical card game) was Turing complete a few years ago but wasn’t able to finish the proof. IIRC there aren’t any known examples of physical games that are Turing complete, though some building games like Minecraft and Dwarf Fortress are. Those are pretty different from two player strategy games though. – Stella Biderman Jul 14 '18 at 18:01
5

(Expanding my comment.)

I think your assessment is correct -- it's much harder to publish results of the form "game X is NP-hard" today than it was last century -- although it is not something I've looked into.

I think the reason for this is the following.

The first few examples of NP-hard games are interesting. It means we can say "many games turn out to be NP-hard". That helps motivate research on NP-hardness and helps scientific communication with the general public.

However, once, say, half a dozen examples have been established, what is the value of adding more examples? Of course, there is value in having more examples, but it becomes more marginal. Each successive example is less surprising and doesn't really change the above statement.

Moreover, many of these proofs are quite messy -- not the sort of thing a reviewer is keen to work through.

Note that this phenomenon is not exclusive to results about games. I think there are many papers that struggle to get published today even though they'd sail in 30 years ago. For example, Karp's 21 NP-complete problems is a celebrated paper, but a similar list of NP-complete problems would struggle to get published today. The reason is simply that those 21 examples were surprising then, but are not today.

An important side note: In essentially all examples, the original game is not NP-hard because it has a finite, albeit extremely large, state space. Thus the NP-hardness is proved about some generalization of the game. Such as Chess on n-by-n boards with slightly modified rules.

  • 1
    +1: The comparison to Karp’s list is really good. It hadn’t occurred to me, but is a really good comparison that supports your narrative quite well. Something that’s implicit but not drawn out of your answer is that papers like these aren’t progress within some sort of framework. If I was to discover a new class of functions that the Sensitivity Conjecture was true for, I would be building towards something: proving the sensitivity conjecture for all Boolean functions. That’s not the case here. – Stella Biderman Jul 14 '18 at 18:21
  • My impression was that interesting games (suitably generalized to arbitrary-sized boards) tend to be complete not for NP but for polynomial space. Is that impression accurate, or was I just looking at a biased sample? – Andreas Blass Jul 14 '18 at 19:07
  • @AndreasBlass Yes, most games involve unbounded alternation, which naturally leads to PSPACE-completeness. However, I'm not an expert on these sorts of results. – Thomas Jul 14 '18 at 19:10
  • @AndreasBlass Yes, many games are EXPTIME-Complete or PSPACE-Complete. The Wikipedia article I link to in the OP has a table with many known results. – Stella Biderman Jul 14 '18 at 19:30
  • @AndreasBlass Yes, I should be more precise in my answer. I changed "NP-complete" to "NP-hard" to capture all the harder classes. – Thomas Jul 14 '18 at 19:41
2

I'm going to say that your assessment isn't correct (point 1). I'd also suggest that the Mathematics site here might be an even better venue for a question such as this. Here is why.

It isn't so much that game theory (complexity, solvability, completeness, ...) isn't interesting any more, but that it is the techniques applied to any given game can be new or old. The same is true of Mathematics in general. If I prove a new and wonderful theorem of any sort in math or cs, using "well-worn" techniques, it won't be interesting to very many people. You can make a lot of cookies with a a good cookie cutter. However, if I prove something with a novel and previously unknown attack, people will go wild. Well, those deep in the particular weeds of that field anyway. Whoa, a bitcoin powered AI cookie cutter. (Sorry.)

My own work from long ago is an example (Math Analysis). At the time I wrote it there were only about five people in the world who could read and analyze it comfortably, including myself and my advisor. I say that just to indicate how obscure a sub-topic it was, not to suggest anything about my ability. The main result was "very nice and a bit more than most dissertations offered", so said another professor who tried to grasp it (a committee member). So far, no big deal. However, the main result used a completely new methodology and a seemingly orthogonal attack on the problem. That is what made it interesting enough to be published in Trans. AMS. It just wasn't the sort of thing that would occur as a matter of course to others, even weed-dwellers.

On the other hand, it was getting extremely difficult to prove much of anything in that small area then as the ground had been so well trodden. The study of Analysis moved on to other areas in which less was known and more could be learned. Suddenly there were lots of papers in the new direction and few in my chosen somewhat weedy field.

But a paper now, to be published in Classical Real Analysis, has to be quite interesting in its techniques, not just its results, unless, of course, it concerns a classic unsolved problem.

So, I think the issue isn't whether games are interesting or not. It is what is new that you can show about how to attack an interesting game. And the problem gets harder and harder as the field gets more and more "trodden."

But that, I think, is true of any mathematical field, including much of theoretical computer science. Show us a new way to attack problems and we will wake up.

Not the answer you're looking for? Browse other questions tagged or ask your own question.