[falserum]

I have a further nitpick regarding terminology.

Wording like “game is more complex” overal seems incorrect. Game is not complex by itself (for example go rules are extreemly simple), all the difficulty and challenge depends on the skill of your oponent. Game only allows the opponent to demonstrate the skill.

[tromp]

Beyond rule complexity, there are at least 5 measures of game complexity in Combinatorial game theory [1]:

    State-space complexity
    Game tree size
    Decision complexity
    Game-tree complexity
    Computational complexity

[1] https://en.wikipedia.org/wiki/Game_complexity

[Kranar]

Those are all meaningful measures of complexity, but it's worth noting that all of them are a function of the number of legal positions (among other things as well).