[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).

[tromp]

That would be quite a strange function. For example, Tic-Tac-Toe has 26830 possible games on 5478 possible positions, while 2x2 Go has 386356909593 possible games on only 57 possible positions.

The major difference of course being that Go allows stones to be captured.

[Kranar]

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).