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.
State-space complexity
Game tree size
Decision complexity
Game-tree complexity
Computational complexity
[1] https://en.wikipedia.org/wiki/Game_complexityThe major difference of course being that Go allows stones to be captured.
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).
I mean I am open to hear the justification for this, but I was fairly certain that all measures of game complexity are a function of the number of legal positions. Now certainly there are other factors, namely the cost of computing the transition from one legal move to another legal move so a simple game might have a very low cost transition function while a complex game has a very complex transition function, but I can't conceive of a game where the number of legal positions bears no weight on the game's complexity.
State count gives an upper bound, though, to how complex a game can be, for sure.
1)has infinitely many legal states/positions
2)imperfect information (another argument often used to argue that game is more complex)
And is:
3)dead simple to play optimally
It's also easy to design a board game with arbitrary number of legal positions that is dead simple to play optimally.