72

It just means that you can create levels or puzzles within these games that encode NP-Hard problems. You can take a graph coloring problem, create an associated Super Mario Bros. level, and that level is beatable if and only if the graph is 3-colorable. If you want to see the specific way the NP-Complete problems are translated into the games, I recommend ...


21

I honestly don't know exactly what kind of model is used by the people making those claims; however, what seems reasonable to me would be talking about the $\mathcal{NP}$-completeness of deciding something about a game situation. Let's take as an example Tetris, since it's the only one from those you quote that I understand enough to talk about. Tetris has ...


7

At a stretch it is an expert system (such as fuzzy logic). As you are not running an algorithm to perform feedback onto the decision parameters based on the output, it's not really learning. However, performing feedback is not the only indicator whether an alogirthm is AI. One could argue that if it acts in a way that appears intelligent, that's all that ...


7

In theory, yes, a peer-to-peer validation network could be used to enforce any unique content (not just money) assuming a sufficiently large validation network. "Sufficiently large" is the catch. Bitcoin validates transactions by having the network nodes "vote" on the transaction's validity. According to Satoshi's proposal: The system is secure as long ...


4

Section IX of the following paper proposes a variant of your idea: OpenConflict: preventing real time map hacks in online games. Elie Bursztein, Mike Hamburg, Jocelyn Lagarenne, and Dan Boneh. IEEE Security & Privacy 2011. The difference is that they propose that detection can be done by the central server, after the fact, by analyzing all of a ...


4

Yes to both of your questions. Both are those are feasible. At least, the second one is certainly feasible; to the extent that I understand the first scenario, I believe that's possible too. There are even existing systems that do something like this. For instance, Namecoin is a system for registering domain names that uses a Bitcoin-like blockchain. ...


4

