Of course, every perfect-information deterministic game is "a somewhat more complex tic-tac-toe variant" from the perspective of sufficient computing power.

Yeah, sure. And I have a program that gives constant time random access to all primes less than 3^^^^3 from the perspective of sufficient computing power.