Jason (jcreed) wrote,

I'm in jetlag can't-sleep-'cause-it's-a-bright-and-sunny-morning-in-my-mind limbo so obviously I started wondering whether a certain decision problem is NP-hard or not at 5am.

It started out as an abstract single-player game idea: you have, like, a planar graph that you think of as a Risk-map, a bunch of little territory connected to each other in some way. There is a territory that you start out "owning", and each territory is labeled by a list of pairs of (resource, int). Kamchatka might have on it [(silver, -5), (caribou, +1), (armies, -10)] or something like that. An action consists of taking over a territory adjacent to some territory you already own, adding its resource-vector to the running total of how many resources you have --- has long as it doesn't involve spending resources you don't have. If I currently have [(silver, 6), (armies, 9)], I can't take over Kamchatka yet, nor could I if I'm not in possession of any territory next to it, even if I did have more armies.

So, decision problem: given a map, an initial territory, and an initial vector of resources, can I take over the whole map? Assuming my 5am brain has not made any errors, I think it's a cute not-very-hard puzzle to see that if there's only one type of resource in the whole map, it's easily in P, and if you allow at least two types of resources, it's NP-hard.

Question I don't know the answer to yet: how hard is it when you restrict to only one type of resource to be mentioned per territory but allow multiple types of resources in the map as a whole?

Separate squishier question: can this actually be made into a fun game? It feels very dry and "woo I am trying to solve an NP-hard decision problem" to me in its present form. Is there a good way to automatically generate "tight" problems, maps that are solvable but suspensefully just-barely-so?
Tags: games, math

  • (no subject)

    Some further progress cleaning up the https://xkcd.com/1360/ -esque augean stables that is my hard drive. Tomato chicken I made a couple days ago…

  • (no subject)

    Did some personal archaeology. Helped a little with laundry. Threw some chicken, onions, tomato, stock, peppers in the slow cooker and hopefully…

  • (no subject)

    Dinner with akiva and dannel at nuevo portal in carroll gardens. Ate a pile of chicken stew and rice and beans and maduros, good times. I do miss…

  • Post a new comment


    Anonymous comments are disabled in this journal

    default userpic

    Your reply will be screened

    Your IP address will be recorded