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 ...


20

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

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

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 ...


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 ...


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

File each given vector function with the win/loss of the game and the team each vector was on. Applications of this data: To gauge map balance and provide the least advantage to any one particular team. Determine how particular elements of the map effect balance. Make bots more effective by determining common strategies employed against bots, and the ...


2

I suggest you to look at other (completely different) approaches, too: write a program that given an Icosoku configuration outputs a SAT instance that can be solved using a SAT solver; (re)write your program using a constraint programming language (for example STP) or write a program that given an Icosoku configuration outputs an intermediate source code ...


2

Another technique that may be suitable for your problem is backtracking. It is often used for solving puzzles such as 8 queens problem, sudoku, etc.


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 ...


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 plausible approach is to use local search. In its simplest form, you could start by randomly assigning people to teams, then repeatedly picking a random pair of people and swapping them gives a better assignment, and iterating. This kind of approach should be easy to implement and flexible. But there's a lot more to say, so let me explain in more ...


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

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,...


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

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 ...


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

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 ...


1

Probably if you apply machine learning methods to the basic movements/fire actions of a specific player you can develop an AI bot that plays well against that player. But adding more high level actions like targets, waypoints, coordinated team actions, terrain features, and so on, you'll probably end up with models that has already been developed for REAL ...


1

The Rubik cube is a different beast, but the techniques to study it might come handy. A look at the mathematics (group theory) behind its solution is Joyner's "Mathematics of the Rubik's Cube", the site http://permutationpuzzles.org with its links might also be of help.


1

It looks like there are elements of (pseudo)randomness in StarCraft. Of course, this does not seem like a major property and you can ask for solving the game without this feature. Then you end up with a very deep game tree that probably does not have any nice mathematical property or symmetry that would help you to effectively handle it. This is where it ...


1

Yes, you are correct. What you suggest is a viable approach in 3D games. Popular game engines already do this, and have been doing this for some time. If you choose to do this through the vertex shader, you can improve performance in many situations. For more information about animation: How animation works in realtime graphics


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