73 votes
Accepted

Why are some games np-complete?

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 ...
Craig Gidney's user avatar
  • 5,852
21 votes

Why are some games np-complete?

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 ...
quicksort's user avatar
  • 4,252
4 votes

Detecting conservation, loss, or gain in a crafting game with items and recipes

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 (...
j_random_hacker's user avatar
3 votes

Finding an optimal solution in a tile painting game

This is the Hamiltonian path problem on partial grid graphs (i.e., graphs which are arbitrary subgraphs of grids) which is known to be NP-complete. Thus, no polynomial algorithm exists unless P = NP. ...
Juho's user avatar
  • 22.6k
3 votes

Playing video games to solve SAT instances

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 ...
user253751's user avatar
  • 1,739
3 votes

How is CPU different from GPU?

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 ...
Jörg W Mittag's user avatar
3 votes

Why are some games np-complete?

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 ...
gnasher729's user avatar
3 votes
Accepted

Detecting conservation, loss, or gain in a crafting game with items and recipes

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, ...
D.W.'s user avatar
  • 159k
2 votes
Accepted

What data structure might this game use?

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 ...
D.W.'s user avatar
  • 159k
2 votes
Accepted

Why isn't the Generalized Super Mario Bros. obviously in NP?

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 ...
Discrete lizard's user avatar
  • 8,248
2 votes

Algorithms for procedural generated mazes

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 ...
Zikoat's user avatar
  • 121
2 votes

Why are some games np-complete?

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 ...
einpoklum's user avatar
  • 965
2 votes
Accepted

Where is the theory about "binary toggling games"?

"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} = [...
orlp's user avatar
  • 13.4k
2 votes
Accepted

Comparing various ways to move a game actor having time-dependent velocity

I can't see any general answer -- I expect it might depends on the circumstances. In the specific situation you mentioned, for the specific choice of $f$ you mention, Case 1 seems better to me, if we ...
D.W.'s user avatar
  • 159k
2 votes

Complexity of simulating idle games (pt1)

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, ...
River's user avatar
  • 21
2 votes

How is CPU different from GPU?

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 ...
ajit's user avatar
  • 376
1 vote

Memory efficient undo data structure

Yes. A relevant technical term is 'persistent data structure'. (See also persistent-data-structure.) There are many techniques for building persistent versions of standard data structures (trees, ...
D.W.'s user avatar
  • 159k
1 vote

Calculate odds that cards drawn from deck sum to at least some number ("Across the Obelisk" problem)

Here's a solution I came up with that's $O(PD + PV\log{P})$, where $D$ = The size of the largest deck $P$ = The number of players (4 in the original problem) $V$ = The max card-value (9 in the ...
BlueRaja - Danny Pflughoeft's user avatar
1 vote

Are there already Neural Network AIs that can play object-finding games?

As is often the case in ML, the only way to find out is to try it (or find someone else who has already tried it). You might be interested in methods for object detection, which basically do what you ...
D.W.'s user avatar
  • 159k
1 vote
Accepted

How can I best represent my 2D thrust problem as a linear programming problem?

Let $s$ be a vector denoting the summed forces from the thrusters, and $d$ the desired direction. Then you want to maximize the dot-product $s \cdot d$, subject to the constraint that $s \cdot d^\top ...
D.W.'s user avatar
  • 159k
1 vote
Accepted

Complexity of simulating idle games (pt1)

Yes. It can be solved efficiently. You can denote the state of the system at any point by a vector $x \in \mathbb{N}^n$, where $n$ is the number of resources and $x_i$ counts how many items of the $...
D.W.'s user avatar
  • 159k
1 vote
Accepted

Playing video games to solve SAT instances

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 ...
Kyle Jones's user avatar
  • 8,091
1 vote

What is the name of the domain or theoretical problem of transmitting game states in an online game

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 ...
D.W.'s user avatar
  • 159k
1 vote
Accepted

The task of recognizing game units in the screenshot

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 ...
D.W.'s user avatar
  • 159k
1 vote

How to validate a connect X game (Tick-Tak-Toe,Gomoku,...)?

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 ...
Discrete lizard's user avatar
  • 8,248
1 vote

Why is the video game Braid Turing-complete?

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 ...
CinchBlue's user avatar
  • 594
1 vote

Extreme instancing for computer graphics

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 ...
aces's user avatar
  • 251

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