I don't see what's strange about that, different functions grow at different rates. That's like saying it's strange that exp(x) is a billion for x = 21 while sqrt(x) is merely ~4 when x = 21.
Go's complexity grows much faster than tic tac toe's complexity as a function of legal positions, but the complexity is still a function of the number of legal positions (among other things, as I pointed out).
