I know for pretty sure that there is a function with the type $f: \forall \alpha, \beta . \alpha \rightarrow \beta$ (at least in a Hindley-Milner type system), but I can't wrap my head over it. Neither could I think of an actual function with this type.

I found a function of this type, which in Standard ML would be written as:

fun f x = f x


But I am not sure of the lambda calculus equivalent of this function.

Moreover, if I'm right about Curry-Howard, the isomorphism of this type is the proposition $\forall A, B . A \implies B$, which does not make sense for me. Is it possible that someone give a function with type $f$ and explain its Curry-Howard equivalent to me?

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.
