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 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 the paper "Classic Nintendo Games are (Computationally) Hard". It's well written and easy to follow.

An important caveat to keep in mind is that the NP-hardness requires generalizing the games in "obvious" ways. For example, Tetris normally has a fixed size board but the hardness proof requires the game to allow arbitrarily large boards. Another example is off-screen enemies in Super Mario Bros: the proof is for a variant of the game where off-screen enemies continue moving as if they were onscreen, instead of ceasing to exist and being reset to their starting position when Mario comes back.

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 a rule called "perfect clear", that gives the player a large bonus if a piece drop clears the board entirely. One might wonder if, given an ordered sequence of pieces $\{P_i\}$ and an integer $k$, there exists a legal sequence of moves for the pieces $P$ that achieves at least $k$ perfect clears. Problem statements such as those are sufficiently abstract that can be modeled with the tools of complexity theory.

Long story short, "$\mathcal{NP}$-complete" means one thing and one thing only, fancy claims such as "Super Mario is $\mathcal{NP}$-complete" have to be translated into a formal statement before they make any actual sense.

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 behavior is very expressive. While at any given point a player may only have a limited, even a fixed, number of possible actions, that's enough to create a space of behaviors or strategies exponential in the length of the game; and while you may be able to provide a simple condition or logical formula on the validity/benefit/correctness of a player's actions locally, globally you get a similar effect as with a large combinatorial circuit, or a k-CNF formula.

Hopefully this makes some intuitive sense and also rings enough CS theory bells.

I'll try to rewrite my response to address some of the points raised by Cort Ammon.

I assume that you read the Wikipedia definition for NP-completeness and and didn't understand it. I'll water down the exact meaning just a bit and explain what I think is the essence of the concept.

Basically when you're playing a game you have some number of moves that you can make and you must chose one of them. You'd like to play "perfectly" which means that you'd never make a "bad" move. So of the allowable moves you'd like to select the best one.

Note that perfect play doesn't mean that you'll always win. The rules of the game can be such that the first or the second player should win. Also some games like Tic-Tac-Toe should end in a draw. Thus what "perfect play" means in this discussion is (1) that you'll never be in a winning position and then lose the game because you made a "bad" move and (2) you'll never miss an opportunity to get into the winning position if such an opportunity arises.

Given the current state of the game what you'd like is to be able to use an evaluation function to calculate the best move rather than search the whole game tree. So the evaluation function would take as input the current game state and calculate what would be the perfect move.

Notice how I am using "calculate" and "function" here. A computer does calculations of course but I don't mean calculate in that sense. By saying "an evaluation function to calculate" I mean like evaluating a mathematical formula. I am specifically trying to exclude an exhaustive tree search of future board positions.

For Nim it is possible to create such a function. The function can calculate if you have a winning move and what that move should be.

On the other hand let's take the game of Qubic. (You're trying to make a line of 4 in a 3D grid. So it is essentially tic-tac-toe on a 4x4x4 grid.) Qubic is NP-complete thus there is no function to calculate the next perfect move. The only way to know if you currently have a winning move is to try all the possible moves of both players to verify that a particular move is a winner, or at least not a loser.

Truthfully the whole game tree for Qubic is small enough so that it can be encoded into a computer program which can play perfectly. What encoding means is that the whole game tree has been explored and all the moves worked out in advance. So the program can essentially do a database call using the current board state and get back the best move for that board state without having to do the tree search each time a move is to be made.

Chess is still an unsolved game. It is unknown if the first or second player should win. It is not possible to be given any board position and predict with certainty who will win. In fact chess has such a large game tree that it is just impossible to search the whole game tree. You'd need computers which are not just 10 or 100 times faster but billions of billions of time faster than any current computer. Thus even with some move look aheads, all chess programs ultimately use an imperfect evaluation function. Think of the chess evaluation function as giving each possible next move a probability of being the best move. That means that might be possible to beat the program even if the program had a winning position at some point.