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 ...
- 5,802
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 ...
- 4,222
4
votes
Consensus protocols in multiplayer video games
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 ...
D.W.♦
- 156k
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 (...
- 5,459
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 ...
- 1,720
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.
...
- 22.5k
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 ...
- 5,830
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.♦
- 156k
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 ...
- 28.3k
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 ...
- 121
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.♦
- 156k
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 ...
- 955
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 ...
- 376
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} = [...
- 12.7k
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 ...
- 7,768
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.♦
- 156k
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, ...
- 21
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.♦
- 156k
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 ...
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.♦
- 156k
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.♦
- 156k
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.♦
- 156k
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 ...
- 8,051
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.♦
- 156k
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.♦
- 156k
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 ...
- 7,768
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 ...
- 584
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 ...
- 251
Only top scored, non community-wiki answers of a minimum length are eligible