Your problem is equivalent to asking whether there is some linear combination of row vectors from your $\mathbb R^{m\times n}$ matrix that has all coefficients positive and sums to a vector in which (a) every element is $\ge 0$ and (b) at least one element is $> 0$. (Notice that the order of the operations doesn't matter: Running them in some order might ...


3

No. The gamer will basically have to work out the SAT problem in their head. Think of any video game puzzle you've solved that wasn't easy. You probably solved it by working out a simpler version of the problem and then solving that. If you "complexify" SAT into a video game level, the best way to solve the video game level will be to simplify it ...


3

This should be solvable with linear programming. Background and setup Let the state vector be a vector of the count of number of each item you have. If the possible items are milk, wheat, sugar, egg, cake, diamonds, then the rule 3 milk + 3 wheat + 2 sugar + 1 egg $\rightarrow$ 1 cake affects the state vector by adding $(-3,-3,-2,-1,1,0)$ to it. So, ...


3

GPUs are highly specialized: they are very good at a very small number of things, but they are extremely bad at everything else. CPUs are general: they are mediocre at everything. GPUs are good at applying the same operation out of a small number of potential operations, and in particular, the same very simple operation to a lot of identical things. E.g. ...


3

From your explanation I assume that the game is not episodic, but sequential: each move outcome is dependent on the previous moves. The Minimax algorithm modification you explained is called Expectimax and is generally a standard approach for such problems as far as I know. In order to avoid the big branching factor you can try some variation of the Monte ...


3

Let's collect what facts we can determine: The sum of all counters $S$ will change by $T-P$ with each cycle of $T$ steps, where $P$ is the number of positive counters at the final step of the cycle. If you end a cycle with $P=T-1$, you have $S\le(T-1)(M-1)$. During the following cyle you can reach $S=(T-1)M$ after $T-1$ steps, but in the next step you will ...


3

A Hidden Markov Model could be useful here. Basically you have a Markov Chain of internal states (e.g. "i just jumped", "i'm running", "i'm ready to jump again") and for each transition of the internal state it generates an action (e.g. "f" or "j") according to a distribution that is different for each internal state. You will need to figure out how many ...


2

If you have to create the maze: Without boundaries Generated uniformly Generated from a seed It is unfortunately impossible without risking an endless loop, but most times it is good enough to create a really large maze. Daedalus has lots of features and implements all the algorithms on this page. To generate a really big maze in Daedalus, start the ...


2

For single player games, you can always ask the question "is there a winning strategy for the player", and that question often has a "YES" answer that can be verified in polynomial time, and may very well be NP complete. For two-player games, the answer can very often not be verified in polynomial time, because to verify that a move for A is a winning move,...


2

"Binary toggling games" are generally just arithmetic problems over GF(2). Your particular problem is equivalent to the following over GF(2): $$\sum_i V_iS_i = 1 + A_M $$ If we write $\vec{S} = [S_1, S_2, \dots]^T$ and $V = [V_1, V_2, \dots]^T$ we find that your problem is actually a simple matrix equation over GF(2): $$V\vec{S} = 1 + A_M$$ You can ...


2

I think you are referring to Hamming Distance. See http://en.wikipedia.org/wiki/Hamming_distance. As for a game, having the extra condition that intermediate modifications must be real words is the Word Ladder. See http://en.wikipedia.org/wiki/Word_ladder.


2

One reason why it is not obvious that reachability of SMB is NP is that we would need a complete formalization of SMB, which the paper does not provide. This makes sense, as the purpose of the paper is to showcase techniques for proving NP- and PSPACE-hardness of reachability problems in generalized video games, and to do that they only have to fully specify ...


2

As you have said in your question, non-cyclical resource production is easy to simulate, but let's describe the simple case before seeing how it impacts the answer. For our cookie-bakery scenario, this is the setup: $$ t_i=0,\ t_f=100 \\ C_i=567,\ C_{cpt}=0,\ C_{bpt}=0 \\ B_i=10,\ B_{cpt}=2,\ B_{bpt}=0 $$ The above describes the initial state of our game, we ...


2

The basic architecture of CPU and GPU are different. Modern CPU's consist of a set of cores. Each core has its own a set of registers, a ALU and a control unit with some private cache. In a CPU the number of ALU's (the actual processor) is in 1-100 range. In a GPU number of ALU's are in thousands. The register files are larger and is shared among multiple ...


1

Given a SAT instance A, another SAT instance B can be constructed such that if it is found satisfiable the satisfying assignment proves the unsatisfiability of A. But the proof is one-sided; if B is found to be unsatisfiable that in itself does not prove that A is satisfiable. This is accomplished by crafting B's clauses such that its variable assignments ...


1

I'm not sure there is a single "name" for this non-trivial situation -- not every situation you will run into will have a single "name" or terminology for that situation -- but there are multiple topics and concepts that seem relevant: As Draconis mentions, serialization or pickling are relevant for how to convert a complex data structure in memory into a ...


1

Machine learning doesn't seem needed, since the image of each unit is always identical. One approach is to obtain a clean image of each unit, and then use template matching to find all locations where the template occurs in the screenshot. You might be able to check all locations in the screenshot whether they exactly match the template image (you will ...


1

One approach that may be useful is to represent your field by a matrix and use a matrix vector product to test whether there is a winning position. Suppose we are playing connect $3$ and are testing whether player $A$ wins by a horizontal row, in this field: A A A _ B B _ _ B _ B B _ B A A A _ A A Construct a matrix $M$ by representing player $A$'s pieces ...


1

Here's a simplistic hand-waving explanation: Such games are in NP because "running" a player's behavior over the course of a game and checking whether s/he wins or loses can be done efficiently (we need it to be in polynomial time in the length of the game, but it's probably linear or $O(n \log(n))$-ish). Such games are NP-hard because the player's ...


1

Because Braid can simulate a variant of Rush Hour, which is at least PSPACE-hard. Additionally, Braid itself is undecidable because it can simulate a counter machine which is equivalent to a Turing machine, and thus determining if any general Braid level is solvable is similar to solving the halting problem, which is undecidable.


1

A hashtable is asymptotically optimal. Your analysis led you astray. The relevant parameter is the number of rules that exist (where each rule specifies a combination of two elements and what new elements that combination produces). Call this $m$. It's easy to see that any data structure will need at least $\Omega(m)$ space. You can't do better than ...


1

Without any way of creating an unmistakeable marker on the tape, this is not possible. (As far as I recall (cannot check right now), the tape in Manufactoria is actually bounded, which would make a difference, but let us assume this is not the case.) Let $i$ be any input string, and consider the computation of a given automaton on $i$, i.e. the sequence $(...


1

Languages like C and C++ can be compiled to include all libraries they use statically (as part of the executable). This means that the executable will be able to run by itself. Of course, even in this case the executable is supported by the operating system, but this is "for free". You are right that practical applications normally use dynamically linked ...


1

One approach is to look at the sum of the values of all the counters. Say you have a strategy that keeps the number of positive counters at $\ge P$ for an extended period of time. Then every $T$ steps, the sum decreases by $P$; but you can only increase the sum by at most $T$ over this time period; so to sustain $P$ positive counters over a long time ...


Only top voted, non community-wiki answers of a minimum length are eligible