Well, it's at least as complex as a Turing machine. That's a statement of complexity.

Maybe you are asking whether it is possible for the winning strategy of a very simple deterministic game to be non-computable. In other words, maybe there's a possible way of defining computability which is orthogonal to complexity. The CS definitions of both terms are closely connected to Turing machines, though. Can you imagine a simple deterministic game that couldn't be "solved" by an algorithm?

The set of all problems that can be solved by a Turing machine if there's an answer (possibly hanging if there's no answer) sits at the top of the complexity hierarchy (it's equivalent to the recursively enumerable languages)

The usual complexity classes of decision problems, such as P and NP, are subsets of what a Turing machine can solve, and so are weaker complexity classes.