[bluecalm]

Complexity of the game has nothing to do with the number of legal positions. It's very easy to design a game with arbitrary number of positions which is very simple. While go might be more complex than chess using a more reasonable measure this argument was used to for arguing nonsense in scientific papers in the past (that some poker games are more complicated than chess because they have more possible states).

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

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

[Kranar]

Are you sure that the complexity of a game has absolutely nothing to do with the number of legal positions?

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.

[jan_Inkepa]

Take a game where you get to pick a single number between one and a billion. If you pick 10 you win. This has a billion states, but it's trivial. I can increase the bound above a billion, it doesn't matter.

State count gives an upper bound, though, to how complex a game can be, for sure.

[nurettin]

Those position counts don't account for blunders or bad tactics which the players will take advantage of in order to simplify and win. In go, any move that lets your opponent cut you off is highly likely a blunder, so counting every other move other than the obvious one you have to play in order to not lose is pretty useless. You can also call it a bad move if you are not under an immediate threat and you are not invading. (this is a guess, I am not a go player) So counting the rest of the moves developing in your territory is also useless.

[bluecalm]

Yes, for example no limit Rock Paper Scissors where you bet an arbitrary amount and your opponent might call or fold is a game that:

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.