The "complexity" of a game is not very well measured by game-tree size alone. Wikipedia lists multiple factors on the game complexity page: https://en.wikipedia.org/wiki/Game_complexity#Measures_of_ga...